Hostname: page-component-586b7cd67f-t7fkt Total loading time: 0 Render date: 2024-11-28T04:59:56.695Z Has data issue: false hasContentIssue false
  • English
  • Français

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

Published online by Cambridge University Press:  22 June 2011

Erik A. Papa Quiroz  and
P. Roberto Oliveira
Erik A. Papa Quiroz
Affiliation:
Universidad Nacional del Callao, Universidad Nacional Mayor de San Marcos, Lima, Peru. [email protected]
P. Roberto Oliveira
Affiliation:
PESC-COPPE Federal University of Rio de Janeiro, Rio de Janeiro, Brazil; [email protected]
Get access

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.

Keywords

Proximal point methodquasiconvex functionHadamard manifoldsfull convergence.
Type
Research Article
Information
ESAIM: Control, Optimisation and Calculus of Variations , Volume 18 , Issue 2 , April 2012 , pp. 483 - 500
Copyright
© EDP Sciences, SMAI, 2011

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Absil, P.A., Mahony, R. and Andrews, B., Convergence of the iterates of descent methods for analytic cost function. SIAM J. Optim. 16 (2005) 531–547. Google Scholar
Alvarez, F., Bolte, J. and Brahic, O., Hessian Riemannian gradient flows in convex programming. SIAM J. Optim. 43 (2004) 477–501. Google Scholar
Attouch, H. and Bolte, J., On the convergence of the proximal algorithm for nonsmooth functions involving analytic features. Math. Program. B 116 (2009) 5–16. Google Scholar
H. Attouch and A. Soubeyran, “Worthwhile-to-move” behaviors as temporary satisficing without too many sacrificing processes. Preprint arXiv:0905.1238 (2009).
Attouch, H. and Teboulle, M., Regularized Lotka-Volterra dynamical system as continuous proximal-like method in optimization. J. Optim. Theory Appl. 121 (2004) 541–580. Google Scholar
W. Ballmann, Lectures on Spaces of Nonpositive Curvature. Birkhäuser, Basel (1995).
Barron, N. and Liu, W., Calculus of variation l ∞. Appl. Math. Opt. 35 (1997) 237–263. Google Scholar
A. Ben-Tal and A. Nemirovski, Lectures on Modern Convex Optimization : Analysis and Engineering Applications, MPS/SIAM Series on Optimization 2. SIAM (2001).
S. Boyd and L. Vanderberghe, Convex Optimization. Cambridge University Press, Cambridge (2004).
M.R. Bridson and A. Haefliger, Metric Spaces of Non-Positive Curvature. Springer-Verlag, Berlin (1999).
Chen, J.S. and Pan, S.S.H., Proximal-like algorithm for a class of nonconvex programming. Pacific Journal of Optimization 4 (2008) 319–333. Google Scholar
Cunha, G.F.M., da Cruz Neto, J.X., and liveira, P.R., A proximal point algorithm with φ-divergence to quasiconvex programming. Optimization 59 (2010) 777–792. Google Scholar
da Cruz Neto, J.X., Ferreira, O.P., Lucambio Perez, L. and Németh, S.Z., Convex-and monotone-transformable mathematical programming and a proximal-like point method. J. Glob. Optim. 35 (2006) 53–69. Google Scholar
M.P. do Carmo, Riemannian Geometry. Birkhäuser, Boston (1992).
P.B. Eberlein, Geometry of Nonpositively Curved Manifolds. University of Chicago Press, Chicago (1996).
Ferreira, O.P. and Oliveira, P.R., Proximal point algorithm on Riemannian manifolds. Optimization 51 (2002) 257–270. Google Scholar
J. Gromicho, Quasiconvex Optimization and Location Theory. Kluwer Academic Publishers, Dordrecht (1998).
J. Jost, Non Positive Curvature : Geometric and Analytic Aspects. Lectures in Mathematics, Base; Boston, Birkhäuser (1997).
Kaplan, A. and Tichatschke, R., Proximal point methods and nonconvex optimization. J. Glob. Optim. 13 (1998) 389–406. Google Scholar
Kiwiel, K.C., Convergence and efficiency of subgradient methods for quasiconvex minimization. Math. Program. A 90 (2001) 1–25. Google Scholar
Martinet, B., 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. Google Scholar
Nesterov, Y.E. and Todd, M.J., On the Riemannian geometry defined by self-concordant barrier and interior-point methods. Found. Comput. Math. 2 (2002) 333–361. Google Scholar
Pan, S.H. and Chen, J.S., Entropy-like proximal algorithms based on a second-order homogeneous distances function for quasiconvex programming. J. Glob. Optim. 39 (2007) 555–575. Google Scholar
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).
Papa Quiroz, E.A. and Oliveira, P.R., A new self-concordant barrier for the hypercube. J. Optim. Theory Appl. 135 (2007) 475–490. Google Scholar
Papa Quiroz, E.A. and Oliveira, P.R., Proximal point methods for quasiconvex and convex functions with Bregman distances on Hadamard manifolds. J. Convex Anal. 16 (2009) 46–69. Google Scholar
T. Rapcsák, Smooth Nonlinear Optimization. Kluwer Academic Publishers (1997).
Rothaus, O.S., Domains of positivity. Abh. Math. Sem. Univ. Hamburg 24 (1960) 189–235. Google Scholar
Rockafellar, R.T., Monotone operations and the proximal point method. SIAM J. Control Optim. 14 (1976) 877–898. Google Scholar
R.T. Rockafellar and R. Wets, Variational Analysis, Grundlehren der Mathematischen, Wissenschaften 317. Springer (1990).
T. Sakai, Riemannian Geometry. American Mathematical Society, Providence, RI (1996).
Souza, S.S., Oliveira, P.R., da Cruz Neto, J.X. and Soubeyran, A., A proximal method with separable Bregman distance for quasiconvex minimization on the nonnegative orthant. Eur. J. Oper. Res. 201 (2010) 365–376. Google Scholar
A. Takayama, Mathematical Economics, 2nd Edition. Cambrigde University Press, Cambridge (1995).
Tseng, P., Convergence of a block coordinate descent method for nondifferentiable minimization. J. Optim. Theory Appl. 109 (2001) 475–494. Google Scholar
C. Udriste, Convex Function and Optimization Methods on Riemannian Manifolds. Kluwer Academic Publishers (1994).
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).