Full convergence of the proximal point method for quasiconvex functions on Hadamard manifolds

Erik A. Papa Quiroz; P. Roberto Oliveira

ESAIM: Control, Optimisation and Calculus of Variations (2012)

  • Volume: 18, Issue: 2, page 483-500
  • ISSN: 1292-8119

Abstract

top
In this paper we propose an extension of the proximal point method to solve minimization problems with quasiconvex objective functions on Hadamard manifolds. To reach this goal, we initially extend the concepts of regular and generalized subgradient from Euclidean spaces to Hadamard manifolds and prove that, in the convex case, these concepts coincide with the classical one. For the minimization problem, assuming that the function is bounded from below, in the quasiconvex and lower semicontinuous case, we prove the convergence of the iterations given by the method. Furthermore, under the assumptions that the sequence of proximal parameters is bounded and the function is continuous, we obtain the convergence to a generalized critical point. In particular, our work extends the applications of the proximal point methods for solving constrained minimization problems with nonconvex objective functions in Euclidean spaces when the objective function is convex or quasiconvex on the manifold.

How to cite

top

Papa Quiroz, Erik A., and Oliveira, P. Roberto. "Full convergence of the proximal point method for quasiconvex functions on Hadamard manifolds." ESAIM: Control, Optimisation and Calculus of Variations 18.2 (2012): 483-500. <http://eudml.org/doc/277815>.

@article{PapaQuiroz2012,
abstract = {In this paper we propose an extension of the proximal point method to solve minimization problems with quasiconvex objective functions on Hadamard manifolds. To reach this goal, we initially extend the concepts of regular and generalized subgradient from Euclidean spaces to Hadamard manifolds and prove that, in the convex case, these concepts coincide with the classical one. For the minimization problem, assuming that the function is bounded from below, in the quasiconvex and lower semicontinuous case, we prove the convergence of the iterations given by the method. Furthermore, under the assumptions that the sequence of proximal parameters is bounded and the function is continuous, we obtain the convergence to a generalized critical point. In particular, our work extends the applications of the proximal point methods for solving constrained minimization problems with nonconvex objective functions in Euclidean spaces when the objective function is convex or quasiconvex on the manifold. },
author = {Papa Quiroz, Erik A., Oliveira, P. Roberto},
journal = {ESAIM: Control, Optimisation and Calculus of Variations},
keywords = {Proximal point method; quasiconvex function; Hadamard manifolds; full convergence.; proximal point method; full convergence},
language = {eng},
month = {7},
number = {2},
pages = {483-500},
publisher = {EDP Sciences},
title = {Full convergence of the proximal point method for quasiconvex functions on Hadamard manifolds},
url = {http://eudml.org/doc/277815},
volume = {18},
year = {2012},
}

TY - JOUR
AU - Papa Quiroz, Erik A.
AU - Oliveira, P. Roberto
TI - Full convergence of the proximal point method for quasiconvex functions on Hadamard manifolds
JO - ESAIM: Control, Optimisation and Calculus of Variations
DA - 2012/7//
PB - EDP Sciences
VL - 18
IS - 2
SP - 483
EP - 500
AB - In this paper we propose an extension of the proximal point method to solve minimization problems with quasiconvex objective functions on Hadamard manifolds. To reach this goal, we initially extend the concepts of regular and generalized subgradient from Euclidean spaces to Hadamard manifolds and prove that, in the convex case, these concepts coincide with the classical one. For the minimization problem, assuming that the function is bounded from below, in the quasiconvex and lower semicontinuous case, we prove the convergence of the iterations given by the method. Furthermore, under the assumptions that the sequence of proximal parameters is bounded and the function is continuous, we obtain the convergence to a generalized critical point. In particular, our work extends the applications of the proximal point methods for solving constrained minimization problems with nonconvex objective functions in Euclidean spaces when the objective function is convex or quasiconvex on the manifold.
LA - eng
KW - Proximal point method; quasiconvex function; Hadamard manifolds; full convergence.; proximal point method; full convergence
UR - http://eudml.org/doc/277815
ER -

References

top
  1. P.A. Absil, R. Mahony and B. Andrews, Convergence of the iterates of descent methods for analytic cost function. SIAM J. Optim.16 (2005) 531–547.  Zbl1092.90036
  2. F. Alvarez, J. Bolte and O. Brahic, Hessian Riemannian gradient flows in convex programming. SIAM J. Optim.43 (2004) 477–501.  Zbl1077.34050
  3. H. Attouch and J. Bolte, On the convergence of the proximal algorithm for nonsmooth functions involving analytic features. Math. Program. B116 (2009) 5–16.  Zbl1165.90018
  4. H. Attouch and A. Soubeyran, “Worthwhile-to-move” behaviors as temporary satisficing without too many sacrificing processes. Preprint arXiv:0905.1238 (2009).  
  5. H. Attouch and M. Teboulle, Regularized Lotka-Volterra dynamical system as continuous proximal-like method in optimization. J. Optim. Theory Appl.121 (2004) 541–580.  Zbl1076.90053
  6. W. Ballmann, Lectures on Spaces of Nonpositive Curvature. Birkhäuser, Basel (1995).  Zbl0834.53003
  7. N. Barron and W. Liu, Calculus of variation l∞. Appl. Math. Opt.35 (1997) 237–263.  Zbl0871.49017
  8. A. Ben-Tal and A. Nemirovski, Lectures on Modern Convex Optimization : Analysis and Engineering Applications, MPS/SIAM Series on Optimization2. SIAM (2001).  Zbl0986.90032
  9. S. Boyd and L. Vanderberghe, Convex Optimization. Cambridge University Press, Cambridge (2004).  
  10. M.R. Bridson and A. Haefliger, Metric Spaces of Non-Positive Curvature. Springer-Verlag, Berlin (1999).  Zbl0988.53001
  11. J.S. Chen and S.S.H. Pan, Proximal-like algorithm for a class of nonconvex programming. Pacific Journal of Optimization4 (2008) 319–333.  Zbl1153.90015
  12. G.F.M. Cunha, J.X. da Cruz Neto, and P.R. liveira, A proximal point algorithm with φ-divergence to quasiconvex programming. Optimization59 (2010) 777–792.  Zbl1194.90098
  13. J.X. da Cruz Neto, O.P. Ferreira, L. Lucambio Perez and S.Z. Németh, Convex-and monotone-transformable mathematical programming and a proximal-like point method. J. Glob. Optim.35 (2006) 53–69.  Zbl1104.90035
  14. M.P. do Carmo, Riemannian Geometry. Birkhäuser, Boston (1992).  
  15. P.B. Eberlein, Geometry of Nonpositively Curved Manifolds. University of Chicago Press, Chicago (1996).  Zbl0883.53003
  16. O.P. Ferreira and P.R. Oliveira, Proximal point algorithm on Riemannian manifolds. Optimization51 (2002) 257–270.  Zbl1013.49024
  17. J. Gromicho, Quasiconvex Optimization and Location Theory. Kluwer Academic Publishers, Dordrecht (1998).  Zbl0914.90220
  18. J. Jost, Non Positive Curvature : Geometric and Analytic Aspects. Lectures in Mathematics, Base; Boston, Birkhäuser (1997).  Zbl0896.53002
  19. A. Kaplan and R. Tichatschke, Proximal point methods and nonconvex optimization. J. Glob. Optim.13 (1998) 389–406.  Zbl0916.90224
  20. K.C. Kiwiel, Convergence and efficiency of subgradient methods for quasiconvex minimization. Math. Program. A90 (2001) 1–25.  Zbl0986.90034
  21. B. Martinet, Brève communication. Régularisation d’inéquations variationelles par approximations successives. Revue Française D’Informatique et de Recherche Opérationelle4 (1970) 154–158.  Zbl0215.21103
  22. Y.E. Nesterov and M.J. Todd, On the Riemannian geometry defined by self-concordant barrier and interior-point methods. Found. Comput. Math.2 (2002) 333–361.  Zbl1049.90127
  23. S.H. Pan and J.S. Chen, Entropy-like proximal algorithms based on a second-order homogeneous distances function for quasiconvex programming. J. Glob. Optim.39 (2007) 555–575.  Zbl1190.90144
  24. E.A. Papa Quiroz and P.R. Oliveira, New Results on Linear Optimization Through Diagonal Metrics and Riemannian Geometry Tools. Technical Report, ES-645/04, PESC COPPE, Federal University of Rio de Janeiro (2004).  
  25. E.A. Papa Quiroz and P.R. Oliveira, A new self-concordant barrier for the hypercube. J. Optim. Theory Appl.135 (2007) 475–490.  Zbl1146.90089
  26. E.A. Papa Quiroz and P.R. Oliveira, Proximal point methods for quasiconvex and convex functions with Bregman distances on Hadamard manifolds. J. Convex Anal.16 (2009) 46–69.  Zbl1176.90361
  27. T. Rapcsák, Smooth Nonlinear Optimization. Kluwer Academic Publishers (1997).  Zbl1009.90109
  28. O.S. Rothaus, Domains of positivity. Abh. Math. Sem. Univ. Hamburg24 (1960) 189–235.  Zbl0096.27903
  29. R.T. Rockafellar, Monotone operations and the proximal point method. SIAM J. Control Optim.14 (1976) 877–898.  Zbl0358.90053
  30. R.T. Rockafellar and R. Wets, Variational Analysis, Grundlehren der Mathematischen, Wissenschaften317. Springer (1990).  
  31. T. Sakai, Riemannian Geometry. American Mathematical Society, Providence, RI (1996).  
  32. S.S. Souza, P.R. Oliveira, J.X. da Cruz Neto and A. Soubeyran, A proximal method with separable Bregman distance for quasiconvex minimization on the nonnegative orthant. Eur. J. Oper. Res.201 (2010) 365–376.  Zbl1217.90158
  33. A. Takayama, Mathematical Economics, 2nd Edition. Cambrigde University Press, Cambridge (1995).  Zbl0313.90008
  34. P. Tseng, Convergence of a block coordinate descent method for nondifferentiable minimization. J. Optim. Theory Appl.109 (2001) 475–494.  Zbl1006.65062
  35. C. Udriste, Convex Function and Optimization Methods on Riemannian Manifolds. Kluwer Academic Publishers (1994).  Zbl0932.53003
  36. H. Wolkowicz, R. Saigal and L. Vanderberge, Eds., Handbook of Semidefinite Programming Theory, Algorithms and Applications, 1st Edition. Internat. Ser. Oper. Management Sci., Springer (2005).  

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.