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.

Author information

Contact details are reproduced from the original publication and may be historical.

M. V. Solodov

Inst. de Matemática Pura e Aplicada, Estrada Dona Castorina 110, Rio de Janeiro, RJ 22460-320, Brazil

B. F. Svaiter

Inst. de Matemática Pura e Aplicada, Estrada Dona Castorina 110, Rio de Janeiro, RJ 22460-320, Brazil

Keywords

  • Maximal monotone operators
  • proximal point methods
  • projection methods

Mathematics Subject Classification

90C25; 49J45, 49M45

References

  1. J.F. Bonnans, J. C. Gilbert, C. Lemaréchal, C. Sagastizábal: A family of variable metric proximal point methods, Mathematical Programming 68 (1995) 15-47.https://doi.org/10.1007/BF01585756Google Scholar
  2. J. V. Burke, Maijian Qian: The variable metric proximal point algorithm, I: Basic convergence theory, Department of Mathematics, University of Washington, Seattle, WA (1996).Google Scholar
  3. J. V. Burke, Maijian Qian: The variable metric proximal point algorithm, II: Quasi-Newton updating, Department of Mathematics, University of Washington, Seattle, WA (1996).Google Scholar
  4. J. Eckstein, D. P. Bertsekas: On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators, Mathematical Programming 55 (1992) 293-318.https://doi.org/10.1007/BF01581204Google Scholar
  5. M. C. Ferris: Finite termination of the proximal point algorithm, Mathematical Programming 50 (1991) 359-366.https://doi.org/10.1007/BF01594944Google Scholar
  6. B. Lemaire: The proximal algorithm, In: J. P. Penot (ed.), International Series of Numerical Mathematics, Birkhäuser, Basel, 1989, 73-87.Google Scholar
  7. C. Lemaréchal, C. Sagastizábal: An approach to variable metric bundle methods, In: J. Henry, J.-P. Yvon (eds.), Lecture Notes in Control and Information Sciences No. 197, System Modelling and Optimization, Springer-Verlag, Berlin et al., 1994, 144-162.https://doi.org/10.1007/BFb0035464Google Scholar
  8. C. Lemaréchal, C. Sagastizábal: Variable metric bundle methods: From conceptual to implementable forms, Mathematical Programming 76 (1997) 393-410.https://doi.org/10.1007/BF02614390Google Scholar
  9. F. J. Luque: Asymptotic convergence analysis of the proximal point algorithm, SIAM Journal on Control and Optimization 22 (1984) 277-293.https://doi.org/10.1137/0322019Google Scholar
  10. B. Martinet: Regularisation d'inequations variationelles par approximations successives, Revue Française d'Informatique et de Recherche Opérationelle 4 (1970) 154-159.https://doi.org/10.1051/m2an/197004R301541Google Scholar
  11. R. Mifflin: A quasi-second-order proximal bundle algorithm, Mathematical Programming 73 (1996) 51-72.https://doi.org/10.1007/BF02592098Google Scholar
  12. J.-J. Moreau: Proximité et dualité dans un espace Hilbertien, Bulletin de la Société Mathématique de France 93 (1965) 273-299.https://doi.org/10.24033/bsmf.1625Google Scholar
  13. G. B. Passty: Weak convergence theorems for nonexpansive mappings in Banach spaces, Journal of Mathematical Analysis and Applications 67 (1979) 274-276.https://doi.org/10.1016/0022-247X(79)90024-6Google Scholar
  14. B. T. Polyak: Introduction to Optimization, Optimization Software, Inc., Publications Division, New York, 1987.Google Scholar
  15. L. Qi, X. Chen: A preconditioning proximal Newton method for nondifferentiable convex optimization, Technical Report AMR 95/20, Department of Applied Mathematics, University of New South Wales, Sydney, SW, Australia, 1995.Google Scholar
  16. R. T. Rockafellar: Augmented Lagrangians and applications of the proximal point algorithm in convex programming, Mathematics of Operations Research 1 (1976) 97-116.https://doi.org/10.1287/moor.1.2.97Google Scholar
  17. R. T. Rockafellar: Monotone operators and the proximal point algorithm, SIAM Journal on Control and Optimization 14 (1976) 877-898.https://doi.org/10.1137/0314056Google Scholar
  18. M. V. Solodov, B. F. Svaiter: A new projection method for variational inequality problems, SIAM Journal on Control and Optimization, To appear.Google Scholar
  19. M. V. Solodov, B. F. Svaiter: A globally convergent inexact Newton method for systems of monotone equations, In: M. Fukushima, L. Qi (eds.), Reformulation - Nonsmooth, Piecewise Smooth, Semismooth and Smoothing Methods, Kluwer Academic Publishers, 1998, 355-369.https://doi.org/10.1007/978-1-4757-6388-1_18Google Scholar
  20. M. V. Solodov, B. F. Svaiter: An inexact hybrid generalized proximal point algorithm and some new results on the theory of Bregman functions, Mathematics of Operations Research, submitted.Google Scholar
  21. M. V. Solodov, B. F. Svaiter: A truly globally convergent Newton-type method for the monotone nonlinear complementarity problem, SIAM Journal on Optimization, submitted.Google Scholar
  22. P. Tseng: On linear convergence of iterative methods for the variational inequality problem, Journal of Computational and Applied Mathematics 60 (1995) 237-252.https://doi.org/10.1016/0377-0427(94)00094-HGoogle Scholar
  23. C. Zhu: Asymptotic convergence analysis of some inexact proximal point algorithms for minimization, SIAM Journal on Optimization 6 (1996) 626-637.https://doi.org/10.1137/S1052623494255923Google Scholar

Suggested citation

M. V. Solodov, B. F. Svaiter. “A Hybrid Projection-Proximal Point Algorithm.” Journal of Convex Analysis 6 (1999), No. 1, 59–70. https://doi.org/10.68381/jca06005

Download BibTeXPublished by Heldermann Verlag.

Published by Heldermann Verlag, 1999. Rights now held by Banach Press LLC.