利用改进的同伦算法求解特征值问题
|
摘要
矩阵特征值问题是机器学习、数据处理以及工程分析和计算中经常需要解决的问题之一.同伦算法是求解矩阵特征值的经典方法;自动微分可以有效、快速地计算出大规模问题相关函数的导数项,并且可以达到机器精度.充分利用自动微分的优点,设计自动微分技术与同伦算法相结合的方法求解矩阵特征值问题.数值实验验证了该算法的有效性.
The matrix eigenvalue problem is one of the important problem appeared in machine learning, data processing and other engineering calculation and numerical analyses.The classical numerical method for the matrix eigenvalue problem is the homotopy algorithm.On the other hand, automatic differentiation is effective, fast in calculating the derivative terms for the large scale problems, and it has the advantage of machine precision for the derivative calculation. In this paper, we propose a combined method for solving the matrix eigenvalue problem by taking advantage of the automatic differentiation and the homotopy algorithm to be together. Numerical experiments demonstrate the effectiveness of the proposed method.
The matrix eigenvalue problem is one of the important problem appeared in machine learning, data processing and other engineering calculation and numerical analyses.The classical numerical method for the matrix eigenvalue problem is the homotopy algorithm.On the other hand, automatic differentiation is effective, fast in calculating the derivative terms for the large scale problems, and it has the advantage of machine precision for the derivative calculation. In this paper, we propose a combined method for solving the matrix eigenvalue problem by taking advantage of the automatic differentiation and the homotopy algorithm to be together. Numerical experiments demonstrate the effectiveness of the proposed method.
引文
[1]徐树方.矩阵计算的理论与方法[M].北京:北京大学出版社,2005年11月第四次印刷.
[2] Li T, Rhee N. Homotopy Algorithm for Symmetric Eigenvalue Problems[J]. Numerische Mathematik, 1989, 55(3):265-280.
[3] Brockman P, Carson T, Cheng Y, Elgindi T, Jensen K, Zhoun X, Elgindi M. Homotopy method for the eigenvalues of symmetric tridiagonal matrices[J]. Journal of Computational and Applied Mathematics, 2013, 237(1):644-653.
[4] Batselier K, Wong N. A QR Algorithm for Symmetric Tensors[J]. arXiv preprint arXiv:1411.1926,2014.
[5]高欢,童小娇.求解对称矩阵最大特征值的Barzilai-Borwein法[J].衡阳师范学院学报,2012, 3:27-32.
[6] Jiang B, Dai Y. Feasible Barzilai-Borwein-like methods for extreme symmetric eigenvalue problems[J]. Optimization Methods and Software, 2013, 28(4):756-784.
[7] Gao H, Dai Y, Tong X. Barzilai-Borwein-like Methods for the Extreme Eigenvalue Problem[J].Journal of Industrial and Management Optimization, 2014, 11(3):999-1019.
[8] Bai Z, Dongarra J, Ruhe A, Vorst H. Templates for the Solution of Algebraic Eigenvalue Problems:A Practical Guide[M]. Philadelphia:SIAM, 2000.
[9] Rall L. Automatic differentiation:Techniques and applications[M]. Berlin:Springer, 1981.
[10] Ozyurt D, Barton P. Application of Targeted Automatic Differentiation to Large-Scale Dynamic Optimization[M]//Automatic Differentiation:Applications, Theory, and Implementations. Springer Berlin Heidelberg, 2006, 50:235-247.
[11] Griewank A, Walther A. Evaluating derivatives:principles and techniques of algorithmic differentiation[M]. Philadelphia:Siam, 2008.
[12]李翔,仲卫涛,钱积新.化工过程优化中的自动微分法[J].石油学报(石油加工), 2001, 17(6):79-83.
[13] Deng N, Zhang H, Zhang C. Further improvement of the Newton-PCG algorithm with automatic differentiation[J]. Optimization Methods and Software, 2001, 16(1-4):151-178.
[14] Zhang H, Deng N. An improved inexact Newton method[J]. Journal of Global Optimization, 2007,39(2):221-234.
[15] Zhang H. On the Halley class of methods for unconstrained optimization problems. Optimization Methods and Software[J], 2010, 25(5):753-762.
[16] Chu M. A simple application of the homotopy method to symmetric eigenvalue problems[J]. Linear Algebra and its Applications, 1984, 59:85-90.
[17] Forth S, Edvall M. User Guide for MAD-A Matlab Automatic Differentiation Toolbox, TOMLAB/MAD, Version 1.4 The Forward Mode[J]. Engineering Systems Department, Defence College of Management and Technology, Cranfield University.
[2] Li T, Rhee N. Homotopy Algorithm for Symmetric Eigenvalue Problems[J]. Numerische Mathematik, 1989, 55(3):265-280.
[3] Brockman P, Carson T, Cheng Y, Elgindi T, Jensen K, Zhoun X, Elgindi M. Homotopy method for the eigenvalues of symmetric tridiagonal matrices[J]. Journal of Computational and Applied Mathematics, 2013, 237(1):644-653.
[4] Batselier K, Wong N. A QR Algorithm for Symmetric Tensors[J]. arXiv preprint arXiv:1411.1926,2014.
[5]高欢,童小娇.求解对称矩阵最大特征值的Barzilai-Borwein法[J].衡阳师范学院学报,2012, 3:27-32.
[6] Jiang B, Dai Y. Feasible Barzilai-Borwein-like methods for extreme symmetric eigenvalue problems[J]. Optimization Methods and Software, 2013, 28(4):756-784.
[7] Gao H, Dai Y, Tong X. Barzilai-Borwein-like Methods for the Extreme Eigenvalue Problem[J].Journal of Industrial and Management Optimization, 2014, 11(3):999-1019.
[8] Bai Z, Dongarra J, Ruhe A, Vorst H. Templates for the Solution of Algebraic Eigenvalue Problems:A Practical Guide[M]. Philadelphia:SIAM, 2000.
[9] Rall L. Automatic differentiation:Techniques and applications[M]. Berlin:Springer, 1981.
[10] Ozyurt D, Barton P. Application of Targeted Automatic Differentiation to Large-Scale Dynamic Optimization[M]//Automatic Differentiation:Applications, Theory, and Implementations. Springer Berlin Heidelberg, 2006, 50:235-247.
[11] Griewank A, Walther A. Evaluating derivatives:principles and techniques of algorithmic differentiation[M]. Philadelphia:Siam, 2008.
[12]李翔,仲卫涛,钱积新.化工过程优化中的自动微分法[J].石油学报(石油加工), 2001, 17(6):79-83.
[13] Deng N, Zhang H, Zhang C. Further improvement of the Newton-PCG algorithm with automatic differentiation[J]. Optimization Methods and Software, 2001, 16(1-4):151-178.
[14] Zhang H, Deng N. An improved inexact Newton method[J]. Journal of Global Optimization, 2007,39(2):221-234.
[15] Zhang H. On the Halley class of methods for unconstrained optimization problems. Optimization Methods and Software[J], 2010, 25(5):753-762.
[16] Chu M. A simple application of the homotopy method to symmetric eigenvalue problems[J]. Linear Algebra and its Applications, 1984, 59:85-90.
[17] Forth S, Edvall M. User Guide for MAD-A Matlab Automatic Differentiation Toolbox, TOMLAB/MAD, Version 1.4 The Forward Mode[J]. Engineering Systems Department, Defence College of Management and Technology, Cranfield University.