Enlarging the convergence ball of Newton's method on Lie groups
DOI:
https://doi.org/10.33993/jnaat441-1051Keywords:
Newton's method, Lie group, Lie algebra, Riemannian manifold, convergence ball, Kantorovich hypothesisAbstract
We present a local convergence analysis of Newton's method for approximating a zero of a mapping from a Lie group into its Lie algebra. Using more precise estimates than before [55, 56] and under the same computational cost, we obtain a larger convergence ball and more precise error bounds on the distances involved. Some examples are presented to further validate the theoretical results.
Downloads
References
P.A. Absil, C.G. Baker and K.A. Gallivan, Trust-region methods on Riemannian manifolds, Found. Comput. Math., 7 (2007), pp. 303-330. http://doi.org/10.1007/s10208-005-0179-9 DOI: https://doi.org/10.1007/s10208-005-0179-9
R.L. Adler, J.P. Dedieu, J.Y. Margulies, M. Martens and M. Shub, Newton'smethod on Riemannian manifolds and a geometric model for the human spine, IMA J. Numer. Anal., 22 (2002), pp. 359-390. http://doi.org/10.1093/imanum/22.3.359 DOI: https://doi.org/10.1093/imanum/22.3.359
F. Alvarez, J. Bolte and J.A. Munier, A unifying local convergence result for Newton's method in Riemannian manifolds, Found. Comput. Math., 8 (2008), pp. 197-226. http://doi.org/10.1007/s10208-006-0221-6 DOI: https://doi.org/10.1007/s10208-006-0221-6
I.K. Argyros, ,An improved unifying convergence analysis of Newton's method in Riemannian manifolds, J. Appl. Math. Comput., 25 (2007), pp. 345-351. http://doi.org/10.1007/BF02832359 DOI: https://doi.org/10.1007/BF02832359
I.K. Argyros, On the local convergence of Newton's method on Lie groups, Pan Amer. Math. J., 17 (2007), pp. 101-109.
I.K. Argyros, A Kantorovich analysis of Newton's method on Lie groups, J. Concrete Appl. Anal., 6 (2008), pp. 21-32.
I.K. Argyros, Convergence and Applications of Newton-type Iterations, Springer Verlag Publ., New York, 2008. http://doi.org/10.1007/978-0-387-72743-1 DOI: https://doi.org/10.1007/978-0-387-72743-1
I.K. Argyros, Newton's method in Riemannian manifolds, Rev. Anal. Numer. Theor. Approx., 37 (2008), pp. 119-125. http://ictp.acad.ro/jnaat/journal/article/view/2008-vol37-no2-art3
I.K. Argyros, Newton's method on Lie groups, J. Appl. Math. Comput., 31 (2009), pp. 217-228, https://doi.org/10.1007/s12190-008-0203-8 DOI: https://doi.org/10.1007/s12190-008-0203-8
I.K. Argyros, A semilocal convergence analysis for directional Newton methods, Math. Comp., 80 (2011), pp. 327-343. http://doi.org/10.1090/S0025-5718-2010-02398-1 DOI: https://doi.org/10.1090/S0025-5718-2010-02398-1
I.K. Argyros, Y.J. Cho S. and Hilout, Numerical methods for equations and its applications, CRC Press/Taylor and Francis Group, New-York, 2012. DOI: https://doi.org/10.1201/b12297
I.K. Argyros and S. Hilout, Newton's method for approximating zeros of vector fields on Riemannian manifolds, J. Appl. Math. Comput., 29 (2009), pp. 417-427. http://doi.org/10.1007/s12190-008-0142-4 DOI: https://doi.org/10.1007/s12190-008-0142-4
I.K. Argyros and S. Hilout, Extending the Newton-Kantorovich hypothesis for solving equations, J. Comput. Appl. Math., 234 (2010), pp. 2993-3006. http://doi.org/10.1016/j.cam.2010.04.014 DOI: https://doi.org/10.1016/j.cam.2010.04.014
I.K. Argyrosand S. Hilout, Weaker conditions for the convergence of Newton's method, J. Complexity, 28 (2012), pp. 364-387. http://doi.org/10.1016/j.jco.2011.12.003 DOI: https://doi.org/10.1016/j.jco.2011.12.003
I.K. Argyros and S. Hilout, Extending the applicability of Newton's method on Lie groups, Appl. Math. Comput., to appear, https://doi.org/10.1016/j.amc.2013.04.007 DOI: https://doi.org/10.1016/j.amc.2013.04.007
I.K. Argyros and S. Hilout, Numerical methods in nonlinear analysis, World Scientific Publ., ISBN-13: 978-9814405829, to appear.
D.A. Bayer and J.C. Lagarias, The nonlinear geometry of linear programming. I. Affine and projective scaling trajectories, Trans. Amer. Math. Soc., 314 (1989), pp. 499-526. http://doi.org/10.1090/S0002-9947-1989-1005525-6 DOI: https://doi.org/10.2307/2001396
R.W. Brockett, Differential geometry and the design of gradient algorithms. Differential geometry: partial differential equations on manifolds (Los Angeles, CA, 1990), pp. 69-92, Proc. Sympos. Pure Math., 54, Part 1, Amer. Math. Soc., Providence, RI,1993. DOI: https://doi.org/10.1090/pspum/054.1/1216576
M.T. Chu and K.R. Driessel, The projected gradient method for least squares matrix approximations with spectral constraints, SIAM J. Numer. Anal., 27 (1990), pp. 1050-1060. http://doi.org/10.1137/0727062 DOI: https://doi.org/10.1137/0727062
J.P. Dedieu, P. Priouret and G. Malajovich, Newton's method on Riemannian manifolds: Convariant α theory, IMA J. Numer. Anal., 23 (2003), pp. 395-419. http://doi.org/10.1093/imanum/23.3.395 DOI: https://doi.org/10.1093/imanum/23.3.395
M.P. Do Carmo, Riemannian Geometry, Boston, Birkhauser, 1992. DOI: https://doi.org/10.1007/978-1-4757-2201-7
A. Edelman, T.A. Arias and S.T. Smith, The geometry of algorithms with orthogonality constraints, SIAM J. Matrix Anal. Appl., 20 (1999), pp. 303-353. http://doi.org/10.1137/S0895479895290954 DOI: https://doi.org/10.1137/S0895479895290954
J.A. Ezquerro and M.A. Hernandez, Generalized differentiability conditions for Newton's method, IMA J. Numer. Anal., 22 (2002), pp. 187-205. http://doi.org/10.1093/imanum/22.2.187 DOI: https://doi.org/10.1093/imanum/22.2.187
J.A. Ezquerro and M.A. Hernández, On an application of Newton's method to nonlinear operators with ω-conditioned second derivative, BIT,42(2002), pp. 519-530, https://doi.org/10.1023/A:1021977126075 DOI: https://doi.org/10.1023/A:1021977126075
O.P. Ferreira and B.F. Svaiter, Kantorovich's theorem on Newton's method in Reimannian manifolds, J. Complexity, 18 (2002), pp. 304-329. http://doi.org/10.1006/jcom.2001.0582 DOI: https://doi.org/10.1006/jcom.2001.0582
D. Gabay, Minimizing a differentiable function over a differential manifold, J. Optim. Theory Appl., 37 (1982), pp. 177-219. http://doi.org/10.1007/BF00934767 DOI: https://doi.org/10.1007/BF00934767
J.M Gutíerrez and M.A. Hernandez, M.A., Newton's method under weak Kantorovich conditions, IMA J. Numer. Anal., 20 (2000), pp. 521-532. http://doi.org/10.1093/imanum/20.4.521 DOI: https://doi.org/10.1093/imanum/20.4.521
B.C. Hall, Lie groups, Lie algebras and representations. An elementary introduction, Graduate Texts in Mathematics, 222, Springer-Verlag, New York, 2003. DOI: https://doi.org/10.1007/978-0-387-21554-9
S. Helgason, Differential geometry, Lie groups and symmetric spaces, Pure and Applied Mathematics, 80, Academic Press, Inc. Harcourt Brace Jovanovich, Publishers, New York-London, 1978.
U. Helmke and J.B. Moore, Singular-value decomposition via gradient and self-equivalent flows, Linear Algebra Appl., 169 (1992), pp. 223-248. http://doi.org/10.1016/0024-3795(92)90180-I DOI: https://doi.org/10.1016/0024-3795(92)90180-I
U. Helmke and J.,B. Moore, Optimization and dynamical systems. With a foreword by R. Brockett, Communications and Control Engineering Series. Springer-Verlag, London, Ltd., London, 1994.
L.V. Kantorovich and Akilov G.P., Functional analysis in normed spaces, Pergamon Press, New York, 1982. DOI: https://doi.org/10.1016/B978-0-08-023036-8.50010-2
C.L. Li, G. Lopez and V. Martiń-Marquez, Monotone vector fields and the proximal point algorithm on Hadamard manifolds, J. Lond. Math. Soc., (2) 79(2009), pp. 663-683. http://doi.org/10.1112/jlms/jdn087 DOI: https://doi.org/10.1112/jlms/jdn087
C. Li and J.H. Wang, ,Convergence of the Newton method and uniqueness of zeros of vector fields on Riemannian manifolds, Sci. China Ser. A, 48 (2005), pp. 1465-1478. http://doi.org/10.1360/04ys0147 DOI: https://doi.org/10.1360/04ys0147
C. Li and J.H. Wang, Newton's method on Riemannian manifolds: Smale's point estimate theory under the γ-condition, IMA J. Numer. Anal.,26(2006), pp. 228-251. http://doi.org/10.1093/imanum/dri039 DOI: https://doi.org/10.1093/imanum/dri039
C. Li, J.H. Wang and J.P. Dedieu, Smale's point estimate theory for Newton's method on Lie groups, J. Complexity, 25 (2009), pp. 128-151. http://doi.org/10.1016/j.jco.2008.11.001 DOI: https://doi.org/10.1016/j.jco.2008.11.001
P.D. Proinov, General local convergence theory for a class of iterative processes and its applications to Newton's method, J. Complexity, 25 (2009), pp. 38-62. http://doi.org/10.1016/j.jco.2008.05.006 DOI: https://doi.org/10.1016/j.jco.2008.05.006
D.G. Luenberger, The gradient projection method along geodesics, Management Sci., 18 (1972), pp. 620-631, https://doi.org/10.1287/mnsc.18.11.620 DOI: https://doi.org/10.1287/mnsc.18.11.620
R.E. Mahony, Optimization algorithms on homogeneous spaces: with applications in linear systems theory, Ph.D. Thesis, Department of Systems Engineering, University of Canberra, Australia, 1994.
R.E. Mahony, The constrained Newton method on a Lie group and the symmetric eigenvalue problem, Linear Algebra Appl., 248 (1996), pp. 67-89. http://doi.org/10.1016/0024-3795(95)00171-9 DOI: https://doi.org/10.1016/0024-3795(95)00171-9
R.E. Mahony, U. Helmke and J.B. Moore, Pole placement algorithms for symmetric realisations, Proceedings of 32nd IEEE Conference on Decision and Control, San Antonio, TX, 1993, pp. 355-1358.
J.B. Moore, R.E. Mahony and U. Helmke, Numerical gradient algorithms for eigenvalue and singular value calculations, SIAM J. Matrix Anal. Appl., 15 (1994), pp. 881-902. http://doi.org/10.1137/S0036141092229732 DOI: https://doi.org/10.1137/S0036141092229732
B. Owren and B. Welfert, The Newton iteration on Lie groups, BIT, 40(2000), pp. 121-145. http://doi.org/10.1023/A:1022322503301 DOI: https://doi.org/10.1023/A:1022322503301
P.D. Proinov, New general convergence theory for iterative processes and its applications to Newton-Kantorovich type theorems, J. Complexity, 26 (2010), pp. 3-42. http://doi.org/10.1016/j.jco.2009.05.001 DOI: https://doi.org/10.1016/j.jco.2009.05.001
W.C. Rheinboldt, An adaptive continuation process for solving system of nonlinear equations, Banach Center Publ., 3 (1977), pp. 129-142. DOI: https://doi.org/10.4064/-3-1-129-142
M. Shub and S. Smale, Complexity of Bezout's theorem. I. Geometric aspects, J. Amer. Math. Soc., 6 (1993), pp. 459-501. http://doi.org/10.1090/S0894-0347-1993-1175980-4 DOI: https://doi.org/10.1090/S0894-0347-1993-1175980-4
S. Smale, Newton's method estimates from data at a point, The merging of disciplines: New directions in Pure, Applied and Computational Mathematics, R. Ewing, K. Grossand C. Martin eds, New-York, Springer Verlag Publ., (1986), pp. 185-196. DOI: https://doi.org/10.1007/978-1-4612-4984-9_13
S.T. Smith, Dynamical systems that perform the singular value decomposition, Systems Control Lett., 16 (1991), pp. 319-327. http://doi.org/10.1016/0167-6911(91)90053-H DOI: https://doi.org/10.1016/0167-6911(91)90053-H
S.T. Smith, S.T. Smith, Geometric optimization methods for adaptive filtering, Thesis (Ph.D.)-Harvard University, ProQuest LLC, Ann Arbor, MI, 1993.
S. T. Smith, S.T. Smith, Optimization techniques on Riemannian manifolds, Hamiltonian and gradient flows, algorithms and control, Fields Inst. Commun., 3, Amer. Math. Soc., Providence, RI, 1994, pp. 113-136. DOI: https://doi.org/10.1090/fic/003/09
J.F. Traub and H. Wozniakowski, Convergence and complexity of Newton iteration for operator equations, J. Assoc. Comput. Mach., 26 (1979), pp. 250-258. http://doi.org/10.1145/322123.322130 DOI: https://doi.org/10.1145/322123.322130
C. Udriste, Convex functions and optimization methods on Riemannian manifolds, Mathematics and its Applications, 297, Kluwer Academic Publishers Group, Dordrecht,1994. DOI: https://doi.org/10.1007/978-94-015-8390-9_3
V.S. Varadarajan, Lie groups, Lie algebras and their representations, Reprint of the 1974 edition. Graduate Texts in Mathematics,102, Springer-Verlag, New York, 1984. DOI: https://doi.org/10.1007/978-1-4612-1126-6
J.H. Wang and C. Li, Uniqueness of the singular points of vector fields on Riemannian manifolds under the γ-condition, J. Complexity, 22 (2006), pp. 533-548. http://doi.org/10.1016/j.jco.2005.11.004 DOI: https://doi.org/10.1016/j.jco.2005.11.004
J.H. Wang and C. Li, Kantorovich's theorem for Newton's method on Lie groups, J. Zheijiang Univ. Sci. A, 8(2007), pp. 978-986. http://doi.org/10.1631/jzus.2007.A0978 DOI: https://doi.org/10.1631/jzus.2007.A0978
J.H. Wang and C. Li, Kantorovich's theorems for Newton's method for mappings and optimization problems on Lie groups, IMA J. Numer. Anal., 31 (2011), pp. 322-347. http://doi.org/10.1093/imanum/drp015 DOI: https://doi.org/10.1093/imanum/drp015
X.H. Wang,Convergence of Newton's method and uniqueness of the solution of equations in Banach space, IMA J. Numer. Anal., 20 (2000), pp. 123-134. http://doi.org/10.1093/imanum/20.1.123 DOI: https://doi.org/10.1093/imanum/20.1.123
P.P. Zabrejko and D.F. Nguen, The majorant method in the theory of Newton-Kantorovich approximations and the Ptak error estimates, Numer. Funct. Anal. Optim., 9 (1987), pp. 671-684. http://doi.org/10.1080/01630568708816254 DOI: https://doi.org/10.1080/01630568708816254
Published
How to Cite
Issue
Section
License
Copyright (c) 2015 Journal of Numerical Analysis and Approximation Theory
This work is licensed under a Creative Commons Attribution 4.0 International License.
Open Access. This article is distributed under the terms of the Creative Commons Attribution 4.0 International License, which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
