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