Journal of Convex Analysis Volume 4 (1997), No. 1, 27–67

Legendre Functions and the Method of Random Bregman Projections

Heinz H. Bauschke

Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada. e-mail: bauschke@cecm.sfu.ca

Jonathan M. Borwein^{1}

Centre for Experimental & Constructive Mathematics, Simon Fraser University, Burnaby, B.C., Canada V5A 1S6. jborwein@cecm.sfu.ca

Received March 13, 1995 Revised manuscript received November 22, 1995

The convex feasibility problem, that is, finding a point in the intersection of finitely many closed convex sets in Euclidean space, arises in various areas of mathematics and physical sciences. It can be solved by the classical method of cyclic orthogonal projections, where, by projecting cyclically onto the sets, a sequence is generated that converges to a point in the intersection. In 1967, Bregman extended this method to non-orthogonal projections based on a new notion of distance, nowadays called “Bregman distance”. The Bregman distance is induced by a convex function. If this function is a so-called “zone consistent Bregman function”, then Bregman’s method works; however, deciding on this can be difficult. In this paper, Bregman’s method is studied within the powerful framework of Convex Analysis. New insights are obtained and the rich class of “Bregman/Legendre functions” is introduced. Bregman’s method still works, if the underlying function is Bregman/Legendre or more generally if it is Legendre but some constraint qualification holds additionally. The key advantage is the broad applicability and verifiability of these concepts. The results presented here are complementary to recent work by Censor and Reich on the method of random Bregman projections (where the sets are projected onto infinitely often – not necessarily cyclically). Special attention is given to examples, some of which connect to Pythagorean means and to Convex Analysis on the Hermitian or symmetric matrices.

Keywords: Bregman function, Bregman projection, convex feasibility problem, convex function, convex set, essentially smooth function, essentially strictly convex function, Hermitian matrix, Legendre function, projection.

1991 Mathematics Subject Classification: Primary 49M45; Secondary 47H17, 52A41, 65F10, 65K05, 90C25.

1. Introduction

Numerous problems in mathematics and physical sciences can be recast in terms of the famous convex feasibility problem:

Given closed convex intersecting sets C_{1}, …, C_{N}, find a point in C_{1} ∩ ⋯ ∩ C_{N} .

1 Research supported by NSERC and by the Shrum Endowment.

ISSN 0944-6532 / $ 2.50 ◯^{c} Heldermann Verlag

28 H. H. Bauschke, J. M. Borwein / Legendre functions

Typically, the points in the intersection are the sought-after solutions of a given problem and the sets C_{1}, …, C_{N} correspond to some constraints. The convex feasibility problem arises in diverse areas such as best approximation theory, conformal mapping theory, image reconstruction, minimization of convex functions, and statistical estimation. Often, it is possible to calculate the orthogonal projection onto the constraints; thus, denoting the orthogonal projection onto the i^{th} constraint set by P_{i}, one can solve the convex feasibility problem by the classical method of cyclic orthogonal projections: Given a starting point y_{0}, generate a sequence (y_{n}) by projecting cyclically onto the constraints, that is

y_{0} ⟼^{P_{1}} y_{1} ⟼^{P_{2}} y_{2} ⋯ ⟼^{P_{N}} y_{N} ⟼^{P_{1}} y_{N+1} ⟼^{P_{2}} · · · .

The sequence (y_{n}) converges to a solution if the underlying space is some Euclidean space IR^{J} as we will henceforth assume. (The interested reader is referred to [3] and the references therein for an attempt at review of the ever growing number of publications on projection algorithms.) Bregman [4] generalized this method in 1967 by allowing (potentially) non-orthogonal projections which are constructed as follows: Given a “sufficiently well-behaved” convex function f, consider the so-called Bregman “distance”

D_{f}(x, y) = f(x) − f(y) − ⟨∇f(y), x − y⟩

between two points x and y. (It is worth emphasizing that D_{f} is not a distance function in the sense of metric topology.) Distances between points induce distances between points and sets (as usual, by taking the appropriate infimum) and hence projections onto the

sets C_{i}, denoted by P_{i}^{(f)} and called Bregman projections onto C_{i} with respect to f. Not surprisingly, the method of cyclic Bregman projections arises by simply replacing P_{i} by P_{i}^{(f)} in the method of cyclic orthogonal projections. Now if f is what is called a “zone consistent Bregman function”, then the method of cyclic Bregman projections indeed produces a sequence converging to a solution of the convex feasibility problem; see the work by Bregman [4], by Censor and Elfving [6], by Censor and Lent [7], and by De Pierro and Iusem [29]. Further progress was made within last year: Censor and Reich (Theorem 3.2 in [12]) established convergence for the method of random Bregman projections (that is, every constraint set is picked up infinitely often – no particular order or periodicity is required); Kiwiel [20] reported related results. Alber and Butnariu [1] investigated the method of cyclic Bregman projections in reflexive Banach spaces. It should be noted that Bregman functions appear also in recent papers on Proximal Point Methods; see, for instance, Burachik’s [5], Chen and Teboulle’s [13], Eckstein’s [14], Iusem’s [19], and Teboulle’s [31]. Unfortunately, verifying that a function f is a Bregman function is not an easy task; moreover, we are not aware of any non-trivial condition sufficient for “zone consistency”.

The objective in this paper is to analyze the method of random Bregman projections within the framework of Convex Analysis and to provide verifiable conditions ensuring convergence of the method.

The paper is organized as follows.

In Section 2, we recall and collect basic facts on well-known concepts of Convex Analysis: essential smoothness, essential strict convexity, Legendre functions, and coercivity.

The importance of these concepts becomes clear immediately in Section 3: Legendre functions are “zone consistent” (Theorem 3.14) – as already indicated, we are not aware of any other (non-trivial) sufficient condition.

Section 4 deals in detail with the class of Bregman functions. The results in the previous sections allow us to remove one (redundant) axiom and to simplify another (Remarks 4.2). Theorem 4.7 completely characterizes the important subclasses of “boundary coercive” and “zone coercive” Bregman functions in terms of conjugate function f^{∗}.

In Section 5, we propose the notion of a “Bregman/Legendre function”. The class of Bregman/Legendre functions lies strictly between the class of Legendre functions and the class of functions which are both Bregman and Legendre. Not surprisingly, we designed “Bregman/Legendreness” so that the method of random Bregman projections works. Just as for Bregman functions, checking for Bregman/Legendreness can be difficult; however, the situation on the real line is highly satisfactory: a Legendre function is Bregman/Legendre if and only if the domain of its conjugate is open (Theorem 5.8); moreover, this extends to all separable multi-dimensional Legendre functions. The class of Bregman/Legendre functions is closed under a variety of operations; hence, it is easy to construct new Bregman/Legendre functions. We are convinced that the notion of a Bregman/Legendre function will become useful in other contexts as well.

Many examples of Bregman/Legendre functions are presented in Section 6. By means of a two-dimensional example, we demonstrate that – unlike for the one-dimensional case – Bregman/Legendreness of a Legendre function really demands more than mere openness of the domain of the conjugate. The important question of computability of Bregman projections is addressed; we offer a new view of Bregman projections onto hyperplanes in Remark 6.13.

Section 7 starts with Pierra’s product space formalization [28], which has become a standard tool in the field. Following Censor, Elfving, and Reich [6], [12], we discuss previous results in this light. It is perhaps surprising that some Pythagorean means can be viewed as Bregman projections onto the diagonal in this product space. The second half of this section connects – based on recent work by Lewis [22, 25, 24, 26] – to the increasingly popular area of Convex Analysis on the Hermitian or symmetric matrices. For example, Hadamard’s inequality can be viewed in the context of Bregman distances as a “measure of non-diagonality”. Moreover, the (negative) “Burg entropy”, ∑_{j} − ln x_{j}, corresponds to the logarithmic barrier function which lies at the heart of modern Linear Programming algorithms such as Interior Point Methods.

The last Section 8 contains our main result stating that the method of random Bregman functions works if f is Bregman/Legendre or if f is Legendre and the constraints and the interior of the domain of f have a point in common (Theorem 8.1). The important special case when each constraint set is a hyperplane is also investigated. These results are complementary to recent results by Censor and Reich [12] and partially generalize earlier work [4], [6], [7], [29]. Whereas Censor and Reich allow operators more general than Bregman projections, we build on the class of Bregman/Legendre functions: again, the important “Burg entropy” is included in our analysis but excluded from the class of Bregman functions.

Throughout the paper, we assume that

E is a Euclidean space IR^{J} with inner product ⟨·, ·⟩ and induced norm ∥ · ∥.

Almost all the facts we use from Convex Analysis can be found in Rockafellar’s fundamental book [30]. The notation is fairly standard: Given convex functions f and g on E, the domain of f (conjugate function of f, recession function of f, gradient of f, subgradient of f, infimal convolution of f and g, respectively) is denoted by dom f (f^{∗}, f0^{+}, ∇f, ∂f, f g, respectively). The indicator function of a set C is denoted ι_{C} and its interior (boundary, closure, respectively) is abbreviated by int C (bd C, cl C, respectively). Finally, I stands for the identity mapping or identity matrix and, for sequences, the symbol “→” indicates convergence.

2. Tools

The concepts in this section are fundamental to our analysis.

2.1. Essential smoothness

Definition 2.1. (Rockafellar’s Section 26 in [30]) Suppose f is a closed convex proper function on E with int(dom f) ≠ ∅. Then f is essentially smooth, if f is differentiable on int(dom f) and

\begin{matrix}(x_{n}) in int(dom f), \\ x_{n} → x ∈ bd(dom f) \end{matrix} \} ⇒ ∥∇f(x_{n})∥ → +∞.

Fact 2.2. (Rockafellar’s Theorem 26.1 and Lemma 26.2 in [30]) Suppose f is closed convex proper on E. Then the following are equivalent.

(i) f is essentially smooth. (ii) f is differentiable on int(dom f) and

lim_{t↓0}⟨∇f(x + t(y − x)), y − x⟩ = −∞, ∀x ∈ bd(dom f), ∀y ∈ int(dom f).

(iii) ∂f(x) = ∅, ∀x ∈ bd(dom f), and ∂f(y) = {∇f(y)}, ∀y ∈ int(dom f).

2.2. Essential strict convexity

Definition 2.3. (Rockafellar’s Section 26 in [30]) Suppose f is closed convex proper on E. Then f is essentially strictly convex, if f is strictly convex on every convex subset of dom ∂f.

Fact 2.4. (Rockafellar’s Theorem 26.3 in [30]) Suppose f is closed convex proper on E. Then the following are equivalent.

(i) f is essentially strictly convex. (ii) f^{∗} is essentially smooth. (iii) ∂f(x) ∩ ∂f(y) = ∅, ∀x, y ∈ dom f, x ≠ y.

We add another useful characterization which follows easily from Fact 2.2 and Fact 2.4.

Proposition 2.5. Suppose f is closed convex proper on E. Then the following are equivalent.

(i) f is essentially strictly convex. (ii) range ∂f = int(dom f^{∗}) = dom ∇f^{∗}. (iii) {y} = ∂f^{∗}(∂f(y)), ∀y ∈ dom ∂f.

Corollary 2.6. Suppose f is closed convex proper on E with int(dom f) ≠ ∅. If f is essentially strictly convex and differentiable on int(dom f), then

∇f(y) ∈ int(dom f^{∗}) and ∇f^{∗}∇f(y) = y, ∀y ∈ int(dom f).

The following example shows that without essential strict convexity, the range ∂f need not be equal to int(dom f^{∗}):

Example 2.7. (“positive energy”) Let f(x) = \frac{1}{2}|x|^{2}, if x ≥ 0; +∞, otherwise on E = IR. Then f^{∗}(x^{∗}) = \frac{1}{2}|x^{∗}|^{2}, if x^{∗} ≥ 0; 0, otherwise. Hence

∇f(int(dom f)) = I(]0, +∞[) = ]0, +∞[ ⫋ IR = int(dom f^{∗}).

2.3. Legendre functions

Imposing essential smoothness and essential strict convexity together leads to Legendre functions, an extremely nice class of convex functions.

Definition 2.8. (Rockafellar’s Section 26 in [30]) Suppose f is closed convex proper on E. Then f is Legendre (or a Legendre function or a convex function of Legendre type), if f is both essentially smooth and essentially strictly convex, i.e. f satisfies L0. int(dom f) ≠ ∅. L1. f is differentiable on int(dom f). L2. lim_{t↓0}⟨∇f(x + t(y − x)), y − x⟩ = −∞, ∀x ∈ bd(dom f), ∀y ∈ int(dom f). L3. f is strictly convex on int(dom f).

Fact 2.9. (Rockafellar’s Theorem 26.5 in [30]) A convex function f is of Legendre type, if and only if its conjugate f^{∗} is. In this case, the gradient mapping

∇f : int(dom f) → int(dom f^{∗}) : x ↦ ∇f(x)

is a topological isomorphism with inverse mapping (∇f)^{−1} = ∇f^{∗}.

In view of Example 2.7 and Fact 2.9, the positive energy is not Legendre. Many examples of Legendre functions will be provided later on.

2.4. Coercivities

Definition 2.10. A function f on E is coercive (or 0-coercive; see Definition X.1.3.7 in [17]) if f has bounded lower level sets: {x ∈ E : f(x) ≤ r} is bounded, ∀r ∈ IR; equivalently,

lim_{∥x∥→+∞} f(x) = +∞.

For instance, affine functions are not coercive, whereas the norm ∥ · ∥ is.

Fact 2.11. (Rockafellar’s Corollary 14.2.2 in [30]) Suppose f is closed convex proper on E and x^{∗} ∈ E. Then x^{∗} ∈ int(dom f^{∗}) if and only if the function f(·) − ⟨x^{∗}, ·⟩ is coercive.

Remark 2.12. Fact 2.11 is a very powerful tool of convex analysis: existence of minimizers is often guaranteed by coercivity and closedness of the function; Fact 2.11 relates coercivity of this function to continuity of its conjugate function which is often much easier to check.

Before we discuss an even stronger version of coercivity, we review facts on the recession function (see Theorem 8.5 in [30] for the definition).

Fact 2.13. (Rockafellar’s Corollary 13.3.4.(c) in [30]) Suppose f is closed convex proper on E. Then

int(dom f^{∗}) = {x^{∗} ∈ E : ⟨x^{∗}, e⟩ < (f0^{+})(e), ∀e ∈ E \ {0}}.

Proposition 2.14. Suppose f is closed convex proper on E. Suppose further (x_{n}) is a sequence in E with lim_{n} ∥x_{n}∥ = +∞ and (x_{n}/∥x_{n}∥) convergent. Then \underline{lim}_{n}f(x_{n})/∥x_{n}∥ ≥ (f0^{+})(lim_{n} x_{n}/∥x_{n}∥).

Proof. Let q := lim_{n} x_{n}/∥x_{n}∥ ≠ 0 and L := lim_{n} f(x_{n})/∥x_{n}∥ ∈ [−∞, +∞] (we assume without loss of generality that (f(x_{n})/∥x_{n}∥) converges — after passing to a subsequence if necessary). Fix any x̂ ∈ dom f and let d_{n} := x_{n} − x̂, for all n. It is easy to check that lim_{n} ∥x_{n}∥/∥d_{n}∥ = 1 and lim_{n} d_{n}/∥d_{n}∥ = q. Fix an arbitrary positive ρ. Then ∥d_{n}∥ ≥ ρ eventually; hence

L = lim_{n} \frac{f(x̂ + ∥d_{n}∥\frac{d_{n}}{∥d_{n}∥}) − f(x̂)}{∥d_{n}∥} ≥ \underline{lim}_{n} \frac{f(x̂ + ρ\frac{d_{n}}{∥d_{n}∥}) − f(x̂)}{ρ} ≥ \frac{f(x̂ + ρq) − f(x̂)}{ρ}.

Now let tend ρ to +∞ to conclude L ≥ (f0^{+})(q).

Definition 2.15. A function f on E is called super-coercive (or 1-coercive; see Definition X.1.3.7 in [17]), if

lim_{∥x∥→+∞} \frac{f(x)}{∥x∥} = +∞.

Evidently, any super-coercive function — for instance, \frac{1}{2}∥·∥^{2} — is coercive. The converse is not true: the norm ∥ · ∥ is only coercive. Super-coercivity has various characterizations.

Proposition 2.16. Suppose f is closed convex proper on E. Then the following are equivalent:

(i) f is super-coercive. (ii) f is co-finite (see Section 13 in [30]), i.e. (f0^{+})(e) = +∞, ∀e ≠ 0; equivalently,

lim_{λ→+∞} \frac{f(λe)}{λ} = +∞, ∀e ≠ 0.

(iii) dom f^{∗} = E. (iv) f(·) − ⟨x^{∗}, ·⟩ is coercive, ∀x^{∗} ∈ E.

Proof. “(i)⇒(ii)”: is trivial. “(ii)⇐(i)”: if not, then there is a sequence (x_{n}) such that ∥x_{n}∥ → +∞ but (f(x_{n})/∥x_{n}∥) is not tending to +∞. Without loss (subsequence!) +∞ > M ≥ f(x_{n})/∥x_{n}∥ and x_{n}/∥x_{n}∥ → e ≠ 0. Proposition 2.14 implies M ≥ (f0^{+})(e), which contradicts the cofiniteness of f. “(ii)⇔(iii)”: is Rockafellar’s Corollary 13.3.1 in [30]. “(iii)⇔(iv)”: clear from Fact 2.11.

3. Bregman distances and Bregman projections

3.1. Bregman distances

Definition 3.1. (see Bregman’s Equation 1.4 in [4]) Suppose f is closed convex proper on E with int(dom f) ≠ ∅. If f is differentiable on int(dom f), then the corresponding Bregman “distance” D_{f} is defined by

D_{f} : E × int(dom f) → [0, +∞] : (x, y) ↦ f(x) − f(y) − ⟨∇f(y), x − y⟩.

Although commonly used, the term “distance” is misleading: neither is D_{f} symmetric (unless f is quadratic, as Iusem [18] proved) nor does D_{f} satisfy the triangle inequality (check ∥ · ∥^{2}). Nonetheless, D_{f} has some “good” distance-like features provided that f is “nice enough”.

Proposition 3.2. Suppose f is closed convex proper on E with int(dom f) ≠ ∅. If f is differentiable on int(dom f), then:

(i) D_{f}(x, y) = f(x) + f^{∗}(∇f(y)) − ⟨∇f(y), x⟩, ∀x ∈ E, ∀y ∈ int(dom f). (ii)

\begin{matrix}(y_{n}) in int(dom f), \\ y_{n} → y ∈ int(dom f) \end{matrix} \} ⇒ D_{f}(y, y_{n}) → 0

Proof. (i): By Theorem 23.5 in [30], f(y) + f^{∗}(∇f(y)) = ⟨∇f(y), y⟩; now substitute. (ii): This is clear from (i), Corollary 25.5.1 and Theorem 23.5 of [30].

A sharper form of Proposition 3.2.(ii) holds on the real line for essentially smooth functions.

Proposition 3.3. Suppose f is essentially smooth on IR. Then

\begin{matrix}(y_{n}) in int(dom f), \\ y_{n} → y ∈ dom f \end{matrix} \} ⇒ D_{f}(y, y_{n}) → 0.

Proof. By Proposition 3.2.(ii), without loss y ∈ dom f \ int(dom f). We can assume there exists some ϵ > 0 such that [y, y + 2ϵ] ⊆ dom f so that y + ϵ ∈ int(dom f) (the case when y is a right endpoint is treated similarly). By essential smoothness,

⟨∇f(y_{n}), ϵ⟩ = ⟨∇f(y + (\frac{y_{n}−y}{ϵ})[(y + ϵ) − y]), [(y + ϵ) − y]⟩ → −∞.

In particular, −∇f(y_{n})(y − y_{n}) < 0 and hence

0 ≤ D_{f}(y, y_{n}) < f(y) − f(y_{n}), for all large n.

Now apply Corollary 7.5.1 of [30].

Remark 3.4. Of course, Proposition 3.3 extends to all separable essentially smooth functions. On the other hand, the proposition does not necessarily hold for non-separable essentially smooth functions; see Example 7.32.

The next proposition is good for building examples. We omit its simple proof.

Proposition 3.5. Suppose f_{1}, …, f_{J} are closed convex proper on some Euclidean spaces E_{1}, …, E_{J} with int(dom f_{1}), …, int(dom f_{J}) ≠ ∅, respectively. If every f_{j} is differentiable on int(dom f_{j}) and if λ_{1}, …, λ_{J} are strictly positive real numbers, then

f : E := _{∏j}E_{j} → ] − ∞, +∞] : x := (x_{1}, …, x_{J}) ↦ ∑_{j} λ_{j}f_{j}(x_{j})

is a closed convex function on E that is differentiable on int(dom f) = ∏_{j} int(dom f_{j}). The corresponding Bregman distance of f is

Df(x, y) = ∑_{j} λ_{j}D_{f_{j}}(x_{j}, y_{j}), ∀x ∈ E, ∀y ∈ int(dom f).

The following proposition will be useful later.

Proposition 3.6. Suppose f is Legendre on IR and dom f = [a, b[, where −∞ < a < b ≤ +∞. If (y_{n}) is a sequence in int(dom f) with y_{n} → b and ∇f(y_{n}) → +∞, then D_{f}(a, y_{n}) → +∞.

Proof. Case 1: b < +∞. Fix any y ∈ ]a, b[. Then eventually y_{n} > y and thus ∇f(y_{n}) ≥ (f(y_{n}) − f(y))/(y_{n} − y). Hence

\begin{matrix}D_{f}(a, y_{n}) = & f(a) − f(y_{n}) + ∇f(y_{n})(y_{n} − a) \\ ≥ & f(a) − f(y_{n}) + \frac{f(y_{n}) − f(y)}{y_{n} − y}(y_{n} − a) \\ = & \{f(a) − f(y)\frac{y_{n} − a}{y_{n} − y}\} + f(y_{n}) \{\frac{y − a}{y_{n} − y} \} . \end{matrix}

The bracketed terms are bounded; moreover, the second bracketed term converges to (y − a)/(b − y) > 0. On the other hand, f(y_{n}) → +∞, because f is closed and b ∉ dom f. The result follows. Case 2: b = +∞. Suppose to the contrary (D_{f}(a, y_{n})) is not tending to +∞. After passing to a subsequence, we assume (D_{f}(a, y_{n})) is bounded. Dividing by y_{n} − a yields

\frac{f(y_{n})}{y_{n} − a} − ∇f(y_{n}) → 0; hence \frac{f(y_{n})}{y_{n} − a} → +∞.

Fix any y > a. Then eventually y_{n} > y and as before

\begin{matrix}D_{f}(a, y_{n}) = & f(a) − f(y_{n}) + ∇f(y_{n})(y_{n} − a) \\ ≥ & f(a) − f(y_{n}) + \frac{f(y_{n}) − f(y)}{y_{n} − y}(y_{n} − a) \\ = & \{f(a) − f(y)\frac{y_{n} − a}{y_{n} − y}\} + \frac{f(y_{n})}{y_{n} − a} \{\frac{y_{n} − a}{y_{n} − y}(y − a)\} . \end{matrix}

Again the bracketed terms are bounded and the second bracketed term converges to y − a > 0, which implies D_{f}(a, y_{n}) → +∞.

Theorem 3.7. (“essential strict convexity helps”) Suppose f is closed convex proper on E, differentiable on int(dom f) ≠ ∅, and essentially strictly convex. Suppose further y ∈ int(dom f). Then:

(i) D_{f}(·, y) is closed convex proper on E, differentiable on int(dom f), and essentially strictly convex.

(ii) ∇f(y) ∈ int(dom f^{∗}). (iii) D_{f}(·, y) is coercive. (iv) D_{f}(x, y) = 0 ⟺ x = y, ∀x ∈ E.

(v) D_{f}(x, y) = D_{f^{∗}}(∇f(y), ∇f(x)), ∀x ∈ int(dom f). (vi) If dom f^{∗} is open, then D_{f}(x, ·) is coercive, ∀x ∈ int(dom f); equivalently,

\begin{matrix}x ∈ int(dom f), (y_{n}) in int(dom f), \\ (D_{f}(x, y_{n})) bounded \end{matrix} \} ⇒ (y_{n}) bounded.

Proof. (i): is clear by Proposition 3.2.(i). (ii),(iii): f essentially strictly convex ⇒ ∇f(y) ∈ int(dom f^{∗}) (Proposition 2.5) ⇔ f^{∗} is continuous at ∇f(y) ⇔ f(·) − ⟨∇f(y), ·⟩ is coercive (Fact 2.11) ⇔ D_{f}(·, y) is coercive (Proposition 3.2.(i)). (iv): Fix x ∈ E. Then D_{f}(x, y) = 0 ⇔ f(x)+f^{∗}(∇f(y)) = ⟨∇f(y), x⟩ ⇔ x = ∇f^{∗}(∇f(y)) ⇔ x = y (Corollary 2.6). (v): D_{f^{∗}}(∇f(y), ∇f(x)) = f^{∗}(∇f(y)) + f^{∗∗}(∇f^{∗}(∇f(x))) − ⟨∇f^{∗}(∇f(x)), ∇f(y)⟩ = f^{∗}(∇f(y)) + f(x) − ⟨x, ∇f(y)⟩ = D_{f}(x, y). (vi): Suppose x ∈ int(dom f), (y_{n}) in int(dom f) with (D_{f}(x, y_{n})) = (f(x)+f^{∗}(∇f(y_{n}))− ⟨x, ∇f(y_{n})⟩) bounded. Since x ∈ int(dom f), the function f^{∗}(·) − ⟨x, ·⟩ is coercive. Hence (∇f(y_{n})) is bounded. f^{∗} is closed, thus all cluster points of (∇f(y_{n})) lie in dom f^{∗} = int(dom f^{∗}). It follows that (y_{n}) = (∇f^{∗}(∇f(y_{n}))) is bounded, too (Corollary 2.6 and Corollary 25.5.1 of [30].

Theorem 3.8. (“essential smoothness helps”) Suppose f is closed convex proper on E, differentiable on int(dom f) ≠ ∅, and essentially smooth. Then:

(i) \begin{matrix}x ∈ int(dom f), (y_{n}) in int(dom f), \\ y_{n} → y ∈ bd(dom f) \end{matrix} \} ⇒ D_{f}(x, y_{n}) → +∞.

(ii) \begin{matrix}x ∈ int(dom f), (y_{n}) in int(dom f), \\ y_{n} → y ∈ cl(dom f), D_{f}(x, y_{n}) bounded \end{matrix} \} ⇒ y ∈ int(dom f) (and D_{f}(y, y_{n}) → 0).

(iii) \begin{matrix}(x_{n}) in dom f, x_{n} → x ∈ dom f, \\ (y_{n}) in int(dom f), y_{n} → y ∈ dom f, \\ \{x, y\} ∩ int(dom f) ≠ ∅, D_{f}(x_{n}, y_{n}) → 0 \end{matrix} \} ⇒ D_{f}(x, y) = 0 (and y ∈ int(dom f)).

Proof. (i): Assume to the contrary that \underline{lim}_{n}D_{f}(x, y_{n}) < +∞. Without loss (subsequences!) , we assume ∥∇f(y_{n})∥ → +∞ (by essential smoothness), ∇f(y_{n})/∥∇f(y_{n})∥ → q ≠ 0, and (D_{f}(x, y_{n})) = (f(x) + f^{∗}(∇f(y_{n})) − ⟨∇f(y_{n}), x⟩) is bounded. Dividing the last sequence by ∥∇f(y_{n})∥ yields f^{∗}(∇f(y_{n}))/∥∇f(y_{n})∥ → ⟨q, x⟩. By Proposition 2.14, ⟨q, x⟩ ≥ (f^{∗}0^{+})(q); thus (Fact 2.13) x ∉ int(dom f) which is absurd. (ii): is equivalent to (i). The “(and D_{f}(y, y_{n}) → 0)” part follows from Proposition 3.2.(ii). (iii): Claim: y ∈ int(dom f). Otherwise, y ∈ dom f \ int(dom f). Then x ∈ int(dom f) and ∥∇f(y_{n})∥ → +∞. We assume (subsequence!) that (∇f(y_{n})/∥∇f(y_{n})∥) is convergent, say to q ≠ 0. Now 0 ← D_{f}(x_{n}, y_{n}) = f(x_{n}) + f^{∗}(∇f(y_{n})) − ⟨∇f(y_{n}), x_{n}⟩; thus division by ∥∇f(y_{n})∥ yields

lim_{n} \frac{f^{∗}(∇f(y_{n}))}{∥∇f(y_{n})∥} = ⟨q, x⟩. Proposition 2.14 implies ⟨q, x⟩ ≥ (f^{∗}0^{+})(q). Hence, by Fact 2.13, x ∉ int(dom f^{∗∗}) = int(dom f). This is the desired contradiction and the claim thus holds. Because f is closed, we get 0 = lim_{n} D_{f}(x_{n}, y_{n}) = lim_{n} f(x_{n}) + f^{∗}(∇f(y)) − ⟨∇f(y), x⟩ ≥ f(x) + f^{∗}(∇f(y)) − ⟨∇f(y), x⟩ = D_{f}(x, y) ≥ 0.

3.2. Legendreness

Theorem 3.9. (“Legendreness helps a lot”) Suppose f is Legendre on E. Then:

(i) D_{f^{∗}}(x^{∗}, y^{∗}) = D_{f}(∇f^{∗}(y^{∗}), ∇f^{∗}(x^{∗})), ∀x^{∗}, ∀y^{∗} ∈ int(dom f^{∗}). (ii) If dom f^{∗} is not open, then D_{f}(x, ·) is not coercive, ∀x ∈ dom f.

(iii) \begin{matrix}(x_{n}) in dom f, x_{n} → x ∈ dom f, \\ (y_{n}) in int(dom f), y_{n} → y ∈ dom f, \\ \{x, y\} ∩ int(dom f) ≠ ∅, D_{f}(x_{n}, y_{n}) → 0 \end{matrix} \} ⇒ x = y.

Proof. (i): f^{∗} is essentially smooth and essentially strictly convex, since f is Legendre. Hence Theorem 3.7.(v) applies. (ii): Fix y^{∗} ∈ dom f^{∗} \int(dom f^{∗}), y_{0}^{∗} ∈ int(dom f^{∗}), and let y_{n}^{∗} := (1−1/n)y^{∗} +(1/n)y_{0}^{∗}, for all n ≥ 2. Then the sequence (y_{n}^{∗}) lies in int(dom f^{∗}) and converges to y^{∗} along the segment between y_{0}^{∗} and y. Hence f^{∗}(y_{n}^{∗}) → f^{∗}(y^{∗}) (Corollary 7.5.1 in [30]). Let y_{n} := ∇f^{∗}(y_{n}^{∗}), for all n; then ∥y_{n}∥ → +∞. Now fix an arbitrary x ∈ dom f. The sequences (⟨y_{n}^{∗}, x⟩), (f^{∗}(y_{n}^{∗})) are (convergent hence) bounded and so is (D_{f}(x, y_{n})) = (f(x) + f^{∗}(y_{n}^{∗}) − ⟨y_{n}^{∗}, x⟩). Therefore, D_{f}(x, ·) is not coercive. (iii): combine Theorem 3.8.(iii) with Theorem 3.7.(iv).

Example 3.10. (“Boltzmann/Shannon”) Suppose f(x) = x ln x − x on dom f = [0, +∞[. Then f is Legendre and f^{∗} = exp has open domain. Fix any x > 0 and y_{n} → +∞. Suppose further that x_{n} ↓ x. A direct check (see also Iusem’s Proposition 9.1 in [19] or Chen and Teboulle’s Lemma 3.1 in [13]) gives

D_{f}(x_{n}, y_{n}) = D_{f}(x, y_{n}) − D_{f}(x, x_{n}) − ∇f(x_{n})(x − x_{n}) + ∇f(y_{n})(x − x_{n}).

The first term, D_{f}(x, y_{n}), tends to +∞ by Theorem 3.7 (vi). The second term, −D_{f}(x, x_{n}), tends to 0 by Proposition 3.2.(ii). The third term, −∇f(x_{n})(x − x_{n}), tends also to 0. Now ∇f(y_{n}) = ln y_{n} → +∞ and x − x_{n} ↑ 0. Hence we can adjust (x_{n}) a posteriori so that D_{f}(x, y_{n}) + ∇f(y_{n})(x − x_{n}) → 0. Then altogether

x_{n} → x ∈ int(dom f) and D_{f}(x_{n}, y_{n}) → 0, but ∥y_{n}∥ → +∞.

Hence the assumption on convergence of (y_{n}) in the hypothesis of Theorem 3.9.(iii) is important.

Theorem 3.9 has an intriguing consequence.

Corollary 3.11. Suppose f is Legendre on E. Then the following implications hold:

D_{f}(x, ·) is coercive, for some x ∈ dom f.
⇒ dom f^{∗} is open.
⇒D_{f}(x, ·) is coercive, for all x ∈ int(dom f).

Consequently, the following are equivalent:

(i) D_{f}(x, ·) is coercive, for some x ∈ int(dom f). (ii) dom f^{∗} is open. (iii) D_{f}(x, ·) is coercive, for all x ∈ int(dom f).

Proof. The first implication is Theorem 3.9.(ii), the second is Theorem 3.7.(vi); the “Consequently” part follows.

3.3. Bregman projections

Having studied Bregman distances in some detail, we now turn to the associated Bregman projections. These are, of course, the key players in the methods investigated later. Fix a closed convex proper function f that is differentiable on int(dom f) and a set C with int(dom f) ∩ C ≠ ∅ (the usual constraint qualification). Pick y ∈ int(dom f). We wish to define a “projection of y onto C w.r.t. f”, denoted P_{C}y or P_{C}^{f}, by

P_{C}y = argmin_{x∈C∩dom f} D_{f}(x, y).

To really speak of a projection, we must require

• existence: the argmin should be nonempty; and

• uniqueness: the argmin should be singleton. Loosely speaking, this is guaranteed by essential strict convexity. In addition, note that y has to lie in int(dom f) to make even sense of the argmin. Moreover, to be able to project the point P_{C}y again (onto another constraint set perhaps), we have to impose • interiority: the argmin should lie in int(dom f). (This shows a posteriori that the constraint qualification “int(dom f) ∩ C ≠ ∅” is necessary.) The interiority condition appears in the literature (for instance, [6]) under the name “zone consistency”. Surprisingly, in all the papers we are aware of, we have nowhere found a non-trivial sufficient condition for interiority/zone consistency. Fortunately, there is one very natural property guaranteeing precisely this: essential smoothness. Altogether, Legendreness is the most natural property guaranteeing “good” Bregman projections.

Theorem 3.12. Suppose f is closed convex proper on E and differentiable on int(dom f). Suppose further C is closed convex with C ∩ int(dom f) ≠ ∅ and y is an arbitrary point in int(dom f). Then:

(i) If f is essentially smooth, then arginf _{x∈C∩dom f} D_{f}(x, y) is nonempty. (ii) If f is strictly convex on dom f, then arginf _{x∈C∩dom f} D_{f}(x, y) is at most singleton. (iii) If f is Legendre, then arginf _{x∈C∩dom f} D_{f}(x, y) is singleton and contained in int(dom f).

Proof. (i): On the one hand, D_{f}(·, y) is closed and coercive (Theorem 3.7). On the other hand, C ∩ cl(dom f) is closed. Altogether, arginf _{x∈C∩cl(dom f)} D_{f}(x, y) is nonempty; of course, this arginf is equal to arginf _{x∈C∩dom f} D_{f}(x, y). (ii): Since f is strictly convex on dom f, so is D_{f}(·, y). (iii): By (i), arginf _{x∈C∩dom f} D_{f}(x, y) is nonempty.

Claim: argmin _{x∈C∩dom f} D_{f}(x, y) ⊆ int(dom f).

Assume to the contrary x̄ ∈ argmin _{x∈C∩dom f} D_{f}(x, y) ∩ (dom f \ int(dom f)). Fix any z ∈ C ∩ int(dom f) and define a closed convex proper function Φ by

Φ : [0, 1] → [0, +∞[ : t ↦ D_{f}((1 − t)x̄ + tz, y).

Then Φ′(t) = ⟨∇f(x̄ + t(z − x̄)), z − x̄⟩ − ⟨∇f(y), z − x̄⟩, for all t ∈]0, 1[. By essential smoothness, lim_{t↓0} Φ′(t) = −∞. This implies Φ(t) < Φ(0), for all small positive t. However, (1 − t)x̄ + tz ∈ C ∩ int(dom f) for these small t; hence we have contradicted the choice of x̄. The claim is verified.

Finally, since D_{f}(·, y) is essentially strictly convex (Theorem 3.7.(i)) and thus strictly convex on int(dom f), we conclude that the argmin is singleton.

Definition 3.13. (see also Censor and Lent’s [7], [6]) Suppose f is closed convex proper on E and differentiable on int(dom f) ≠ ∅. We say that f is zone consistent, if for every closed convex set C with C ∩ int(dom f) ≠ ∅ and every y ∈ int(dom f), the arginf

arginf_{x∈C∩dom f} D_{f}(x, y)

is singleton and contained in int(dom f); that is, f is zone consistent with respect to every C. We denote this point by P_{C}y or P_{C}^{f}y and call the mapping

P_{C} : int(dom f) → C ∩ int(dom f) : y ↦ P_{C}y

H. H. Bauschke, J. M. Borwein / Legendre functions 39

the Bregman projection w.r.t. f. Theorem 3.12.(iii) now becomes: Theorem 3.14. Every Legendre function is zone consistent. Example 3.15. (“strict convexity alone is not enough”) Consider the “positive energy” f(x) := \frac{1}{2}∥x∥^{2} on dom f := \{x ∈ IR^{2} : x ≥ 0\} and C := \{(x_{1}, x_{2}) ∈ IR^{2} : x_{1} + x_{2} = 1\}. Then C ∩ int(dom f) ∋ (\frac{1}{2}, \frac{1}{2}) is nonempty. Let further y := (2, 1) ∈ int(dom f). One easily checks that

P_{C}^{f}(y) = (1, 0) ∉ int(dom f).

Hence f is not zone consistent. The following proposition is useful for calculating Bregman projections. Proposition 3.16. Suppose f is Legendre on E and C is closed convex with C ∩ int(dom f) ≠ ∅. Suppose further y ∈ int(dom f). Then the Bregman projection P_{C}y is characterized by

P_{C}y ∈ C ∩ int(dom f) and ⟨∇f(y) − ∇f(P_{C}y), C − P_{C}y⟩ ≤ 0.

In addition,

D_{f}(P_{C}y, y) ≤ D_{f}(c, y) − D_{f}(c, P_{C}y), for all c ∈ C ∩ dom f.

Proof. Convex calculus time!

x̄ = P_{C}y

Theorem 3.12.(iii)

⇔

x̄ = argmin_{x∈C∩int(dom f)} D_{f}(x, y)

⇔  x̄ = argmin_{x∈C∩int(dom f)} f(x) − ⟨∇f(y), x⟩

⇔  x̄ = argmin_{x∈E} f(x) + ⟨−∇f(y), x⟩ + ι_{C}(x) + ι_{int(dom f)}(x)
⇔  0 ∈ ∂ (f(·) + ⟨−∇f(y), ·⟩ + ι_{C}(·) + ι_{int(dom f)}(·)) (x̄)
⇔^{[30,Theorem 23.8]} 0 ∈ ∇f(x̄) − ∇f(y) + ∂ι_{C}(x̄) and x̄ ∈ int(dom f),

which gives the desired characterization. The “In addition” part is a trivial expansion.

Remark 3.17. If f = \frac{1}{2}∥·∥^{2}, then the characterization of P_{C}y becomes the well-known characterization of orthogonal projections:

P_{C}y ∈ C and ⟨C − P_{C}y, y − P_{C}y⟩ ≤ 0.

In this section, it has become obvious that essential smoothness or essential strict convexity guarantees many desirable properties of Bregman distances. Most importantly, Legendreness gives rise to well-defined and well-behaved Bregman projections.

4. Bregman functions

Bregman functions were introduced and utilized by Censor and Lent in [7]. The notion rests on Bregman’s fundamental work [4] from 1967.

Definition 4.1. Suppose f is closed convex proper on E. Then f is Bregman (or a Bregman function), if the following properties (B0)–(B5) hold: (B0) dom f is closed and int(dom f) ≠ ∅. (B1) f is continuously differentiable on int(dom f). (B2) f is strictly convex and continuous on dom f. (B3) (i) D_{f}(·, y) is coercive, ∀y ∈ int(dom f).

(ii) D_{f}(x, ·) is coercive, ∀x ∈ dom f. (B4) (y_{n}) in int(dom f), y_{n} → y ⇒ D_{f}(y, y_{n}) → 0.

(B5) \begin{matrix}(x_{n}) in dom f, (x_{n}) bounded, \\ (y_{n}) in int(dom f), y_{n} → y, \\ D_{f}(x_{n}, y_{n}) → 0 \end{matrix} \} ⇒ x_{n} → y.

Remarks 4.2.

• (B0) is quite restrictive: “Burg’s entropy”, − ln x, is automatically excluded since its domain is not closed. However, this function is known to be an extremely wellbehaved convex function.

• In (B1), it suffices to require differentiability of f throughout int(dom f): if f is differentiable throughout int(dom f), then it is actually continuously differentiable (see Rockafellar’s Corollary 25.5.1 in [30]).

• (B2) implies essential strict convexity of f.

• (B3)(i) is redundant: indeed, by (B2), f is essentially strictly convex and (B3)(i) follows from Theorem 3.7.(iii).

• If f is also essentially smooth (and hence Legendre), then (B3)(ii) simplifies (via Corollary 3.11) as follows: •• dom f open, i.e. dom f = E: (B3).(ii) ⇔ dom f^{∗} open. •• dom f not open: (B3).(ii) ⇔ D_{f}(x, ·) is coercive, ∀x ∈ bd(dom f).

Remark 4.3. One of the most important requirements of the function generating the Bregman distance is interiority/zone consistency. However: although the “positive energy” f(x) = \frac{1}{2}∥x∥^{2} on dom f := \{x ∈ E : x_{j} ≥ 0, ∀j\} in two (or more) dimensions is a Bregman function, it is not zone consistent (see Example 3.15). This is a serious shortcoming of Bregman functions. On the other hand, we have seen that Legendre functions guarantee zone consistency automatically. The path we follow is now obvious: in the next section, we introduce “Bregman/Legendre” functions which combine the best of both worlds: they are Legendre functions with “a little more”; this “little extra” is just enough to make the convergence analysis of the methods studied later work. Even better: in case of separable functions, it turns out extremely easy to verify “Bregman/Legendreness” and Burg’s entropy “belongs to the club of Bregman/Legendre functions”. The positive energy is not in this class; nonetheless, this is reasonable since this function is not zone consistent anyway.

In [19], Iusem discusses two additional useful properties of Bregman functions:

Definition 4.4. (Iusem [19]) Suppose f is Bregman on E.

(i) f is called boundary coercive, if

\begin{matrix}(x_{n}) in int(dom f), y ∈ int(dom f), \\ x_{n} → x ∈ bd(dom f) \end{matrix} \} ⇒ ⟨∇f(x_{n}), y − x_{n}⟩ → −∞.

(ii) f is called zone coercive, if ∇f is onto.

It turns out that these concepts are just some old friends in disguise.

Theorem 4.5. Suppose f is Bregman on E. Then:

(i) f is boundary coercive if and only if f is essentially smooth. (ii) f is zone coercive if and only if f is essentially smooth and super-coercive.

Proof. (i): “⇒”: Fix x ∈ bd(dom f), y ∈ int(dom f), and t_{n} ↓ 0. Set x_{n} := x+t_{n}(y−x), for all n. By boundary coercivity,

−∞ ← ⟨∇f(x_{n}), y − x_{n}⟩ = ⟨∇f(x + t_{n}(y − x)), (1 − t_{n})(y − x)⟩.

The last term is negative for all large n; hence ⟨∇f(x_{n}), y−x_{n}⟩ ≥ ⟨∇f(x+t_{n}(y−x)), y−x⟩, for all large n. It follows that ⟨∇f(x + t_{n}(y − x), y − x⟩ → −∞, i.e. essential smoothness of f. “⇐”: Fix y ∈ int(dom f) and (x_{n}) in int(dom f) converging to x ∈ bd(dom f). Since f and f^{∗} are Legendre, we have ∥∇f(x_{n})∥ → +∞ and ∇f(x_{n}), ∇f(y) ∈ int(dom f^{∗}). Also, D_{f^{∗}}(·, ∇f(y)) is coercive and hence

\begin{aligned}+∞ & ← D_{f^{∗}}(∇f(x_{n}), ∇f(y)) = D_{f}(y, x_{n}) \\ & = f(y) − f(x_{n}) − ⟨∇f(x_{n}), y − x_{n}⟩. \end{aligned}

By (B2), f(x_{n}) → f(x) ∈ IR. Therefore, ⟨∇f(x_{n}), y − x_{n}⟩ → −∞ and f is boundary coercive. (ii): Fix a Bregman function f. “⇒”: By Theorem X.4.1.3 in [17], f^{∗} is strictly convex on dom f^{∗} = E. In view of Fact 2.4 and Proposition 2.16, this means that f is essentially smooth and super-coercive. “⇐”: Super-coercivity is precisely dom f^{∗} = E; hence f^{∗} is sub-differentiable everywhere: dom ∂f^{∗} = range ∂f = E. Now ∂f is at most singleton (Fact 2.2); thus range ∂f = range ∇f = E. The proof is complete.

We now obtain Teboulle’s generalization (see Burachik’s Lemma 2.6 in [5]) of Iusem’s Corollary 9.1 in [19].

Corollary 4.6. For every Bregman function, the following implications hold:

zone coercivity ⇒ boundary coercivity ⇒ Legendreness.

Of course, zone coercivity is genuinely stronger than boundary coercivity: The exponential function exp on IR is boundary coercive but not zone coercive. We end this section with a verifiable sufficient condition for “Bregmanness”.

Theorem 4.7. Suppose f is strictly convex and differentiable on int(dom f) = E, i.e. f is Legendre with dom f = E. Then:

(i) dom f^{∗} is open ⇔ f is Bregman and boundary coercive. (ii) dom f^{∗} = E ⇔ f is Bregman and zone coercive.

Proof. Fix f strictly convex and differentiable on dom f = E. We first check that f is Bregman except for possibly (B3)(ii). (B0): √. (B1): √ (see Remarks 4.2). (B2): √. (B3)(i): √ (see Remarks 4.2). (B3)(ii): Theorem 3.9 says: D_{f}(x, ·) is coercive, ∀x ∈ int(dom f) = dom f = E if and only if dom f^{∗} is open. (B4): √ (Proposition 3.2.(ii)). (B5): √ (Theorem 3.9.(iii)). Hence: f is Bregman ⇔ (B3)(ii) holds ⇔ dom f^{∗} is open. Consequently, (i) is true. But (ii) follows from Theorem 4.5 and Proposition 2.16.

Proposition 2.16 now implies:

Corollary 4.8. Suppose f is strictly convex differentiable throughout E and supercoercive. Then f is Bregman and zone coercive.

Remark 4.9. Corollary 4.8 improves upon De Pierro and Iusem’s Theorem 5.1 in [29]. Their proof is quite complicated and different from the present, more conceptual proof.

5. Legendre functions and Bregman/Legendre functions

The last section underlined impressively the need for Legendre functions; we thus collect some basic facts.

Proposition 5.1. Suppose f is Legendre on E.

(i) Suppose α > 0. Then αf is Legendre with D_{αf} = αD_{f}. (ii) Suppose g is closed convex proper on E and essentially smooth. If int(dom f) ∩

int(dom g) ≠ ∅, then f + g is Legendre with D_{f+g} = D_{f} + D_{g}. (iii) Suppose T is an affine isomorphism of E. Then f ∘ T is Legendre with D_{f∘T} (x, y) =

D_{f}(T x, T y), ∀x ∈ E, y ∈ int(dom(f ∘ T)) = T^{−1}(int(dom f)). (iv) Suppose s is convex, differentiable, and strictly increasing on IR. Then s∘f is Legendre

with D_{s∘f}(x, y) = D_{s}(f(x), f(y)) + ∇s(f(y))D_{f}(x, y), ∀x ∈ E, y ∈ int(dom(s ∘ f)) = int(dom f).

(v) Suppose g is closed, convex, proper, essentially strictly convex on E with int(dom g^{∗})∩ int(dom f^{∗}) ≠ ∅. Then f g is Legendre.

Proof. (i): is trivial. (ii): f + g is a closed convex proper function on E. We check L0 through L3. L0: int(dom(f + g)) = int((dom f) ∩ (dom g)) = int(dom f) ∩ int(dom g) ≠ ∅. L1: f + g is differentiable on int(dom(f + g)), since f and g are. L2: Suppose x ∈ bd(dom(f +g)). Then x ∈ bd(dom f)∪bd(dom g). Fix y ∈ int(dom(f + g)) = int(dom f) ∩ int(dom g).

Case 1: x ∈ bd(dom f). Then lim_{t↓0}⟨∇f(x + t(y − x)), y − x⟩ = −∞. If x ∈ bd(dom g), then lim_{t↓0}⟨∇g(x + t(y − x)), y − x⟩ = −∞. Otherwise, x ∈ int(dom g) and lim_{t↓0}⟨∇g(x + t(y − x)), y − x⟩ = ⟨∇g(x), y − x⟩ ∈ IR. For either alternative, lim_{t↓0}⟨∇(f + g)(x + t(y − x)), y − x⟩ = −∞, as sought for. Case 2: x ∈ int(dom f). Then x ∈ bd(dom g) and we reason analogously. L3: f + g is strictly convex on int(dom(f + g)), since f is. (iii): follows easily with results of Section 6 of [30]. (iv): L0, L1, and L3 are easy. For L2, recall ∇(s ∘ f)(y) = ∇s(f(y))∇f(y). Essential smoothness holds, since ∇s is increasing and strictly positive, and since f is minorized by affine functions. (v): g^{∗} is essentially smooth and f^{∗} is Legendre. By (ii), f^{∗} + g^{∗} is Legendre and so is (f^{∗} + g^{∗})^{∗} = f g; see Theorem 16.4 of [30].

We now define Bregman/Legendre functions which form a subclass in the class of Legendre functions. However, they are more general than the class of functions that are both Bregman and Legendre.

Definition 5.2. Suppose f is Legendre on E. We say f is Bregman/Legendre (or a Bregman/Legendre function), if the following properties BL0-BL3 hold: BL0. dom f^{∗} is open. BL1. D_{f}(x, ·) is coercive, ∀x ∈ dom f \ int(dom f). BL2.

\begin{matrix}x ∈ dom f \ int(dom f), (y_{n}) in int(dom f), \\ y_{n} → y ∈ bd(dom f), (D_{f}(x, y_{n})) bounded \end{matrix} \} ⇒ D_{f}(y, y_{n}) → 0 (and hence y ∈ dom f).

BL3.

\begin{matrix}(x_{n}), (y_{n}) in int(dom f), x_{n} → x ∈ dom f \ int(dom f), \\ y_{n} → y ∈ dom f \ int(dom f), D_{f}(x_{n}, y_{n}) → 0 \end{matrix} \} ⇒ x = y.

Remark 5.3.

• In view of Corollary 3.11, BL0 and BL1 together say that D_{f}(x, ·) is coercive, ∀x ∈ dom f. The split into BL0 and BL1 is on purpose and will allow us to make clear which part is used; see, for instance, the proof of Theorem 8.1. Also, BL0 and BL1 together are (B3)(ii) in Definition 4.1. Again, there is a nice split as in Remarks 4.2: •• dom f open: BL0 and BL1 ⇔ dom f^{∗} open ⇔ D_{f}(x, ·) is coercive, for some x ∈ dom f. •• dom f not open: BL0 and BL1 ⇔ dom f^{∗} open and BL1 ⇔ D_{f}(x, ·) is coercive, for all x ∈ dom f \ int(dom f).

• BL1 is equivalent to

\begin{matrix}x ∈ dom f \ int(dom f), (y_{n}) in int(dom f), \\ (D_{f}(x, y_{n})) bounded \end{matrix} \} ⇒ (y_{n}) bounded.

• BL2 is at least formally more general than (B4) in Definition 4.1.

• BL3 is equivalent to (B5) in Definition 4.1; however, BL3 is slightly easier to check.

• The “Boltzmann/Shannon entropy” f(x) := x ln x − x on dom f := [0, +∞[ is Bregman/Legendre. Given 0 ∈ bd(dom f) and y_{n} → +∞, we can find a sequence x_{n} ↓ 0 such that D_{f}(x_{n}, y_{n}) → 0 by reckoning similarly to Example 3.10 and by using the decomposition

D_{f}(x_{n}, y_{n}) = D_{f}(0, y_{n}) + f(x_{n}) − f(0) − ∇f(y_{n})(x_{n} − 0).

This shows the importance of the hypotheses in BL1 and BL3. In Section 6, we see that Definition 5.2 is flexible enough to include a nice large set of examples.

Remark 5.4. For closed convex proper functions on E, the following strict implications hold:

Legendre ⇐ Bregman/Legendre ⇐ Bregman and Legendre ⇒ Bregman.

The strictness of the implications follows from the following examples: exp is Legendre but neither Bregman/Legendre nor Bregman. − ln is Bregman/Legendre but not Bregman. f(x) = \frac{1}{2}|x|^{2}, if x ≥ 0; +∞, else, is Bregman but neither Bregman/Legendre nor Legendre. We now develop the basic facts on Bregman/Legendre functions. The following Proposition will be useful later.

Proposition 5.5. Suppose f is Bregman/Legendre on E. Then:

\begin{matrix}(y_{n}) in int(dom f), y_{n} → y ∈ dom f \ int(dom f), \\ x ∈ dom f \ int(dom f), D_{f}(x, y_{n}) → 0 \end{matrix} \} ⇒ x = y.

Proof. Suppose the hypothesis of the implication holds. Let x_{n} := (1−1/n)x+(1/n)y_{n}, for all n ≥ 2. Then the sequence (x_{n}) lies in int(dom f) and x_{n} → x. The convexity of D_{f}(·, y_{n}) yields D_{f}(x_{n}, y_{n}) ≤ D_{f}(x, y_{n}) → 0. Now apply BL3 and conclude x = y.

Checking “Bregman/Legendreness” can be very easy:

Theorem 5.6. Suppose f is Legendre on E with dom f open. Then:

f is Bregman/Legendre ⇔ dom f^{∗} is open.

Proof. BL0 and BL1 ⇔ dom f^{∗} open, as observed in Remarks 5.3. Now BL2 and BL3 hold trivially.

Remark 5.7. De Pierro and Iusem (Theorem 5.1 in [29]) proved that if f is twice continuously differentiable, strictly convex on E and super-coercive, then f is Bregman. Theorem 5.6 can be viewed as a very potent generalization of their result; see also Corollary 4.8.

On the real line, we only have to check the domain of the conjugate:

Theorem 5.8. Suppose f is Legendre on IR. Then:

(i) BL0 and BL1 ⇔ dom f^{∗} is open. (ii) BL2 always holds. (iii) BL3 always holds.

Consequently,

f is Bregman/Legendre ⇔ f is Legendre and dom f^{∗} is open.

Proof. The theorem is clear if dom f is open (Theorem 5.6). So we assume without loss that dom f is not open. (i): “⇒”: follows from Corollary 3.11. “⇐”: In view of Corollary 3.11, it is enough to show that BL1 holds. We can assume that dom f is unbounded, say dom f = [x, +∞[ (the remaining case dom f = ] − ∞, x] is treated analogously). Now let us assume to the contrary that BL1 fails, i.e. there is a sequence (y_{n}) in int(dom f) = ]x, +∞[ with y_{n} ↑ +∞ but (D_{f}(x, y_{n})) bounded. Claim: ∇f(y_{n}) → +∞. Because f is convex, ∇f is increasing. If the claim does not hold, then we have ∇f(y_{n}) → y^{∗}. Now

(f(x) + f^{∗}(∇f(y_{n})) − ⟨∇f(y_{n}), x⟩)

is a bounded sequence. Since f^{∗} is closed, we get y^{∗} ∈ dom f^{∗} = int(dom f^{∗}) and further y_{n} = ∇f^{∗}(∇f(y_{n})) → ∇f^{∗}(y^{∗}) which is absurd. The claim thus holds. Apply Proposition 3.6 to obtain D_{f}(x, y_{n}) → +∞, the desired contradiction. (ii): Suppose x, y, and the sequence (y_{n}) are as in the hypothesis of BL2. In view of Proposition 3.3, we only have to show that y ∈ dom f. This is obviously true if dom f is closed. Hence we can assume that dom f is neither open nor closed, i.e. of the form [a, b[ (or ]a, b] but this is again treated similarly). The only (potentially) “critical” case is therefore dom f = [x, y[. Since y_{n} → y ∈ bd(dom f), the sequence (∇f(y_{n})) has to tend to +∞. By Proposition 3.6, D_{f}(x, y_{n}) → +∞ which contradicts our assumption. Thus the “critical” case never occurs and BL2 is established, i.e. (ii) holds. (iii): Suppose (x_{n}), (y_{n}), x, and y are as in the hypothesis of BL3. Now BL3 holds trivially unless dom f has two boundary points. We assume to the contrary that BL3 fails, i.e. dom f = [x, y]. Case 1: x < y. Note that ∇f(y_{n}) → +∞. Now

0 ← D_{f}(x_{n}, y_{n}) = f(x_{n}) − f(y_{n}) − ∇f(y_{n})(x_{n} − y_{n});

hence ∇f(y_{n}) − (f(x) − f(y))/(x − y) → 0, which is absurd. Case 2: x > y is proved similarly.

Remark 5.9.

• Theorem 5.8 is powerful and extends easily to separable functions (see Corollary 5.13 below). Having used so heavily the one-dimensionality in the proof of Theorem 5.8, it doesn’t come as a surprise that the non-separable multi-dimensional case is much more involved; see Section 6.

• The previous results yield easily the following characterization:

f is Bregman and Legendre on IR if and only if

f is Legendre on IR, dom f is closed, and dom f^{∗} is open.

Proposition 5.10. Suppose f is Bregman/Legendre on E.

(i) If α > 0, then αf is Bregman/Legendre. (ii) Suppose g is essentially smooth on E with

\begin{matrix}x ∈ dom g, (y_{n}) in int(dom g), \\ y_{n} → y ∈ cl(dom g), (D_{g}(x, y_{n})) bounded \end{matrix} \} ⇒ D_{g}(y, y_{n}) → 0.  (S2)

If int(dom f) ∩ int(dom g) ≠ ∅, then f + g is Bregman/Legendre. (iii) If T is an affine isomorphism of E, then f ∘ T is Bregman/Legendre.

Proof. (i): is trivial. (ii): Let h := f + g. Then h is Legendre with Bregman distance D_{h} = D_{f} + D_{g} (Proposition 5.1.(ii)). We have to check BL0 through BL3 for h. BL0: Fix a point x ∈ int(dom h) and a sequence (y_{n}) in int(dom h) with (D_{h}(x, y_{n})) bounded. Then x ∈ int(dom f), (y_{n}) lies in int(dom f), and (D_{f}(x, y_{n})) is bounded. Now dom f^{∗} is open, thus (y_{n}) is bounded (Corollary 3.11 for f). Since x and (y_{n}) were chosen arbitrarily, Corollary 3.11 applies once more and yields the openness of dom h^{∗}. BL1: Fix x ∈ dom h \ int(dom h) and a sequence (y_{n}) in int(dom h) with (D_{h}(x, y_{n})) bounded. Note that (y_{n}) is in int(dom f) and that (D_{f}(x, y_{n})) is bounded. If x ∈ dom f \ int(dom f), then, by BL1 for f, the sequence (y_{n}) is bounded. Otherwise, x ∈ int(dom f) and the boundedness of (y_{n}) follows from BL0 and Corollary 3.11 (for f). BL2: Fix x ∈ dom h \ int(dom h) and (y_{n}) in int(dom h) with y_{n} → y ∈ bd(dom h) and (D_{h}(x, y_{n})) bounded. Then (D_{f}(x, y_{n})) and (D_{g}(x, y_{n})) are bounded. S2 implies y ∈ dom g and D_{g}(y, y_{n}) → 0. It suffices to show that y ∈ dom f and D_{f}(y, y_{n}) → 0. Case 1: x ∈ int(dom f). Employ Theorem 3.8.(ii). Case 2: x ∈ dom f \ int(dom f). If y ∈ int(dom f), then use Proposition 3.2.(ii). Otherwise, y ∈ bd(dom f), and we apply BL2. BL3: Fix sequences (x_{n}), (y_{n}) in int(dom h) with x_{n} → x ∈ dom h \ int(dom h), y_{n} → y ∈ dom h \ int(dom h), and D_{h}(x_{n}, y_{n}) → 0. If {x, y} ∩ int(dom f) ≠ ∅, then we make use of Theorem 3.9.(iii). Otherwise, x, y ∈ dom f \ int(dom f) and BL3 does it. (iii): Denote f ∘ T by g and the linear part of T by L (i.e. T x = Lx + T 0, for all x ∈ E). Then one checks that g^{∗}(x^{∗}) = f^{∗}((L^{∗})^{−1}x^{∗}) − ⟨(L^{∗})^{−1}, T 0⟩ so that dom g^{∗} = L^{∗} dom f^{∗} is open. Hence BL0 holds. BL1 through BL3 for g follow straight-forwardly from the corresponding properties for f.

Corollary 5.11. Suppose f is Bregman/Legendre on E. Suppose further g is affine or Bregman/Legendre on E. If int(dom f)∩int(dom g) ≠ ∅, then f +g is Bregman/Legendre.

Proof. It is enough to show that g satisfies the hypothesis of Proposition 5.10.(ii). If g is affine, this is done easily. Otherwise, g is Bregman/Legendre with int(dom f) ∩ int(dom g) ≠ ∅ and we only have to check S2. So fix x ∈ dom g, (y_{n}) in int(dom g) with y_{n} → y ∈ cl(dom g) and (D_{g}(x, y_{n})) bounded. Goal: y ∈ dom g and D_{g}(y, y_{n}) → 0. Case 1: x ∈ int(dom g). Apply Theorem 3.8.(ii). Case 2: x ∈ dom g \ int(dom g). If y ∈ int(dom g), then use Proposition 3.2.(ii). Else y ∈ bd(dom g) and BL2 (for g) does the job.

Theorem 5.12. Suppose f_{1}, .., f_{J} are Bregman/Legendre on Euclidean spaces E_{1}, .., E_{J}, respectively. If λ_{1}, …, λ_{J} are strictly positive real numbers, then

f : E := ∏_{j} E_{j} → ] − ∞, +∞] : x := (x_{1}, …, x_{J}) ↦ ∑_{j} λ_{j}f_{j}(x_{j})

is Bregman/Legendre on E.

Proof. Note that ∇f(x) = (∇f_{1}(x_{1}), …, ∇f_{J}(x_{J})), int(dom f) = ∏_{j} int(dom f_{j}), and D_{f}(x, y) = ∑_{j} D_{f_{j}}(x_{j}, y_{j}) (Proposition 3.5). We first check that f is Legendre; see Definition 2.8. L0: √. L1: √. L2: Take (x_{n}) in int(dom f) with x_{n} → x = (x_{1}, …, x_{J}) ∈ bd(dom f). Then there is a j such that x_{j} ∈ bd(dom f_{j}). Hence, by Fact 2.2,

∥∇f(x_{n})∥ ≥ ∥∇f_{j}((x_{n})_{j})∥ → +∞;

thus L2 holds. L3: √. Next, we check BL0-BL3. BL0,BL1: Since each f_{j} are Bregman/Legendre, we have that each D_{f_{j}}(x_{j}, ·) is coercive, ∀x_{j} ∈ dom f_{j}. It easily follows that D_{f}(x, ·) is coercive, ∀x ∈ dom f. BL2: Pick x, y, and (y_{n}) as in the hypothesis of BL2 for f. If y_{j} ∈ int(dom f_{j}), apply Proposition 3.2.(ii) to conclude D_{f_{j}}(y_{j}, (y_{n})_{j}) → 0. Else y_{j} ∈ bd(dom f_{j}) and, depending on the location of x_{j}, either Theorem 3.8.(ii) or BL2 for f_{j} applies. BL3: Fix x, y, (x_{n}), and (y_{n}) as in the hypothesis of BL3 for f. Then for every j, we obtain x_{j} = y_{j} either by Theorem 3.9.(iii) or by BL3 for f_{j}.

Corollary 5.13. Suppose f_{1}, …, f_{J} are Legendre on IR with dom f_{1}^{∗}, …, dom f_{J}^{∗} open. Then

f : E = IR^{J} → ] − ∞, +∞] : x := (x_{1}, …, x_{J}) ↦ ∑_{j} f_{j}(x_{j})

is Bregman/Legendre type on E.

Proof. Combine Theorem 5.8 with Theorem 5.12.

6. Examples

6.1. Bregman/Legendre functions on the real line

All convex functions in the examples of this subsection are Legendre. Deciding whether or not they are Bregman/Legendre is, thanks to Theorem 5.8, extremely easy: simply check the openness of dom f^{∗}. Examples 6.1 to 6.7 are standard; see Rockafellar’s Section 12 of [30].

Example 6.1. Suppose 1 < p < +∞ and f(x) = \frac{1}{p}|x|^{p} on dom f = IR. Then

f^{∗}(x^{∗}) = \frac{1}{q}|x^{∗}|^{q} on dom f^{∗} = IR, where \frac{1}{p} + \frac{1}{q} = 1. Hence f and f^{∗} are Bregman/Legendre.

We state an important special instance of the preceding example:

Example 6.2. (norm^{2}) f(x) = \frac{1}{2}|x|^{2} is Bregman/Legendre on IR.

Example 6.3. Suppose 0 < p < 1 and f(x) = −\frac{1}{p}x^{p} on dom f = [0, +∞[. Then

f^{∗}(x^{∗}) = −\frac{1}{q}(−x^{∗})^{q} on dom f^{∗} = ] − ∞, 0[, where \frac{1}{p} + \frac{1}{q} = 1. Hence f is Bregman/Legendre whereas f^{∗} is not.

Example 6.4. (“Hellinger”) Suppose f(x) = −\sqrt{1 − x^{2}} on dom f = [−1, +1]. Then f^{∗}(x^{∗}) = \sqrt{1 + (x^{∗})^{2}} on dom f^{∗} = IR. Hence f is Bregman/Legendre whereas f^{∗} is not.

Example 6.5. (“Boltzmann/Shannon”) Suppose f(x) = x ln x−x on dom f = [0, +∞[. Then f^{∗}(x^{∗}) = exp x^{∗} on dom f^{∗} = IR. Hence f is Bregman/Legendre whereas f^{∗} is not.

Example 6.6. (“Fermi/Dirac”) Suppose f(x) = x ln x + (1 − x) ln(1 − x) on dom f = [0, 1]. Then f^{∗}(x^{∗}) = ln(1 + exp x^{∗}) on dom f^{∗} = IR. Hence f is Bregman/Legendre whereas f^{∗} is not.

Example 6.7. (“Burg”) Suppose f(x) = −\frac{1}{2} −ln x on dom f = ]0, +∞[. Then f^{∗}(x^{∗}) = −\frac{1}{2} − ln(−x^{∗}) on dom f^{∗} = ] − ∞, 0[. Hence f and f^{∗} are Bregman/Legendre.

Example 6.8. (De Pierro & Iusem’s Example on page 438 in [29]) Suppose f(x) = \frac{1}{2}(x^{2}−4x+3), if x ≤ 1; − ln x, otherwise; on dom f = IR. Then f^{∗}(x^{∗}) = \frac{1}{2}(x^{∗})^{2}+2x^{∗}+ \frac{1}{2}, if x^{∗} ≤ −1; −1 − ln(−x^{∗}), if −1 ≤ x^{∗} < 0; on dom f^{∗} = ] − ∞, 0[. Hence f and f^{∗} are Bregman/Legendre.

We summarize these examples in table 1 on page 23.

6.2. Multi-dimensional (Bregman/)Legendre functions

On the real line or in the separable case, Theorem 5.8 and Theorem 5.12 (see also Corollary 5.13) provide an extremely easy and elegant check for the somewhat cumbersome conditions in the definition of a Bregman/Legendre function (Definition 5.2). The question arises if BL1 through BL3 hold “for free” as soon as BL0 holds. This is, however, false as the following example illustrates:

Example 6.9. Suppose

f : IR^{2} → ] − ∞, +∞] : (x, r) ↦ \{ \begin{matrix}r ln(r^{2}/x), & if x, r > 0; \\ 0, & if x ≥ 0, r = 0; \\ +∞, & otherwise. \end{matrix}

Then f is Legendre and

f^{∗} : IR^{2} → ] − ∞, +∞] : (x^{∗}, r^{∗}) ↦ \{ \begin{matrix}exp(r^{∗} − 2)/(−x^{∗}), & if x^{∗} < 0; \\ +∞, & otherwise. \end{matrix}

Hence dom f^{∗} is open, i.e. BL0 holds. Nonetheless, f is not Bregman/Legendre, because BL1 through BL3 fail.

Some Bregman/Legendre functions on IR

f(x)  dom f  Remarks
\frac{1}{p}|x|^{p}  IR  1 < p < +∞
\frac{1}{2}x^{2}  IR  norm^{2}
−\frac{1}{p}x^{p}  [0, +∞[  0 < p < 1
−\sqrt{1 − x^{2}}  [−1, +1]  “Hellinger”
x ln x − x  [0, +∞[  “Boltzmann/Shannon”
x ln x + (1 − x) ln(1 − x)  [0, 1]  “Fermi/Dirac”
−\frac{1}{2} ln x  ]0, +∞[  “Burg”

\begin{aligned}\frac{1}{2}(x^{2} − 4x + 3), x & ≤ 1; \\ − ln x, x & ≥ 1. \end{aligned}  IR  “De Pierro & Iusem”

Table 1.

Proof. Verifying that f is of Legendre type and calculating f^{∗} is straight-forward but somewhat tedious. Thus we indicate only where BL1 through BL3 go wrong. BL1: Set x := (1, 0) and y_{n} := (n, 1), for all n. Then D_{f}(x, y_{n}) = 1 + 1/n → 1, but (y_{n}) is clearly unbounded. BL2: Choose x := (0, 0), y := (0, 1), and y_{n} := (1/n, 1), for all n. Then y_{n} → y ∉ dom f, although D(x, y_{n}) ≡ 1. BL3: Let x := (2, 0), y := (1, 0), x_{n} := (2, 1/n), and y_{n} := (1, 1/n), for all n. Then D_{f}(x_{n}, y_{n}) = (1 − ln(2n))/n → 0; however, x ≠ y.

Remark 6.10. It might appear that we pulled Example 6.9 out of a hat. This is not true; in fact, a nice systematic way to generate interesting convex non-separable functions is as follows:

Let g be defined on IR^{J−1} with int(dom g) = {x ∈ IR^{J−1} : x > 0} and h be defined on IR with int(dom h) = {r ∈ IR : r > 0}. Construct

f : IR^{J} → ] − ∞, +∞] : (x, r) ↦ \{ \begin{matrix}rg(x/r) + h(r), & if x ∈ dom g and r > 0; \\ (g0^{+})(x) + h(0), & if x ∈ dom g and r = 0; \\ +∞, & otherwise. \end{matrix}

Then f is closed convex proper; see Rockafellar’s Remark following Corollary 8.5.1 on page 67 in [30]. The reader will enjoy discovering nice patterns such as

D_{f}((x, r), (y, s)) = rD_{g}(x/r, y/s) + D_{h}(r, s),

for (x, r), (y, s) ∈ int(dom f). Example 6.9 arises by choosing

g(x) = − ln x and h(r) = r ln r.

6.3. Bregman projections

Having built a stock of examples of Bregman/Legendre functions, we now consider Bregman projections.

Proposition 6.11. (see also Censor and Elfving’s Lemma 6.1 in [6]) Suppose f is Legendre on E and C is an affine subspace of E, say C = {x ∈ E : Ax = b}, for A : E → IR^{M} : x ↦ (⟨a^{(m)}, x⟩)_{m=1}^{M} and b ∈ IR^{M}. Suppose further C ∩ int(dom f) ≠ ∅ and y ∈ int(dom f). Then z = P_{C}y exactly when

z ∈ int(dom f), Az = b, and ∇f(z) = ∇f(y) + ∑_{m=1}^{M} μ_{m}a^{(m)},

for some parameters μ_{1}, …, μ_{M} ∈ IR which will be unique whenever A is onto (equivalently, the vectors a^{(1)}, …, a^{(M)} are linearly independent).

Proof. This is clear from Proposition 3.16 and the fact that (kernel A)^{⊥} = range A^{∗} = span(a^{(1)}, …, a^{(M)}).

Corollary 6.12. (see also Bregman’s Theorem 3 in [4]) Suppose f is a convex function of Legendre type on E and H is a hyperplane in E, say H = {x ∈ E : ⟨a, x⟩ = b}, for some a ∈ E \ {0} and b ∈ IR. Suppose further H ∩ int(dom f) ≠ ∅ and y ∈ int(dom f). Then z = P_{H}y exactly when

z ∈ int(dom f), ⟨a, z⟩ = b, and ∇f(z) = ∇f(y) + μa,

for some (unique) parameter μ ∈ IR.

Remark 6.13. In practice, the projection P_{H}y (in the setting of Corollary 6.12) can be computed as follows:

1. Get z as a function of μ by Fact 2.9:

z(μ) = (∇f^{∗})(∇f(y) + μa).

2. Estimate μ by solving ⟨a, z(μ)⟩ = b subject to z(μ) ∈ int(dom f).

3. Compute z(μ) through 1. Table 2 contains the function z(μ) = (z_{j}(μ))_{j=1}^{J} of Step 1 for some convex functions of Bregman/Legendre type of the form f(x) = ∑_{j} f_{j}(x_{j})

Step 2 is quite hard: only for f(x) = \frac{1}{2}∥x∥^{2} can one solve ⟨a, z(μ)⟩ = b explicitly for μ (and one then recovers the well-known formula for the orthogonal projection onto a hyperplane). However, μ can be estimated by iterative methods — in some cases, even a one-step approximation by the secant method is enough to guarantee convergence of a particular case of the method of Bregman projections (defined in Section 8); this nice observation is due to Censor et al. [9].

f_{j}(x_{j})  z_{j}(μ)
\frac{1}{2}x_{j}^{2}  y_{j} + μa_{j}
x_{j} ln x_{j} − x_{j}  y_{j} exp(μa_{j})
x_{j} ln x_{j} + (1 − x_{j}) ln(1 − x_{j})  \frac{exp(μa_{j})y_{j}/(1 − y_{j})}{1 + exp(μa_{j})y_{j}/(1 − y_{j})}
−\frac{1}{2} − ln x_{j}  y_{j}/(1 − μa_{j}y_{j})
\frac{1}{p}|x_{j}|^{p}  (sign(y_{j})|y_{j}|^{p−1} + μa_{j})^{1/(p−1)}

−\sqrt{1 − x_{j}^{2}}  \frac{μa_{j} + y_{j}/(1 − y_{j}^{2})^{1/2}}{\sqrt{(μa_{j} + y_{j}/(1 − y_{j}^{2})^{1/2})^{2} + 1}}

−4\sqrt{x_{j}}  y_{j}/(1 − \sqrt{y_{j}}μa_{j}/2)^{2}

Table 2.

Remark 6.14. Frequently, the interior of domain of the Legendre function on E is the strictly positive cone E^{+} := {x ∈ E : x_{j} > 0, ∀j}. Let a hyperplane in E be given by H := {x ∈ E : ⟨a, x⟩ = b}, for some a ∈ E \ {0} and b ∈ IR. Then H ∩ E^{+} = ∅ if and only

a ≥ 0 and b ≤ 0 or a ≤ 0 and b ≥ 0.

In applications, typically a ≥ 0, a ≠ 0, and b > 0; therefore, H ∩ E^{+} is nonempty and Corollary 6.12 applies.

Example 6.15. Let f(x) = ∑_{j} x_{j} ln x_{j} − x_{j} on dom f = {x ∈ IR^{J} : x_{j} ≥ 0, ∀j}

and H be the “probabilistic hyperplane” H = {x ∈ IR^{J} : ∑_{j} x_{j} = 1}. By Remark 6.14

(or by considering (1/J)(1, 1, …, 1) ∈ IR^{J}), we have H ∩ int(dom f) ≠ ∅. Moreover, the projection onto H has the beautiful form

P_{H}y = \frac{1}{∑_{j} y_{j}} y;

as is readily verified using Remark 6.13.

7. More Examples

7.1. Product spaces and Pythagorean means

Throughout this subsection, we assume that f_{1}, …, f_{N} are Bregman/Legendre functions on some Euclidean space E = IR^{J}, that C_{1}, …, C_{N} are closed convex nonempty subsets of E, and that λ_{1}, …, λ_{N} are strictly positive real numbers.

By Theorem 5.12,

f : E := ∏_{i} E → ] − ∞, +∞] : x := (x_{1}, …, x_{N}) ↦ ∑_{i} λ_{i}f_{i}(x_{i})

is Bregman/Legendre on E. Define the product set

C := ∏_{i} C_{i} = {(x_{1}, …, x_{N}) ∈ E : x_{i} ∈ C_{i}, ∀i}

and the diagonal set

Δ := {(e, …, e) ∈ E : e ∈ E}.

Then C ∩ Δ ≠ ∅ if and only if ⋂_{i} C_{i} ≠ ∅; this reduction to two sets in the product space E goes back at least as far as Pierra [28]. Now what do the Bregman projections onto C and Δ with respect to f look like? They are well-defined (Theorem 3.12) as soon as C ∩ int(dom f) ≠ ∅ and Δ ∩ int(dom f) ≠ ∅; equivalently:

C_{i} ∩ int(dom f_{i}) ≠ ∅, for all i; and ⋂_{i} int(dom f_{i}) ≠ ∅.  (∗)

The next proposition is easily verified; see also the closely related Lemmata 4.1 and 4.2 in [6] by Censor and Elfving.

Proposition 7.1. If (∗) holds, then for every y = (y_{1}, …, y_{N}) ∈ ∏_{i} int(dom f_{i}):

(i) P_{C}^{f}(y) = (P_{C_{1}}^{f_{1}}(y_{1}), …, P_{C_{N}}^{f_{N}} (y_{N})).

(ii) z = (z, …, z) = P f_{Δ}(y) if and only if

z ∈ ⋂_{i} int(dom f_{i}) and ∑_{i} λ_{i}∇f_{i}(z) = ∑_{i} λ_{i}∇f_{i}(y_{i}).

Proof. (i): Obvious, since D_{f}(x, y) = ∑_{i} λ_{i}D_{f_{i}}(x_{i}, y_{i}) is separable. (ii): By Proposition 3.16, z = (z, …, z) = P f_{Δ}(y) if and only if z ∈ ⋂_{i} int(dom f_{i}) and

⟨∇f(y) − ∇f(z), Δ − z⟩ ≤ 0.

Now Δ − z = Δ is a subspace and Δ^{⊥} = {(x_{1}, …, x_{N}) ∈ E : ∑_{i} x_{i} = 0}; the result follows.

Corollary 7.2. Suppose f is Bregman/Legendre on E and λ_{1}, …, λ_{N} are strictly positive weights: ∑_{i} λ_{i} = 1. Let f(x) := ∑_{i} λ_{i}f(x_{i}), for all x = (x_{1}, …, x_{N}) ∈ E. If y = (y_{1}, …, y_{N}) ∈ ∏_{i} int(dom f), then

P f_{Δ}(y) = (z, …, z), where z = ∇f^{∗}(∑_{i} λ_{i}∇f(y_{i})).

Proof. Clear from Proposition 7.1.(ii) and Fact 2.9. Note that z is indeed in int(dom f) by Fact 2.9 and the fact that the interior of a convex set is convex: y_{i} ∈ int(dom f), ∀i

H. H. Bauschke, J. M. Borwein / Legendre functions 53

⇒ ∇f(y_{i}) ∈ int(dom f^{∗}), ∀i ⇒ ∑_{i} λ_{i}∇f(y_{i}) ∈ int(dom f^{∗}) ⇒ ∇f^{∗}(∑_{i} λ_{i}∇f(y_{i})) = z ∈ int(dom f). Corollary 7.2 allows explicit calculation of Bregman projections onto the diagonal. It is pleasing that these projections turn out to be Pythagorean means if we use the best known Bregman/Legendre functions. Until the end of this subsection, let λ_{1}, …, λ_{N} be strictly positive weights. We denote the j^{th} coordinate of a vector x ∈ E by x(j). The following examples are readily verified with Corollary 7.2: Example 7.3. (p-norm and the (p − 1)-Hölder mean) Suppose 1 < p < +∞ and f(x) = \frac{1}{p}∥x∥_{p}^{p} = \frac{1}{p} ∑_{j} |x(j)|^{p} on dom f = E = IR^{J}. Let f(x) = ∑_{i} λ_{i}f(x_{i}) and y ∈ ∏_{i} int(dom f) = E = (IR^{J})^{N}. Then P f_{Δ}(y) = (z, …, z), where

z(j) = (λ_{1}|y_{1}(j)|^{p−1} + ⋯ + λ_{N}|y_{N}(j)|^{p−1})^{\frac{1}{p−1}} , for all j;

i.e. the j^{th} coordinate of P f_{Δ}(y) is the (p − 1)-Hölder mean of y_{1}(j), …, y_{N}(j). Two special cases deserve further attention; for p = 2 we obtain: Example 7.4. (2-norm and the arithmetic mean) Suppose f(x) = \frac{1}{2}∥x∥^{2} = \frac{1}{2} ∑_{j} |x(j)|^{2} on dom f = E = IR^{J}. Let f(x) = ∑_{i} λ_{i}f(x_{i}) and y ∈ ∏_{i} int(dom f) = E = (IR^{J})^{N}. Then

P f_{Δ}(y) = λ_{1}y_{1} + ⋯ + λ_{N}y_{N};

i.e. the j^{th} coordinate of P f_{Δ}(y) is the arithmetic mean of y_{1}(j), …, y_{N}(j). And p = 3 gives: Example 7.5. (3-norm and the quadratic mean) Suppose f(x) = \frac{1}{3}∥x∥_{3}^{3} = \frac{1}{3} ∑_{j} |x(j)|^{3} on dom f = E = IR^{J}. Let f(x) = ∑_{i} λ_{i}f(x_{i}) and y ∈ ∏_{i} int(dom f) = E = (IR^{J})^{N}. Then P f_{Δ}(y) = (z, …, z), where

z(j) = (λ_{1}|y_{1}(j)|^{2} + ⋯ + λ_{N}|y_{N}(j)|^{2})^{\frac{1}{2}} , for all j;

i.e. the j^{th} coordinate of P f_{Δ}(y) is the quadratic mean of y_{1}(j), …, y_{N}(j). Example 7.6. (“Boltzmann/Shannon” and the geometric mean) Suppose f(x) = ∑_{j} x(j) ln x(j) − x(j) on dom f = {x ∈ E = IR^{J} : x(j) ≥ 0 ∀j}. Let f(x) = ∑_{i} λ_{i}f(x_{i}) and y ∈ ∏_{i} int(dom f) = ∏_{i}{x ∈ E = IR^{J} : x(j) > 0, ∀j}. Then P f_{Δ}(y) = (z, …, z), where

z(j) = ∏_{i}(y_{i}(j))^{λ_{j}}, for all j;

i.e. the j^{th} coordinate of P f_{Δ}(y) is the geometric mean of y_{1}(j), …, y_{N}(j). Remark 7.7. Example 7.6 is the limiting case p = 1 of Example 7.3 in the sense that

lim_{p↓1} P p-norm_{Δ} = P Boltzmann/Shannon_{Δ}

point-wise on the interior of the domain of Boltzmann/Shannon.

The formula for the next example is precisely the one from Example 7.3.

Example 7.8. (p-root and the (p − 1)-Hölder mean – again!) Suppose 0 < p < 1 and f(x) = −\frac{1}{p} ∑_{j} |x(j)|^{p} on dom f = \{x ∈ E = IR^{J} : x(j) ≥ 0, ∀j\}. Let f(x) = ∑_{i} λ_{i}f(x_{i})

and y ∈ ∏_{i} int(dom f) = ∏_{i}{x ∈ E = IR^{J} : x(j) > 0, ∀j}. Then P f_{Δ}(y) = (z, …, z), where

z(j) = (λ_{1}(y_{1}(j))^{p−1} + ⋯ + λ_{N}(y_{N}(j))^{p−1})^{\frac{1}{p−1}} , for all j;

i.e. the j^{th} coordinate of P f_{Δ}(y) is the (p − 1)-Hölder mean of y_{1}(j), …, y_{N}(j).

Example 7.9. (“Burg” and the harmonic mean) Suppose f(x) = − ∑_{j} ln x(j) on

dom f = {x ∈ E = IR^{J} : x(j) > 0, ∀j}. Let f(x) = ∑_{i} λ_{i}f(x_{i}) and y ∈ ∏_{i} int(dom f) = ∏_{i}{x ∈ E = IR^{J} : x(j) > 0, ∀j}. Then P f_{Δ}(y) = (z, …, z), where

z(j) = \frac{1}{\frac{λ_{1}}{y_{1}(j)} + ⋯ + \frac{λ_{N}}{y_{N} (j)}} , for all j;

i.e. the j^{th} coordinate of P f_{Δ}(y) is the harmonic mean of y_{1}(j), …, y_{N}(j).

Remark 7.10. Example 7.9 can be viewed as the limiting case p = 0 of Example 7.8 in the sense that

lim_{p↓0} P p-root_{Δ} = P Burg_{Δ}

point-wise on the interior of the domain of Burg.

Example 7.11. (“Fermi/Dirac”) Suppose f(x) = ∑_{j} x(j) ln x(j)+(1−x(j)) ln(1−x(j))

on dom f = [0, 1]^{J}. Let f(x) = ∑_{i} λ_{i}f(x_{i}) and y ∈ ∏_{i} int(dom f) = (]0, 1[^{J})^{N}. Then P f_{Δ}(y) = (z, …, z), where

z(j) = \frac{∏_{i}(x_{i}(j))^{λ_{i}}}{∏_{i}(x_{i}(j))^{λ_{i}} + ∏_{i}(1 − x_{i}(j))^{λ_{i}}} , for all j.

Remark 7.12.

• It is not too surprising that the geometric mean (resp. the harmonic mean) appears as limiting case of the Hölder mean for p = 1 in Remark 7.7 (resp. p = 0 in Remark 7.10), since in fact the “Boltzmann/Shannon entropy” (resp. the “Burg entropy”) is the “limiting” case of “an affine pertubation” of the p-norm (resp. the p-root) in the sense that

lim_{p↓1}(t^{p} − t)/(p − 1) − pt = t ln t − t (resp. lim_{p↓0}(1 − t^{p})/p = − ln t ).

• The projection onto the diagonal Δ shares “mean”-like properties since the j^{th} coordinate of P_{Δ}^{f} is of the form φ^{−1}(λ_{1}φ(a_{1})+⋯+λ_{N}φ(a_{N})) (Fact 2.9 and Corollary 7.2), where φ is strictly increasing by the strict convexity of f.

• Examples 7.4, 7.6, and 7.9 also appear in Censor and Reich’s Example 4.1 in [12]. However, Example 7.9 is given for purely formal reasons – essentially because the function − ln is not Bregman and thus not covered by their framework (see also Remarks 4.2).

7.2. The Hermitian matrices

Lewis recently demonstrated [22, 25, 24, 26] that many parts of classical matrix analysis can be very satisfactorily studied within the framework of convex analysis. This viewpoint has provided numerous insights and examples; a glimpse is provided in this subsection where we assume throughout that

H is the real vector space of J × J Hermitian matrices.

(Recall that X ∈ IC^{J×J} is Hermitian, if X^{∗} := \overline{X^{T}} = X.) Denoting the trace of a matrix by tr, the vectorspace H becomes a Hilbert space through

⟨X, Y ⟩ = tr(XY^{∗}), ∀X, ∀Y ∈ H.

For brevitiy, we denote the J × J permutation matrices by P and the J × J unitary matrices by U. (Recall that U ∈ IC^{J×J} is unitary, if U^{∗} = U^{−1}.) Let λ(X) := (λ_{1}(X), λ_{2}(X), …, λ_{J}(X)) be the eigenvalues of X in decreasing order, so that λ is a mapping from H to IR^{J}. Assume further that

f : IR^{J} → ] − ∞, +∞]

is closed, convex, permutation-symmetric, and proper. (f is called permutation-symmetric, if f(P x) = f(x), ∀x ∈ IR^{J}, ∀P ∈ P.)

Fact 7.13. (Lewis’ Corollary 2.7 and Theorem 2.6 in [22]) The induced function

f ∘ λ : H → ] − ∞, +∞] : X ↦ f(λ(X))

is unitarily equivalent, i.e. (f ∘ λ)(U^{∗}XU) = (f ∘ λ)(X), ∀X ∈ H, ∀U ∈ U. Moreover,

(f ∘ λ)^{∗} = f^{∗} ∘ λ.

The punchline is that there is a nice relationship between properties of f and of f ∘ λ. Often, it is enough to study the much simpler function f and still possible to get useful information on f ∘ λ; for instance:

Fact 7.14. (Lewis)

(i) dom(f ∘ λ) = λ^{−1}(dom f). (ii) int(dom(f ∘ λ)) = λ^{−1}(int(dom f)). (iii) f ∘ λ is Legendre if and only if f is.

Proof. (i) and (ii) follow from Theorem 5.4 in [26]. Corollary 3.3 in [22] in tandem with Corollary 3.5 in [22] implies (iii).

Of course, we want to know when f ∘ λ is a Bregman/Legendre function. Theorem 5.6 gives an easy criterion:

Proposition 7.15. If dom f and dom f^{∗} are open, then f ∘ λ is Bregman/Legendre.

Proof. By Fact 7.14.(i),(ii),

int(dom(f ∘ λ)) = λ^{−1}(int(dom f)) = λ^{−1}(dom f) = dom(f ∘ λ);

hence dom(f ∘ λ) is open. Now (f ∘ λ)^{∗} = f^{∗} ∘ λ; thus (by similar reasoning), dom(f ∘ λ)^{∗} is open. Apply Theorem 5.6.

Example 7.16. (p-norm) Suppose 1 < p < +∞ and f(x) = ∑_{j} \frac{1}{p}|x_{j}|^{p} = \frac{1}{p}∥x∥_{p}^{p} on

dom f = int(dom f) = E = IR^{J}. Then f ∘ λ is Bregman/Legendre and

(f ∘ λ)(X) = \frac{1}{p}∥λ(X)∥_{p}^{p} = ∑_{j} \frac{1}{p}|λ_{j}(X)|^{p},

for all X ∈ dom(f ∘ λ) = H.

The next example shows that the famous “logarithmic barrier function”, also known as Burg’s entropy on H, is Bregman/Legendre:

Example 7.17. Suppose f(x) = ∑_{j} − ln x_{j} on dom f = {x ∈ E : x_{j} > 0, ∀j}. Then f ∘ λ is Bregman/Legendre and

(f ∘ λ)(X) = − ln det X,

for all X ∈ dom(f ∘ λ) = {X ∈ H : X positive semidefinite}. The best we could possibly hope for would be a result like

“f ∘ λ is a convex function of Bregman/Legendre type if and only if f is”;

this will, however, turn out to be false even for the “Boltzmann/Shannon entropy”. For this counter-example, some machinery has to be developed; along the way, we will obtain some interesting positive results. Given a vector x = (x_{j}) ∈ IR^{J}, we write Δ(x) or Δx for the J × J diagonal matrix with diagonal entries x_{1}, …, x_{J}. Similarly, given a J × J matrix X with diagonal entries X_{11}, …, X_{JJ}, we write Δ(X) or ΔX for the diagonal matrix with diagonal entries X_{11}, …, X_{JJ} or for the vector in IR^{J} with components X_{11}, …, X_{JJ}. (It will be clear from the context which object is meant.) We give a chain of useful facts and omit or comment only briefly on their proofs.

Proposition 7.18. Suppose X ∈ H is diagonal: X = Δ(X). Then

⟨X, Y ⟩ = ⟨X, ΔY ⟩, ∀Y ∈ H.

Proposition 7.19. (Lewis) Suppose f is a Legendre function and Y ∈ int(dom(f ∘ λ)). Then

(i) ∇(f ∘ λ)(Y) = V (Δ∇f(λ(Y)))V^{∗}, ∀V ∈ U with V^{∗}Y V = Δλ(Y). (ii) ∇(f ∘ λ)(U^{∗}Y U) = U^{∗}∇(f ∘ λ)(Y)U, ∀U ∈ U. (iii) ⟨∇(f ∘ λ)(U^{∗}Y U), U^{∗}(X − Y)U⟩ = ⟨∇(f ∘ λ)(Y), X − Y ⟩, ∀U ∈ U, ∀X ∈ H.

Proof. (i) follows from Lewis’ Corollary 3.3 in [22].

(i) implies (ii), which in turn implies (iii).

Remark 7.20. If Y ∈ int(dom(f ∘ λ)) is diagonal, then so is ∇(f ∘ λ)(Y): simply pick V as a permutation matrix in Proposition 7.19.(i).

Corollary 7.21. D_{f∘λ}(X, Y) = D_{f∘λ}(U^{∗}XU, U^{∗}Y U), ∀X ∈ H, ∀Y ∈ int(dom(f ∘ λ)), ∀U ∈ U.

Proof.

D_{f∘λ} = (f ∘ λ)(X) − (f ∘ λ)(Y) − ⟨∇(f ∘ λ)(Y), X − Y ⟩
= (f ∘ λ)(U^{∗}XU) − (f ∘ λ)(U^{∗}Y U) − ⟨∇(f ∘ λ)(U^{∗}Y U), U^{∗}(X − Y)U⟩
= D_{f∘λ}(U^{∗}XU, U^{∗}Y U).

The last corollary allows reduction to the case when one matrix is diagonal.

Proposition 7.22. (Lewis [23]) Suppose X ∈ H and ΔX is decreasing: X_{11} ≥ X_{22} ≥ ⋯ ≥ X_{JJ}. Then

ΔX ∈ conv{P λ(X) : P ∈ P}.

Proof. Since P is finite, so is {P λ(X) : P ∈ P}. Hence conv{P λ(X) : P ∈ P} is compact. Assume to the contrary that ΔX ∉ conv{P λ(X) : P ∈ P}. Separation yields z ∈ IR^{J} such that ⟨z, ΔX⟩ > sup⟨z, conv{P λ(X) : P ∈ P}⟩. Now

sup⟨z, conv{P λ(X) : P ∈ P}⟩ = sup⟨z, {P λ(X) : P ∈ P}⟩
= sup{⟨P z, λ(X)⟩ : P ∈ P}.

The last supremum is attained for some P̃ ∈ P. By Lemma 2.1 in [22], P̃ z has precisely the components of z, but arranged decreasingly. Invoking Lemma 2.1 in [22], Proposition 7.18, and a result due to von Neumann (see Theorem 2.2 in [22]), we obtain

⟨P̃ z, λ(X)⟩ = sup⟨z, conv{P λ(X) : P ∈ P}⟩
< ⟨z, ΔX⟩
≤ ⟨P̃ z, ΔX⟩
= ⟨Δ(P̃ z), Δ(X)⟩
= ⟨Δ(P̃ z), X⟩
≤ ⟨λ(Δ(P̃ z)), λ(X)⟩
= ⟨P̃ z, λ(X)⟩,

which is the desired contradiction.

Corollary 7.23. Suppose C ⊆ IR^{J} is convex and permutation-symmetric: P C = C, ∀P ∈ P. If Y ∈ λ^{−1}(C), then ΔY ∈ C.

Proof. Note that Y ∈ λ^{−1}(C) ⇔ λ(Y) ∈ C ⇔ P λ(Y) ∈ C, ∀P ∈ P. Also, there is some P̃ ∈ P such that Δ(P̃ Y P̃) is a decreasing re-arrangement of ΔY. Thus, using Proposition 7.22,

Δ(P̃ Y P̃) ∈ conv{P λ(P̃ Y P̃) : P ∈ P} = conv{P λ(Y) : P ∈ P} ⊆ C;

hence ΔY ∈ C.

Theorem 7.24. Suppose X ∈ dom(f ∘ λ), Y ∈ int(dom(f ∘ λ)), and X is diagonal: X = ΔX. Then: (i)

D_{f∘λ}(X, Y) =D_{f∘λ}(X, ∇(f^{∗} ∘ λ)Δ∇(f ∘ λ)(Y))
+ (f^{∗} ∘ λ)(∇(f ∘ λ)(Y))
− (f^{∗} ∘ λ)(Δ∇(f ∘ λ)(Y)).

(ii)

D_{f∘λ}(∇(f^{∗} ∘ λ)Δ∇(f ∘ λ)(Y), Y) =(f^{∗} ∘ λ)(∇(f ∘ λ)(Y))
− (f^{∗} ∘ λ)(Δ∇(f ∘ λ)(Y)
=D_{f^{∗}∘λ}(∇(f ∘ λ)(Y), Δ∇(f ∘ λ)(Y)).

(iii)

\begin{matrix}D_{f∘λ}(X, Y) = & D_{f∘λ}(X, ∇(f^{∗} ∘ λ)Δ∇(f ∘ λ)(Y)) \\ + D_{f∘λ}(∇(f^{∗} ∘ λ)Δ∇(f ∘ λ)(Y), Y). \end{matrix}

Proof. Y ∈ int(dom(f ∘λ)) implies ∇(f ∘λ)(Y) ∈ int(dom(f ∘λ)^{∗}) = int(dom(f^{∗} ∘λ)) = λ^{−1}(int(dom f^{∗})) by Fact 2.9, Fact 7.13, and Fact 7.14.(ii). Hence Δ∇(f ∘ λ)(Y) ∈ λ^{−1}(int(dom f^{∗})) = int(dom(f ∘ λ)^{∗}), by Corollary 7.23. Thus ∇(f^{∗} ∘ λ)Δ∇(f ∘ λ)(Y) ∈ int(dom(f ∘ λ)), by Fact 2.9 and Fact 7.13; in other words: all terms appearing in the statement of the theorem make sense. Using Proposition 7.18, we deduce (i):

D_{f∘λ}(X, Y) = (f ∘ λ)(X) + (f^{∗} ∘ λ)(∇(f ∘ λ)(Y)) − ⟨∇(f ∘ λ)(Y), X⟩
= (f ∘ λ)(X) + (f^{∗} ∘ λ)(Δ∇(f ∘ λ)(Y)) − ⟨Δ∇(f ∘ λ)(Y), X⟩
+ (f^{∗} ∘ λ)(∇(f ∘ λ)(Y)) − (f^{∗} ∘ λ)(Δ∇(f ∘ λ)(Y))
= D_{f∘λ}(X, ∇(f^{∗} ∘ λ)Δ∇(f ∘ λ)(Y))
+ (f^{∗} ∘ λ)(∇(f ∘ λ)(Y)) − (f^{∗} ∘ λ)(Δ∇(f ∘ λ)(Y)).

By Remark 7.20, the matrix ∇(f^{∗} ∘ λ)Δ∇(f ∘ λ)(Y) is diagonal. Setting X equal to the last matrix yields the first equation of (ii); the second one is just Theorem 3.7.(v). Now (iii) follows.

Remark 7.25. Theorem 7.24 is quite useful when investigating the method of random projections on the Hermitian matrices, because the nonnegative Bregman distance is further broken up into two nonnegative parts. “Deconjugating” Theorem 7.24.(ii) yields

Corollary 7.26. For all Y ∈ int(dom(f ∘ λ)):

D_{f∘λ}(Y, ΔY) = (f ∘ λ)(Y) − (f ∘ λ)(ΔY) ≥ 0;

equality holds if and only if Y = ΔY, i.e. Y is diagonal.

We can thus interpret D_{f∘λ}(Y, ΔY) as a “measure of non-diagonality” of Y, which turns out to be well-known for certain instances of f:

Example 7.27. (p-trace)

(i) Suppose 1 < p < +∞. Then for all Y ∈ H:

∥λ(Y)∥_{p} ≥ ∥λ(ΔY)∥_{p};

equality holds if and only if Y = ΔY. (ii) Suppose 0 < p < 1. Then for all Y ∈ H that are positive definite:

−\frac{1}{p} ∑_{j}(λ_{j}(Y))^{p} ≥ −\frac{1}{p} ∑_{j} Y_{jj}^{p};

equality holds if and only if Y = ΔY.

Proof. (i): Consider f(x) = ∑_{j} \frac{1}{p}|x_{j}|^{p} on dom f = IR^{J}.

(ii): Consider f(x) = − ∑_{j} \frac{1}{p}x_{j}^{p} on dom f = \{x ∈ IR^{J} : x_{j} ≥ 0, ∀j\}. Note that

int(dom(f ∘ λ)) = λ^{−1}(int(dom f)) = the positive definite matrices in H.

Example 7.28. (Hadamard’s inequality; see, e.g., Chapter 9, Section B of [27]) For all Y ∈ H that are positive definite:

det Y ≤ ∏_{j} Y_{jj};

equality holds if and only if Y = ΔY.

Proof. Consider f(x) = ∑_{j} − ln x_{j} on dom f = {x ∈ IR^{J} : x_{j} > 0 ∀j}. Then (f ∘ λ)(X) = − ln det X on the positive definite matrices in H; see Lewis’ Section 4 in [22].

We now give the counter-example announced at the beginning of this subsection.

Example 7.29. (“Boltzmann/Shannon ∘λ” is not Bregman/Legendre on H) Suppose f(x) = ∑_{j=1}^{2} x_{j} ln x_{j} − x_{j} on dom f = {x ∈ IR^{2} : x_{j} ≥ 0, ∀j}. Let

B = ( \begin{matrix}1 & 0 \\ 0 & 0 \end{matrix} );

then B ∈ dom(f ∘λ)\int(dom(f ∘λ)). Suppose further (λ_{n}), (μ_{n}), (s_{n}), (c_{n}) are sequences of strictly positive real numbers with λ_{n} ↑ 1, μ_{n} < λ_{n}, μ_{n} ↓ 0, s_{n}^{2}+c_{n}^{2} = 1, s_{n} → 0, c_{n} → 1. Let

V_{n} = ( \begin{matrix}c_{n} & −s_{n} \\ s_{n} & c_{n} \end{matrix} ) and Y_{n} = V_{n} ( \begin{matrix}λ_{n} & 0 \\ 0 & μ_{n} \end{matrix} ) V_{n}^{∗}.

Then V_{n} is unitary, V_{n} → I, B_{n} ∈ int(dom(f ∘ λ)) = the positive definite matrices in H, and B_{n} → B. Also, for X ∈ dom(f ∘ λ), Y ∈ int(dom(f ∘ λ)),

\begin{matrix}D_{f∘λ} = & (f ∘ λ)(X) + (f^{∗} ∘ λ)(∇(f ∘ λ)(Y)) − ⟨∇(f ∘ λ)(Y), X⟩ \\ = & ∑_{j=1}^{2} λ_{j}(X) ln λ_{j}(X) − λ_{j}(X) + ∑_{j=1}^{2} λ_{j}(Y) − ⟨∇(f ∘ λ)(Y), X⟩. \end{matrix}

Thus

D_{f∘λ}(0, B_{n}) = ∑_{j=1}^{2} λ_{j}(B_{n}) = tr(B_{n}) = λ_{n} + μ_{n} → 1,

and all hypotheses of BL2 hold. By Proposition 7.19.(i),

∇(f ∘ λ)(B_{n}) =V_{n} ( \begin{matrix}ln λ_{n} & 0 \\ 0 & ln μ_{n} \end{matrix} ) V_{n}^{∗}

= ( \begin{matrix}c_{n}^{2} ln λ_{n} + s_{n}^{2} ln μ_{n} & c_{n}s_{n}(ln λ_{n} − ln μ_{n}) \\ c_{n}s_{n}(ln λ_{n} − ln μ_{n}) & s_{n}^{2} ln λ_{n} + c_{n}^{2} ln μ_{n} \end{matrix} );

so

D_{f∘λ}(B, B_{n}) = −1 + λ_{n} + μ_{n} − (c_{n}^{2} ln λ_{n} + s_{n}^{2} ln μ_{n}).

Thus, for large n,

D_{f∘λ}(B, B_{n}) ≈ −s_{n}^{2} ln μ_{n}.

A posteriori, it is easy to arrange that the sequence (−s_{n}^{2} ln μ_{n}) does not converge to 0 (as would be required to satisfy BL2). Take, for instance, s_{n} = 1/\sqrt{n} and μ_{n} = exp(−n^{2}); then the sequence (−s_{n}^{2} ln μ_{n}) = (n) even tends to +∞.

Remark 7.30. Using Theorem 7.24, one can show that “Boltzmann/Shannon∘λ” satisfies BL1; see also Remark 7.25.

Remark 7.31. It is clear that all results in this subsection on unitarily invariant matrix functions defined on the Hermitian matrices have counter-parts for orthogonally invariant matrix functions defined on the symmetric matrices. In particular, Example 7.29 can be interpreted as an example on IR^{3}, since IR^{3} and the symmetric 2 × 2 matrices are isomorphic. This opens another avenue for constructing interesting non-separable convex functions. Specifically, Example 7.29 translates to the following:

Example 7.32. IR^{3} is isomorphic to the symmetric 2 × 2 matrices via

T x = T (x_{1}, x_{2}, x_{3}) = ( \begin{matrix}x_{1} & x_{2} \\ x_{2} & x_{3} \end{matrix} ) , ∀x = (x_{1}, x_{2}, x_{3}) ∈ IR^{3}.

The matrix T x is positive semi-definite if and only if x_{1}, x_{3} ≥ 0 and x_{1}x_{3} − x_{2}^{2} ≥ 0. The eigenvalues of T x in decreasing order are

λ(T x) = \frac{1}{2}(x_{1} + x_{3} + \sqrt{(x_{1} − x_{3})^{2} + 4x_{2}^{2}}, x_{1} + x_{3} − \sqrt{(x_{1} − x_{3})^{2} + 4x_{2}^{2}}).

Now let f(y) = y_{1} ln y_{1} − y_{1} + y_{2} ln y_{2} − y_{2} on IR^{2}. Then F = f ∘ λ ∘ T is a Legendre function but F is not Bregman/Legendre. For instance, this interpretation makes the convexity of F a triviality. On the other hand, it seems not to be easy to check convexity directly. Also, this example induces the counter-example announced in Remark 3.4. We conclude this section with a truly matrix-based example.

Example 7.33. (Doubly stochastic constraints) Let S be the real Hilbert space of J × J symmetric matrices with ⟨X, Y ⟩ = tr(XY^{T}), ∀X, ∀Y ∈ S (see Remark 7.31). The elements of the i^{th} row (or column) of a given matrix Y ∈ S add up to 1 exactly when

⟨A_{i}, Y ⟩ = 1, where (A_{i})_{mn} = \{ \begin{matrix}1, & if m = n = i; \\ \frac{1}{2}, & if m ≠ n and i ∈ \{m, n\}; \\ 0, & otherwise. \end{matrix}

Hence Y is doubly-stochastic, if Y ∈ ⋂_{i} H_{i}, where H_{i} = {X ∈ S : ⟨A_{i}, X⟩ = 1}. The orthogonal projection (i.e. the Bregman projection w.r.t. \frac{1}{2}∥ · ∥^{2}) is explicitly given through

P_{H_{i}}Y = Y − \frac{∑_{j} Y_{ij} − 1}{(J + 1)/2}A_{i}.

Bregman projections with respect to other (Bregman/)Legendre functions can be approximated by the procedure described in Remark 6.13.

8. The method of random Bregman projections

It is convenient to abbreviate the following assumption (A):

f is a Legendre function on E,

C_{1}, …, C_{N} are closed convex sets with ⋂_{i} C_{i} ∩ dom f ≠ ∅, (A)

C_{i} ∩ int(dom f) ≠ ∅, ∀i.

Note that it may happen that ⋂_{i} C_{i} ∩ int(dom f) = ∅.

Let r be a random mapping for {1, …, N}, i.e. a mapping from IN onto {1, …, N} that takes each value in {1, …, N} infinitely often.

The method of random Bregman projections generates a sequence (y_{n}) by

y_{0} ∈ int(dom f) and y_{n+1} := P_{C_{r(n+1)}}y_{n}, ∀n ≥ 0. (M)

For instance, we could consider the random function r(n) ≡ n mod N (where we let the modN function take values in {1, …, N}) and thus obtain the well-known method of cyclic Bregman projections. We refer to the point y_{0} as the starting point.

In view of Theorem 3.14, assumption (A) guarantees that the sequence generated by method (M) lies in int(dom f) and is thus well-defined (the interiority/zone consistency condition!).

Theorem 8.1. Suppose assumption (A) and (at least) one of the following conditions hold:

(i) f is a Bregman/Legendre function. (ii) ⋂_{i} C_{i} ∩ int(dom f) ≠ ∅ and dom f^{∗} is open.

(iii) dom f and dom f^{∗} are open. Then for an arbitrary starting point y_{0} ∈ int(dom f), the sequence (y_{n}) generated by method (M) converges to some point y in ⋂_{i} C_{i} ∩ dom f and D_{f}(y, y_{n}) → 0. If (ii) or (iii) holds, then y actually belongs to ⋂_{i} C_{i} ∩ int(dom f).

Proof. (i): Proposition 3.16 yields

1. D_{f}(y_{n+1}, y_{n}) ≤ D_{f}(c, y_{n}) − D_{f}(c, y_{n+1}), ∀n ≥ 0, ∀c ∈ C_{r(n+1)} ∩ dom f.

Hence

2. D_{f}(y_{n+1}, y_{n}) ≤ D_{f}(c, y_{n}) − D_{f}(c, y_{n+1}), ∀n ≥ 0, ∀c ∈ ⋂_{i} C_{i} ∩ dom f.

Fix any c ∈ ⋂_{i} C_{i} ∩ dom f and observe that (D_{f}(c, y_{n})) is decreasing and hence bounded. By Corollary 3.11 (i.e. BL0) or BL1 (depending on the location of c), the sequence

3. (y_{n}) is bounded.

Suppose now that ȳ is an arbitrary cluster point of (y_{n}), say y_{k_{n}} → ȳ. Step by step, we collect properties on ȳ.

Property 1: ȳ ∈ dom f and D_{f}(ȳ, y_{k_{n}}) → 0.

If ȳ ∈ int(dom f), then apply Proposition 3.2.(ii). If ⋂_{i} C_{i} ∩int(dom f) ≠ ∅, then pick any c in this intersection; Property 1 then follows from 2 and Theorem 3.8.(ii). Otherwise, ȳ ∈ bd(dom f) and we make use of BL2. Property 1 is established for all cases.

Property 2: ȳ ∈ ⋂_{i} C_{i}. We can assume without loss that r(k_{n}) ≡ ρ ∈ {1, …, N} (after passing to a subsequence if necessary). Let’s define

I_{in} := {i ∈ {1, …, N} : ȳ ∈ C_{i}} and I_{out} := {1, …, N} \ I_{in}.

We want to show that I_{out} = ∅. So let us assume to the contrary that I_{out} ≠ ∅. Since r is a random mapping, we can also assume (subsequence!) that {r(k_{n}), r(k_{n} + 1), …, r(k_{n+1} − 1)} = {1, …, N}. For every n, pick m_{n} maximal in {k_{n}, k_{n} + 1, …, k_{n+1} − 1} such that r(m_{n}) ∈ I_{in}. This is possible, since ρ ∈ I_{in} and I_{out} is assumed to be nonempty. Then, by definition of m_{n}, for every k_{n} ≤ ν ≤ m_{n}, r(ν) ∈ I_{in}; hence, by using 1 successively, D_{f}(ȳ, y_{m_{n}}) ≤ D_{f}(ȳ, y_{k_{n}}). It follows with Property 1 that

3. D_{f}(ȳ, y_{m_{n}}) → 0.

Claim 1: y_{m_{n}} → ȳ. We can assume without loss (subsequence!) that y_{m_{n}} → z̄ ∈ dom f with D_{f}(z̄, y_{m_{n}}) → 0 (Property 1). If {ȳ, z̄} ∩ int(dom f) ≠ ∅, then 3 and Theorem 3.9.(iii) imply ȳ = z̄. Otherwise ȳ, z̄ ∈ dom f \ int(dom f) and Proposition 5.5 applies. Claim 1 thus holds. After passing to yet another subsequence if necessary, we assume without loss that r(m_{n}+ 1) ≡ i, for some i ∈ I_{out}; and that y_{m_{n}+1} → z̄ ∈ dom f ∩ C_{i}. Note that by 2,

4. D_{f}(y_{m_{n}+1}, y_{m_{n}}) → 0.

Claim 2: ȳ = z̄. If ȳ or z̄ is in the interior of dom f, then use 4 and Theorem 3.9.(iii); otherwise, use 4 and BL3. Claim 2 is verified.

Claim 2 now yields the contradiction i ∈ I_{in} ∩ I_{out}. Consequently, Property 2 does hold. Property 1, Property 2, and 1 imply

Property 3: D_{f}(ȳ, y_{n}) → 0.

It remains to show that the entire sequence converges to ȳ. Let z̄ be a (possibly different) cluster point of (y_{n}), say y_{l_{n}} → z̄. By Properties 1 through 3 (for (y_{l_{n}}) and z̄),

5. z̄ ∈ ⋂_{i} C_{i} ∩ dom f and D_{f}(z̄, y_{n}) → 0.

If {ȳ, z̄} ∩ int(dom f) ≠ ∅, then ȳ = z̄ by Theorem 3.9.(iii). Otherwise, ȳ, z̄ ∈ dom f \ int(dom f) and D_{f}(ȳ, y_{l_{n}}) → 0 (Property 3). Then Proposition 5.5 applies and yields ȳ = z̄. The proof for (i) is complete. (ii): is proved as (i), with the exceptions that the stronger ȳ ∈ int(dom f) is derived and that BL1 through BL3 are not needed. (iii): is then clear, since (iii) implies (ii).

Remark 8.2. Let us see how the conditions (i), (ii), and (iii) are related.

• “(iii)⇒(ii)” and “(iii)⇒(i)” but not vice versa: this follows from assumption (A), Theorem 5.6, and the example x ln x − x on E = IR = C_{1} with N = 1.

• On the real line, “(i)⇔(ii)”: use assumption (A) and a direct interval argument for proving “⇒” and Theorem 5.8 for “⇐”.

• In general, (i) and (ii) are independent: if N = 1, E = C_{1} = IR^{2}, and f is as in Example 6.9, then (ii) holds but (i) does not. And if N = 2, f(x) = ∑_{j} x_{j} ln x_{j} − x_{j}

on E = IR^{2}, then (i) holds but (ii) fails. To summarize, we can say that the method of random Bregman projections always works for two quite general situations:

• the function f is Bregman/Legendre – which is easy to check for separable functions.

• the constraint qualification ⋂_{i} C_{i} ∩ dom f ≠ ∅ holds and f is just Legendre with dom f^{∗} open. Here, the conditions on f are readily verifiable whereas the constraint qualification requires some a priori knowledge.

Remark 8.3.

• The proof of Theorem 8.1 is an extension of the proof of the authors’ (Theorem 3.10 of [3]). We want to remark that the latter proof in turn relies on an idea developed almost simultaneously by Flåm and Zowe [16], by Tseng [32], and by Elsner et al. [15] around the beginning of the decade; this idea is also present in Censor and Reich’s analysis [12].

• Though similar, the assumptions in Censor and Reich’s work [12] differ from ours: they allow one to draw operators from a possibly infinite pool whereas our underlying distance function is more general. For instance, “Burg’s entropy”, − ln, is excluded in [12] but included here.

• It is clear that Theorem 8.1, Theorem 5.12, and the results in the first half of Section 7 imply convergence results for simultaneous Bregman projection methods. This procedure is straight-forward; the development follows along the lines of Censor and Elfving work [6]. Our present analysis has the advantage that interiority/zone consistency of the Bregman projections in the product space is guaranteed automatically.

• A pointer to some references on the method of random orthogonal projections (in Hilbert space) is the first author’s [2].

• In August 1994, during the Mathematical Programming conference in Ann Arbor, K. Kiwiel announced results that appear to be related to Theorem 8.1.

We can say more on the limit in the important case of hyperplanes:

Theorem 8.4. Suppose assumption (A) holds for hyperplanes C_{i} = {x ∈ E : ⟨a_{i}, x⟩ = b_{i}}, where a_{i} ∈ E \ {0}, b_{i} ∈ IR. Suppose also (at least) one of the following conditions is satisfied:

(i) f is a Bregman/Legendre function. (ii) ⋂_{i} C_{i} ∩ int(dom f) ≠ ∅ and dom f^{∗} is open. (iii) dom f and dom f^{∗} are open. Suppose further the set {z ∈ E : ∇f(z) ∈ span(a_{1}, …, a_{N})} is nonempty and y_{0} is an arbitrary element of it. Then the sequence (y_{n}) generated by method (M) with starting point y_{0} converges to some point in

argmin_{x∈dom f∩∩_{i}C_{i}} f(x).

In case of (ii) or (iii), the argmin is singleton and an element of int(dom f).

Proof. Theorem 8.1 yields the convergence of the sequence (y_{n}) to some point y in dom f ∩ ⋂_{i} C_{i} with D_{f}(y, y_{n}) → 0. Define A : E → IR^{N} : x ↦ (⟨a_{i}, x⟩)_{i}. Then, by Corollary 6.12, the entire sequence (y_{n}) belongs to Z := {z ∈ E : ∇f(z) ∈ span(a_{1}, …, a_{N})} = {z ∈ E : ∇f(z) ∈ range A^{∗}}. Now fix an arbitrary element x in ⋂_{i} C_{i} ∩ dom f. Then y − x ∈ kernel A = (range A^{∗})^{⊥} so that

\begin{matrix}f(y) − f(x) = & f(y) − f(x) − ⟨∇f(y_{n}), y − x⟩ \\ = & D_{f}(y, y_{n}) − D_{f}(x, y_{n}) \\ ≤ & D_{f}(y, y_{n}) \\ → & 0. \end{matrix}

Thus y is contained in the argmin. Finally, if (ii) or (iii) holds, then y ∈ int(dom f) by Theorem 8.1. But f is strictly convex on int(dom f) and the argmin is therefore singleton.

Remark 8.5.

• Theorem 8.4 remains true if we replace “hyperplane” by “affine subspace”. The proof is the same, but notationally much less convenient. Classical results on the method of orthogonal projections are obtained for the choice f(x) = \frac{1}{2}∥x∥^{2}; for more, see [3] and the references therein.

• Assuming the hypothesis of Theorem 8.4, suppose the argmin _{x∈dom f} f(x) is actually contained in int(dom f). By essential strict convexity of f, the argmin is singleton, say x_{0}. We now can simply choose y_{0} = x_{0} as starting point for the method (M), because ∇f(y_{0}) = 0 ∈ span(a_{1}, …, a_{N}). The following table contains a selection of Legendre functions on IR for which this technique applies; of course, this extends to separable Legendre functions.

f(x)  argmin_{x∈dom f} f(x)

\frac{1}{2}|x|^{2}  0
x ln x − x  1
x ln x + (1 − x) ln(1 − x)  \frac{1}{2}
\frac{1}{p}|x|^{p}  0
−\sqrt{1 − x^{2}}  0

• Related though somewhat different to Theorem 8.4 are the following:

•• Bregman’s [4] (cyclic control).

•• Censor and Lent’s [7] (cyclic control).

•• De Pierro and Iusem’s [29] (cyclic control, but “relaxed” projections).

•• Censor and Lent’s [8] (cyclic control for “Burg’s entropy”, − ln, with “bare hands”). •• Censor and Reich’s [12] (more general operators but the function that induces the Bregman distance has to be Bregman; see the Remarks in Section 4).

Acknowledgment. It is our pleasure to thank Adrian Lewis for extremely helpful discussions on the subsection on Hermitian matrices in Section 7.2, for the proof of Proposition 7.22, and for sending us [22, 25, 24, 26]. We wish to thank Regina Burachik, Dan Butnariu, Yair Censor, Alfredo Iusem, and Krzysztof Kiwiel for providing us with [5], [1], [6], [19], and [21]. Thanks are also due to two anonymous referees who made several valuable comments and suggestions; one referee pointed out that Censor et al. considered in [11], [10] slight extensions of Bregman functions which do include Burg’s entropy.

References

[1] Y. Alber and D. Butnariu: Convergence of Bregman-projection methods for solving consistent convex feasibility problems in reflexive Banach spaces. Journal of Optimization Theory and Applications (1994) Accepted for Publication.

[2] H.H. Bauschke: A norm convergence result on random products of relaxed projections in Hilbert space. Transactions of the American Mathematical Society, 347(4) (1995) 1365– 1374.

[3] H.H. Bauschke and J.M. Borwein: On projection algorithms for solving convex feasibility problems. SIAM Review 38(3) (1996) 367–426.

[4] L.M. Bregman: The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming. U.S.S.R. Computational Mathematics and Mathematical Physics 7(3) (1967) 200–217.

66 H. H. Bauschke, J. M. Borwein / Legendre functions

[5] R.S. Burachik: Generalized Proximal Point Methods of the Variational Inequality Problem. PhD thesis, Rio de Janeiro, 1995.

[6] Y. Censor and T. Elfving: A multiprojection algorithm using Bregman projections in a product space. Numerical Algorithms 8 (1994) 221–239.

[7] Y. Censor and A. Lent: An iterative row-action method for interval convex programming. Journal of Optimization Theory and Applications 34(3) (1981) 321–353.

[8] Y. Censor and A. Lent: Optimization of “log x” entropy over linear equality constraints. SIAM Journal on Control and Optimization 25(4) (1987) 921–933.

[9] Y. Censor, A.R. de Pierro, T. Elfving, G.T. Herman, and A.N. Iusem: On iterative methods for linearly constrained entropy maximization. In A. Wakulicz, editor, Numerical Analysis and Mathematical Modelling, pages 145–163, Warsaw, 1990. Polish Scientific Publishers. Banach Center Publications Volume 24.

[10] Y. Censor, A.R. de Pierro, and A.N. Iusem: On maximization of entropies and a generalization of Bregman’s method for convex programming. Technical Report MIPG 113, Medical Image Processing Group, Department of Radiology, University of Pennsylvania, Philadelphia, U.S.A., 1986.

[11] Y. Censor, A.R. de Pierro, and A.N. Iusem: Optimization of Burg’s entropy over linear constraints. Applied Numerical Mathematics 7 (1991) 151–165.

[12] Y. Censor and S. Reich: Iterations of paracontractions and firmly nonexpansive operators with applications to feasibility and optimization. Optimization 37(4) (1996) 323–339.

[13] G. Chen and M. Teboulle: Convergence analysis of a proximal-like minimization algorithm using Bregman functions. SIAM Journal on Optimization 3(3) (1993) 538–543.

[14] J. Eckstein: Nonlinear proximal point algorithms using Bregman functions, with applications to convex programming. Mathematics of Operations Research 18(1) (1993) 202–226.

[15] L. Elsner, I. Koltracht, and M. Neumann: Convergence of sequential and asynchronous nonlinear paracontractions. Numerische Mathematik 62 (1992) 305–319.

[16] S.D. Flåm and J. Zowe: Relaxed outer projections, weighted averages and convex feasibility. BIT 30 (1990) 289–300.

[17] J.-B. Hiriart-Urruty and C. Lemaréchal: Convex Analysis and Minimization Algorithms II, volume 306 of Grundlehren der mathematischen Wissenschaften. Springer-Verlag, 1993.

[18] A.N. Iusem, 1994: Personal communication.

[19] A.N. Iusem: Proximal point methods in optimization, May 1994. Unpublished manuscript.

[20] K.C. Kiwiel: conference talk in Ann Arbor, Michigan, August 1994.

[21] K.C. Kiwiel: Free-steering relaxation methods for problems with strictly convex costs and linear constraints. WP-94-89, International Institute for Applied Systems Analysis, Laxenburg, Austria, September 1994. Revised July 1995.

[22] A.S. Lewis: Convex analysis on the Hermitian matrices. SIAM Journal on Optimization 6(1) (1996) 164–177.

[23] A.S. Lewis, 1994: Personal communication.

[24] A.S. Lewis: The convex analysis of unitarily invariant matrix norms. Journal of Convex Analysis 2 (1995) 173–183.

[25] A.S. Lewis: Derivatives of spectral functions. Mathematics of Operations Research 21(3) (1996) 576–588.

[26] A.S. Lewis: Group invariance and convex matrix analysis. SIAM Journal on Matrix Analysis 17(4) (1996) 927–949.

[27] A.W. Marshall and I. Olkin: Inequalities: Theory of Majorization and Its Applications, volume 143 of Mathematics in Science and Engineering. Academic Press, New York, 1979.

[28] G. Pierra: Decomposition through formalization in a product space. Mathematical Programming 28 (1984) 96–115.

[29] A.R. de Pierro and A.N. Iusem: A relaxed version of Bregman’s method for convex programming. Journal of Optimization Theory and Applications 51(3) (1986) 421–440.

[30] R.T. Rockafellar: Convex Analysis. Princeton University Press, Princeton, NJ, 1970.

[31] M. Teboulle: Entropic proximal mappings with applications to nonlinear programming. Mathematics of Operations Research 17(3) (1992) 670–690.

[32] P. Tseng: On the convergence of the products of firmly nonexpansive mappings. SIAM Journal on Optimization 2(3) (1992) 425–434.

68 H. H. Bauschke, J. M. Borwein / Legendre functions HIER :

Leere Seite