×

Adaptive quadratically regularized Newton method for Riemannian optimization. (English) Zbl 1415.65139

Summary: Optimization on Riemannian manifolds widely arises in eigenvalue computation, density functional theory, Bose-Einstein condensates, low rank nearest correlation, image registration, signal processing, and so on. We propose an adaptive quadratically regularized Newton method which approximates the original objective function by the second-order Taylor expansion in Euclidean space but keeps the Riemannian manifold constraints. The regularization term in the objective function of the subproblem enables us to utilize a Cauchy-point-like condition as the standard trust-region method for proving global convergence. The subproblem can be solved inexactly either by first-order methods or by performing corresponding Riemannian Newton-type steps. In the latter case, we can further take advantage of negative curvature directions. Both global convergence and superlinear local convergence are guaranteed under mild conditions. Extensive computational experiments and comparisons with other state-of-the-art methods indicate that the proposed algorithm is very promising.

MSC:

65K05 Numerical mathematical programming methods
90C26 Nonconvex programming, global optimization
90C55 Methods of successive quadratic programming type
65F15 Numerical computation of eigenvalues and eigenvectors of matrices

References:

[1] P.-A. Absil, C. G. Baker, and K. A. Gallivan, Trust-region methods on Riemannian manifolds, Found. Comput. Math., 7 (2007), pp. 303–330. · Zbl 1129.65045
[2] P.-A. Absil, R. Mahony, and R. Sepulchre, Optimization Algorithms on Matrix Manifolds, Princeton University Press, Princeton, NJ, 2008. · Zbl 1147.65043
[3] P.-A. Absil, R. Mahony, and J. Trumpf, An extrinsic look at the Riemannian Hessian, in Geometric Science of Information, Springer, New York, 2013, pp. 361–368. · Zbl 1323.53014
[4] P.-A. Absil and J. Malick, Projection-like retractions on matrix manifolds, SIAM J. Optim., 22 (2012), pp. 135–158. · Zbl 1248.49055
[5] N. Agarwal, Z. Allen-Zhu, B. Bullins, E. Hazan, and T. Ma, Finding approximate local minima faster than gradient descent, in Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, ACM, New York, 2017, pp. 1195–1199. · Zbl 1369.68290
[6] E. Birgin and J. Mart\inez, The use of quadratic regularization with a cubic descent condition for unconstrained optimization, SIAM J. Optim., 27 (2017), pp. 1049–1074. · Zbl 1370.90260
[7] N. Boumal, P.-A. Absil, and C. Cartis, Global rates of convergence for nonconvex optimization on manifolds, IMA J. Numer. Anal., 00 (2018), pp. 1–33.
[8] N. Boumal, B. Mishra, P.-A. Absil, and R. Sepulchre, Manopt, a Matlab toolbox for optimization on manifolds, J. Mach. Learn. Res., 15 (2014), pp. 1455–1459, . · Zbl 1319.90003
[9] R. H. Byrd, J. Nocedal, and F. Oztoprak, An inexact successive quadratic approximation method for L-1 regularized optimization, Math. Program., 157 (2016), pp. 375–396. · Zbl 1342.49037
[10] Y. Carmon, J. C. Duchi, O. Hinder, and A. Sidford, Accelerated Methods for Non-Convex Optimization, preprint, , 2016. · Zbl 1400.90250
[11] C. Cartis, N. I. M. Gould, and P. L. Toint, Adaptive cubic regularisation methods for unconstrained optimization. Part I: Motivation, convergence and numerical results, Math. Program., 127 (2011), pp. 245–295. · Zbl 1229.90192
[12] H. Chen, Y. Sun, J. Gao, Y. Hu, and B. Yin, Fast optimization algorithm on Riemannian manifolds and its application in low-rank learning, Neurocomputing, 291 (2018), pp. 59–70.
[13] F. E. Curtis and D. P. Robinson, Exploiting Negative Curvature in Deterministic and Stochastic Optimization, preprint, , 2017.
[14] J. Duchi, E. Hazan, and Y. Singer, Adaptive subgradient methods for online learning and stochastic optimization, J. Mach. Learn. Res., 12 (2011), pp. 2121–2159. · Zbl 1280.68164
[15] A. Edelman, T. A. Arias, and S. T. Smith, The geometry of algorithms with orthogonality constraints, SIAM J. Matrix Anal. Appl., 20 (1998), pp. 303–353. · Zbl 0928.65050
[16] D. Gabay, Minimizing a differentiable function over a differential manifold, J. Optim. Theory Appl., 37 (1982), pp. 177–219. · Zbl 0458.90060
[17] B. Gao, X. Liu, X. Chen, and Y. Yuan, A new first-order framework for orthogonal constrained optimization problems, SIAM J. Optim., 28 (2018), pp. 302–332. · Zbl 1382.65171
[18] N. I. M. Gould, S. Lucidi, M. Roma, and P. L. Toint, Exploiting negative curvature directions in linesearch methods for unconstrained optimization, Optim. Methods Softw., 14 (2000), pp. 75–98. · Zbl 0988.90039
[19] W. Huang, P.-A. Absil, and K. A. Gallivan, A Riemannian symmetric rank-one trust-region method, Math. Program., 150 (2015), pp. 179–216. · Zbl 1314.65083
[20] W. Huang, P.-A. Absil, and K. A. Gallivan, A Riemannian BFGS method for nonconvex optimization problems, in Numerical Mathematics and Advanced Applications ENUMATH 2015, Springer, New York, 2016, pp. 627–634. · Zbl 1352.65153
[21] W. Huang, P.-A. Absil, K. A. Gallivan, and P. Hand, ROPTLIB: An Object-Oriented C++ Library for Optimization on Riemannian Manifolds, Technical report FSU16-14.v2, Florida State University, Tallahassee, 2016.
[22] W. Huang, K. A. Gallivan, and P.-A. Absil, A Broyden class of quasi-Newton methods for Riemannian optimization, SIAM J. Optim., 25 (2015), pp. 1660–1685. · Zbl 1461.65156
[23] B. Iannazzo and M. Porcelli, The Riemannian Barzilai-Borwein method with nonmonotone line search and the matrix geometric mean computation, IMA J. Numer. Anal., 38 (2018), pp. 495–517. · Zbl 1477.65096
[24] B. Jiang and Y.-H. Dai, A framework of constraint preserving update schemes for optimization on Stiefel manifold, Math. Program., 153 (2015), pp. 535–575. · Zbl 1325.49037
[25] E. W. Karas, S. A. Santos, and B. F. Svaiter, Algebraic rules for quadratic regularization of Newton method, Comput. Optim. Appl., 60 (2015), pp. 343–376. · Zbl 1309.90102
[26] D. Kressner, M. Steinlechner, and B. Vandereycken, Low-rank tensor completion by Riemannian optimization, BIT Numer. Math., 54 (2014), pp. 447–468. · Zbl 1300.65040
[27] K. Kreutz-Delgado, The Complex Gradient Operator and the CR-Calculus, , 2009.
[28] J. D. Lee, Y. Sun, and M. A. Saunders, Proximal Newton-type methods for minimizing composite functions, SIAM J. Optim., 24 (2014), pp. 1420–1443. · Zbl 1306.65213
[29] J. Nocedal and S. J. Wright, Numerical Optimization, 2nd ed., Springer Series in Operations Research and Financial Engineering, Springer, New York, 2006. · Zbl 1104.65059
[30] S. Paternain, A. Mokhtari, and A. Ribeiro, A Second Order Method for Nonconvex Optimization, preprint, , 2017.
[31] C. Qi, Numerical optimization methods on Riemannian manifolds, Ph.D. dissertation, Florida State University, Tallahassee, 2011.
[32] W. Ring and B. Wirth, Optimization methods on Riemannian manifolds and their application to shape space, SIAM J. Optim., 22 (2012), pp. 596–627. · Zbl 1250.90111
[33] S. T. Smith, Optimization techniques on Riemannian manifolds, Fields Inst. Commun., 3 (1994), pp. 113–136. · Zbl 0816.49032
[34] T. Steihaug, The conjugate gradient method and trust regions in large scale optimization, SIAM J. Numer. Anal., 20 (1983), pp. 626–637. · Zbl 0518.65042
[35] C. Udriste, Convex Functions and Optimization Methods on Riemannian Manifolds, Vol. 297, Springer Science & Business Media, New York, 1994. · Zbl 0932.53003
[36] M. Ulbrich, Z. Wen, C. Yang, D. Klöckner, and Z. Lu, A proximal gradient method for ensemble density functional theory, SIAM J. Sci. Comput., 37 (2015), pp. A1975–A2002. · Zbl 1325.65095
[37] B. Vandereycken, Low-rank matrix completion by Riemannian optimization, SIAM J. Optim., 23 (2013), pp. 1214–1236. · Zbl 1277.15021
[38] Z. Wen, A. Milzarek, M. Ulbrich, and H. Zhang, Adaptive regularized self-consistent field iteration with exact Hessian for electronic structure calculation, SIAM J. Sci. Comput., 35 (2013), pp. A1299–A1324. · Zbl 1273.82004
[39] Z. Wen and W. Yin, A feasible method for optimization with orthogonality constraints, Math. Program., 142 (2013), pp. 397–434. · Zbl 1281.49030
[40] X. Wu, Z. Wen, and W. Bao, A regularized Newton method for computing ground states of Bose-Einstein condensates, J. Sci. Comput., 73 (2017), pp. 303–329. · Zbl 1433.82025
[41] C. Yang, J. C. Meza, B. Lee, and L.-W. Wang, KSSOLV—A MATLAB toolbox for solving the Kohn-Sham equations, ACM Trans. Math. Softw., 36 (2009), pp. 1–35. · Zbl 1364.65112
[42] W. H. Yang, L.-H. Zhang, and R. Song, Optimality conditions for the nonlinear programming problems on Riemannian manifolds, Pacific J. Optim., 10 (2014), pp. 415–434. · Zbl 1322.90096
[43] Y. Yang, Globally convergent optimization algorithms on Riemannian manifolds: Uniform framework for unconstrained and constrained optimization, J. Optim. Theory Appl., 132 (2007), pp. 245–265. · Zbl 1153.90017
[44] H. Zhang and W. W. Hager, A nonmonotone line search technique and its application to unconstrained optimization, SIAM J. Optim., 14 (2004), pp. 1043–1056. · Zbl 1073.90024
[45] X. Zhang, J. Zhu, Z. Wen, and A. Zhou, Gradient type optimization methods for electronic structure calculations, SIAM J. Sci. Comput., 36 (2014), pp. C265–C289. · Zbl 1300.82006
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.