Skip to main content
SpringerLink
Log in

Coupling the Proximal Point Algorithm with Approximation Methods

  • Published:
Journal of Optimization Theory and Applications Aims and scope Submit manuscript

Abstract

We study the convergence of a diagonal process for minimizing a closed proper convex function f, in which a proximal point iteration is applied to a sequence of functions approximating f. We prove that, when the approximation is sufficiently fast, and also when it is sufficiently slow, the sequence generated by the method converges toward a minimizer of f. Comparison to previous work is provided through examples in penalty methods for linear programming and Tikhonov regularization.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. MOREAU, J. J., Proximité et Dualité dans un Espace Hilbertien, Bulletin de la Societé Mathématique de France, Vol. 93, pp. 273–299, 1965.

    Google Scholar 

  2. MARTINET, B., Algorithmes pour la Résolution de Problémes d'Optimisation et de Minimax, Thesis, Universitè de Grenoble, 1972.

  3. MARTINET, B., Régularisation d'Inéquations Variationnelles par Approximations Successives, Revue Française d'Informatique et Recherche Opérationnelle, Vol. 4, pp. 154–159, 1970.

    Google Scholar 

  4. ROCKAFELLAR, R. T., Monotone Operators and the Proximal Point Algorithm, SIAM Journal on Control and Optimization, Vol. 14, pp. 877–898, 1976.

    Google Scholar 

  5. BRÉZIS, H., and LIONS, P. L., Produits Infinis de Résolvantes, Israel Journal of Mathematics, Vol. 29, pp. 329–345, 1978.

    Google Scholar 

  6. AUSLENDER, A., Numerical Methods for Nondifferentiable Convex Optimization, Mathematical Programming Studies, Vol. 30, pp. 102–127, 1987.

    Google Scholar 

  7. LEMAIRE, B., About the Convergence of the Proximal Method, Advances in Optimization, Lecture Notes in Economics and Mathematical Systems, Springer Verlag, Berlin, Germany, Vol. 382, pp. 39–51, 1992.

    Google Scholar 

  8. CORREA, R., and LEMARECHAL, C., Convergence of Some Algorithms for Convex Minimization, Mathematical Programming, Vol. 62, pp. 261–275, 1993.

    Google Scholar 

  9. GÜLER, O., On the Convergence of the Proximal Point Algorithm for Convex Minimization, SIAM Journal on Control and Optimization, Vol. 29, 403–419, 1991.

    Google Scholar 

  10. BAHRAOUI, M. A., Suites Diagonalement Stationnaires en Optimisation Convexe, Thesis, Université de Montpellier II, 1994.

  11. ALART, P., and LEMAIRE, B., Penalization in Nonclassical Convex Programming via Variational Convergence, Mathematical Programming, Vol. 51, pp. 307–331, 1991.

    Google Scholar 

  12. AUSLENDER, A., CROUZEIX, J. P., and FEDIT, P., Penalty Proximal Methods in Convex Programming, Journal of Optimization Theory and Applications, Vol. 55, pp. 1–21, 1988.

    Google Scholar 

  13. KAPLAN, A., On a Convex Programming Method with Internal Regularization, Soviet Mathematics Doklady, Vol. 19, pp. 795–799, 1978.

    Google Scholar 

  14. LEMAIRE, B., On the Convergence of Some Iterative Methods for Convex Minimization, Recent Developments in Optimization, Edited by R. Durier and C. Michelot, Lecture Notes in Economics and Mathematical Systems, Springer-Verlag, Berlin, Germany, Vol. 429, pp. 252–268, 1995.

    Google Scholar 

  15. MOUALLIF, K., Sur la Convergence d'une Méthode Associant Pénalisation et Régularisation, Bulletin de la Societé Royale des Sciences de Liège, Vol. 56, pp. 175–180, 1987.

    Google Scholar 

  16. MOUALLIF, K., and TOSSINGS, P., Une Méthode de Pénalisation Exponentielle Associée à une Régularisation Proximale, Bulletin de la Societé Royale des Sciences de Liège, Vol. 56, pp. 181–190, 1987.

    Google Scholar 

  17. MOUDAFI, A., Coupling Proximal Algorithm and Tikhonov Method, Nonlinear Times and Digest, Vol. 1, pp. 203–210, 1994.

    Google Scholar 

  18. BRÉZIS, H., Opérateurs Maximaux Monotones et Semigroups de Contractions dans les Espaces de Hilbert, Mathematical Studies, North-Holland, Amsterdam, Netherlands, Vol. 5, 1973.

    Google Scholar 

  19. BRÉZIS, H., Asymptotic Behavior of Some Evolution Systems, Nonlinear Evolution Equations, Academic Press, New York, New York, 1978.

    Google Scholar 

  20. BRÜCK, R. E., Asymptotic Convergence of Nonlinear Contraction Semigroups in Hilbert Space, Journal of Functional Analysis, Vol. 18, pp. 15–26, 1975.

    Google Scholar 

  21. FURUYA, H., MIYASHIBA, K., and KENMOCHI, N., Asymptotic Behavior of Solutions to a Class of Nonlinear Evolution Equations, Journal of Differential Equations, Vol. 62, pp. 73–94, 1986.

    Google Scholar 

  22. COMINETTI, R., Asymptotic Convergence of the Steepest Descent Method for the Exponential Penalty in Linear Programming, Journal of Convex Analysis, Vol. 2, pp. 145–152, 1995.

    Google Scholar 

  23. ATTOUCH, H., and COMINETTI, R., A Dynamical Approach to Convex Minimization Coupling Approximation with the Steepest Descent Method, Journal of Differential Equations, Vol. 128, pp. 519–540, 1996.

    Google Scholar 

  24. ATTOUCH, H., Variational Convergence for Functions and Operators, Applicable Mathematics Series, Pitman, London, England, 1984.

    Google Scholar 

  25. ATTOUCH, H., Viscosity Solutions of Minimization Problems, SIAM Journal on Optimization, Vol. 6, pp. 769–806, 1996.

    Google Scholar 

  26. TIKHONOV, A., and ARSENINE, V., Méthodes de Résolution de Problèmes Mal Posés, Mir, Moscow, Russia, 1974.

    Google Scholar 

  27. GONZAGA, C., Path Following Methods for Linear Programming, SIAM Review, Vol. 34, pp. 167–224, 1992.

    Google Scholar 

  28. GÜLER, O., Limiting Behavior of Weighted Central Paths in Linear Programming, Technical Report, Department of Mathematics and Statistics, University of Maryland, Baltimore, Maryland, 1991.

    Google Scholar 

  29. MEGIDDO, N., Pathways to the Optimal Set in Linear Programming, Progress in Mathematical Programming: Interior-Point and Related Methods, Springer Verlag, Berlin, Germany, pp. 131–158, 1989.

    Google Scholar 

  30. TORRALBA, D., Convergence Epigraphique et Changements d'Echelle en Analyse Variationnelle et Optimisation, Thesis, Université de Montepellier II, 1996.

  31. COMINETTI, R., and SAN MARTÍN, J., Asymptotic Analysis of the Exponential Penalty Trajectory in Linear Programming, Mathematical Programming, Vol. 67, pp. 169–187, 1994.

    Google Scholar 

  32. OPIAL, Z., Weak Convergence of the Sequence of Successive Approximations for Nonexpansive Mappings, Bulletin of the American Mathematical Society, Vol. 73, pp. 591–597, 1967.

    Google Scholar 

  33. POLYAK, B. T., Introduction to Optimization, Translation Series in Mathematics and Engineering, Optimization Software, Publications Division, New York, New York, 1987.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Departamento de Ingeniería Matemática, Universidad de Chile, Santiago, Chile

    R. Cominetti (Professor)

Authors
  1. R. Cominetti
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Cominetti, R. Coupling the Proximal Point Algorithm with Approximation Methods. Journal of Optimization Theory and Applications 95, 581–600 (1997). https://doi.org/10.1023/A:1022621905645

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1022621905645

Search

Navigation