# American Institute of Mathematical Sciences

July  2017, 13(3): 1587-1599. doi: 10.3934/jimo.2017008

## A fast continuous method for the extreme eigenvalue problem

 1 College of Applied Sciences, Beijing University of Technology, Beijing 100124, China 2 School of Mathematics and Statistics, Central South University, Changsha, Hunan 410083, China

* Corresponding author: zbli@lsec.cc.ac.cn

Received  July 2015 Revised  April 2016 Published  December 2016

Fund Project: This research was supported by the National Science Foundation of China (61179033), Collaborative Innovation Center on Beijing Society-building and Social Governance, and Shandong Provincial Natural Science Foundation of China (ZR2013FL032).

Matrix eigenvalue problems play a significant role in many areas of computational science and engineering. In this paper, we propose a fast continuous method for the extreme eigenvalue problem. We first convert such a nonconvex optimization problem into a minimization problem with concave objective function and convex constraints based on the continuous methods developed by Golub and Liao. Then, we propose a continuous method for solving such a minimization problem. To accelerate the convergence of this method, a self-adaptive step length strategy is adopted. Under mild conditions, we prove the global convergence of this method. Some preliminary numerical results are presented to verify the effectiveness of the proposed method eventually.

Citation: Huan Gao, Zhibao Li, Haibin Zhang. A fast continuous method for the extreme eigenvalue problem. Journal of Industrial and Management Optimization, 2017, 13 (3) : 1587-1599. doi: 10.3934/jimo.2017008
##### References:
 [1] A. Auslender, Optimisation: Méthodes Numériques, Masson, Paris, 1976. [2] M. T. Chu, On the continuous realization of iterative processes, SIAM Review, 30 (1988), 375-387.  doi: 10.1137/1030090. [3] M. T. Chu, Matrix differential equations: a continuous realization process for linear algebra problems, Nonlinear Analysis, Theory, Methods and Applications, 18 (1992), 1125-1146.  doi: 10.1016/0362-546X(92)90157-A. [4] A. Cichocki and R. Unbehauen, Neural networks for computing eigenvalues and eigenvectors, Biological Cybernetics, 68 (1992), 155-164.  doi: 10.1007/BF00201437. [5] F. Facchinei and J. S. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems, Springer-Verlag, New York, 2003. [6] H. R. Fang and Y. Saad, A filtered Lanczos procedure for extreme and interior eigenvalue problems, SIAM Journal on Scientific Computing, 34 (2012), A2220-A2246.  doi: 10.1137/110836535. [7] M. Fukushima, Equivalent differentiable optimization problems and descent methods for asymmetric variational inequality problems, Mathematical Programming, 53 (1992), 99-110.  doi: 10.1007/BF01585696. [8] H. Gao, Y. H. Dai and X. J. Tong, Barzilai-Borwein-like methods for the extreme eigenvalue problem, Journal of Industrial and Management Optimization, 11 (2015), 999-1019.  doi: 10.3934/jimo.2015.11.999. [9] X. B. Gao, G. H. Golub and L. Z. Liao, Continuous methods for symmetric generalized eigenvalue problems, Linear Algebra and its Applications, 428 (2008), 676-696.  doi: 10.1016/j.laa.2007.08.034. [10] G. H. Golub and C. F. Van Loan, Matrix Computation, 3rd ed., The John Hopkins University Press, 1996. [11] G. H. Golub and L. Z. Liao, Continuous methods for extreme and interior eigenvalue problems, Linear Algebra and its Applications, 415 (2006), 31-51.  doi: 10.1016/j.laa.2005.01.009. [12] D. R. Han and H. K. Lo, Solving non-additive traffic assignment problems: A descent method for co-coercive variational inequalities, European Journal of Operational Research, 159 (2004), 529-544.  doi: 10.1016/S0377-2217(03)00423-5. [13] B. He, A projection and contraction method for a class of linear complementarity problems and its application in convex quadratic programming, Applied Mathematics and Optimization, 25 (1992), 247-262.  doi: 10.1007/BF01182323. [14] J. J. Hopfield, Neural networks and physical systems with emergent collective computational ability, Proc. National Academy of Sciences of the United States of America, 79 (1982), 2554-2558.  doi: 10.1073/pnas.79.8.2554. [15] J. J. Hopfield, Neurons with graded response have collective computational properties like those of two-state neurons, Proc. National Academy of Sciences of the United States of America, 81 (1984), 3088-3092.  doi: 10.1073/pnas.81.10.3088. [16] J. J. Hopfield and D. W. Tank, Neural computation of decisions in optimization problems, Biological Cybernetics, 52 (1985), 141-152. [17] L. Z. Liao, A Study of the Dual Affine Scaling Continuous Trajectories for Linear Programming, Journal of Optimization Theory and Applications, 163 (2014), 548-568.  doi: 10.1007/s10957-013-0495-1. [18] E. E. Ovtchinnikov, Jacobi correction equation, line search, and conjugate gradients in Hermitian eigenvalue computation Ⅰ: Computing an extreme eigenvalue, SIAM Journal on Numerical Analysis, 46 (2014), 2567-2592.  doi: 10.1137/070688742. [19] W. Rudin, Principles of Mathematical Analysis, 3rd ed., McGraw-Hill Book Company, 1976. [20] J. J. E. Slotine and W. Li, Applied Nonlinear Control, Prentice Hall, New Jersey, 1991. [21] H. A. van der Vorst and G. H. Golub, 150 years old and still alive: Eigenproblems, In: I. S. Duff, Editor, The State of the Art in Numerical Analysis, 63 (1997), 93-119. [22] T. Zhu and Z. G. Yu, A simple proof for some important properties of the projection mapping, Mathematical Inequalities and Applications, 7 (2004), 453-456.  doi: 10.7153/mia-07-45.

show all references

##### References:
 [1] A. Auslender, Optimisation: Méthodes Numériques, Masson, Paris, 1976. [2] M. T. Chu, On the continuous realization of iterative processes, SIAM Review, 30 (1988), 375-387.  doi: 10.1137/1030090. [3] M. T. Chu, Matrix differential equations: a continuous realization process for linear algebra problems, Nonlinear Analysis, Theory, Methods and Applications, 18 (1992), 1125-1146.  doi: 10.1016/0362-546X(92)90157-A. [4] A. Cichocki and R. Unbehauen, Neural networks for computing eigenvalues and eigenvectors, Biological Cybernetics, 68 (1992), 155-164.  doi: 10.1007/BF00201437. [5] F. Facchinei and J. S. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems, Springer-Verlag, New York, 2003. [6] H. R. Fang and Y. Saad, A filtered Lanczos procedure for extreme and interior eigenvalue problems, SIAM Journal on Scientific Computing, 34 (2012), A2220-A2246.  doi: 10.1137/110836535. [7] M. Fukushima, Equivalent differentiable optimization problems and descent methods for asymmetric variational inequality problems, Mathematical Programming, 53 (1992), 99-110.  doi: 10.1007/BF01585696. [8] H. Gao, Y. H. Dai and X. J. Tong, Barzilai-Borwein-like methods for the extreme eigenvalue problem, Journal of Industrial and Management Optimization, 11 (2015), 999-1019.  doi: 10.3934/jimo.2015.11.999. [9] X. B. Gao, G. H. Golub and L. Z. Liao, Continuous methods for symmetric generalized eigenvalue problems, Linear Algebra and its Applications, 428 (2008), 676-696.  doi: 10.1016/j.laa.2007.08.034. [10] G. H. Golub and C. F. Van Loan, Matrix Computation, 3rd ed., The John Hopkins University Press, 1996. [11] G. H. Golub and L. Z. Liao, Continuous methods for extreme and interior eigenvalue problems, Linear Algebra and its Applications, 415 (2006), 31-51.  doi: 10.1016/j.laa.2005.01.009. [12] D. R. Han and H. K. Lo, Solving non-additive traffic assignment problems: A descent method for co-coercive variational inequalities, European Journal of Operational Research, 159 (2004), 529-544.  doi: 10.1016/S0377-2217(03)00423-5. [13] B. He, A projection and contraction method for a class of linear complementarity problems and its application in convex quadratic programming, Applied Mathematics and Optimization, 25 (1992), 247-262.  doi: 10.1007/BF01182323. [14] J. J. Hopfield, Neural networks and physical systems with emergent collective computational ability, Proc. National Academy of Sciences of the United States of America, 79 (1982), 2554-2558.  doi: 10.1073/pnas.79.8.2554. [15] J. J. Hopfield, Neurons with graded response have collective computational properties like those of two-state neurons, Proc. National Academy of Sciences of the United States of America, 81 (1984), 3088-3092.  doi: 10.1073/pnas.81.10.3088. [16] J. J. Hopfield and D. W. Tank, Neural computation of decisions in optimization problems, Biological Cybernetics, 52 (1985), 141-152. [17] L. Z. Liao, A Study of the Dual Affine Scaling Continuous Trajectories for Linear Programming, Journal of Optimization Theory and Applications, 163 (2014), 548-568.  doi: 10.1007/s10957-013-0495-1. [18] E. E. Ovtchinnikov, Jacobi correction equation, line search, and conjugate gradients in Hermitian eigenvalue computation Ⅰ: Computing an extreme eigenvalue, SIAM Journal on Numerical Analysis, 46 (2014), 2567-2592.  doi: 10.1137/070688742. [19] W. Rudin, Principles of Mathematical Analysis, 3rd ed., McGraw-Hill Book Company, 1976. [20] J. J. E. Slotine and W. Li, Applied Nonlinear Control, Prentice Hall, New Jersey, 1991. [21] H. A. van der Vorst and G. H. Golub, 150 years old and still alive: Eigenproblems, In: I. S. Duff, Editor, The State of the Art in Numerical Analysis, 63 (1997), 93-119. [22] T. Zhu and Z. G. Yu, A simple proof for some important properties of the projection mapping, Mathematical Inequalities and Applications, 7 (2004), 453-456.  doi: 10.7153/mia-07-45.
Sketch three trajectories of two different orders
Sketch three trajectories of two different orders
Results for Example 1
 n 100 500 1000 2000 3000 4000 5000 ODE45(Sec.) 0.328 5.297 17.2199 86.188 130.016 389.016 642.234 Iterations 31 55 43 51 39 55 60 Time (Sec.) 0.016 0.531 1.484 6.734 11.594 29.125 48.094
 n 100 500 1000 2000 3000 4000 5000 ODE45(Sec.) 0.328 5.297 17.2199 86.188 130.016 389.016 642.234 Iterations 31 55 43 51 39 55 60 Time (Sec.) 0.016 0.531 1.484 6.734 11.594 29.125 48.094
Results for Example 2
 n 100 500 1000 2000 3000 4000 5000 ODE45(Sec.) 0.234 5.359 44.343 80.469 149.234 314.516 452.859 Iterations 43 61 99 47 39 51 51 Time (Sec.) 0.031 0.578 3.438 6.328 11.594 26.781 41.234
 n 100 500 1000 2000 3000 4000 5000 ODE45(Sec.) 0.234 5.359 44.343 80.469 149.234 314.516 452.859 Iterations 43 61 99 47 39 51 51 Time (Sec.) 0.031 0.578 3.438 6.328 11.594 26.781 41.234
 [1] Zhao-Han Sheng, Tingwen Huang, Jian-Guo Du, Qiang Mei, Hui Huang. Study on self-adaptive proportional control method for a class of output models. Discrete and Continuous Dynamical Systems - B, 2009, 11 (2) : 459-477. doi: 10.3934/dcdsb.2009.11.459 [2] Gang Qian, Deren Han, Lingling Xu, Hai Yang. Solving nonadditive traffic assignment problems: A self-adaptive projection-auxiliary problem method for variational inequalities. Journal of Industrial and Management Optimization, 2013, 9 (1) : 255-274. doi: 10.3934/jimo.2013.9.255 [3] Hatim Tayeq, Amal Bergam, Anouar El Harrak, Kenza Khomsi. Self-adaptive algorithm based on a posteriori analysis of the error applied to air quality forecasting using the finite volume method. Discrete and Continuous Dynamical Systems - S, 2021, 14 (7) : 2557-2570. doi: 10.3934/dcdss.2020400 [4] Yuan Shen, Chang Liu, Yannian Zuo, Xingying Zhang. A modified self-adaptive dual ascent method with relaxed stepsize condition for linearly constrained quadratic convex optimization. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022101 [5] Ya-Zheng Dang, Zhong-Hui Xue, Yan Gao, Jun-Xiang Li. Fast self-adaptive regularization iterative algorithm for solving split feasibility problem. Journal of Industrial and Management Optimization, 2020, 16 (4) : 1555-1569. doi: 10.3934/jimo.2019017 [6] Tengfei Yan, Qunying Liu, Bowen Dou, Qing Li, Bowen Li. An adaptive dynamic programming method for torque ripple minimization of PMSM. Journal of Industrial and Management Optimization, 2021, 17 (2) : 827-839. doi: 10.3934/jimo.2019136 [7] Fanni M. Sélley. A self-consistent dynamical system with multiple absolutely continuous invariant measures. Journal of Computational Dynamics, 2021, 8 (1) : 9-32. doi: 10.3934/jcd.2021002 [8] Huiyi Bao, Tao Du, Luyue Sun. Adaptive attitude determination of bionic polarization integrated navigation system based on reinforcement learning strategy. Mathematical Foundations of Computing, 2022  doi: 10.3934/mfc.2022014 [9] Taqseer Khan, Harindri Chaudhary. Adaptive controllability of microscopic chaos generated in chemical reactor system using anti-synchronization strategy. Numerical Algebra, Control and Optimization, 2022, 12 (3) : 611-620. doi: 10.3934/naco.2021025 [10] Yanan Mao, Caixia Gao, Ruidong Yan, Aruna Bai. Modeling and identification of hybrid dynamic system in microbial continuous fermentation. Numerical Algebra, Control and Optimization, 2015, 5 (4) : 359-368. doi: 10.3934/naco.2015.5.359 [11] Siu-Long Lei. Adaptive method for spike solutions of Gierer-Meinhardt system on irregular domain. Discrete and Continuous Dynamical Systems - B, 2011, 15 (3) : 651-668. doi: 10.3934/dcdsb.2011.15.651 [12] Haibo Jin, Long Hai, Xiaoliang Tang. An optimal maintenance strategy for multi-state systems based on a system linear integral equation and dynamic programming. Journal of Industrial and Management Optimization, 2020, 16 (2) : 965-990. doi: 10.3934/jimo.2018188 [13] Xue Lu, Niall Adams, Nikolas Kantas. On adaptive estimation for dynamic Bernoulli bandits. Foundations of Data Science, 2019, 1 (2) : 197-225. doi: 10.3934/fods.2019009 [14] Tamar Friedlander, Naama Brenner. Adaptive response and enlargement of dynamic range. Mathematical Biosciences & Engineering, 2011, 8 (2) : 515-528. doi: 10.3934/mbe.2011.8.515 [15] Francis Akutsah, Akindele Adebayo Mebawondu, Hammed Anuoluwapo Abass, Ojen Kumar Narain. A self adaptive method for solving a class of bilevel variational inequalities with split variational inequality and composed fixed point problem constraints in Hilbert spaces. Numerical Algebra, Control and Optimization, 2021  doi: 10.3934/naco.2021046 [16] Mihai Mihăilescu. An eigenvalue problem possessing a continuous family of eigenvalues plus an isolated eigenvalue. Communications on Pure and Applied Analysis, 2011, 10 (2) : 701-708. doi: 10.3934/cpaa.2011.10.701 [17] Jingang Zhai, Guangmao Jiang, Jianxiong Ye. Optimal dilution strategy for a microbial continuous culture based on the biological robustness. Numerical Algebra, Control and Optimization, 2015, 5 (1) : 59-69. doi: 10.3934/naco.2015.5.59 [18] Glenn Ledder, Donna Sylvester, Rachelle R. Bouchat, Johann A. Thiel. Continuous and pulsed epidemiological models for onchocerciasis with implications for eradication strategy. Mathematical Biosciences & Engineering, 2018, 15 (4) : 841-862. doi: 10.3934/mbe.2018038 [19] Qiang Guo, Dong Liang. An adaptive wavelet method and its analysis for parabolic equations. Numerical Algebra, Control and Optimization, 2013, 3 (2) : 327-345. doi: 10.3934/naco.2013.3.327 [20] Hong Niu, Zhijiang Feng, Qijin Xiao, Yajun Zhang. A PID control method based on optimal control strategy. Numerical Algebra, Control and Optimization, 2021, 11 (1) : 117-126. doi: 10.3934/naco.2020019

2021 Impact Factor: 1.411

## Metrics

• PDF downloads (281)
• HTML views (489)
• Cited by (0)

## Other articlesby authors

• on AIMS
• on Google Scholar

[Back to Top]