Journal of Convex Analysis, Vol. 6, No. 1, pp. 59-70 (1999)

A Hybrid Projection-Proximal Point Algorithm

M. V. Solodov and B. F. Svaiter

Instituto de Matematica Pura e Aplicada, Estrada Dona Castorina 110, Jardim Botanico, Rio de Janeiro, RJ 22460-320, Brazil, \{solodov,benar\}

Abstract: We propose a modification of the classical proximal point algorithm for finding zeroes of a maximal monotone operator in a Hilbert space. In particular, an approximate proximal point iteration is used to construct a hyperplane which strictly separates the current iterate from the solution set of the problem. This step is then followed by a projection of the current iterate onto the separating hyperplane. All information required for this projection operation is readily available at the end of the approximate proximal step, and therefore this projection entails no additional computational cost. The new algorithm allows significant relaxation of tolerance requirements imposed on the solution of proximal point subproblems, which yields a more practical framework. Weak global convergence and local linear rate of convergence are established under suitable assumptions. Additionally, presented analysis yields an alternative proof of convergence for the exact proximal point method, which allows a nice geometric interpretation, and is somewhat more intuitive than the classical proof.

Keywords: Maximal monotone operators, proximal point methods, projection methods

Classification (MSC2000): 90C25, 49J45, 49M45

Full text of the article:

[Previous Article] [Next Article] [Contents of this Number]
© 1999--2000 ELibM for the EMIS Electronic Edition