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 & Management Optimization, 2017, 13 (3) : 1587-1599. doi: 10.3934/jimo.2017008
References:
[1] A. Auslender, Optimisation: Méthodes Numériques, Masson, Paris, 1976. Google Scholar
[2]

M. T. Chu, On the continuous realization of iterative processes, SIAM Review, 30 (1988), 375-387. doi: 10.1137/1030090. Google Scholar

[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. Google Scholar

[4]

A. Cichocki and R. Unbehauen, Neural networks for computing eigenvalues and eigenvectors, Biological Cybernetics, 68 (1992), 155-164. doi: 10.1007/BF00201437. Google Scholar

[5] F. Facchinei and J. S. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems, Springer-Verlag, New York, 2003. Google Scholar
[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. Google Scholar

[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. Google Scholar

[8]

H. GaoY. 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. Google Scholar

[9]

X. B. GaoG. 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. Google Scholar

[10] G. H. Golub and C. F. Van Loan, Matrix Computation, 3rd ed., The John Hopkins University Press, 1996. Google Scholar
[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[16]

J. J. Hopfield and D. W. Tank, Neural computation of decisions in optimization problems, Biological Cybernetics, 52 (1985), 141-152. Google Scholar

[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. Google Scholar

[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. Google Scholar

[19] W. Rudin, Principles of Mathematical Analysis, 3rd ed., McGraw-Hill Book Company, 1976. Google Scholar
[20] J. J. E. Slotine and W. Li, Applied Nonlinear Control, Prentice Hall, New Jersey, 1991. Google Scholar
[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. Google Scholar

[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. Google Scholar

show all references

References:
[1] A. Auslender, Optimisation: Méthodes Numériques, Masson, Paris, 1976. Google Scholar
[2]

M. T. Chu, On the continuous realization of iterative processes, SIAM Review, 30 (1988), 375-387. doi: 10.1137/1030090. Google Scholar

[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. Google Scholar

[4]

A. Cichocki and R. Unbehauen, Neural networks for computing eigenvalues and eigenvectors, Biological Cybernetics, 68 (1992), 155-164. doi: 10.1007/BF00201437. Google Scholar

[5] F. Facchinei and J. S. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems, Springer-Verlag, New York, 2003. Google Scholar
[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. Google Scholar

[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. Google Scholar

[8]

H. GaoY. 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. Google Scholar

[9]

X. B. GaoG. 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. Google Scholar

[10] G. H. Golub and C. F. Van Loan, Matrix Computation, 3rd ed., The John Hopkins University Press, 1996. Google Scholar
[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[16]

J. J. Hopfield and D. W. Tank, Neural computation of decisions in optimization problems, Biological Cybernetics, 52 (1985), 141-152. Google Scholar

[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. Google Scholar

[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. Google Scholar

[19] W. Rudin, Principles of Mathematical Analysis, 3rd ed., McGraw-Hill Book Company, 1976. Google Scholar
[20] J. J. E. Slotine and W. Li, Applied Nonlinear Control, Prentice Hall, New Jersey, 1991. Google Scholar
[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. Google Scholar

[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. Google Scholar

Figure 1.  Sketch three trajectories of two different orders
Figure 2.  Sketch three trajectories of two different orders
Table 1.  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
Table 2.  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 & 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 & Management Optimization, 2013, 9 (1) : 255-274. doi: 10.3934/jimo.2013.9.255

[3]

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 & Management Optimization, 2017, 13 (5) : 1-15. doi: 10.3934/jimo.2019017

[4]

Siu-Long Lei. Adaptive method for spike solutions of Gierer-Meinhardt system on irregular domain. Discrete & Continuous Dynamical Systems - B, 2011, 15 (3) : 651-668. doi: 10.3934/dcdsb.2011.15.651

[5]

Yanan Mao, Caixia Gao, Ruidong Yan, Aruna Bai. Modeling and identification of hybrid dynamic system in microbial continuous fermentation. Numerical Algebra, Control & Optimization, 2015, 5 (4) : 359-368. doi: 10.3934/naco.2015.5.359

[6]

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 & Management Optimization, 2017, 13 (5) : 1-26. doi: 10.3934/jimo.2018188

[7]

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

[8]

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

[9]

Mihai Mihăilescu. An eigenvalue problem possessing a continuous family of eigenvalues plus an isolated eigenvalue. Communications on Pure & Applied Analysis, 2011, 10 (2) : 701-708. doi: 10.3934/cpaa.2011.10.701

[10]

Qiang Guo, Dong Liang. An adaptive wavelet method and its analysis for parabolic equations. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 327-345. doi: 10.3934/naco.2013.3.327

[11]

Jingang Zhai, Guangmao Jiang, Jianxiong Ye. Optimal dilution strategy for a microbial continuous culture based on the biological robustness. Numerical Algebra, Control & Optimization, 2015, 5 (1) : 59-69. doi: 10.3934/naco.2015.5.59

[12]

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

[13]

Wing Yan Lee, Fangda Liu. Analysis of a dynamic premium strategy: From theoretical and marketing perspectives. Journal of Industrial & Management Optimization, 2018, 14 (4) : 1545-1564. doi: 10.3934/jimo.2018020

[14]

Siyu Liu, Xue Yang, Yingjie Bi, Yong Li. Dynamic behavior and optimal scheduling for mixed vaccination strategy with temporary immunity. Discrete & Continuous Dynamical Systems - B, 2019, 24 (4) : 1469-1483. doi: 10.3934/dcdsb.2018216

[15]

Wai-Ki Ching, Tang Li, Sin-Man Choi, Issic K. C. Leung. A tandem queueing system with applications to pricing strategy. Journal of Industrial & Management Optimization, 2009, 5 (1) : 103-114. doi: 10.3934/jimo.2009.5.103

[16]

Jeongsim Kim, Bara Kim. Stability of a cyclic polling system with an adaptive mechanism. Journal of Industrial & Management Optimization, 2015, 11 (3) : 763-777. doi: 10.3934/jimo.2015.11.763

[17]

Lei-Hong Zhang, Li-Zhi Liao. A generalized projective dynamic for solving extreme and interior eigenvalue problems. Discrete & Continuous Dynamical Systems - B, 2008, 10 (4) : 997-1019. doi: 10.3934/dcdsb.2008.10.997

[18]

Hui Meng, Fei Lung Yuen, Tak Kuen Siu, Hailiang Yang. Optimal portfolio in a continuous-time self-exciting threshold model. Journal of Industrial & Management Optimization, 2013, 9 (2) : 487-504. doi: 10.3934/jimo.2013.9.487

[19]

Alexander J. Zaslavski. Structure of approximate solutions of dynamic continuous time zero-sum games. Journal of Dynamics & Games, 2014, 1 (1) : 153-179. doi: 10.3934/jdg.2014.1.153

[20]

Dongho Kim, Eun-Jae Park. Adaptive Crank-Nicolson methods with dynamic finite-element spaces for parabolic problems. Discrete & Continuous Dynamical Systems - B, 2008, 10 (4) : 873-886. doi: 10.3934/dcdsb.2008.10.873

2018 Impact Factor: 1.025

Metrics

  • PDF downloads (28)
  • HTML views (358)
  • Cited by (0)

Other articles
by authors

[Back to Top]