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.  
  2. F. Alvarez, J. Bolte and O. Brahic, Hessian Riemannian gradient flows in convex programming. SIAM J. Optim.43 (2004) 477–501.  
  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.  
  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.  
  6. W. Ballmann, Lectures on Spaces of Nonpositive Curvature. Birkhäuser, Basel (1995).  
  7. N. Barron and W. Liu, Calculus of variation l∞. Appl. Math. Opt.35 (1997) 237–263.  
  8. A. Ben-Tal and A. Nemirovski, Lectures on Modern Convex Optimization : Analysis and Engineering Applications, MPS/SIAM Series on Optimization2. SIAM (2001).  
  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).  
  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.  
  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.  
  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.  
  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).  
  16. O.P. Ferreira and P.R. Oliveira, Proximal point algorithm on Riemannian manifolds. Optimization51 (2002) 257–270.  
  17. J. Gromicho, Quasiconvex Optimization and Location Theory. Kluwer Academic Publishers, Dordrecht (1998).  
  18. J. Jost, Non Positive Curvature : Geometric and Analytic Aspects. Lectures in Mathematics, Base; Boston, Birkhäuser (1997).  
  19. A. Kaplan and R. Tichatschke, Proximal point methods and nonconvex optimization. J. Glob. Optim.13 (1998) 389–406.  
  20. K.C. Kiwiel, Convergence and efficiency of subgradient methods for quasiconvex minimization. Math. Program. A90 (2001) 1–25.  
  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.  
  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.  
  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.  
  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.  
  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.  
  27. T. Rapcsák, Smooth Nonlinear Optimization. Kluwer Academic Publishers (1997).  
  28. O.S. Rothaus, Domains of positivity. Abh. Math. Sem. Univ. Hamburg24 (1960) 189–235.  
  29. R.T. Rockafellar, Monotone operations and the proximal point method. SIAM J. Control Optim.14 (1976) 877–898.  
  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.  
  33. A. Takayama, Mathematical Economics, 2nd Edition. Cambrigde University Press, Cambridge (1995).  
  34. P. Tseng, Convergence of a block coordinate descent method for nondifferentiable minimization. J. Optim. Theory Appl.109 (2001) 475–494.  
  35. C. Udriste, Convex Function and Optimization Methods on Riemannian Manifolds. Kluwer Academic Publishers (1994).  
  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.