Abstract

Given an approximation {fn} of a given objective function f, we provide simple and fairly general conditions under which a diagonal proximal point algorithm approximates the value inf f at a reasonable rate. We also perform some numerical tests and present a short survey on finite convergence

Author information

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

Juan Peypouquet

Departamento de Matemática, Universidad Técnica Federico Santa María, Avenida España 1680, Valparaíso, Chile

juan.peypouquet@usm.cl

References

  1. P. Alart, B. Lemaire: Penalization in non-classical convex programming via variational convergence, Math. Program., Ser. A 51 (1991) 307–331.https://doi.org/10.1007/BF01586942Google Scholar
  2. F. Alvarez, R. Cominetti: Primal and dual convergence of a proximal point exponential penalty method for linear programming, Math. Program. 93 (2002) 87–96.https://doi.org/10.1007/s10107-002-0295-0Google Scholar
  3. H. Attouch, R. Cominetti: A dynamical approach to convex minimization coupling approximation with the steepest descent method, J. Differ. Equations 128 (1996) 519–540.https://doi.org/10.1006/jdeq.1996.0104Google Scholar
  4. A. Auslender: Numerical methods for nondifferentiable convex optimization, Math. Program. Study 30 (1987) 102–127.https://doi.org/10.1007/BFb0121157Google Scholar
  5. A. Auslender, J.-P. Crouzeix, P. Fedit: Penalty-proximal methods in convex programming, J. Optimization Theory Appl. 55 (1987) 1–21.https://doi.org/10.1007/BF00939042Google Scholar
  6. M. A. Bahraoui, B. Lemaire: Diagonal bundle methods for convex minimization, unpublished.Google Scholar
  7. H. Brézis, P.-L. Lions: Produits infinis de résolvantes, Israel J. Math. 29 (1978) 329–345.https://doi.org/10.1007/BF02761171Google Scholar
  8. R. Cominetti: Coupling the proximal point algorithm with approximation methods, J. Optimization Theory Appl. 95 (1997) 581–600.https://doi.org/10.1023/A:1022621905645Google Scholar
  9. R. Cominetti, M. Courdurier: Coupling general penalty schemes for convex programming with the steepest descent and the proximal point algorithm, SIAM J. Optim. 13 (2002) 745–765.https://doi.org/10.1137/S1052623401397242Google Scholar
  10. M. G. Crandall, T. M. Liggett: Generation of semi-groups of nonlinear transformations on general Banach spaces, Amer. J. Math. 93 (1971) 265–298.https://doi.org/10.2307/2373376Google Scholar
  11. M. Ferris: Finite termination of the proximal point algorithm, Math. Program., Ser. A 50 (1991) 359–366.https://doi.org/10.1007/BF01594944Google Scholar
  12. E. G. Gol’shtein: A method for the modification of monotone mappings, Ehkon. Mat. Metody 11 (1975) 1144–1159.Google Scholar
  13. O. Güler: On the convergence of the proximal point algorithm for convex minimization, SIAM J. Control Optimization 29 (1991) 403–419.https://doi.org/10.1137/0329022Google Scholar
  14. O. Güler: New proximal point algorithms for convex minimization, SIAM J. Optim. 2 (1992) 649–664.https://doi.org/10.1137/0802032Google Scholar
  15. O. Güler: Convergence rate estimates for the gradient differential inclusion, Optim. Methods Softw. 20 (2005) 729–735.https://doi.org/10.1080/10556780500094770Google Scholar
  16. A. Kaplan: On a convex programming method with internal regularization, Sov. Math., Dokl. 19 (1978) 795–799.Google Scholar
  17. A. Kaplan, R. Tichatschke: Proximal methods in view of interior-point strategies, J. Optimization Theory Appl. 98 (1998) 399–429.https://doi.org/10.1023/A:1022693618829Google Scholar
  18. K. Knopp: Theory and Application of Infinite Series, Blackie & Son, London (1951).Google Scholar
  19. Y. Kobayashi: Difference approximation of Cauchy problems for quasi-dissipative operators and generation of nonlinear semigroups, J. Math. Soc. Japan 27 (1975) 640–665.https://doi.org/10.2969/jmsj/02740640Google Scholar
  20. B. Lemaire: About the convergence of the proximal method, Advances in Optimization (Lambrecht, 1991), W. Oettli et al. (ed.), Lect. Notes Econ. Math. Syst. 382, Springer, Berlin (1992) 39–51.https://doi.org/10.1007/978-3-642-51682-5_4Google Scholar
  21. B. Martinet: Régularisation d’inéquations variationnelles par approximations successives, Rev. Franç. Inform. Rech. Opér., Sér R-3 4 (1970) 154–158.https://doi.org/10.1051/m2an/197004R301541Google Scholar
  22. A. Moudafi: Coupling proximal algorithm and Tikhonov method, Nonlinear Times Dig. 1 (1994) 203–210.Google Scholar
  23. R.T. Rockafellar: Augmented lagrangians and applications of the proximal point algorithm in convex programming, Math. Oper. Res. 1 (1976) 97–116.https://doi.org/10.1287/moor.1.2.97Google Scholar
  24. R. T. Rockafellar: Monotone operators and the proximal point algorithm, SIAM J. Control Optimization 14 (1976) 877–898.https://doi.org/10.1137/0314056Google Scholar
  25. M. Solodov, B. Svaiter: A hybrid projection-proximal point algorithm, J. Convex Analysis 6 (1999) 59–70.https://doi.org/10.68381/jca06005Google Scholar

Suggested citation

J. Peypouquet. “Asymptotic Convergence to the Optimal Value of Diagonal Proximal Iterations in Convex Minimization.” Journal of Convex Analysis 16 (2009), No. 1, 277–286. https://doi.org/10.68381/jca16015

Download BibTeXPublished by Heldermann Verlag.

Published by Heldermann Verlag, 2009. Rights now held by Banach Press.