Abstract
Extension of concepts and techniques of linear spaces for the Riemannian setting has been frequently attempted. One reason for the extension of such techniques is the possibility to transform some Euclidean non-convex or quasi-convex problems into Riemannian convex problems. In this paper, a version of Kantorovich’s theorem on Newton’s method for finding a singularity of differentiable vector fields defined on a complete Riemannian manifold is presented. In the presented analysis, the classical Lipschitz condition is relaxed using a general majorant function, which enables us to not only establish the existence and uniqueness of the solution but also unify earlier results related to Newton’s method. Moreover, a ball is prescribed around the points satisfying Kantorovich’s assumptions and convergence of the method is ensured for any starting point within this ball. In addition, some bounds for the Q-quadratic convergence of the method, which depends on the majorant function, are obtained.
Similar content being viewed by others
References
Absil, P.-A., Amodei, L., Meyer, G.: Two Newton methods on the manifold of fixed-rank matrices endowed with Riemannian quotient geometries. Comput. Stat. 29(3–4), 569–590 (2014)
Adler, R.L., Dedieu, J.-P., Margulies, J.Y., Martens, M., Shub, M.: Newton’s method on Riemannian manifolds and a geometric model for the human spine. IMA J. Numer. Anal. 22(3), 359–390 (2002)
Alvarez, F., Bolte, J., Munier, J.: A unifying local convergence result for Newton’s method in Riemannian manifolds. Found. Comput. Math. 8(2), 197–226 (2008)
Amat, S., Busquier, S., Castro, R., Plaza, S.: Third-order methods on Riemannian manifolds under Kantorovich conditions. J. Comput. Appl. Math. 255, 106–121 (2014)
Argyros, I.K.: An improved unifying convergence analysis of Newton’s method in Riemannian manifolds. J. Appl. Math. Comput. 25(1–2), 345–351 (2007)
Argyros, I.K., Hilout, S.: Newton’s method for approximating zeros of vector fields on Riemannian manifolds. J. Appl. Math. Comput. 29(1–2), 417–427 (2009)
Argyros, I.K., Magreñán, Á.A.: Extending the applicability of Gauss-Newton method for convex composite optimization on Riemannian manifolds. Appl. Math. Comput. 249, 453–467 (2014)
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)
Blum, L., Cucker, F., Shub, M., Smale, S.: Complexity and real computation. Springer, New York (1998). With a foreword by Richard M. Karp
Da 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. Global Optim. 35(1), 53–69 (2006)
Dedieu, J.-P., Priouret, P., Malajovich, G.: Newton’s method on Riemannian manifolds: convariant alpha theory. IMA J. Numer. Anal. 23(3), 395–419 (2003)
Dedieu, J.-P., Shub, M.: Multihomogeneous Newton methods. Math. Comp. 69(231), 1071–1098 (2000). (electronic)
do Carmo, M.P.: Riemannian geometry. Mathematics: Theory & Applications (Translated from the second Portuguese edition by Francis Flaherty). Birkhäuser Boston, Inc., Boston (1992)
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)
Ferreira, O.P., Gonçalves, M.L.N., Oliveira, P.R.: Convergence of the Gauss-Newton method for convex composite optimization under a majorant condition. SIAM J. Optim. 23(3), 1757–1783 (2013)
Ferreira, O.P., Silva, R.C.M.: Local convergence of Newton’s method under a majorant condition in Riemannian manifolds. IMA J. Numer. Anal. 32(4), 1696–1713 (2012)
Ferreira, O.P., Svaiter, B.F.: Kantorovich’s theorem on Newton’s method in Riemannian manifolds. J. Complexity 18(1), 304–329 (2002)
Ferreira, O.P., Svaiter, B.F.: Kantorovich’s majorants principle for Newton’s method. Comput. Optim. Appl. 42(2), 213–229 (2009)
Ferreira, O.P., Svaiter, B.F.: A robust Kantorovich’s theorem on the inexact Newton method with relative residual error tolerance. J. Complex. 28(3), 346–363 (2012)
Gabay, D.: Minimizing a differentiable function over a differential manifold. J. Optim. Theory Appl. 37(2), 177–219 (1982)
Hamilton, R.S.: The inverse function theorem of Nash and Moser. Bull. Am. Math. Soc. (N.S.) 7(1), 65–222 (1982)
Hiriart-Urruty, J.-B., Lemaréchal, C.: Convex Analysis and Minimization Algorithms: Fundamentals. I. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 305. Springer, Berlin (1993)
Karmarkar, N.: Riemannian geometry underlying interior-point methods for linear programming. In: Lagaries, J.C., Todd, M.J. (eds.) Contemporary Mathematics. Mathematical developments arising from linear programming, vol. 114, pp. 51–75. American Mathematical Society, Providence (1990)
Krantz, S.G., Parks, H.R.: The Implicit Function Theorem: History, Theory, and Applications. Modern Birkhäuser Classics. Birkhäuser/Springer, New York, Reprint of the 2003 edition (2013)
Lang, S.: Differential and Riemannian Manifolds vol. 160 of Graduate Texts in Mathematics, 3rd edn. Springer, New York (1995)
Li, C., Wang, J.: Newton’s method on Riemannian manifolds: Smale’s point estimate theory under the \(\gamma \)-condition. IMA J. Numer. Anal. 26(2), 228–251 (2006)
Li, C., Wang, J.: Newton’s method for sections on Riemannian manifolds: generalized covariant \(\alpha \)-theory. J. Complexity 24(3), 423–451 (2008)
Li, C., Wang, J.-H., Dedieu, J.-P.: Smale’s point estimate theory for Newton’s method on Lie groups. J. Complex. 25(2), 128–151 (2009)
Manton, J.H.: A framework for generalising the Newton method and other iterative methods from Euclidean space to manifolds. Numer. Math. 129(1), 91–125 (2015)
Miller, S.A., Malick, J.: Newton methods for nonsmooth convex minimization: connections among U-Lagrangian, Riemannian Newton and SQP methods. Math. Program. 104((2–3, Ser. B)), 609–633 (2005)
Moser, J.: A new technique for the construction of solutions of nonlinear differential equations. Proc. Nat. Acad. Sci. USA. 47, 1824–1831 (1961)
Nash, J.: The imbedding problem for Riemannian manifolds. Ann. Math. 2(63), 20–63 (1956)
Nesterov, Y., Nemirovskii, A.: Interior-point Polynomial Algorithms in Convex Programming. SIAM Studies in Applied Mathematics, vol. 13. Society for Industrial and Applied Mathematics (SIAM), Philadelphia (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)
Owren, B., Welfert, B.: The Newton iteration on Lie groups. BIT 40(1), 121–145 (2000)
Rapcsák, T.: Smooth Nonlinear Optimization in \({ R}^n\). Nonconvex Optimization and its Applications, vol. 19. Kluwer Academic Publishers, Dordrecht (1997)
Ring, W., Wirth, B.: Optimization methods on Riemannian manifolds and their application to shape space. SIAM J. Optim. 22(2), 596–627 (2012)
Schulz, V.H.: A Riemannian view on shape optimization. Found. Comput. Math. 14(3), 483–501 (2014)
Shub, M.: Some remarks on dynamical systems and numerical analysis. In: Lava-Carrero, L., Lewowicz J. (eds.) Dynamical Systems and Partial Differential Equations, pp. 69–91. Universidad Simon Bolivar, Caracas (1986)
Smale, S.: Newton’s method estimates from data at one point. In: Ewing, R.E., Gross, K.I., Martin, C.F. (eds.) The Merging of Disciplines: New Directions in Pure, Applied, and Computational Mathematics, pp. 185–196. Springer, New York (1986)
Smith, S.T.: Optimization techniques on Riemannian manifolds. In: Bloch, A. (ed.) Fields Institute Communications. Hamiltonian and Gradient Flows, Algorithms and Control, vol. 3, pp. 113–136. American Mathematical Society, Providence (1994)
Udrişte, C.: Convex Functions and Optimization Methods on Riemannian Manifolds. Mathematics and its Applications, vol. 297. Kluwer Academic Publishers Group, Dordrecht (1994)
Wang, J.H.: Convergence of Newton’s method for sections on Riemannian manifolds. J. Optim. Theory Appl. 148(1), 125–145 (2011)
Wang, J.-H., Huang, S., Li, C.: Extended Newton’s method for mappings on Riemannian manifolds with values in a cone. Taiwan. J. Math. 13(2B), 633–656 (2009)
Wang, J.-H., Yao, J.-C., Li, C.: Gauss-Newton method for convex composite optimizations on Riemannian manifolds. J. Global Optim. 53(1), 5–28 (2012)
Wayne, C.E.: An introduction to KAM theory. In: Wayne,C.E., Levermore C.D. (eds.) Lectures in Applied Mathematics. Dynamical Systems and Probabilistic Methods in Partial Differential Equations, vol. 31, pp. 3–29. American Mathematical Society, Providence (1996)
Wen, Z., Yin, W.: A feasible method for optimization with orthogonality constraints. Math. Program. 142(1–2, Ser. A), 397–434 (2013)
Zabrejko, P.P., Nguen, D.F.: The majorant method in the theory of Newton-Kantorovich approximations and the Pták error estimates. Numer. Funct. Anal. Optim. 9(5–6), 671–684 (1987)
Zhang, L.-H.: Riemannian Newton method for the multivariate eigenvalue problem. SIAM J. Matrix Anal. Appl. 31(5), 2972–2996 (2010)
Acknowledgments
Funding was provided by Fundação de Apoio a Pesquisa do Estado de Goiás (Grant No. 201210267000909-05/2012), CNPq (Grant No 305158/2014-7), CAPES.
Author information
Authors and Affiliations
Corresponding author
Additional information
This work was supported by PRONEX-Optimization (FAPERJ/CNPq), CNPq 305158/2014-7, FAPEG, CAPES.
Rights and permissions
About this article
Cite this article
Bittencourt, T., Ferreira, O.P. Kantorovich’s theorem on Newton’s method under majorant condition in Riemannian manifolds. J Glob Optim 68, 387–411 (2017). https://doi.org/10.1007/s10898-016-0472-y
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10898-016-0472-y