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.
Similar content being viewed by others
References
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)
Li, C., Mordukhovich, B.S., Wang, J., Yao, J.C.: Weak sharp minima on Riemannian manifolds. SIAM J. Optim. 21(4), 1523–1560 (2011)
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)
Grohs, P., Hosseini, S.: \(\varepsilon \)-subgradient algorithms for locally lipschitz functions on Riemannian manifolds. Adv. Comput. Math. 42(2), 333–360 (2016)
Bento, G.C., Melo, J.G.: Subgradient method for convex feasibility on Riemannian manifolds. J. Optim. Theory Appl. 152(3), 773–785 (2012)
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)
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)
Rapcsák, T.: Smooth Nonlinear Optimization in \({ R}^n\), Nonconvex Optimization and its Applications, vol. 19. Kluwer Academic Publishers, Dordrecht (1997)
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)
Luenberger, D.G.: The gradient projection method along geodesics. Manag. Sci. 18, 620–631 (1972)
Udrişte, C.: Convex Functions and Optimization Methods on Riemannian Manifolds, Mathematics and its Applications, vol. 297. Kluwer Academic Publishers Group, Dordrecht (1994)
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)
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)
Gabay, D.: Minimizing a differentiable function over a differential manifold. J. Optim. Theory Appl. 37(2), 177–219 (1982)
Ferreira, O.P., Oliveira, P.R.: Subgradient algorithm on Riemannian manifolds. J. Optim. Theory Appl. 97(1), 93–104 (1998)
Martinet, B.: Régularisation d’inéquations variationnelles par approximations successives. Rev. Fr. Inf. Rech. Opér. 4(Ser. R–3), 154–158 (1970)
Rockafellar, R.T.: Monotone operators and the proximal point algorithm. SIAM J. Control Optim. 14(5), 877–898 (1976)
Ferreira, O.P., Oliveira, P.R.: Proximal point algorithm on Riemannian manifolds. Optimization 51(2), 257–270 (2002)
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)
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)
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)
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)
Zhang, H., Sra, S.: First-order methods for geodesically convex optimization. In: JMLR: Workshop and Conference Proceedings 49(1), 1–21 (2016)
Boumal, N., Absil, P.A., Cartis, C.: Global rates of convergence for nonconvex optimization on manifolds. ArXiv e-prints 1(1), 1–31 (2016)
Zhang, H., Reddi, S.J., Sra, S.: Fast stochastic optimization on Riemannian manifolds. ArXiv e-prints pp. 1–17 (2016)
Bačák, M.: The proximal point algorithm in metric spaces. Israel J. Math. 194(2), 689–701 (2013)
do Carmo, M.P.: Riemannian Geometry. Mathematics: Theory & Applications. Birkhäuser Boston, Inc., Boston (1992). Translated from the second Portuguese edition by Francis Flaherty
Sakai, T.: Riemannian Geometry, Translations of Mathematical Monographs, vol. 149. American Mathematical Society, Providence (1996)
Cruz Neto, J.X., Lima, L.L., Oliveira, P.R.: Geodesic algorithms in Riemannian geometry. Balkan J. Geom. Appl. 3(2), 89–100 (1998)
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)
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)
Nesterov, Y.: Introductory Lectures on Convex Optimization, Applied Optimization, vol. 87. Kluwer Academic Publishers, Boston (2004)
Beck, A., Teboulle, M.: A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J. Imaging Sci. 2(1), 183–202 (2009)
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
Corresponding author
Additional information
Communicated by Sándor Zoltán Németh.
Rights and permissions
About this article
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
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10957-017-1093-4