Abstract

This paper generalizes the proximal point method using Bregman distances to solve convex and quasiconvex optimization problems on Hadamard manifolds. We will proved that the sequence generated by our method is well defined and converges to an optimal solution of the problem. Also, we obtain the same convergence properties for the classical proximal method, applied to quasiconvex problems. Finally, we give some examples of Bregman distances in non-Euclidean spaces.

Author information

Contact details are reproduced from the original publication and may be historical.

Paulo Roberto Oliveira

PESC-COPPE, Federal University of Rio de Janeiro, Rio de Janeiro, Brazil

poliveir@cos.ufrj.br

Keywords

  • Proximal point algorithms
  • Hadamard manifolds
  • Bregman distances
  • Bregman functions

References

  1. K. Arrow, G. Debreu: Existence of an equilibrium for a competitive economy, Econometrica 22 (1954) 265–290.https://doi.org/10.2307/1907353Google Scholar
  2. N. Barron, W. Liu: Calculus of variations l∞, Appl. Math. Optimization 35 (1997) 237–263.https://doi.org/10.1007/BF02683330Google Scholar
  3. R. S. Burachik, A. Iusem: Generalized proximal point algorithm for the variational inequality problem in Hilbert space, SIAM J. Optim. 8 (1998) 197–216.https://doi.org/10.1137/S1052623495286302Google Scholar
  4. R. S. Burachik, S. Scheimberg: A proximal point method for the variational inequality problem in Banach spaces, SIAM J. Control Optim. 39(5) (2000) 1633–1649.https://doi.org/10.1137/S0363012998339745Google Scholar
  5. Y. Censor, A. Zenios: Proximal minimization algorithm with D-functions, J. Optim. Theory Appl. 73(3) (1992) 451–464.https://doi.org/10.1007/BF00940051Google Scholar
  6. Y. Censor, A. Lent: An iterative row-action method for interval convex programming, J. Optim. Theory Appl. 34(3) (1981) 321–353.https://doi.org/10.1007/BF00934676Google Scholar
  7. G. Chen, M. Teboulle: Convergence analysis of the proximal-like minimization algorithm using Bregman functions, SIAM J. Optim. 3 (1993) 538–543.https://doi.org/10.1137/0803026Google Scholar
  8. G. F. M. Cunha, A. M. Pinto, P. R. Oliveira, J. X. da Cruz Neto: Generalization of the primal and dual affine scaling algorithms, Technical Report ES 675/05, PESC/COPPE, Federal University of Rio de Janeiro, Rio de Janeiro (2005).Google Scholar
  9. J. X. da Cruz Neto, O. P. Ferreira, L. Lucambio Perez, S. Z. Németh: Convex- and monotone-transformable mathematical programming and a proximal-like point method, J. Glob. Optim. 35(1) (2006) 53–69.https://doi.org/10.1007/s10898-005-6741-9Google Scholar
  10. J. X. da Cruz Neto, L. L. Lima, P. R. Oliveira: Geodesic algorithms in Riemannian geometry, Balkan J. Geom. Appl. 3(2) (1998) 89–100.Google Scholar
  11. M. P. do Carmo: Riemannian Geometry, Birkhäuser, Boston (1992).https://doi.org/10.1007/978-1-4757-2201-7Google Scholar
  12. D. den Hertog, C. Roos, T. Terlaky: Inverse barrier methods for linear programming, Report 91-27, Faculty of Technical Mathematics and Informatics, Delft University of Technology, Delft (1991).Google Scholar
  13. O. P. Ferreira, P. R. Oliveira: Subgradient algorithm on Riemannian manifolds, J. Optim. Theory Appl. 97(1) (1998) 93–104.https://doi.org/10.1023/A:1022675100677Google Scholar
  14. O. P. Ferreira, P. R. Oliveira: Proximal point algorithm on Riemannian manifolds, Optimization 51(2) (2002) 257–270.https://doi.org/10.1080/02331930290019413Google Scholar
  15. D. Gabay: Minimizing a differentiable function over a differential manifold, J. Optim. Theory Appl. 37(2) (1982) 177–219.https://doi.org/10.1007/BF00934767Google Scholar
  16. O. Garciga, A. Iusem: Proximal methods with penalization effects in Banach spaces, Numer. Funct. Anal. Optimization 25(1-2) (2004) 69–91.https://doi.org/10.1081/NFA-120034119Google Scholar
  17. W. Ginsberg: Concavity and quasiconcavity in economics, J. Econ. Theory 6 (1973) 596–605.https://doi.org/10.1016/0022-0531(73)90080-XGoogle Scholar
  18. Y. Goudou, J. Munier: The heavy ball with friction method: the quasiconvex case, submitted (2005).Google Scholar
  19. A. Iusem: Métodos de Ponto Proximal em Otimização, IMPA, Rio de Janeiro (1995).Google Scholar
  20. K. C. Kiwiel: Proximal minimization methods with generalized Bregman functions, SIAM J. Control Optim. 35 (1997) 1142–1168.https://doi.org/10.1137/S0363012995281742Google Scholar
  21. D. G. Luenberger: The gradient projection method along geodesics, Manage. Sci., Theory 18(11) (1972) 620–631.https://doi.org/10.1287/mnsc.18.11.620Google Scholar
  22. Y. E. Nesterov, M. J. Todd: On the Riemannian geometry defined by self-concordant barriers and interior-point methods, Found. Comput. Math. 2 (2002) 333–361.https://doi.org/10.1007/s102080010032Google Scholar
  23. E. A. Papa Quiroz, 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, Rio de Janeiro (2004).Google Scholar
  24. E. A. Papa Quiroz, P. R. Oliveira: A new self-concordant barrier for the hypercube, J. Optim. Theory Appl. 135 (2007) 475–490.https://doi.org/10.1007/s10957-007-9220-2Google Scholar
  25. E. A. Papa Quiroz, P. R. Oliveira: Proximal methods to solve zeros of monotone operators with Bregman function on Riemannian manifolds, working paper.Google Scholar
  26. G. J. Pereira, P. R. Oliveira: A new class of proximal algorithms for the nonlinear complementary problems, in: Optimization and Control with Applications, L. Qi et al. (ed.), Applied Optimization 96, Springer, New York (2005) 552–562.Google Scholar
  27. T. Rapcsák: Smooth Nonlinear Optimization of Rn, Kluwer, Dordrecht (1997).https://doi.org/10.1007/978-1-4615-6357-0Google Scholar
  28. R. Saigal: The primal power affine scaling method, Ann. Oper. Res. 62(1) (1996) 375–417.https://doi.org/10.1007/BF02206824Google Scholar
  29. T. Sakai: Riemannian Geometry, AMS, Providence (1996).https://doi.org/10.1090/mmono/149Google Scholar
  30. S. Souza, G. L. de Oliveira, J. X. da Cruz Neto, P. R. Oliveira: A new class of interior proximal methods with variable metric for optimization over the positive orthant, working paper.Google Scholar
  31. S. T. Smith: Optimization techniques on Riemannian manifolds, in: Hamiltonian and Gradient Flows, Algorithms and Control, A. Bloch (ed.), Fields Inst. Commun. 3, AMS, Providence (1994) 113–136.https://doi.org/10.1090/fic/003/09Google Scholar
  32. A. Takayama: Mathematical Economics. 2nd Ed., Cambrigde University Press, Cambridge (1995).Google Scholar
  33. C. Udriste: Convex Functions and Optimization Methods on Riemannian Manifolds, Kluwer, Dordrecht (1994).https://doi.org/10.1007/978-94-015-8390-9Google Scholar

Suggested citation

E. A. Papa Quiroz, P. R. Oliveira. “Proximal Point Methods for Quasiconvex and Convex Functions with Bregman Distances on Hadamard Manifolds.” Journal of Convex Analysis 16 (2009), No. 1, 49–69. https://doi.org/10.68381/jca16003

Download BibTeXPublished by Heldermann Verlag.

Published by Heldermann Verlag, 2009. Rights now held by Banach Press LLC.