A UNIFIED FRAMEWORK FOR SOME INEXACT PROXIMAL POINT ALGORITHMS^*

Abstract

We present a unified framework for the design and convergence analysis of a class of algorithms based on approximate solution of proximal point subproblems. Our development further enhances the constructive approximation approach of the recently proposed hybrid projection–proximal and extragradient–proximal methods. Specifically, we introduce an even more flexible error tolerance criterion, as well as provide a unified view of these two algorithms. Our general method possesses global convergence and local (super)linear rate of convergence under standard assumptions, while using a constructive approximation criterion suitable for a number of specific implementations. For example, we show that close to a regular solution of a monotone system of semismooth equations, two Newton iterations are sufficient to solve the proximal subproblem within the required error tolerance. Such systems of equations arise naturally when reformulating the nonlinear complementarity problem.

^*Research of the first author is supported by CNPq Grant 300734/95-6, by PRONEX-Optimization, and by FAPERJ, research of the second author is supported by CNPq Grant 301200/93-9(RN), by PRONEX-Optimization, and by FAPERJ.

Keywords:

• Maximal monotone operator
• Proximal point algorithm
• Approximation criteria
• AMS Subject Classifications: 90C30; 90C30

Acknowledgments

Notes

^*Research of the first author is supported by CNPq Grant 300734/95-6, by PRONEX-Optimization, and by FAPERJ, research of the second author is supported by CNPq Grant 301200/93-9(RN), by PRONEX-Optimization, and by FAPERJ.