Mathematical  Culture and Thought

Mathematical Culture and Thought

Newton's Optimization Method in Geodesic Spaces

Document Type : Original

Author
Department of Applied Mathematics, Shahid Beheshti University, Iran
Abstract
Many important spaces in data science or engineering problems are nonlinear spaces. Therefore, in recent years, numerical methods for optimizing functions defined on Riemannian manifolds have received much attention and research. On the other hand, geometers such as Alexandrov and Gromov opened a new door to the study of geometric objects by inventing geodesic spaces. These spaces are generalizations of Riemannian manifolds and, among other advantages, they lack the tensor complexities of these manifolds. These spaces contain many crude mathematical objects, including graphs or topological manifolds. In this article, Newton's method for finding the minimum point of a self-concordant function on geodesic metric spaces is presented. One of the important advantages of this type of investigation compared to Newton's method on Riemannian manifolds is the simplicity of the theory and the reduction of the amount of computation. Despite the lack of a smooth structure and tensor algebra on curves, we show, simply by using the concept of "geodesic curve", that Newton's method can be successfully and even more simply designed and implemented on a wide range of common mathematical structures.
Keywords
Subjects

[1] Absil, P. A., Mahony, R., Sepulchre, R., Optimization Algorithms on Matrix Manifolds,
Princeton University Press, Princeton, NJ, 2008.
[2] Ahmadi Kakavandi, B., Amini, M., Duality and subdifferential for convex functions on
complete CAT(0) metric spaces, Nonlinear Anal., 73 (2010), 3450–3455.
[3] Ahmadi Kakavandi, B., Weak topologies in complete CAT(0) metric spaces, Proc. Amer.
Math. Soc., 141 (2013), 1029–1039.
[4] Alexander, S., Kapovitch, V., Petrunin, A., An Invitation to Alexandrov Geometry: CAT(0)
spaces, Springer, Cham, 2019.
[5] Bačák, M., Convex Analysis and Optimization in Hadamard Spaces, De Gruyter, Berlin,
2014.
[6] de A. Bortoloti, M. A., Fernandes, T. A., Ferreira, O. P. Yuan, J., Damped Newton’s
method on Riemannian manifolds, J. Global Optim., 77 (2020), 643–660.
[7] Boyd, S., Vandenberghe, L. , Convex Optimization, Cambridge University Press, Cambridge,
2004.
[8] Bridson, M., Haefliger, A., Metric Spaces of Nonpositive Curvature, Springer, Berlin,
1999.
[9] Burago, D., Burago, Y., Ivanov, S., A Course in Metric Geometry, Amer. Math. Soc.,
Providence, RI, 2001.
[10] Gromov, M., Metric Structures for Riemannian and Non-Riemannian Spaces; reprint of
the 2001 English ed., Birkhäuser Boston, Boston, 2007.
[11] Huang, W., Absil, P. A., Gallivan, K. A., A Riemannian BFGS method for nonconvex optimization
problems, In: Numerical Mathematics and Advanced Applications (ENUMATH
2015), Lecture Notes in Computational Science and Engineering, vol. 112, Springer, Cham,
2016, 627–634.
[12] Fernandes, T. A., Ferreira, O. P., Yuan, J., On the superlinear convergence of Newton’s
method on Riemannian manifolds, J. Optim. Theory Appl., 173 (2017), 828–843.
[13] Ji, H., Optimization approaches on smooth manifolds, Ph.D. thesis, Australian National
University, Canberra, 2007.
[14] Jiang, D., Moore, J. B., Ji, H., Self-concordant functions for optimization on smooth manifolds,
J. Global Optim., 38 (2007), 437–457.
[15] Kirk, W. A., Shahzad, N., Fixed Point Theory in Distance Spaces, Springer, Cham, 2014.
[16] Lott, J., Villani, C., Ricci curvature for metric-measure spaces via optimal transport, Ann.
of Math., 169 (2009), 903–991.
[17] Manton, J. H., A framework for generalising the Newton method and other iterative methods
from Euclidean space to manifolds, Numer. Math., 129 (2015), 91–125.
[18] Nesterov, Y., Nemirovskii, A., Interior-Point Polynomial Algorithms in Convex Programming,
SIAM, Philadelphia, PA, 1994.
[19] Nesterov, Y., Todd, M., On the Riemannian geometry defined by self-concordant barriers
and interior-point methods, Found. Comput. Math., 2 (2002), 333–361.
[20] Papadopoulos, A., Metric Spaces, Convexity and Nonpositive Curvature, European Mathematical
Society, Zürich, 2005.
[21] Perelman, G., Spaces with curvature bounded below, In Proceedings of the International
Congress of Mathematicians (Zürich, 1994), Vol. 1, 2, Birkhäuser, Basel, 1995, 517–525.
[22] Smith, S., Optimization techniques on Riemannian manifolds, Fields Inst. Commun., 3
(1994), 113–146.
[23] Sormani, C., Friedmann cosmology and almost isotropy, Geom. Funct. Anal., 14 (2004),
853–912.
[24] Shalev-Shwartz, S., Ben-David, S., Understanding Machine Learning: From Theory to
Algorithms, Cambridge University Press, New York, 2014.
[25] Udrişte, C., Convex Functions and Optimization Methods on Riemannian Manifolds,
Kluwer Academic Publishers Group, Dordrecht, 1994.

  • Receive Date 20 June 2020
  • Revise Date 13 September 2020
  • Accept Date 17 September 2020
  • Publish Date 20 February 2022