Minimization of Bregman’s divergence functions, and its relation to

linear programming

Péter Kas ^{1} -Emil Klafszky ^{2} -Levente Mályusz ^{3} -Gœkhan İzbirak ^{4}

Abstract. Minimization of Bregman’s divergence functions can replace the “least squares” as a measure of distance in the positive orthant. In this paper a general class of divergence functions is defined, and the convex programming problem of the minimization of divergence functions over a set of linear constraints is considered. A perfect duality for the resulting convex programming problem is presented by using the Young inequality, hence we call the programming Young programming. The Young programming is shown to be an analytical approximation of linear programming. A common framework of row-action methods for the solution of Young programming problems is presented, and row-action methods are shown to be gradient type methods in terms of the dual problem.

Keywords: minimization of divergence functions, convex programming, analytical approximation of linear programming, row-action methods

1. Introduction. Let f_{j} : R → R, j = 1, 2, ..., n be strictly concave and differentiable functions, and let F (x) = ∑_{j=1}^{n} f_{j}(x_{j}), x = (x_{1}, x_{2}, ...x_{n}). Then a class of divergence functions can be generated by the following mapping D_{F} : R^{n}xR^{n} → R,

D_{F} (x||y) = F (y) + (y)(x − y) − F (x)
= ∑_{j=1}^{n}(f_{j}(y_{j}) + fj^{′}(y_{j})(x_{j} − y_{j}) − f_{j}(x_{j})), x, y ∈ R^{n}.

D_{F} can serve as a “measure of distance” between x and y ∈ R^{n} with respect to F, although strictly speaking D_{F} is not a distance function for it is not symmetric and the triangle inequality does not hold. Nevertheless the family of functions of the form D_{F}

1Department of Mathematics, Eastern Mediterranean University, G.Magusa,TRNC,Mersin-10,Turkey

2Department for Building Management, Technical University, Muegyetem rkp.3.,Budapest,1111,Hungary

3Department for Building Management, Technical University, Muegyetem rkp.3.,Budapest,1111,Hungary

4Department of Mathematics, Eastern Mediterranean University, G.Magusa,TRNC,Mersin-10,Turkey

(F being not necessarily of a sum form) was introduced by Bregman [1]. He developed an iterative algorithm for minimizing F under linear constraints, whose steps involved projections with respect to the distance defined by D_{F}. A projection with respect to D_{F} onto a convex set is calculated by minimizing D_{F} over all x in the set, for a fixed y whose projection onto the set is sought. Bregman’s divergence functions include e.g. squared Euclidean distance, I-divergence [19], Itakura-Saito distance [15] and Csiszar’s α-divergence [9]. Bregman’s pioneering work followed by Censor and Lent’s study [3] has initiated an extensive research on D_{F} distances and projections. Primal-dual rowaction methods using D_{F} projections are published in [1], [3], [4], [6], [5], [11], [16], proximal minimization algorithms with D_{F} functions are published in [7], [8], [12], [22], an axiomatization of inference rules for linear inverse problems is presented in [10], properties of the dual are investegated in [17], [18].

The purpose of this paper is to contribute the theory of D_{F} projections by formulating a perfect dual of the problem (dual of the dual is the primal), pointing out that there is a natural way to associate a linear programming problem with D_{F} projections, and the optimal solutions of a series of D_{F} projections approaches to an optimal solution of the corresponding linear programming problem. It may be also interesting that the dual problem enables us to give a dual interpretation to row-action methods.

To keep the discussion simple we consider the case f_{1} = f_{2} = ... = f_{n} = f. The discussion of different f_{j}, j = 1, 2, .., n functions follows the same line of thoughts but includes more bookkeeping. It will be convenient for us to define the D_{F} projection problem in a slightly different way, we call it Young programming problem, which is nevertheless equivalent to the D_{F} projection problem. The concept of Young programming is based on the Young inequality. In section 1 we shortly recall the inequality in a form that is convenient to use in the rest of the paper. In section 2 some basic facts of linear programming are restated in a form that is easy to generalize to Young programming. In section 3 the Young programming is introduced and the duality is discussed. In section 4 a parametric form Young programming is shown to be an analytical approximation of the corresponding linear programming problem. Finally in section 5 a row-action method for the solution of Young programming problems is presented. A dual interpretation of the row-action method is shown to be a gradient type method.

1. The Young inequality. The Young inequality was first published by W.H.Young in 1912. A generalized form of the inequality can be found in [14]. We recall the inequality in a form that is convenient to use in the rest of the paper. Let φ : R → R be a continuous, strictly decreasing function, and consider the curve γ_{φ} = {(x, φ(x)) : x ∈ R}. The following definition offers a way to describe how much an arbitrary point (u, v) of the plane is “away” from the curve γ_{φ}. Definition 1. Let (u, v) ∈ R^{2} and denote ψ = φ^{−1}, then

S_{φ}(u, v) = (u − ψ(v))v − ∫_{ψ(v)}^{u} φ(t)dt (= (v − φ(u))u − ∫_{φ(u)}^{v} ψ(t)dt).

is called the inaccurance of (u, v) with respect to γ_{φ}.

Geometrically S_{φ}(u, v) is the area of the shaded region in Figure 1.

[figure: Figure 1.; u; v; φ(u); ψ(v); S_{φ}(u, v)]

The Young inequality states that

S_{φ}(u, v) ≥ 0 for every (u, v) ∈ R^{2}

and equality holds if and only if v = φ(u). The geometric interpretation or a straightforward computation proves the statement. The inaccurance can be termed in R^{2n} as follows.

Definition 2. Let (u, v) ∈ R^{2n}, u = (u_{1}, u_{2}, …, u_{n}) , v = (v_{1}, v_{2}, …, v_{n}), then

S_{φ}(u, v) := ∑_{j=1}^{n} S_{φ}(u_{j}, v_{j})

is called the inaccurance of (u, v) ∈ R^{2n} with respect to γ_{φ}, i.e. the inaccurance is computed coordinatewisely.

Interesting examples of functions of the form S_{φ}(u, v) are displayed by certain divergence functions. Obviously

D_{F} (x||y) = ∑_{j=1}^{n}( f(y_{j}) + f′(y_{j})(x_{j} − y_{j}) − f(x_{j}) )
= ∑_{j=1}^{n}( f′(y_{j})(x_{j} − y_{j}) + ∫_{x_{j}}^{y_{j}} f′(t)dt ), x, y ∈ R^{n}.

Let f : R → R be defined by f′ = φ. It is easy to verify that

S_{φ}(u, φ(v)) = D_{f}(u||v), for all u, v ∈ R,

or alternatively

S_{φ}(u, v) = D_{f}(u||ψ(v)), for all u, v ∈ R.

Some special cases, divergence functions known in the literature, are obtained by choosing

• φ(t) = − ln t − 1, then S_{φ}(u, φ(v)) = u ln \frac{u}{v} − u + v known as I-divergence, introduced by Kullback [19],

• φ(t) = \frac{1}{t}, then S_{φ}(u, φ(v)) = ln \frac{v}{u} − \frac{u}{v} − 1 known as Itakura-Saito divergence [15],

• φ(t) = t^{α−1}, α < 1, α ≠ 0, then S_{φ}(u, φ(v)) = \frac{1}{α}(v^{α} − u^{α} + αv^{α−1}(u − v)) known as Csiszar’s α-divergence [9].

2. Linear Programming. Since the Young programming will be introduced as an analytical approximation of linear programming, it is convenient to recall some basic facts of linear programming. Let A be an m by n matrix and denote a^{(1)}, a^{(2)}, …, a^{(m)} ∈ R^{n} the rows of A. Denote L and L^{⊥} the rowspace of matrix A, and the solution space of Ax = 0, respectively. Let x̂, ẑ ∈ R^{n} be arbitrary but fixed vectors. Let us define the affine subspaces ẑ ⊕ L = {z ∈ R^{n} : z = ẑ + w for some w ∈ L} and x̂ ⊕ L^{⊥} = {x ∈ R^{n} : x = x̂ + w for some w ∈ L^{⊥}}. Then clearly

x ∈ x̂ ⊕ L^{⊥} if and only if Ax = Ax̂,

and z ∈ ẑ ⊕ L if and only if z = ẑ + yA (for some y ∈ R^{m}).

Denote x_{j}, z_{j} the j-th coordinate of x, z, respectively, and consider the following feasibility problem, which is in fact the linear programming problem in an equilibrium form. Problem 1. Let x̂, ẑ ∈ R^{n} be arbitrary but fixed vectors. Find a feasible solution (if any) to the set of constraints below.

x ∈ x̂ ⊕ L^{⊥}, z ∈ ẑ ⊕ L  (0.1)
x ≥ 0, z ≥ 0 (0.2)
x_{j}z_{j} = 0, j = 1, 2, …, n.  (0.3)

The next lemma states some elementary but crucial observations about Problem 1. Lemma 1. Let x̂, ẑ ∈ R^{n} be arbitrary but fixed vectors.

(i) If x and z satisfy (1) , then xẑ + x̂z = xz + x̂ẑ. (ii) If x and z satisfy (1),(2) , then xẑ + x̂z ≥ x̂ẑ. (iii) If x and z satisfy (1),(3) , then xẑ + x̂z = x̂ẑ.

Proof. Elementary computation proves (i), (ii) and (iii) are obvious. □ Let P = {x : x ∈ x̂⊕L^{⊥}, x ≥ 0}, and D = {z : z ∈ ẑ⊕L, z ≥ 0}. The following problem presents three equivalent settings of the linear programming problem. Problem 2. Let x̂, ẑ ∈ R^{n} be arbitrary but fixed vectors.

(i) (Equilibrium form) Find a feasible solution to (1),(2) and (3).

(ii) (Optimization form) Find a feasible solution to (1),(2) such that ∑_{j=1}^{n} x_{j}z_{j} is

minimum. (iii) (Primal-Dual form) Find solutions to both problems below

primal  dual
min{∑_{j=1}^{n} x_{j}ẑ_{j} : x ∈ P} min{∑_{j=1}^{n} x̂_{j}z_{j} : z ∈ D}.

The next theorem restates the wellknown duality theorem of linear programming in three equivalent forms corresponding to problem settings in Problem 2. Theorem 1. (Duality theorem) Let x̂, ẑ ∈ R^{n} be arbitrary but fixed vectors.

(i) If (1),(2) is feasible, then (1),(2),(3) is feasible.

(ii) If (1),(2) is feasible, then there are x^{∗} ∈ P, z^{∗} ∈ D such that ∑_{j=1}^{n} x_{j}^{∗}z_{j}^{∗} = 0. (iii) If P ≠ ∅ and D ≠ ∅, then there are optimal solutions x^{∗} ∈ P and z^{∗} ∈ D to both the primal and the dual problems, respectively, furthermore x^{∗}z^{∗} = 0.

The standard way in the literature is to prove Theorem 1 (iii) directly, then (i) and (ii) are easy corollaries. Finally let us point out that if we drop the assumption that curve γ is defined to be the graph of a function φ in Definition 1, then the term x_{j}z_{j} can be interpreted as the inaccurance of (x_{j}, z_{j}) with respect to γ = {(x, z) : x ≥ 0, z ≥ 0, xz = 0}. In the next section an equilibrium function, φ : R_{+} → R_{+} will be introduced as an analytical approximation of γ.

3. Young Programming. Let φ : R_{+} → R_{+} continuous, strictly decreasing function with lim_{x→0+} φ(x) = ∞, lim_{x→∞} φ(x) = 0. Let γ_{φ} = {(x, φ(x)) : x ∈ R_{+}} and denote ψ = φ^{−1}. According to Definition 1 the inaccurance of (x, z) ∈ R^{2}, x > 0, z > 0 with respect to γ_{φ} is

S_{φ}(x, z) = (x − ψ(z))z − ∫_{ψ(z)}^{x} φ(t)dt.

The basic properties of S_{φ}(x, z) are summarized in the following lemma. Lemma 2. Let φ : R_{+} → R_{+} continuous, strictly decreasing function with lim_{x→0+} φ(x) = ∞, lim_{x→∞} φ(x) = 0. Let ψ = φ^{−1}. Then

(i) S_{φ}(x, z) is strictly convex function in x > 0 and z > 0, respectively.

(ii) S_{φ}(x, z) ≥ 0 for every x > 0, z > 0, and S_{φ}(x, z) = 0 if and only if x = ψ(z). (iii) \frac{∂}{∂x}S_{φ}(x, z) = z − φ(x) for every x > 0, z > 0. (iv) \frac{∂}{∂z}S_{φ}(x, z) = x − ψ(z) for every x > 0, z > 0.

(v) lim_{x→0+} \frac{∂}{∂x}S_{φ}(x, z) = −∞ for every z > 0. (vi) lim_{z→0+} \frac{∂}{∂z}S_{φ}(x, z) = −∞ for every x > 0. (vii) lim_{x→∞} \frac{∂}{∂x}S_{φ}(x, z) = z for every z > 0. (viii) lim_{z→∞} \frac{∂}{∂x}S_{φ}(x, z) = x for every x > 0. (ix) lim_{x→∞} S_{φ}(x, z) = ∞ for every z > 0.

(x) lim_{z→∞} S_{φ}(x, z) = ∞ for every x > 0.

(xi) S_{φ}(x, z) = S_{ψ}(z, x) for every x > 0 and z > 0.

Proof. Elementary computation proves each property. □ The inaccurance of (x, z) ∈ R^{2n}, x > 0, z > 0 with respect to γ_{φ}, as introduced in Definition 2, is computed coordinatewisely, i.e. for every x = (x_{1}, x_{2}, …, x_{n}), x_{j} > 0, j = 1, 2, …, n and z = (z_{1}, z_{2}, …, z_{n}), z_{j} > 0, j = 1, 2, …, n

S_{φ}(x, z) := ∑_{j=1}^{n} S_{φ}(x_{j}, z_{j}).

In the rest of this section the Young programming is presented by a complete analogy to linear programming as is discussed in section 2. Let us consider the following feasibility problem, which is in fact the Young programming problem in an equilibrium form. Problem 3. Let x̂ > 0, ẑ > 0 be arbitrary but fixed vectors. Find a feasible solution to the set of constraints below.

x ∈ x̂ ⊕ L^{⊥}, z ∈ ẑ ⊕ L  (0.4)

x > 0,  z > 0  (0.5)
x_{j} = ψ(z_{j}), j = 1, 2, …, n.  (0.6)

The next lemma states some elementary but crucial observations about Problem 3. Lemma 3. Let x̂ > 0, ẑ > 0 be arbitrary but fixed vectors.

(i) If x and z satisfy (4),(5) , then S_{φ}(x, ẑ) + S_{φ}(x̂, z) = S_{φ}(x, z) + S_{φ}(x̂, ẑ).
(ii) If x and z satisfy (4),(5) , then S_{φ}(x, ẑ) + S_{φ}(x̂, z) ≥ S_{φ}(x̂, ẑ).
(iii) If x and z satisfy (4),(5),(6) , then S_{φ}(x, ẑ) + S_{φ}(x̂, z) = S_{φ}(x̂, ẑ).

Proof. Elementary computation proves (i), (ii) and (iii) are obvious. □ Let P_{+} = {x : x ∈ x̂ ⊕ L^{⊥}, x > 0}, and D_{+} = {z : z ∈ ẑ ⊕ L, z > 0}. The following problem presents three equivalent settings of the Young programming problem. Problem 4. Let x̂ > 0, ẑ > 0 be arbitrary but fixed vectors.

(i) (Equilibrium form) Find a feasible solution to (4),(5) and (6).

(ii) (Optimization form) Find a feasible solution to (4),(5) such that ∑_{j=1}^{n} S_{φ}(x_{j}, z_{j})

is minimum. (iii) (Primal-Dual form) Find solutions to both problems below

primal  dual
min{∑_{j=1}^{n} S_{φ}(x_{j}, ẑ_{j}) : x ∈ P_{+}} min{∑_{j=1}^{n} S_{φ}(x̂_{j}, z_{j}) : z ∈ D_{+}}.

The primal and dual Young programming problems as defined in Problem 4 are symmetrical in the sense that dual of the dual is the primal. For a proof of this statement the reader is referred to [18]. The next theorem presents three equivalent forms of the duality theorem corresponding to problem settings in Problem 4. Theorem 2. (Duality theorem) Let x̂ > 0, ẑ > 0 be arbitrary but fixed vectors.

(i) The system (4),(5),(6) is feasible.

(ii) There are unique x^{∗} ∈ P_{+} and z^{∗} ∈ D_{+} such that ∑_{j=1}^{n} S_{φ}(x_{j}^{∗}, z_{j}^{∗}) = 0.

(iii) There exist x^{∗} ∈ P_{+} and z^{∗} ∈ D_{+} unique optimal solutions to the primal and the dual problems, respectively. Furthermore x_{j}^{∗} = ψ(z_{j}^{∗}), j = 1, 2, …, n.

Instead of referring to proofs of more general statements (duality theorems of convex programming, see e.g. [21]) we prefer to give a short proof of Theorem 2 (iii).

Proof. The proof can be formulated on both the primal and the dual sides. To emphasize the symmetricity we show the proof in both cases. I. Proof on the dual side: Because of Lemma 2 (i),(vi) and (x) the dual objective function attains its unique minimum in D_{+}. Denote z^{∗} the minimum and let x_{j}^{∗} := ψ(z_{j}^{∗}) > 0, j = 1, 2, …, n. Suppose that a^{(i)}x^{∗} ≠ a^{(i)}x̂ for some i. Let z(θ) := z^{∗} + θa^{(i)}. Clearly z(θ) ∈ D_{+} for small enough θ, and

\frac{d}{dθ}S(x̂, z(θ))|_{θ=0} = a^{(i)}x̂ − a^{(i)}x^{∗} ≠ 0

what is in contradiction with the assumption that z^{∗} is dual optimal solution. Therefore x^{∗} is primal optimal solution. II. Proof on the primal side: Because of Lemma 2 (i),(v) and (ix) the primal objective function attains its unique minimum in P_{+}. Denote x^{∗} the minimum and let z_{j}^{∗} := φ(x_{j}^{∗}) > 0, j = 1, 2, …, n. Suppose that z^{∗} − ẑ ≠ yA i.e. z^{∗} − ẑ ∉ L(a^{(1)}, a^{(2}), …, a^{(n)}). Then there exists an x̃ ∈ L^{⊥}(a^{(1)}, a^{(2)}, …, a^{(n)}) such that x̃(z^{∗} − ẑ) ≠ 0. Let x(θ) := x^{∗} + θx̃. Clearly x(θ) ∈ P_{+} for small enough θ, and

\frac{d}{dθ}S(x(θ), ẑ)|_{θ=0} = x̃(ẑ − z^{∗}) ≠ 0

what is in contradiction with the assumption that x^{∗} is primal optimal solution. Therefore z^{∗} is dual optimal solution. This completes the proof of (iii). To show that (i),(ii),(iii) are equivalent statements it is enough to note that S_{φ}(x, z) ≥ 0 for every x > 0, z > 0 and S_{φ}(x, z) = 0 if and only if x_{j} = ψ(z_{j}), j = 1, 2, …, n. □

The next corollary points out that the optimal solutions of the primal and dual problems do not depend on the choice of parameter vectors x̂ ∈ x̂⊕L^{⊥}, x̂ > 0 and ẑ ∈ ẑ⊕L, ẑ > 0. Corollary 1. Let x̂, ẑ be given. There exist unique x^{∗} ∈ x̂ ⊕ L^{⊥}, z^{∗} ∈ ẑ ⊕ L such that x_{j}^{∗} = ψ(z_{j}^{∗}), j = 1, 2, …, n and

S_{φ}(x^{∗}, z) + S_{φ}(x, z^{∗}) = S_{φ}(x, z), ∀x ∈ x̂ ⊕ L^{⊥}, ∀z ∈ ẑ ⊕ L.

Proof. Obvious from Theorem 2. □ Another important implication of the duality theorem is noted in the following corollary. Corollary 2. Let x̂, ẑ be given and denote x^{∗} = argmin{S_{φ}(x, ẑ) : x ∈ x̂ ⊕ L^{⊥}, x > 0} and z^{∗} = argmin{S_{φ}(x̂, z) : z ∈ ẑ ⊕ L, z > 0}. Suppose that L′ ⊆ L and denote z′^{∗} = argmin{S_{φ}(x̂, z) : z ∈ ẑ ⊕ L′, z > 0}. Then

x^{∗} = argmin{S_{φ}(x, z′^{∗}) : x ∈ x̂ ⊕ L^{⊥}, x > 0}.

Proof. Since z′^{∗} ∈ ẑ ⊕ L′ ⊆ ẑ ⊕ L, the statement follows from Corollary 1. □ Observations of Corollary 1 and Corollary 2 give rise to the row-action method proposed in section 5.

4. Approximation of the LP Problems. In this section we introduce a parameter ϵ > 0 in the Young programming problem, and prove that the sequence of optimal solutions of parametric Young programming problems converges to an optimal solution of the corresponding linear programming problem. Definition 3. Let ϵ > 0, φ : R_{+} → R_{+} continuous, strictly decreasing function with lim_{x→0+} φ(x) = ∞, lim_{x→∞} φ(x) = 0. Define φ_{ϵ}(x) := ϵφ(x). Denote ψ_{ϵ} = φ_{ϵ}^{−1}. Clearly ψ_{ϵ}(x) = ψ(\frac{x}{ϵ}), where ψ = φ^{−1}. Let us consider the following parametric version of the Young programming primal-dual pair. Problem 5. Let x̂ > 0, ẑ > 0 be arbitrary but fixed vectors. Find a solution to both problems below

primal  dual
x ∈ x̂ ⊕ L^{⊥}  z ∈ ẑ ⊕ L
x > 0  z > 0
min ∑_{j=1}^{n} S_{φ_{ϵ}}(x_{j}, ẑ_{j}) min ∑_{j=1}^{n} S_{φ_{ϵ}}(x̂_{j}, z_{j}).

For every given ϵ > 0, denote x^{∗}(ϵ), z^{∗}(ϵ) the optimal solutions to Problem 5. The next theorem points out that the sets of optimal solutions {x^{∗}(ϵ) : ϵ < ϵ_{0}}, {z^{∗}(ϵ) : ϵ < ϵ_{0}} are bounded for a small enough ϵ_{0} > 0. Theorem 3. Let ϵ < ϵ_{0} = min_{j} \frac{ẑ_{j}}{φ(x̂_{j})}. Then there exists a K ∈ R_{+} such that x_{j}^{∗}(ϵ) < K and z_{j}^{∗}(ϵ) < K for j = 1, 2, ..., n.

Proof. The optimality of x^{∗}(ϵ) and z^{∗}(ϵ) implies that

∑_{j=1}^{n} S_{φ_{ϵ}}(x_{j}^{∗}(ϵ), ẑ_{j}) + ∑_{j=1}^{n} S_{φ_{ϵ}}(x̂_{j}, z_{j}^{∗}(ϵ)) = ∑_{j=1}^{n} S_{φ_{ϵ}}(x̂_{j}, ẑ_{j})

Let ϵ < ϵ_{0} = min_{j} \frac{ẑ_{j}}{φ(x̂_{j})}. It is clear from the geometric interpretation of S_{φ}(x, z) in Figure 1 that S_{φ_{ϵ}}(x̂_{j}, ẑ_{j}) < x̂_{j}ẑ_{j} for every ϵ < ϵ_{0} and j = 1, 2, ..., n. Since S_{φ_{ϵ}}(x̂_{j}, z_{j}^{∗}(ϵ)) ≥ 0, j = 1, 2, ..., n, we have that

∑_{j=1}^{n} S_{φ_{ϵ}}(x_{j}^{∗}(ϵ), ẑ_{j}) < ∑_{j=1}^{n} x̂_{j}ẑ_{j}

for every ϵ < ϵ_{0}, which implies the boundedness of x_{j}^{∗}(ϵ), j = 1, 2, ..., n for lim_{x→∞} S_{φ_{ϵ}}(x_{j}, ẑ_{j}) = ∞. The proof to show the boundedness of z_{j}^{∗}(ϵ), j = 1, 2, ..., n follows the same line of thoughts. □ Corollary 3. Let x^{∗}(ϵ), z^{∗}(ϵ) be optimal solutions of Problem 4. Then

lim_{ϵ→0} x_{j}^{∗}(ϵ)z_{j}^{∗}(ϵ) = 0 , j = 1, 2, ...n

Proof. If lim_{ϵ→0} z_{j}^{∗}(ϵ) = 0, then due to the boundedness of x_{j}^{∗}(ϵ) the corollary follows. If z_{j}^{∗}(ϵ) ≥ a > 0 for all ϵ < ϵ_{0}, then lim_{ϵ→0} x_{j}^{∗}(ϵ) = lim_{ϵ→0} φ(\frac{z_{j}^{∗}(ϵ)}{ϵ}) = 0 and the corollary follows. □ Putting together the observations of this section we get that lim_{ϵ→0} x^{∗}(ϵ) = x^{∗} and that lim_{ϵ→0} z^{∗}(ϵ) = z^{∗} are optimal solutions of the linear programming primal-dual pair corresponding to Problem 5, i.e.

primal  dual
x ∈ x̂ ⊕ L^{⊥}  z ∈ ẑ ⊕ L
x > 0  z > 0
min ∑_{j=1}^{n} x_{j}ẑ_{j} min ∑_{j=1}^{n} x̂_{j}z_{j}.

5. Algorithms. Row-action type algorithms as defined in [2] are ones that use only the previous iterate in each iterative steps, and access is required to only one row of the system of equations of the constraint set. The following algorithm is a row-action method for the solution of the Young programming problem as is stated in Problem2(iii).

Algorithm 1. (row-action method) Let z^{0} = ẑ and i := k(mod m). For k = 1, 2, ... perform Step k:

x^{k} = argmin{S_{φ}(x, z^{k−1}) : a^{(i)}x = a^{(i)}x̂}
z_{j}^{k} = φ(x_{j}^{k}), j = 1, 2, ..., n.

It may be interesting to point out that in terms of the dual Step k reads as follows Step k:

z^{k} = z^{k−1} + ϑ_{k}a^{(i)}

where

ϑ_{k} = argmin{S_{φ}(x̂, z^{k−1} + ϑa^{(i)}) : ϑ ∈ R}.

That is, in dual terms, Step k is a one-dimensional minimization problem along the row vector a^{(i)}, i = k(mod m) at each step.

Algorithm 1 provides a common framework for row-action methods that are to minimize divergence functions over a set of linear constraints. The convergency of Algorithm 1 was shown by Csiszar [9] if any of the following two assumtions holds

(A1) the set {x : a^{(i)}x = a^{(i)}x̂} is bounded for at least one i, 1 ≤ i ≤ m, (A2) ∫_{0}^{a} φ(t) dt = ∞, for some a > 0.

Typically A1 holds for problems involving discrete random variables, where the sum of the components is 1. A2 holds for example for φ(x) = x^{α−1}, α ≤ 0. The convergency of Algorithm 1 without any further assumption, although it is likely to be true, remains an open question according to the best knowledge of the authors.

Bibliography

[1] 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, USSR Computational Mathematics and Mathematical Physics, 7(1967), pp.200-217.

[2] Y.Censor, Row-action methods for huge and sparse systems and their applications, SIAM Review, 23(1981), pp.444-466.

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

[4] Y.Censor and A.Lent, Optimization of “log x” entropy over linear equality constraints, SIAM J.Control and Optimization, 25(1987), pp.921-933.

[5] Y.Censor, A.R.De Pierro, V.Elfving, G.T.Herman and A.N.Iusem, On iterative methods for linearly constrained entropy maximization,in Numerical Analysis and Mathematic Modelling, Banach Center Publications, Polish Scientific Publisher, Warsaw,1990, Vol.24, pp.145-163.

[6] Y.Censor, A.R.De Pierro and A.N.Iusem, Optimization of Burg’s entropy over linear constraints, Applied Numerical Mathematics, 7(1991), pp.151-165.

[7] Y.Censor and A.Zenios, Proximal minimization algorithm with D-functions, Journal of Optimization Theory and Applications, 73(1992), pp.451-464.

[8] G.Chen and M.Teboulle, Convergence analysis of a proximal-like optimization algorithm using Bregman functions, SIAM Journal on Optimization, 3(1993), pp.538-543.

[9] I.Csiszar, I-divergence geometry of probability distributions and minimization problems, Annals of Probability, 3(1975), pp.146-156.

[10] I.Csiszar, Why least squares and maximum entropy? An axiomatic approach to inference for linear inverse problems, Annals of Statistics, 19(1991), pp.2032-2066.

[11] 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(1986), pp.421-440.

[12] P.P.B.Eggermont, Multiplicative iterative algorithms for convex programming, Linear Algebra and its Applications, 130(1990), pp.25-42.

[13] G.B.Dantzig, Linear Programming and Extensions, Princeton University Press, Princeton, NJ, 1963.

[14] J.B.Hiriart-Urruty and C.Lemarechal, Convex analysis and minimization algorithms I., Spriger Verlag, 1993.

[15] F.Itakura and S.Saito, Analysis synthesis telephony based on the maximum likelihood method, Reports of the Sixth International Congress on Acoustics (Ed.Y.Kohasi), Tokyo, Japan, 1968, pp.17-20.

[16] A.N.Iusem, On dual convergence and the rate of primal convergence of Bregman’s convex programming method, SIAM Journal on Optimization, 1(1991), pp.401-423.

[17] P.Kas and E.Klafszky, On the duality of the mixed entropy programming, Optimization, 27(1993), pp.253-258.

[18] P.Kas and E.Klafszky, On the dual of linear inverse problems, European Journal of Operational Resesarch, 91(1996), pp.634-639.

[19] S.Kullback, Information Theory and Statistics, John Wiley and Sons, 1977.

[20] A.Lent and Y.Censor, Extentions of Hildreth’s row-action method for quadratic programming, SIAM J.Control and Optimization, 18(1980), pp.444-454.

[21] R.T.Rockafeller, Convex Analysis, Princeton University Press, Princeton, NJ, 1970.

[22] M.Teboulle, Entropic proximal mappings with applications to nonlinear programming, Mathematics of Operations Research, 17(1992), pp.670-690.