Bregman distance

Given a convex closed set $ C \subset \mathbf R ^ {n} $ with non-empty interior $ C ^ {o} $ and a Bregman function $ f $ with zone $ C $, the Bregman distance $ {D _ {f} } : {C \times C ^ {o} } \rightarrow \mathbf R $ is defined as:

$$ D _ {f} ( x,y ) = f ( x ) - f ( y ) - \left \langle {\nabla f ( y ) ,x - y } \right \rangle . $$

Bregman distances were introduced in [a1]. For several examples of Bregman distances for relevant sets $ C $, see Bregman function. It follows easily from the properties of Bregman functions that $ D _ {f} ( x,y ) \geq 0 $ for all $ x \in C $ and all $ y \in C ^ {o} $, that $ D _ {f} ( x,y ) = 0 $ if and only if $ x = y $ and that $ D _ {f} ( \cdot,y ) $ is a convex function (cf. also convex function (of a real variable)) for all $ y \in C ^ {o} $. In general, $ D _ {f} $ does not satisfy the triangle inequality, it is not symmetric (i.e. it is not true that $ D _ {f} ( x,y ) = D _ {f} ( y,x ) $ for all $ x $, $ y $) and $ D _ {f} ( x, \cdot ) $ is not convex. If $ C = \mathbf R ^ {n} $ and either $ D _ {f} $ is symmetric or $ D _ {f} ( x, \cdot ) $ is convex for all $ x \in C $, then $ f $ is a quadratic function and $ D _ {f} $ is the square of an elliptic norm. A basic property of Bregman distances, which follows easily from the definition, is the following:

$$ D _ {f} ( x,y ) + D _ {f} ( y,z ) - D _ {f} ( x,z ) = $$

$$ = \left \langle {\nabla f ( z ) - \nabla f ( y ) ,x - y } \right \rangle $$

for all $ x \in C $, and all $ y,z \in C ^ {o} $. Given a closed convex set $ L \subset \mathbf R ^ {n} $ such that $ L \cap C \neq \emptyset $, the Bregman projection onto $ L $, $ {P _ {L} ^ {f} } : {C ^ {o} } \rightarrow L $, is defined as

$$ P _ {L} ^ {f} ( z ) = { \mathop{\rm argmin} } \left \{ {D _ {f} ( x,z ) } : {x \in L \cap C } \right \} . $$

The properties of Bregman distances ensure existence and uniqueness of $ P _ {L} ^ {f} ( z ) $ for all $ z \in C ^ {o} $. Given closed convex sets $ L _ {1} \dots L _ {m} $ such that $ P _ {L _ {i} } ^ {f} ( z ) \in C ^ {o} $ for all $ z \in C ^ {o} $ and all $ i $( such sets are said to be zones consistent with $ f $), it is interesting to consider a sequence of successive Bregman projections onto the convex sets $ L _ {i} $, i.e. the sequence $ \{ x ^ {k} \} $ with $ x ^ {0} \in C ^ {o} $ and iterative formula given by

$$ x ^ {k + 1 } = P _ {L _ {i ( k ) } } ^ {f} ( x ^ {k} ) , $$

where $ i ( k ) $ is the index of the convex set used in the $ k $ th iteration (for instance cyclically, i.e. $ i ( k ) = k { \mathop{\rm mod} } m $). This algorithm, called Bregman's method, converges to a point in $ L = \cap _ {i = 1 } ^ {m} L _ {i} $ if $ L $ is non-empty (see [a1]). It has been proved in [a1] that if all the sets $ L _ {i} $ are hyperplanes, then the limit of the sequence $ \{ x ^ {k} \} $ is also the unique solution of $ { \mathop{\rm min} } f $, subject to $ x \in \cap _ {i = 1 } ^ {m} L _ {i} $. This property also holds for an underrelaxed version of the method, of the type

$$ x ^ {k + 1 } = P _ {H _ {k} } ^ {f} ( k ) , $$

where $ H _ {k} $ is a hyperplane parallel to $ L _ {i ( k ) } $ and lying between $ x ^ {k} $ and $ L _ {i ( k ) } $( see [a3]). Under suitable modifications in the definition of the hyperplane $ H _ {k} $, the method has been extended to the case of minimization of $ f $ subject to linear inequalities and linear interval constraints (see [a2], [a5]). The entropy maximization method known as MART (multiplicative algebraic reconstruction technique, see [a4]) is a particular case of Bregman's method with $ C = \mathbf R _ {+} ^ {n} $( the non-negative orthant of $ \mathbf R ^ {n} $) and $ f ( x ) = \sum _ {j = 1 } ^ {n} x _ {j} { \mathop{\rm log} } x _ {j} $, under a specific underrelaxation strategy.

Bregman distances have also been used to generate generalized proximal point methods for convex optimization and variational inequalities (cf. Proximal point methods in mathematical programming).

References

[a1]	L.M. Bregman, "The relaxation method of finding the common points of convex sets and its application to the solution of problems in convex programming" USSR Comput. Math. Math. Phys. , 7 : 3 (1967) pp. 200–217 (In Russian)
[a2]	Y. Censor, A. Lent, "An iterative row-action method for interval convex programming" J. Optimization Th. Appl. , 34 (1981) pp. 321–353
[a3]	A.R. de Pierro, A.N. Iusem, "A relaxed version of Bregman's method for convex programming" J. Optimization Th. Appl. , 51 (1986) pp. 421–440
[a4]	R. Gordon, R. Bender, G.T. Herman, "Algebraic reconstruction techniques (art) for three dimensional electron microscopy and x-ray photography" J. Theor. Biology , 29 (1970) pp. 471–481
[a5]	A.N. Iusem, S.A. Zenios, "Interval underrelaxed Bregman method with an application" Optimization , 35 (1995) pp. 227–250