July  2015, 11(3): 999-1019. doi: 10.3934/jimo.2015.11.999

Barzilai-Borwein-like methods for the extreme eigenvalue problem

1. 

College of Applied Sciences, Beijing University of Technology, Beijing 100124, China

2. 

State Key Laboratory of Scientific and Engineering Computing, Institute of Computational Mathematics and Scientific/Engineering Computing, AMSS, Chinese Academy of Sciences, Beijing 100190, China

3. 

Hunan Province Key Laboratory of Smart Grids Operation and Control, Changsha University of Science and Technology, Changsha 410004, Hunan Province, China

Received  November 2012 Revised  June 2014 Published  October 2014

We consider numerical methods for the extreme eigenvalue problem of large scale symmetric positive definite matrices. By the variational principle, the extreme eigenvalue can be obtained by minimizing some unconstrained optimization problem. Firstly, we propose two adaptive nonmonotone Barzilai-Borwein-like methods for the unconstrained optimization problem. Secondly, we prove the global convergence of the two algorithms under some conditions. Thirdly, we compare our methods with eigs and the power method for the standard test problems from the UF Sparse Matrix Collection. The primary numerical experiments indicate that the two algorithms are promising.
Citation: Huan Gao, Yu-Hong Dai, Xiao-Jiao Tong. Barzilai-Borwein-like methods for the extreme eigenvalue problem. Journal of Industrial & Management Optimization, 2015, 11 (3) : 999-1019. doi: 10.3934/jimo.2015.11.999
References:
[1]

G. Auchmuty, Unconstrained variational principles for eigenvalues of real symmetric matrices,, SIAM J. Math. Anal., 20 (1989), 1186.  doi: 10.1137/0520078.  Google Scholar

[2]

J. Barzilai and J. M. Borwein, Two point step size gradient methods,, IMA Journal of Numerical Analysis, 8 (1988), 141.  doi: 10.1093/imanum/8.1.141.  Google Scholar

[3]

Z. Bai, J. Dongarra, A. Ruhe and H. van der Vorst, Templates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide,, SIAM, (2000).  doi: 10.1137/1.9780898719581.  Google Scholar

[4]

J. K. Cullum and R. A. Willoughby, Lanczos Algorithms for Large Symmetric Eigenvalue,, the United States of America: SIAM, (1985).   Google Scholar

[5]

Y. H. Dai, On the nonmonotone line search,, Journal of Optimization Theory and Applications, 112 (2002), 315.  doi: 10.1023/A:1013653923062.  Google Scholar

[6]

Y. H. Dai and R. Fletcher, Projected Barzilai-Borwein methods for large-scale box-constrained quadratic programming,, Numerische Mathematik, 100 (2005), 21.  doi: 10.1007/s00211-004-0569-y.  Google Scholar

[7]

Y. H. Dai, W. W. Hager, K. Schittkowski and H. C. Zhang, The cycle Barzilai-Borwein method for unconstrained optimization,, IMA Journal of Numerical Analysis, 26 (2006), 604.  doi: 10.1093/imanum/drl006.  Google Scholar

[8]

Y. H. Dai and C. X. Kou, A nonlinear conjugate gradient algorithm with an optimal property and an improved Wolfe line search,, SIAM Journal on Optimization, 23 (2013), 296.  doi: 10.1137/100813026.  Google Scholar

[9]

Y. H. Dai and L. Z. Liao, $R$-linear convergence of the Barzilai and Borwein gradient method,, IMA Journal of Numerical Analysis, 22 (2002), 1.  doi: 10.1093/imanum/22.1.1.  Google Scholar

[10]

Y. H. Dai and H. C. Zhang, Adaptive two-point stepsize gradient algorithm,, Numerical Algorithms, 27 (2001), 377.  doi: 10.1023/A:1013844413130.  Google Scholar

[11]

T. A. Davis and Y. H. Hu, The University of Florida Sparse Matrix Collection,, University of Florida, (2011).  doi: 10.1145/2049662.2049663.  Google Scholar

[12]

E. D. Dolan and J. J. Moré, Benchmarking optimization software with performance profiles,, Mathematical Programming Series A, 91 (2002), 201.  doi: 10.1007/s101070100263.  Google Scholar

[13]

R. Fletcher, On the Barzilai-Borwein method,, in Optimization and Control with Applications (eds. L.Q. Qi, 96 (2005), 235.  doi: 10.1007/0-387-24255-4_10.  Google Scholar

[14]

L. Grippo, F. Lampariello and S. Lucidi, A nonmonotone line search technique for Newton's method,, SIAM Journal on Numerical Analysis, 23 (1986), 707.  doi: 10.1137/0723046.  Google Scholar

[15]

G. H. Golub and C. F. Van Loan, Matrix computation,, $3^{nd}$ edition, (1996).   Google Scholar

[16]

W. W. Hager and H. Zhang, A new conjugate gradient method with guaranteed descent and an efficient line search,, SIAM Journal on Optimization, 16 (2005), 170.  doi: 10.1137/030601880.  Google Scholar

[17]

B. Jiang and Y. H. Dai, Feasible Barzilai-Borwein-like methods for extreme symmetric eigenvalue problems,, Optimization Methods and Software, 28 (2013), 756.  doi: 10.1080/10556788.2012.656115.  Google Scholar

[18]

M. Mongeau and M. Torki, Computing eigenelements of real symmetric matrices via optimization,, Computational Optimization and Applications, 29 (2004), 263.  doi: 10.1023/B:COAP.0000044182.33308.82.  Google Scholar

[19]

M. Raydan, On the Barzilai and Borwein of steplength for gradient method,, IMA Journal of Numerical Analysis, 13 (1993), 321.  doi: 10.1093/imanum/13.3.321.  Google Scholar

[20]

Y. Saad, Numerical Methods for Large Eigenvalue Problems,, Manchester University: The Society of Industrial and Applied Mathematics, (2011).  doi: 10.1137/1.9781611970739.  Google Scholar

[21]

A. H. Sameh and J. A. Wisniewski, A trace minimization algorithm for the generalized eigenvalue problem computations,, SIAM Journal on Numerical Analysis, 19 (1982), 1243.  doi: 10.1137/0719089.  Google Scholar

[22]

P. L. Toint, Non-monotone trust-region algorithms for nonlinear optimization subject to convex constraints,, Mathematical Programming, 77 (1997), 69.  doi: 10.1007/BF02614518.  Google Scholar

[23]

H. C. Zhang and W. W. Hager, PACBB: A projected adaptive CBB (PACBB) method for box constrained optimization,, Nonconvex Optimization and Its Applications, 82 (2006), 387.   Google Scholar

[24]

B. Zhou, L. Gao and Y. H. Dai, Gradient methods with adaptive step sizes,, Computation Optimization and Applications, 35 (2006), 69.  doi: 10.1007/s10589-006-6446-0.  Google Scholar

show all references

References:
[1]

G. Auchmuty, Unconstrained variational principles for eigenvalues of real symmetric matrices,, SIAM J. Math. Anal., 20 (1989), 1186.  doi: 10.1137/0520078.  Google Scholar

[2]

J. Barzilai and J. M. Borwein, Two point step size gradient methods,, IMA Journal of Numerical Analysis, 8 (1988), 141.  doi: 10.1093/imanum/8.1.141.  Google Scholar

[3]

Z. Bai, J. Dongarra, A. Ruhe and H. van der Vorst, Templates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide,, SIAM, (2000).  doi: 10.1137/1.9780898719581.  Google Scholar

[4]

J. K. Cullum and R. A. Willoughby, Lanczos Algorithms for Large Symmetric Eigenvalue,, the United States of America: SIAM, (1985).   Google Scholar

[5]

Y. H. Dai, On the nonmonotone line search,, Journal of Optimization Theory and Applications, 112 (2002), 315.  doi: 10.1023/A:1013653923062.  Google Scholar

[6]

Y. H. Dai and R. Fletcher, Projected Barzilai-Borwein methods for large-scale box-constrained quadratic programming,, Numerische Mathematik, 100 (2005), 21.  doi: 10.1007/s00211-004-0569-y.  Google Scholar

[7]

Y. H. Dai, W. W. Hager, K. Schittkowski and H. C. Zhang, The cycle Barzilai-Borwein method for unconstrained optimization,, IMA Journal of Numerical Analysis, 26 (2006), 604.  doi: 10.1093/imanum/drl006.  Google Scholar

[8]

Y. H. Dai and C. X. Kou, A nonlinear conjugate gradient algorithm with an optimal property and an improved Wolfe line search,, SIAM Journal on Optimization, 23 (2013), 296.  doi: 10.1137/100813026.  Google Scholar

[9]

Y. H. Dai and L. Z. Liao, $R$-linear convergence of the Barzilai and Borwein gradient method,, IMA Journal of Numerical Analysis, 22 (2002), 1.  doi: 10.1093/imanum/22.1.1.  Google Scholar

[10]

Y. H. Dai and H. C. Zhang, Adaptive two-point stepsize gradient algorithm,, Numerical Algorithms, 27 (2001), 377.  doi: 10.1023/A:1013844413130.  Google Scholar

[11]

T. A. Davis and Y. H. Hu, The University of Florida Sparse Matrix Collection,, University of Florida, (2011).  doi: 10.1145/2049662.2049663.  Google Scholar

[12]

E. D. Dolan and J. J. Moré, Benchmarking optimization software with performance profiles,, Mathematical Programming Series A, 91 (2002), 201.  doi: 10.1007/s101070100263.  Google Scholar

[13]

R. Fletcher, On the Barzilai-Borwein method,, in Optimization and Control with Applications (eds. L.Q. Qi, 96 (2005), 235.  doi: 10.1007/0-387-24255-4_10.  Google Scholar

[14]

L. Grippo, F. Lampariello and S. Lucidi, A nonmonotone line search technique for Newton's method,, SIAM Journal on Numerical Analysis, 23 (1986), 707.  doi: 10.1137/0723046.  Google Scholar

[15]

G. H. Golub and C. F. Van Loan, Matrix computation,, $3^{nd}$ edition, (1996).   Google Scholar

[16]

W. W. Hager and H. Zhang, A new conjugate gradient method with guaranteed descent and an efficient line search,, SIAM Journal on Optimization, 16 (2005), 170.  doi: 10.1137/030601880.  Google Scholar

[17]

B. Jiang and Y. H. Dai, Feasible Barzilai-Borwein-like methods for extreme symmetric eigenvalue problems,, Optimization Methods and Software, 28 (2013), 756.  doi: 10.1080/10556788.2012.656115.  Google Scholar

[18]

M. Mongeau and M. Torki, Computing eigenelements of real symmetric matrices via optimization,, Computational Optimization and Applications, 29 (2004), 263.  doi: 10.1023/B:COAP.0000044182.33308.82.  Google Scholar

[19]

M. Raydan, On the Barzilai and Borwein of steplength for gradient method,, IMA Journal of Numerical Analysis, 13 (1993), 321.  doi: 10.1093/imanum/13.3.321.  Google Scholar

[20]

Y. Saad, Numerical Methods for Large Eigenvalue Problems,, Manchester University: The Society of Industrial and Applied Mathematics, (2011).  doi: 10.1137/1.9781611970739.  Google Scholar

[21]

A. H. Sameh and J. A. Wisniewski, A trace minimization algorithm for the generalized eigenvalue problem computations,, SIAM Journal on Numerical Analysis, 19 (1982), 1243.  doi: 10.1137/0719089.  Google Scholar

[22]

P. L. Toint, Non-monotone trust-region algorithms for nonlinear optimization subject to convex constraints,, Mathematical Programming, 77 (1997), 69.  doi: 10.1007/BF02614518.  Google Scholar

[23]

H. C. Zhang and W. W. Hager, PACBB: A projected adaptive CBB (PACBB) method for box constrained optimization,, Nonconvex Optimization and Its Applications, 82 (2006), 387.   Google Scholar

[24]

B. Zhou, L. Gao and Y. H. Dai, Gradient methods with adaptive step sizes,, Computation Optimization and Applications, 35 (2006), 69.  doi: 10.1007/s10589-006-6446-0.  Google Scholar

[1]

Hong Seng Sim, Wah June Leong, Chuei Yee Chen, Siti Nur Iqmal Ibrahim. Multi-step spectral gradient methods with modified weak secant relation for large scale unconstrained optimization. Numerical Algebra, Control & Optimization, 2018, 8 (3) : 377-387. doi: 10.3934/naco.2018024

[2]

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

[3]

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399

[4]

Sandrine Anthoine, Jean-François Aujol, Yannick Boursier, Clothilde Mélot. Some proximal methods for Poisson intensity CBCT and PET. Inverse Problems & Imaging, 2012, 6 (4) : 565-598. doi: 10.3934/ipi.2012.6.565

[5]

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

[6]

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

[7]

J. Frédéric Bonnans, Justina Gianatti, Francisco J. Silva. On the convergence of the Sakawa-Shindo algorithm in stochastic control. Mathematical Control & Related Fields, 2016, 6 (3) : 391-406. doi: 10.3934/mcrf.2016008

[8]

Rafael Luís, Sandra Mendonça. A note on global stability in the periodic logistic map. Discrete & Continuous Dynamical Systems - B, 2020, 25 (11) : 4211-4220. doi: 10.3934/dcdsb.2020094

[9]

Fernando P. da Costa, João T. Pinto, Rafael Sasportes. On the convergence to critical scaling profiles in submonolayer deposition models. Kinetic & Related Models, 2018, 11 (6) : 1359-1376. doi: 10.3934/krm.2018053

[10]

Alberto Bressan, Carlotta Donadello. On the convergence of viscous approximations after shock interactions. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 29-48. doi: 10.3934/dcds.2009.23.29

[11]

Lakmi Niwanthi Wadippuli, Ivan Gudoshnikov, Oleg Makarenkov. Global asymptotic stability of nonconvex sweeping processes. Discrete & Continuous Dynamical Systems - B, 2020, 25 (3) : 1129-1139. doi: 10.3934/dcdsb.2019212

[12]

Caifang Wang, Tie Zhou. The order of convergence for Landweber Scheme with $\alpha,\beta$-rule. Inverse Problems & Imaging, 2012, 6 (1) : 133-146. doi: 10.3934/ipi.2012.6.133

[13]

Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023

[14]

Bernold Fiedler, Carlos Rocha, Matthias Wolfrum. Sturm global attractors for $S^1$-equivariant parabolic equations. Networks & Heterogeneous Media, 2012, 7 (4) : 617-659. doi: 10.3934/nhm.2012.7.617

[15]

Jiangxing Wang. Convergence analysis of an accurate and efficient method for nonlinear Maxwell's equations. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2429-2440. doi: 10.3934/dcdsb.2020185

[16]

Manoel J. Dos Santos, Baowei Feng, Dilberto S. Almeida Júnior, Mauro L. Santos. Global and exponential attractors for a nonlinear porous elastic system with delay term. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2805-2828. doi: 10.3934/dcdsb.2020206

[17]

Abdulrazzaq T. Abed, Azzam S. Y. Aladool. Applying particle swarm optimization based on Padé approximant to solve ordinary differential equation. Numerical Algebra, Control & Optimization, 2021  doi: 10.3934/naco.2021008

[18]

Mohsen Abdolhosseinzadeh, Mir Mohammad Alipour. Design of experiment for tuning parameters of an ant colony optimization method for the constrained shortest Hamiltonian path problem in the grid networks. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 321-332. doi: 10.3934/naco.2020028

[19]

Reza Lotfi, Yahia Zare Mehrjerdi, Mir Saman Pishvaee, Ahmad Sadeghieh, Gerhard-Wilhelm Weber. A robust optimization model for sustainable and resilient closed-loop supply chain network design considering conditional value at risk. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 221-253. doi: 10.3934/naco.2020023

[20]

Irena PawŃow, Wojciech M. Zajączkowski. Global regular solutions to three-dimensional thermo-visco-elasticity with nonlinear temperature-dependent specific heat. Communications on Pure & Applied Analysis, 2017, 16 (4) : 1331-1372. doi: 10.3934/cpaa.2017065

2019 Impact Factor: 1.366

Metrics

  • PDF downloads (268)
  • HTML views (0)
  • Cited by (3)

Other articles
by authors

[Back to Top]