View source for Proximal point methods in mathematical programming

<!--
p1102501.png
$#A+1 = 79 n = 0
$#C+1 = 79 : ~/encyclopedia/old_files/data/P110/P.1100250 Proximal point methods in mathematical programming
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}}

The proximal point method for finding a zero of a maximal monotone [[Operator|operator]]  $  T : {\mathbf R  ^ {n} } \rightarrow { {\mathcal P} ( \mathbf R  ^ {n} ) } $
generates a sequence  $  \{ x  ^ {k} \} $, 
starting with any  $  x  ^ {0} \in \mathbf R  ^ {n} $, 
whose iteration formula is given by

$$ \tag{a1 }
0 \in T _ {k} ( x ^ {k + 1 } ) ,
$$

where  $  T _ {k} ( x ) = T ( x ) + \lambda _ {k} ( x - x  ^ {k} ) $
and  $  \{ \lambda _ {k} \} $
is a bounded sequence of positive real numbers. The origin of the method can be traced back to the study of regularization of ill-posed problems (see [[#References|[a3]]]; [[Regularization method|Regularization method]]; [[Ill-posed problems|Ill-posed problems]]) and is closely related to Moreau–Yoshida convolution (see [[#References|[a5]]]). A survey on the method can be found in [[#References|[a4]]]. The basic properties of the method, as established in [[#References|[a7]]], are as follows.

i) The sequence  $  \{ x  ^ {k} \} $
is well defined (in the sense that  $  T _ {k} $
has a unique zero), converges to a zero of  $  T $
if such a zero exists, and is unbounded otherwise.

ii) If  $  T $
is strongly monotone, then the convergence rate of  $  \{ x  ^ {k} \} $
is linear, and super-linear when  $  {\lim\limits } _ {k \rightarrow \infty }  \lambda _ {k} = 0 $. 
When  $  T $
is the [[Subdifferential|subdifferential]] of a convex polyhedral function  $  f $ (i.e. the [[epigraph]] of  $  f $
is a polyhedron), then convergence is finite.

iii) Convergence properties are preserved under inexact computation of the zero of  $  T _ {k} $, 
in the following sense: (a1) is replaced by  $  \| {x ^ {k + 1 } - {\widetilde{x}  }  ^ {k} } \| \leq  \varepsilon _ {k} $, 
where  $  0 \in T _ {k} ( {\widetilde{x}  }  ^ {k} ) $
and  $  \sum _ {k = 0 }   ^  \infty  \varepsilon _ {k} < \infty $.

When  $  T = \partial  f $ (the subdifferential of a convex function  $  f $), 
then (a1) is equivalent to

$$ \tag{a2 }
x ^ {k + 1 } = { \mathop{\rm argmin} } \left \{ f ( x ) + {
\frac{\lambda _ {k} }{2}
 } \left \| {x - x  ^ {k} } \right \|  ^ {2} \right \}
$$

and the zeros of  $  T $
are the minimizers of  $  f $, 
so that  $  \{ x  ^ {k} \} $
converges to a minimizer of  $  f $. 
If  $  T $
is the subdifferential of the dual objective of a convex optimization problem, then the sequence  $  \{ x  ^ {k} \} $
coincides with the dual sequence generated by the augmented Lagrangian method (see [[#References|[a6]]]).

All these properties hold also for maximal monotone operators in a [[Hilbert space|Hilbert space]], in which case convergence is understood in the sense of the [[Weak topology|weak topology]].

The proximal point method can be applied to problems with convex constraints, e.g. the variational inequality problem  $  { \mathop{\rm VI} } ( T,C ) $, 
for a closed and convex set  $  C \subset  \mathbf R  ^ {n} $, 
which consists of finding a  $  z \in C $
such that there exists an  $  u \in T ( z ) $
satisfying  $  \langle  {u,x - z } \rangle \geq  0 $
for all  $  x \in C $. 
When  $  T = \partial  f $
with convex  $  f $, 
$  { \mathop{\rm VI} } ( T,C ) $
reduces to minimizing  $  f ( x ) $
subject to  $  x \in C $. 
For applying the proximal point method to  $  { \mathop{\rm VI} } ( T,C ) $
it suffices to replace  $  T $
by  $  T + N _ {C} $, 
where  $  N _ {C} $
is the normal cone operator of  $  C $. 
In such a case, (a1) becomes equivalent to stating that  $  x ^ {k + 1 } $
solves  $  { \mathop{\rm VI} } ( T,C ) $
and (a2) becomes

$$ 
x ^ {k + 1 } = { \mathop{\rm argmin} } \left \{ {f ( x ) + {
\frac{\lambda _ {k} }{2}
 } \left \| {x - x  ^ {k} } \right \|  ^ {2} } : {x \in C } \right \} .
$$

There is another way to deal with constrained problems in the context of the proximal point method, without introducing the normal cone of  $  C $, 
for the case when  $  C $
has non-empty interior and when a boundary-coercive [[Bregman function|Bregman function]]  $  g $
with zone  $  C $
is available. In this case the method starts with  $  x  ^ {0} \in C  ^ {o} $ (the interior of  $  C $) 
and the iterative formula is still (a1) but now  $  T _ {k} ( x ) = T ( x ) + \lambda _ {k} ( \nabla g ( x ) - \nabla g ( x  ^ {k} ) ) $. 
In the optimization case, i.e.  $  T = \partial  f $, 
this formula is equivalent to

$$ 
x ^ {k + 1 } = { \mathop{\rm argmin} } \{ f ( x ) + \lambda _ {k} D _ {g} ( x,x  ^ {k} ) \}
$$

where  $  D _ {g} $
is the [[Bregman distance|Bregman distance]] associated with  $  g $. 
This generalization of the proximal point method is an interior point algorithm, in the sense that the sequence  $  \{ x  ^ {k} \} $
lies in the interior of  $  C $ (cf. also [[Interior-point methods in mathematical programming|Interior-point methods in mathematical programming]]). Under certain technical hypotheses on  $  T $, 
satisfied, e.g., when  $  T = \partial  f $, 
property i) above still holds, i.e. the sequence  $  \{ x  ^ {k} \} $
converges to a solution of  $  { \mathop{\rm VI} } ( T,C ) $
when a solution exists and is unbounded otherwise, [[#References|[a8]]]. A property of this generalization, not shared by the original proximal point method (a1), is that for certain problems, including [[Linear programming|linear programming]] and [[Quadratic programming|quadratic programming]], the limit of the sequence  $  \{ x  ^ {k} \} $
is the solution of the problem which minimizes the Bregman distance to the initial iterate  $  x  ^ {0} $ (see [[#References|[a2]]], [[#References|[a10]]]). This procedure also generates augmented Lagrangian-type methods when  $  T $
is the subdifferential of the dual objective of a convex optimization problem. For instance, when  $  C $
is the non-negative orthant of  $  \mathbf R  ^ {n} $
and  $  g ( x ) = \sum _ {j = 1 }   ^ {n} x _ {j} { \mathop{\rm log} } x _ {j} $, 
the sequence  $  \{ x  ^ {k} \} $
coincides with the dual sequence of the Bertsekas exponential multipliers method (see [[#References|[a1]]], [[#References|[a11]]]).

Finally, some results are available for the proximal point method with Bregman distances under inexact solutions of the subproblems, in the spirit of property iii) above, [[#References|[a9]]]. Convergence is guaranteed for the sequence generated by  $  0 \in {\widehat{T}  } _ {k} ( x ^ {k + 1 } ) $, 
with  $  {\widehat{T}  } _ {k} ( x ) = T ^ {\varepsilon _ {k} } ( x ) + \lambda _ {k} ( \nabla g ( x ) - \nabla g ( x  ^ {k} ) ) $, 
where  $  \sum _ {k = 0 }   ^  \infty  \varepsilon _ {k} < \infty $
and, for any monotone operator  $  T $
and any  $  \varepsilon \geq  0 $, 
$  T  ^  \varepsilon  $
is defined as

$$ 
T  ^  \varepsilon  ( x ) = \{ {u \in \mathbf R  ^ {n} } : 
$$

$$ 
 \ 
{} {\left \langle  {u - v,x - y } \right \rangle \geq  - \varepsilon  \textrm{ for  all  }  y \in \mathbf R  ^ {n} , v \in T ( y ) } \} .
$$

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  D. Bertsekas,   "Constrained optimization and Lagrange multipliers" , Acad. Press  (1982)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  A.N. Iusem,   "On some properties of generalized proximal point methods for quadratic and linear programming"  ''J. Optimization Th. Appl.'' , '''85'''  (1995)  pp. 593–612</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  M.A. Krasnoselskii,   "Two observations about the method of successive approximations"  ''Uspekhi Mat. Nauk'' , '''10'''  (1955)  pp. 123–127  (In Russian)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  B. Lemaire,   "The proximal algorithm"  J.P. Penot (ed.) , ''Internat. Ser. Numer. Math.'' , '''87''' , Birkhäuser  (1989)  pp. 73–87</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  J. Moreau,   "Proximité et dualité dans un espace hilbertien"  ''Bull. Soc. Math. France'' , '''93'''  (1965)  pp. 273–299</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  R.T. Rockafellar,   "Augmented Lagrangians and applications of the proximal point algorithm in convex programming"  ''Math. of Oper. Res.'' , '''1'''  (1976)  pp. 97–116</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  R.T. Rockafellar,   "Monotone operators and the proximal point algorithm"  ''SIAM J. Control Optim.'' , '''14'''  (1976)  pp. 877–898</TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top">  R.S. Burachik,   A.N. Iusem,   "A generalized proximal point algorithm for the variational inequality in a Hilbert space"  ''SIAM J. Optim.''  (to appear)</TD></TR><TR><TD valign="top">[a9]</TD> <TD valign="top">  R.S. Burachik,   A.N. Iusem,   B.F. Svaiter,   "Enlargement of monotone operators with applications to variational inequalities"  ''Set Valued Anal.''  (to appear)</TD></TR><TR><TD valign="top">[a10]</TD> <TD valign="top">  A.N. Iusem,   "On some properties of generalized proximal point methods for variational inequalities"  ''J. Optim. Th. &amp; Appl.''  (to appear)</TD></TR><TR><TD valign="top">[a11]</TD> <TD valign="top">  A.N. Iusem,   B.F. Svaiter,   M. Teboulle,   "Entropy-like proximal methods in convex programming"  ''Math. of Oper. Res.'' , '''19'''  (1994)  pp. 790–814</TD></TR></table>