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]

SIAM J. Math. Anal., 20 (1989), 1186-1207. doi: 10.1137/0520078.  Google Scholar

[2]

IMA Journal of Numerical Analysis, 8 (1988), 141-148. doi: 10.1093/imanum/8.1.141.  Google Scholar

[3]

SIAM, Philadelphia, 2000. doi: 10.1137/1.9780898719581.  Google Scholar

[4]

the United States of America: SIAM, 1985. Google Scholar

[5]

Journal of Optimization Theory and Applications, 112 (2002), 315-330. doi: 10.1023/A:1013653923062.  Google Scholar

[6]

Numerische Mathematik, 100 (2005), 21-47. doi: 10.1007/s00211-004-0569-y.  Google Scholar

[7]

IMA Journal of Numerical Analysis, 26 (2006), 604-627. doi: 10.1093/imanum/drl006.  Google Scholar

[8]

SIAM Journal on Optimization, 23 (2013), 296-320. doi: 10.1137/100813026.  Google Scholar

[9]

IMA Journal of Numerical Analysis, 22 (2002), 1-10. doi: 10.1093/imanum/22.1.1.  Google Scholar

[10]

Numerical Algorithms, 27 (2001), 377-385. doi: 10.1023/A:1013844413130.  Google Scholar

[11]

University of Florida, ACM Transactions on Mathematical Software, 2011. doi: 10.1145/2049662.2049663.  Google Scholar

[12]

Mathematical Programming Series A, 91 (2002), 201-213. doi: 10.1007/s101070100263.  Google Scholar

[13]

in Optimization and Control with Applications (eds. L.Q. Qi, K.L. Teo and X.Q. Yang), 96 (2005), 235-256. doi: 10.1007/0-387-24255-4_10.  Google Scholar

[14]

SIAM Journal on Numerical Analysis, 23 (1986), 707-716. doi: 10.1137/0723046.  Google Scholar

[15]

$3^{nd}$ edition, John Hopkins University Press, Baltimore, MD, 1996. Google Scholar

[16]

SIAM Journal on Optimization, 16 (2005), 170-192. doi: 10.1137/030601880.  Google Scholar

[17]

Optimization Methods and Software, 28 (2013), 756-784. doi: 10.1080/10556788.2012.656115.  Google Scholar

[18]

Computational Optimization and Applications, 29 (2004), 263-287. doi: 10.1023/B:COAP.0000044182.33308.82.  Google Scholar

[19]

IMA Journal of Numerical Analysis, 13 (1993), 321-326. doi: 10.1093/imanum/13.3.321.  Google Scholar

[20]

Manchester University: The Society of Industrial and Applied Mathematics, 2011. doi: 10.1137/1.9781611970739.  Google Scholar

[21]

SIAM Journal on Numerical Analysis, 19 (1982), 1243-1259. doi: 10.1137/0719089.  Google Scholar

[22]

Mathematical Programming, 77 (1997), 69-94. doi: 10.1007/BF02614518.  Google Scholar

[23]

Nonconvex Optimization and Its Applications, 82 (2006), 387-392. Google Scholar

[24]

Computation Optimization and Applications, 35 (2006), 69-86. doi: 10.1007/s10589-006-6446-0.  Google Scholar

show all references

References:
[1]

SIAM J. Math. Anal., 20 (1989), 1186-1207. doi: 10.1137/0520078.  Google Scholar

[2]

IMA Journal of Numerical Analysis, 8 (1988), 141-148. doi: 10.1093/imanum/8.1.141.  Google Scholar

[3]

SIAM, Philadelphia, 2000. doi: 10.1137/1.9780898719581.  Google Scholar

[4]

the United States of America: SIAM, 1985. Google Scholar

[5]

Journal of Optimization Theory and Applications, 112 (2002), 315-330. doi: 10.1023/A:1013653923062.  Google Scholar

[6]

Numerische Mathematik, 100 (2005), 21-47. doi: 10.1007/s00211-004-0569-y.  Google Scholar

[7]

IMA Journal of Numerical Analysis, 26 (2006), 604-627. doi: 10.1093/imanum/drl006.  Google Scholar

[8]

SIAM Journal on Optimization, 23 (2013), 296-320. doi: 10.1137/100813026.  Google Scholar

[9]

IMA Journal of Numerical Analysis, 22 (2002), 1-10. doi: 10.1093/imanum/22.1.1.  Google Scholar

[10]

Numerical Algorithms, 27 (2001), 377-385. doi: 10.1023/A:1013844413130.  Google Scholar

[11]

University of Florida, ACM Transactions on Mathematical Software, 2011. doi: 10.1145/2049662.2049663.  Google Scholar

[12]

Mathematical Programming Series A, 91 (2002), 201-213. doi: 10.1007/s101070100263.  Google Scholar

[13]

in Optimization and Control with Applications (eds. L.Q. Qi, K.L. Teo and X.Q. Yang), 96 (2005), 235-256. doi: 10.1007/0-387-24255-4_10.  Google Scholar

[14]

SIAM Journal on Numerical Analysis, 23 (1986), 707-716. doi: 10.1137/0723046.  Google Scholar

[15]

$3^{nd}$ edition, John Hopkins University Press, Baltimore, MD, 1996. Google Scholar

[16]

SIAM Journal on Optimization, 16 (2005), 170-192. doi: 10.1137/030601880.  Google Scholar

[17]

Optimization Methods and Software, 28 (2013), 756-784. doi: 10.1080/10556788.2012.656115.  Google Scholar

[18]

Computational Optimization and Applications, 29 (2004), 263-287. doi: 10.1023/B:COAP.0000044182.33308.82.  Google Scholar

[19]

IMA Journal of Numerical Analysis, 13 (1993), 321-326. doi: 10.1093/imanum/13.3.321.  Google Scholar

[20]

Manchester University: The Society of Industrial and Applied Mathematics, 2011. doi: 10.1137/1.9781611970739.  Google Scholar

[21]

SIAM Journal on Numerical Analysis, 19 (1982), 1243-1259. doi: 10.1137/0719089.  Google Scholar

[22]

Mathematical Programming, 77 (1997), 69-94. doi: 10.1007/BF02614518.  Google Scholar

[23]

Nonconvex Optimization and Its Applications, 82 (2006), 387-392. Google Scholar

[24]

Computation Optimization and Applications, 35 (2006), 69-86. doi: 10.1007/s10589-006-6446-0.  Google Scholar

[1]

Sarra Delladji, Mohammed Belloufi, Badreddine Sellami. Behavior of the combination of PRP and HZ methods for unconstrained optimization. Numerical Algebra, Control & Optimization, 2021, 11 (3) : 377-389. doi: 10.3934/naco.2020032

[2]

Hong-Yi Miao, Li Wang. Preconditioned inexact Newton-like method for large nonsymmetric eigenvalue problems. Numerical Algebra, Control & Optimization, 2021  doi: 10.3934/naco.2021012

[3]

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

[4]

Zehui Jia, Xue Gao, Xingju Cai, Deren Han. The convergence rate analysis of the symmetric ADMM for the nonconvex separable optimization problems. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1943-1971. doi: 10.3934/jimo.2020053

[5]

Craig Cowan. Supercritical elliptic problems involving a Cordes like operator. Discrete & Continuous Dynamical Systems, 2021  doi: 10.3934/dcds.2021037

[6]

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, 2007, 17 (2) : 397-402. doi: 10.3934/dcds.2007.17.397

[7]

Tengteng Yu, Xin-Wei Liu, Yu-Hong Dai, Jie Sun. Variable metric proximal stochastic variance reduced gradient methods for nonconvex nonsmooth optimization. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021084

[8]

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

[9]

Xiaofei Liu, Yong Wang. Weakening convergence conditions of a potential reduction method for tensor complementarity problems. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021080

[10]

Jiangang Qi, Bing Xie. Extremum estimates of the $ L^1 $-norm of weights for eigenvalue problems of vibrating string equations based on critical equations. Discrete & Continuous Dynamical Systems - B, 2021, 26 (7) : 3505-3516. doi: 10.3934/dcdsb.2020243

[11]

Xin-Guang Yang, Rong-Nian Wang, Xingjie Yan, Alain Miranville. Dynamics of the 2D Navier-Stokes equations with sublinear operators in Lipschitz-like domains. Discrete & Continuous Dynamical Systems, 2021, 41 (7) : 3343-3366. doi: 10.3934/dcds.2020408

[12]

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

[13]

Takeshi Saito, Kazuyuki Yagasaki. Chebyshev spectral methods for computing center manifolds. Journal of Computational Dynamics, 2021  doi: 10.3934/jcd.2021008

[14]

Samira Shahsavari, Saeed Ketabchi. The proximal methods for solving absolute value equation. Numerical Algebra, Control & Optimization, 2021, 11 (3) : 449-460. doi: 10.3934/naco.2020037

[15]

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

[16]

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

[17]

Fioralba Cakoni, Pu-Zhao Kow, Jenn-Nan Wang. The interior transmission eigenvalue problem for elastic waves in media with obstacles. Inverse Problems & Imaging, 2021, 15 (3) : 445-474. doi: 10.3934/ipi.2020075

[18]

Jun He, Guangjun Xu, Yanmin Liu. New Z-eigenvalue localization sets for tensors with applications. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021058

[19]

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

[20]

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

2019 Impact Factor: 1.366

Metrics

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

Other articles
by authors

[Back to Top]