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]

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

[2]

Kuan-Hsiang Wang. An eigenvalue problem for nonlinear Schrödinger-Poisson system with steep potential well. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021030

[3]

Alexandr Mikhaylov, Victor Mikhaylov. Dynamic inverse problem for Jacobi matrices. Inverse Problems & Imaging, 2019, 13 (3) : 431-447. doi: 10.3934/ipi.2019021

[4]

Simone Cacace, Maurizio Falcone. A dynamic domain decomposition for the eikonal-diffusion equation. Discrete & Continuous Dynamical Systems - S, 2016, 9 (1) : 109-123. doi: 10.3934/dcdss.2016.9.109

[5]

Thomas Y. Hou, Ruo Li. Nonexistence of locally self-similar blow-up for the 3D incompressible Navier-Stokes equations. Discrete & Continuous Dynamical Systems - A, 2007, 18 (4) : 637-642. doi: 10.3934/dcds.2007.18.637

[6]

Xiaoyi Zhou, Tong Ye, Tony T. Lee. Designing and analysis of a Wi-Fi data offloading strategy catering for the preference of mobile users. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021038

[7]

Xianchao Xiu, Ying Yang, Wanquan Liu, Lingchen Kong, Meijuan Shang. An improved total variation regularized RPCA for moving object detection with dynamic background. Journal of Industrial & Management Optimization, 2020, 16 (4) : 1685-1698. doi: 10.3934/jimo.2019024

[8]

Chaoqian Li, Yajun Liu, Yaotang Li. Note on $ Z $-eigenvalue inclusion theorems for tensors. Journal of Industrial & Management Optimization, 2021, 17 (2) : 687-693. doi: 10.3934/jimo.2019129

[9]

Yuncherl Choi, Taeyoung Ha, Jongmin Han, Sewoong Kim, Doo Seok Lee. Turing instability and dynamic phase transition for the Brusselator model with multiple critical eigenvalues. Discrete & Continuous Dynamical Systems - A, 2021  doi: 10.3934/dcds.2021035

[10]

Carlos Gutierrez, Nguyen Van Chau. A remark on an eigenvalue condition for the global injectivity of differentiable maps of $R^2$. Discrete & Continuous Dynamical Systems - A, 2007, 17 (2) : 397-402. doi: 10.3934/dcds.2007.17.397

[11]

Zhihua Zhang, Naoki Saito. PHLST with adaptive tiling and its application to antarctic remote sensing image approximation. Inverse Problems & Imaging, 2014, 8 (1) : 321-337. doi: 10.3934/ipi.2014.8.321

[12]

Gloria Paoli, Gianpaolo Piscitelli, Rossanno Sannipoli. A stability result for the Steklov Laplacian Eigenvalue Problem with a spherical obstacle. Communications on Pure & Applied Analysis, 2021, 20 (1) : 145-158. doi: 10.3934/cpaa.2020261

[13]

Murat Uzunca, Ayşe Sarıaydın-Filibelioǧlu. Adaptive discontinuous galerkin finite elements for advective Allen-Cahn equation. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 269-281. doi: 10.3934/naco.2020025

[14]

Armin Lechleiter, Tobias Rienmüller. Factorization method for the inverse Stokes problem. Inverse Problems & Imaging, 2013, 7 (4) : 1271-1293. doi: 10.3934/ipi.2013.7.1271

[15]

Rabiaa Ouahabi, Nasr-Eddine Hamri. Design of new scheme adaptive generalized hybrid projective synchronization for two different chaotic systems with uncertain parameters. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2361-2370. doi: 10.3934/dcdsb.2020182

[16]

M. Grasselli, V. Pata. Asymptotic behavior of a parabolic-hyperbolic system. Communications on Pure & Applied Analysis, 2004, 3 (4) : 849-881. doi: 10.3934/cpaa.2004.3.849

[17]

Elena Bonetti, Pierluigi Colli, Gianni Gilardi. Singular limit of an integrodifferential system related to the entropy balance. Discrete & Continuous Dynamical Systems - B, 2014, 19 (7) : 1935-1953. doi: 10.3934/dcdsb.2014.19.1935

[18]

Dmitry Treschev. A locally integrable multi-dimensional billiard system. Discrete & Continuous Dynamical Systems - A, 2017, 37 (10) : 5271-5284. doi: 10.3934/dcds.2017228

[19]

Nizami A. Gasilov. Solving a system of linear differential equations with interval coefficients. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2739-2747. doi: 10.3934/dcdsb.2020203

[20]

Eduardo Casas, Christian Clason, Arnd Rösch. Preface special issue on system modeling and optimization. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021008

2019 Impact Factor: 1.366

Metrics

  • PDF downloads (144)
  • HTML views (484)
  • Cited by (0)

Other articles
by authors

[Back to Top]