A variable metric proximal point algorithm for monotone operators

The proximal point algorithm (PPA) is a method for solving inclusions of th e form 0 is an element of 2 T(z), where T is a monotone operator on a Hilbe rt space. The algorithm is one of the most powerful and versatile solution techniques for solving variational inequalities, convex programs, and conve x-concave mini-max problems. It possesses a robust convergence theory for v ery general problem classes and is the basis for a wide variety of decompos ition methods called splitting methods. Yet the classical PPA typically exh ibits slow convergence in many applications. For this reason, acceleration methods for the PPA algorithm are of great practical importance. In this pa per we propose a variable metric implementation of the proximal point algor ithm. In essence, the method is a Newton-like scheme applied to the Moreau- Yosida resolvent of the operator T. In this article, we establish the globa l and linear convergence of the proposed method. In addition, we characteri ze the superlinear convergence of the method. In a companion work, we estab lish the superlinear convergence of the method when implemented with Broyde n updating (the nonsymmetric case) and BFGS updating (the symmetric case).