View source for Bregman distance

<!--
b1108801.png
$#A+1 = 64 n = 0
$#C+1 = 64 : ~/encyclopedia/old_files/data/B110/B.1100880 Bregman distance
Automatically converted into TeX, above some diagnostics.
Please remove this comment and the {{TEX|auto}} line below,
if TeX found to be correct.
-->

{{TEX|auto}}
{{TEX|done}}

Given a convex closed set  $  C \subset  \mathbf R  ^ {n} $
with non-empty interior  $  C  ^ {o} $
and a [[Bregman function|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 [[#References|[a1]]]. For several examples of Bregman distances for relevant sets  $  C $, 
see [[Bregman function|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)|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 [[#References|[a1]]]). It has been proved in [[#References|[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 [[#References|[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 [[#References|[a2]]], [[#References|[a5]]]). The entropy maximization method known as MART (multiplicative algebraic reconstruction technique, see [[#References|[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|Proximal point methods in mathematical programming]]).

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  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)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  Y. Censor,   A. Lent,   "An iterative row-action method for interval convex programming"  ''J. Optimization Th. Appl.'' , '''34'''  (1981)  pp. 321–353</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  A.N. Iusem,   S.A. Zenios,   "Interval underrelaxed Bregman method with an application"  ''Optimization'' , '''35'''  (1995)  pp. 227–250</TD></TR></table>