Skip to main content
SpringerLink
Log in

Iteration-Complexity of Gradient, Subgradient and Proximal Point Methods on Riemannian Manifolds

  • Published:
Journal of Optimization Theory and Applications Aims and scope Submit manuscript

Abstract

This paper considers optimization problems on Riemannian manifolds and analyzes the iteration-complexity for gradient and subgradient methods on manifolds with nonnegative curvatures. By using tools from Riemannian convex analysis and directly exploring the tangent space of the manifold, we obtain different iteration-complexity bounds for the aforementioned methods, thereby complementing and improving related results. Moreover, we also establish an iteration-complexity bound for the proximal point method on Hadamard manifolds.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Wang, X., Li, C., Wang, J., Yao, J.C.: Linear convergence of subgradient algorithm for convex feasibility on Riemannian manifolds. SIAM J. Optim. 25(4), 2334–2358 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  2. Li, C., Mordukhovich, B.S., Wang, J., Yao, J.C.: Weak sharp minima on Riemannian manifolds. SIAM J. Optim. 21(4), 1523–1560 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  3. Wang, X.M., Li, C., Yao, J.C.: Subgradient projection algorithms for convex feasibility on Riemannian manifolds with lower bounded curvatures. J. Optim. Theory Appl. 164(1), 202–217 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  4. Grohs, P., Hosseini, S.: \(\varepsilon \)-subgradient algorithms for locally lipschitz functions on Riemannian manifolds. Adv. Comput. Math. 42(2), 333–360 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  5. Bento, G.C., Melo, J.G.: Subgradient method for convex feasibility on Riemannian manifolds. J. Optim. Theory Appl. 152(3), 773–785 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  6. Bento, G.C., Ferreira, O.P., Oliveira, P.R.: Proximal point method for a special class of nonconvex functions on Hadamard manifolds. Optimization 64(2), 289–319 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  7. Cruz Neto, J.X., Ferreira, O.P., Pérez, L.R.L., Németh, S.Z.: Convex- and monotone-transformable mathematical programming problems and a proximal-like point method. J. Glob. Optim. 35(1), 53–69 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  8. Rapcsák, T.: Smooth Nonlinear Optimization in \({ R}^n\), Nonconvex Optimization and its Applications, vol. 19. Kluwer Academic Publishers, Dordrecht (1997)

    Book  MATH  Google Scholar 

  9. Smith, S.T.: Optimization techniques on Riemannian manifolds. In: Bloch, A. (ed.) Hamiltonian and Gradient Flows, Algorithms and Control. Fields Inst. Commun., vol. 3, pp. 113–136. Amer. Math. Soc., Providence (1994)

  10. Luenberger, D.G.: The gradient projection method along geodesics. Manag. Sci. 18, 620–631 (1972)

    Article  MathSciNet  MATH  Google Scholar 

  11. Udrişte, C.: Convex Functions and Optimization Methods on Riemannian Manifolds, Mathematics and its Applications, vol. 297. Kluwer Academic Publishers Group, Dordrecht (1994)

    Book  MATH  Google Scholar 

  12. Nesterov, Y.E., Todd, M.J.: On the Riemannian geometry defined by self-concordant barriers and interior-point methods. Found. Comput. Math. 2(4), 333–361 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  13. Edelman, A., Arias, T.A., Smith, S.T.: The geometry of algorithms with orthogonality constraints. SIAM J. Matrix Anal. Appl. 20(2), 303–353 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  14. Gabay, D.: Minimizing a differentiable function over a differential manifold. J. Optim. Theory Appl. 37(2), 177–219 (1982)

    Article  MathSciNet  MATH  Google Scholar 

  15. Ferreira, O.P., Oliveira, P.R.: Subgradient algorithm on Riemannian manifolds. J. Optim. Theory Appl. 97(1), 93–104 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  16. Martinet, B.: Régularisation d’inéquations variationnelles par approximations successives. Rev. Fr. Inf. Rech. Opér. 4(Ser. R–3), 154–158 (1970)

    MATH  Google Scholar 

  17. Rockafellar, R.T.: Monotone operators and the proximal point algorithm. SIAM J. Control Optim. 14(5), 877–898 (1976)

    Article  MathSciNet  MATH  Google Scholar 

  18. Ferreira, O.P., Oliveira, P.R.: Proximal point algorithm on Riemannian manifolds. Optimization 51(2), 257–270 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  19. Li, C., López, G., Martín-Márquez, V.: Monotone vector fields and the proximal point algorithm on Hadamard manifolds. J. Lond. Math. Soc. 79(3), 663–683 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  20. Bento, G.C., Cruz Neto, J.X., Oliveira, P.R.: A new approach to the proximal point method: convergence on general Riemannian manifolds. J. Optim. Theory Appl. 168(3), 743–755 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  21. Souza, J.C.O., Oliveira, P.R.: A proximal point algorithm for DC fuctions on Hadamard manifolds. J. Glob. Optim. 63(4), 797–810 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  22. Papa Quiroz, E.A., Quispe, E.M., Oliveira, P.R.: Steepest descent method with a generalized Armijo search for quasiconvex functions on Riemannian manifolds. J. Math. Anal. Appl. 341(1), 467–477 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  23. Zhang, H., Sra, S.: First-order methods for geodesically convex optimization. In: JMLR: Workshop and Conference Proceedings 49(1), 1–21 (2016)

  24. Boumal, N., Absil, P.A., Cartis, C.: Global rates of convergence for nonconvex optimization on manifolds. ArXiv e-prints 1(1), 1–31 (2016)

    Google Scholar 

  25. Zhang, H., Reddi, S.J., Sra, S.: Fast stochastic optimization on Riemannian manifolds. ArXiv e-prints pp. 1–17 (2016)

  26. Bačák, M.: The proximal point algorithm in metric spaces. Israel J. Math. 194(2), 689–701 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  27. do Carmo, M.P.: Riemannian Geometry. Mathematics: Theory & Applications. Birkhäuser Boston, Inc., Boston (1992). Translated from the second Portuguese edition by Francis Flaherty

  28. Sakai, T.: Riemannian Geometry, Translations of Mathematical Monographs, vol. 149. American Mathematical Society, Providence (1996)

    Google Scholar 

  29. Cruz Neto, J.X., Lima, L.L., Oliveira, P.R.: Geodesic algorithms in Riemannian geometry. Balkan J. Geom. Appl. 3(2), 89–100 (1998)

    MathSciNet  MATH  Google Scholar 

  30. Bento, G.C., Cruz Neto, J.X.: A subgradient method for multiobjective optimization on Riemannian manifolds. J. Optim. Theory Appl. 159(1), 125–137 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  31. Bento, G.C., Ferreira, O.P., Oliveira, P.R.: Local convergence of the proximal point method for a special class of nonconvex functions on Hadamard manifolds. Nonlinear Anal. 73(2), 564–572 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  32. Nesterov, Y.: Introductory Lectures on Convex Optimization, Applied Optimization, vol. 87. Kluwer Academic Publishers, Boston (2004)

    Book  MATH  Google Scholar 

  33. Beck, A., Teboulle, M.: A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J. Imaging Sci. 2(1), 183–202 (2009)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

This work was supported by CNPq Grants 458479/2014-4, 312077/2014-9, 305158/2014-7, 444134/2014-0, 406975/2016-7.

Author information

Authors and Affiliations

  1. IME, Universidade Federal de Goiás, Goiânia, GO, 74001-970, Brazil

    Glaydston C. Bento, Orizon P. Ferreira & Jefferson G. Melo

Authors
  1. Glaydston C. Bento
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Orizon P. Ferreira
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Jefferson G. Melo
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jefferson G. Melo.

Additional information

Communicated by Sándor Zoltán Németh.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Bento, G.C., Ferreira, O.P. & Melo, J.G. Iteration-Complexity of Gradient, Subgradient and Proximal Point Methods on Riemannian Manifolds. J Optim Theory Appl 173, 548–562 (2017). https://doi.org/10.1007/s10957-017-1093-4

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10957-017-1093-4

Keywords

Mathematics Subject Classification

Search

Navigation