A Riemannian symmetric rank-one trust-region method

详细信息    查看全文

• 作者：Wen Huang ; P.-A. Absil ; K. A. Gallivan
• 关键词：Riemannian optimization ; Optimization on manifolds ; Symmetric rank ; one update ; Rayleigh quotient ; Joint diagonalization ; Stiefel manifold ; 65K05 ; 90C48 ; 90C53
• 刊名：Mathematical Programming
• 出版年：2015
• 出版时间：May 2015
• 年：2015
• 卷：150
• 期：2
• 页码：179-216
• 全文大小：470 KB
• 参考文献：1. Absil, PA, Baker, CG, Gallivan, KA (2007) Trust-region methods on Riemannian manifolds. Found. Comput. Math. 7: pp. 303-330 CrossRef
  2. Absil, PA, Mahony, R, Sepulchre, R (2008) Optimization algorithms on matrix manifolds. Princeton University Press, Princeton, NJ CrossRef
  3. Absil, PA, Malick, J (2012) Projection-like retractions on matrix manifolds. SIAM Journal on Optimization 22: pp. 135-158 CrossRef
  4. Adler, RL, Dedieu, JP, Margulies, JY (2002) Newton’s method on Riemannian manifolds and a geometric model for the human spine. IMA J. Numer. Anal. 22: pp. 359-390 CrossRef
  5. Afsari, B, Tron, R, Vidal, R (2013) On the convergence of gradient descent for finding the Riemannian center of mass. SIAM J. Control Optim. 51: pp. 2230-2260 CrossRef
  6. Boothby, WM (2003) An Introduction to Differentiable Manifolds and Riemannian Geometry. Academic Press, London
  7. Borsdorf, R.: Structured Matrix Nearness Problems: Theory and Algorithms. Ph.D. thesis, The University of Manchester (2012)
  8. Boumal, N., Absil, P.A.: RTRMC: A Riemannian trust-region method for low-rank matrix completion. Adv. Neural Inf. Process. Syst. 24(NIPS), 406-14 (2011)
  9. Boumal, N., Mishra, B.: The Manopt toolbox. http://www.manopt.org
  10. Brace, I., Manton, J.H.: An improved BFGS-on-manifold algorithm for computing weighted low rank approximations. In Proceedings of 17th International Symposium on Mathematical Theory of Networks and Systems, pp. 1735-738 (2006)
  11. Byrd, RH, Khalfan, HF, Schnabel, RB (1996) Analysis of a symmetric rank-one trust region method. SIAM J. Optim. 6: pp. 1025-1039 CrossRef
  12. Byrd, RH, Nocedal, J, Schnabel, RB (1994) Representations of quasi-Newton matrices and their use in limited memory methods. Math. Program. 63: pp. 129-156 CrossRef
  13. do Carmo, M.P.: Riemannian geometry. Mathematics: Theory & Applications (1992)
  14. Chavel, I.: Riemannian Geometry: A Modern Introduction, 2nd ed. Cambridge Studies in Advanced Mathematics (2006)
  15. Conn, AR, Gould, NIM, Toint, PL (1991) Convergence of quasi-Newton matrices generated by the symmetric rank one update. Math. Program. 50: pp. 177-195 CrossRef
  16. Conn, A.R., Gould, N.I.M., Toint, P.L.: Trust-region methods. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, MPS/SIAM Series on Optimization (2000)
  17. Edelman, A, Arias, TA, Smith, ST (1998) The geometry of algorithms with orthogonality constraints. SIAM J. Matrix Anal. Appl. 20: pp. 303-353 CrossRef
  18. Gabay, D (1982) Minimizing a differentiable function over a differential manifold. J. Optim. Theory Appl. 37: pp. 177-219 CrossRef
  19. Gallivan, KA, Qi, C, Absil, PA A Riemannian Dennis-Moré condition. In: Berry, MW, Gallivan, KA, Gallopoulos, E, Grama, A, Philippe, B, Saad, Y, Saied, F eds. (2012) High-Performance Scientific Computing. Springer, London, pp. 281-293 CrossRef
  20. Huang, W.: Optimization algorithms on Riemannian manifolds with applications. Ph.D. thesis, Department of Mathematics, Florida State University (2013)
  21. Ishteva, M, Absil, PA, Huffel, S, Lathauwer, L (2011) Best low multilinear rank approximation of higher-order tensors, based on the Riemannian trust-region scheme. SIAM J. Matrix Anal. Appl. 32: pp. 115-135 CrossRef
  22. Jiang, B., Dai, Y.H.: A framework of constraint preserving update schemes for optimization on the Stiefel manifold (2013). ArXiv:1301.0172 <
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Calculus of Variations and Optimal Control
  Mathematics of Computing
  Numerical Analysis
  Combinatorics
  Mathematical and Computational Physics
  Mathematical Methods in Physics
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1436-4646

文摘

The well-known symmetric rank-one trust-region method—where the Hessian approximation is generated by the symmetric rank-one update—is generalized to the problem of minimizing a real-valued function over a \(d\) -dimensional Riemannian manifold. The generalization relies on basic differential-geometric concepts, such as tangent spaces, Riemannian metrics, and the Riemannian gradient, as well as on the more recent notions of (first-order) retraction and vector transport. The new method, called RTR-SR1, is shown to converge globally and \(d+1\) -step q-superlinearly to stationary points of the objective function. A limited-memory version, referred to as LRTR-SR1, is also introduced. In this context, novel efficient strategies are presented to construct a vector transport on a submanifold of a Euclidean space. Numerical experiments—Rayleigh quotient minimization on the sphere and a joint diagonalization problem on the Stiefel manifold—illustrate the value of the new methods.