Previous Articles    

ACCELERATED OPTIMIZATION WITH ORTHOGONALITY CONSTRAINTS

Jonathan W. Siegel   

  1. Department of Mathematics, Pennsylvania State University, University Park, PA, USA
  • Received:2018-10-29 Revised:2019-04-11 Published:2021-03-15

Jonathan W. Siegel. ACCELERATED OPTIMIZATION WITH ORTHOGONALITY CONSTRAINTS[J]. Journal of Computational Mathematics, 2021, 39(2): 207-226.

We develop a generalization of Nesterov's accelerated gradient descent method which is designed to deal with orthogonality constraints. To demonstrate the effectiveness of our method, we perform numerical experiments which demonstrate that the number of iterations scales with the square root of the condition number, and also compare with existing state-of-the-art quasi-Newton methods on the Stiefel manifold. Our experiments show that our method outperforms existing state-of-the-art quasi-Newton methods on some large, ill-conditioned problems.

CLC Number: 

[1] P.A. Absil, R. Mahony and R. Sepulchre, Optimization algorithms on matrix manifolds, Princeton University Press, Princeton 2009.
[2] S. Bubeck et al. Convex optimization:Algorithms and complexity, Foundations and Trends R in Machine Learning, 8:3-4(2005), 231-357.
[3] A. Edelman, T. A Arias and S. T Smith, The geometry of algorithms with orthogonality constraints, SIAM journal on Matrix Analysis and Applications, 20:2(1998), 303-353.
[4] W. Huang, K. A Gallivan and P.A. Absil, A Broyden class of quasi-Newton methods for Riemannian optimization, SIAM Journal on Optimization, 25:3(2015), 1660-1685.
[5] W. Huang et al. ROPTLIB:an object-oriented C++ library for optimization on Riemannian manifolds, ACM Transactions on Mathematical Software (TOMS), 44:4(2018), 43.
[6] S. Lang, Fundamentals of differential geometry, Springer Science & Business Media, 191(2012).
[7] Q. H. Lin and L. Xiao, An adaptive accelerated proximal gradient method and its homotopy continuation for sparse optimization, Int. Conference on Machine Learning, (2014), 73-81.
[8] Y.Y. Liu, F.H. Shang, J. Cheng, H. Cheng and L.C. Jiao, Accelerated first-order methods for geodesically convex optimization on Riemannian manifolds, Advances in Neural Information Processing Systems, (2017), 4868-4877.
[9] R. M Martin, Electronic structure:basic theory and practical methods, Cambridge university press, Cambridge 2004.
[10] Y. Nesterov, A method of solving a convex programming problem with convergence rate O (1/k2), Soviet Mathematics Doklady, 27:2(1983), 372-376.
[11] Y. Nesterov, Gradient methods for minimizing composite functions, Mathematical Programming, 140:1(2013), 125-161.
[12] B. O'donoghue and E. Candes, Adaptive restart for accelerated gradient schemes, Foundations of computational mathematics, 15:3(2015), 715-732.
[13] V. Ozolinš et al. Compressed modes for variational problems in mathematics and physics, Proceedings of the National Academy of Sciences, 110:46(2013), 18368-18373.
[14] J. W. Siegel, Accelerated First-Order Optimization with Orthogonality Constraints, Diss. UCLA, 2018.
[15] J. Sherman and W. J Morrison, Adjustment of an inverse matrix corresponding to a change in one element of a given matrix, The Annals of Mathematical Statistics, 21:1(1950), 124-127.
[16] M. D Spivak, A comprehensive introduction to differential geometry, Publish or perish, Berkeley 1970.
[17] W. J. Su, S. Boyd and E. J Candes, A differential equation for modeling Nesterov's accelerated gradient method:theory and insights, Journal of Machine Learning Research, 17:153(2016), 1-43.
[18] Z. W. Wen and W. T. Yin, A feasible method for optimization with orthogonality constraints, Mathematical Programming, 142:1-2(2013), 397-434.
[19] S. T. Yau, Non-existence of continuous convex functions on certain Riemannian manifolds, Mathematische Annalen, 207:4(1974), 269-270.
[20] H. Y. Zhang and S. Sra, Towards Riemannian Accelerated Gradient Methods, arXiv preprint arXiv:1806.02812, 2018.
[21] X. Zhang, J. W. Zhu, Z. W. Wen, A. H. Zhou Gradient type optimization methods for electronic structure calculations, SIAM Journal on Scientific Computing, 36:3(2014), C265-C289.
[22] X. J. Zhu, A Riemannian conjugate gradient method for optimization on the Stiefel manifold, Computational Optimization and Applications, 67:1(2017), 73-110.
[23] R. Zimmermann, A matrix-algebraic algorithm for the Riemannian logarithm on the Stiefel manifold under the canonical metric, SIAM Journal on Matrix Analysis and Applications, 38:2(2017), 322-342.
[1] Zhenyue Zhang , Yuyang Qiu , Keqin Du . CONDITIONS FOR OPTIMAL SOLUTIONS OF UNBALANCED PROCRUSTES PROBLEM ON STIEFEL MANIFOLD [J]. Journal of Computational Mathematics, 2007, 25(6): 661-671.
Viewed
Full text


Abstract