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.

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

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

[4]

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

[5]

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

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

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

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

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

[10]

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

[11]

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

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

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

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

[15]

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

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

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

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

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

[20]

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

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

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

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

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

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.

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

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

[4]

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

[5]

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

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

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

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

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

[10]

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

[11]

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

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

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

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

[15]

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

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

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

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

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

[20]

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

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

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

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

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

[1]

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

[2]

Wataru Nakamura, Yasushi Narushima, Hiroshi Yabe. Nonlinear conjugate gradient methods with sufficient descent properties for unconstrained optimization. Journal of Industrial & Management Optimization, 2013, 9 (3) : 595-619. doi: 10.3934/jimo.2013.9.595

[3]

Guanghui Zhou, Qin Ni, Meilan Zeng. A scaled conjugate gradient method with moving asymptotes for unconstrained optimization problems. Journal of Industrial & Management Optimization, 2017, 13 (2) : 595-608. doi: 10.3934/jimo.2016034

[4]

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

[5]

Shummin Nakayama, Yasushi Narushima, Hiroshi Yabe. Memoryless quasi-Newton methods based on spectral-scaling Broyden family for unconstrained optimization. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-21. doi: 10.3934/jimo.2018122

[6]

Alexander Mielke. Weak-convergence methods for Hamiltonian multiscale problems. Discrete & Continuous Dynamical Systems - A, 2008, 20 (1) : 53-79. doi: 10.3934/dcds.2008.20.53

[7]

Mohamed Aly Tawhid. Nonsmooth generalized complementarity as unconstrained optimization. Journal of Industrial & Management Optimization, 2010, 6 (2) : 411-423. doi: 10.3934/jimo.2010.6.411

[8]

Björn Sandstede, Arnd Scheel. Evans function and blow-up methods in critical eigenvalue problems. Discrete & Continuous Dynamical Systems - A, 2004, 10 (4) : 941-964. doi: 10.3934/dcds.2004.10.941

[9]

Qun Lin, Hehu Xie. Recent results on lower bounds of eigenvalue problems by nonconforming finite element methods. Inverse Problems & Imaging, 2013, 7 (3) : 795-811. doi: 10.3934/ipi.2013.7.795

[10]

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

[11]

Jie Sun. On methods for solving nonlinear semidefinite optimization problems. Numerical Algebra, Control & Optimization, 2011, 1 (1) : 1-14. doi: 10.3934/naco.2011.1.1

[12]

Li-Fang Dai, Mao-Lin Liang, Wei-Yuan Ma. Optimization problems on the rank of the solution to left and right inverse eigenvalue problem. Journal of Industrial & Management Optimization, 2015, 11 (1) : 171-183. doi: 10.3934/jimo.2015.11.171

[13]

Tetsutaro Shibata. Global behavior of bifurcation curves for the nonlinear eigenvalue problems with periodic nonlinear terms. Communications on Pure & Applied Analysis, 2018, 17 (5) : 2139-2147. doi: 10.3934/cpaa.2018102

[14]

Chunlin Hao, Xinwei Liu. Global convergence of an SQP algorithm for nonlinear optimization with overdetermined constraints. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 19-29. doi: 10.3934/naco.2012.2.19

[15]

Jun Chen, Wenyu Sun, Zhenghao Yang. A non-monotone retrospective trust-region method for unconstrained optimization. Journal of Industrial & Management Optimization, 2013, 9 (4) : 919-944. doi: 10.3934/jimo.2013.9.919

[16]

Lijuan Zhao, Wenyu Sun. Nonmonotone retrospective conic trust region method for unconstrained optimization. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 309-325. doi: 10.3934/naco.2013.3.309

[17]

Lixing Han. An unconstrained optimization approach for finding real eigenvalues of even order symmetric tensors. Numerical Algebra, Control & Optimization, 2013, 3 (3) : 583-599. doi: 10.3934/naco.2013.3.583

[18]

Xin Zhang, Jie Wen, Qin Ni. Subspace trust-region algorithm with conic model for unconstrained optimization. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 223-234. doi: 10.3934/naco.2013.3.223

[19]

Maria Fărcăşeanu, Mihai Mihăilescu, Denisa Stancu-Dumitru. Perturbed fractional eigenvalue problems. Discrete & Continuous Dynamical Systems - A, 2017, 37 (12) : 6243-6255. doi: 10.3934/dcds.2017270

[20]

Ravi P. Agarwal, Kanishka Perera, Zhitao Zhang. On some nonlocal eigenvalue problems. Discrete & Continuous Dynamical Systems - S, 2012, 5 (4) : 707-714. doi: 10.3934/dcdss.2012.5.707

2017 Impact Factor: 0.994

Metrics

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

Other articles
by authors

[Back to Top]