Variable Metric Implementations of the Proximal Point Algorithm
J. V. Burke
ABSTRACT. The Proximal Point Algorithm (PPA) is a
method for solving inclusions of the form
0 lies in T(z) ,
where T is a monotone operator on a Hilbert
space. The algorithm is one of the most powerful and versatile solution
techniques for solving variational inequalities, convex programs, and
convex-concave mini-max programs. In the context of convex
programming, where the problem is to minimize a convex function
f, the operator T is the convex subdifferential of
f. In this case, the PPA can be viewed as an implementation of
the method of steepest descent applied to the Moreau-Yosida
regularization of f:
fr(x)
=min{f(z)
+ (2r)-1 |z-x|2} .
Motivated by this
interpretation, we consider a variable metric implementation of the
method and study conditions under which such an implementation
accelerates convergence. In this talk, we describe both the global and
local convergence properties of the variable metric proximal point
algorithm and provide conditions under which some standard matrix secant
updating strategies yield the local super-linear convergence of the
method.