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

Papa Quiroz, Erik A.; Oliveira, P. Roberto

ESAIM: Control, Optimisation and Calculus of Variations, Tome 18 (2012) no. 2, pp. 483-500.

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.

[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. | MR | Zbl

[2] F. Alvarez, J. Bolte and O. Brahic, Hessian Riemannian gradient flows in convex programming. SIAM J. Optim. 43 (2004) 477-501. | MR | Zbl

[3] H. Attouch and J. Bolte, On the convergence of the proximal algorithm for nonsmooth functions involving analytic features. Math. Program. B 116 (2009) 5-16. | MR | Zbl

[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. | MR | Zbl

[6] W. Ballmann, Lectures on Spaces of Nonpositive Curvature. Birkhäuser, Basel (1995). | MR

[7] N. Barron and W. Liu, Calculus of variation l∞. Appl. Math. Opt. 35 (1997) 237-263. | MR | Zbl

[8] A. Ben-Tal and A. Nemirovski, Lectures on Modern Convex Optimization : Analysis and Engineering Applications, MPS/SIAM Series on Optimization 2. SIAM (2001). | MR | Zbl

[9] S. Boyd and L. Vanderberghe, Convex Optimization. Cambridge University Press, Cambridge (2004). | MR | Zbl

[10] M.R. Bridson and A. Haefliger, Metric Spaces of Non-Positive Curvature. Springer-Verlag, Berlin (1999). | MR | Zbl

[11] J.S. Chen and S.S.H. Pan, Proximal-like algorithm for a class of nonconvex programming. Pacific Journal of Optimization 4 (2008) 319-333. | MR | Zbl

[12] G.F.M. Cunha, J.X. da Cruz Neto, and P.R. liveira, A proximal point algorithm with φ-divergence to quasiconvex programming. Optimization 59 (2010) 777-792. | MR | Zbl

[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. | MR | Zbl

[14] M.P. Do Carmo, Riemannian Geometry. Birkhäuser, Boston (1992). | MR | Zbl

[15] P.B. Eberlein, Geometry of Nonpositively Curved Manifolds. University of Chicago Press, Chicago (1996). | MR | Zbl

[16] O.P. Ferreira and P.R. Oliveira, Proximal point algorithm on Riemannian manifolds. Optimization 51 (2002) 257-270. | MR | Zbl

[17] J. Gromicho, Quasiconvex Optimization and Location Theory. Kluwer Academic Publishers, Dordrecht (1998). | MR | Zbl

[18] J. Jost, Non Positive Curvature : Geometric and Analytic Aspects. Lectures in Mathematics, Base; Boston, Birkhäuser (1997). | Zbl

[19] A. Kaplan and R. Tichatschke, Proximal point methods and nonconvex optimization. J. Glob. Optim. 13 (1998) 389-406. | MR | Zbl

[20] K.C. Kiwiel, Convergence and efficiency of subgradient methods for quasiconvex minimization. Math. Program. A 90 (2001) 1-25. | MR | Zbl

[21] B. Martinet, Brève communication. Régularisation d'inéquations variationelles par approximations successives. Revue Française D'Informatique et de Recherche Opérationelle 4 (1970) 154-158. | Numdam | Zbl

[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. | MR | Zbl

[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. | Zbl

[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. | MR | Zbl

[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. | MR | Zbl

[27] T. Rapcsák, Smooth Nonlinear Optimization. Kluwer Academic Publishers (1997). | MR | Zbl

[28] O.S. Rothaus, Domains of positivity. Abh. Math. Sem. Univ. Hamburg 24 (1960) 189-235. | MR | Zbl

[29] R.T. Rockafellar, Monotone operations and the proximal point method. SIAM J. Control Optim. 14 (1976) 877-898. | MR | Zbl

[30] R.T. Rockafellar and R. Wets, Variational Analysis, Grundlehren der Mathematischen, Wissenschaften 317. Springer (1990). | MR | Zbl

[31] T. Sakai, Riemannian Geometry. American Mathematical Society, Providence, RI (1996). | MR | Zbl

[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. | MR | Zbl

[33] A. Takayama, Mathematical Economics, 2nd Edition. Cambrigde University Press, Cambridge (1995). | MR | Zbl

[34] P. Tseng, Convergence of a block coordinate descent method for nondifferentiable minimization. J. Optim. Theory Appl. 109 (2001) 475-494. | MR | Zbl

[35] C. Udriste, Convex Function and Optimization Methods on Riemannian Manifolds. Kluwer Academic Publishers (1994). | MR | Zbl

[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). | MR | Zbl