• Previous Article
    Steady-state and first passage time distributions for waiting times in the $ MAP/M/s+G $ queueing model with generally distributed patience times
  • JIMO Home
  • This Issue
  • Next Article
    Optimal replenishment, pricing and preservation technology investment policies for non-instantaneous deteriorating items under two-level trade credit policy
doi: 10.3934/jimo.2021206
Online First

Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Online First articles via the “Online First” tab for the selected journal.

Trace minimization method via penalty for linear response eigenvalue problems

1. 

China National Clearing Center, Beijing 100048, China

2. 

School of Economics and Management, University of the Chinese Academy of Sciences, Beijing 100190, China

3. 

School of Applied Mathematics, Nanjing University of Finance & Economics, Nanjing 210023, China

4. 

Hefei 168 Middle School, Hefei 230031, China

*Corresponding author: Yuan Shen

Received  June 2021 Revised  August 2021 Early access December 2021

Fund Project: The second author is supported by the National Social Science Foundation of China under Grants 19AZD018, 20BGL028, 19BGL205, 17BTQ063

In various applications, such as the computation of energy excitation states of electrons and molecules, and the analysis of interstellar clouds, the linear response eigenvalue problem, which is a special type of the Hamiltonian eigenvalue problem, is frequently encountered. However, traditional eigensolvers may not be applicable to this problem owing to its inherently large scale. In fact, we are usually more interested in computing some of the smallest positive eigenvalues. To this end, a trace minimum principle optimization model with orthogonality constraint has been proposed. On this basis, we propose an unconstrained surrogate model called trace minimization via penalty, and we establish its equivalence with the original constrained model, provided that the penalty parameter is larger than a certain threshold. By avoiding the orthogonality constraint, we can use a gradient-type method to solve this model. Specifically, we use the gradient descent method with Barzilai–Borwein step size. Moreover, we develop a restarting strategy for the proposed algorithm whereby higher accuracy and faster convergence can be achieved. This is verified by preliminary experimental results.

Citation: Yadan Chen, Yuan Shen, Shanshan Liu. Trace minimization method via penalty for linear response eigenvalue problems. Journal of Industrial and Management Optimization, doi: 10.3934/jimo.2021206
References:
[1]

Z. Bai and R. Li, Minimization principles for the linear response eigenvalue problem I: Theory, SIAM J. Matrix Anal. Appl., 33 (2012), 1075-1100.  doi: 10.1137/110838960.

[2]

Z. Bai and R. Li, Minimization principles for the linear response eigenvalue problem II: Computation, SIAM J. Matrix Anal. Appl., 34 (2013), 392-416.  doi: 10.1137/110838972.

[3]

Z. BaiR. Li and W. Lin, Linear response eigenvalue problem solved by extended locally optimal preconditioned conjugate gradient methods, Sci. China Math., 59 (2016), 1443-1460.  doi: 10.1007/s11425-016-0297-1.

[4]

P. BennerH. Fassbender and M. Stoll, A Hamiltonian Krylov-Schur-type method based on the symplectic Lanczos process, Linear Algebra Appl., 435 (2011), 578-600.  doi: 10.1016/j.laa.2010.04.048.

[5]

M. E. Casida, Time-dependent density-functional response theory for molecules, Recent Advances in Density Functional Methods, (1995), 155–192. doi: 10.1142/9789812830586_0005.

[6]

U. FlaschkaW. Lin and J. Wu, A KQZ algorithm for solving linear-response eigenvalue equations, Linear Algebra Appl., 165 (1992), 93-123.  doi: 10.1016/0024-3795(92)90231-X.

[7]

G. Golub and W. Kahan, Calculating the singular values and pseudo-inverse of a matrix, J. Soc. Indust. Appl. Math. Ser. B Numer. Anal., 2 (1965), 205-224.  doi: 10.1137/0702016.

[8]

M. GruningA. Marini and X. Gonze, Exciton-plasmon states in nanoscale materials: Breakdown of the Tamm-Dancoff approximation, Nano Letters, 9 (2009), 2820-2824.  doi: 10.1021/nl803717g.

[9]

W. Lin, P. van Dooren and Q. Xu, Equivalent Characterizations of Periodical Ininvariant Subspaces, NCTS Preprints Series 1998-8, National Center for Theoretical Sciences, Math. Division, National Tsing Hua University, 1998.

[10]

X. Liu, Z. Wen and Y. Zhang, Limited memory block Krylov subspace optimization for computing dominant singular value decompositions, SIAM J. Sci. Comput., 35 (2013), A1641–A1668. doi: 10.1137/120871328.

[11]

X. LiuZ. Wen and Y. Zhang, An efficient Gauss-Newton algorithm for symmetric low-rank product matrix approximations, SIAM J. Optim., 25 (2015), 1571-1608.  doi: 10.1137/140971464.

[12]

M. J. LuceroA. M. N. NiklassonS. Tretiak and M. Challacombe, Molecular-orbital-free algorithm for excited states in time-dependent perturbation theory, J. Chem. Phys., 129 (2008), 064114.  doi: 10.1063/1.2965535.

[13]

M. T. Lusk and A. E. Mattsson, High-performance computing for materials design to advance energy science, MRS Bulletin, 36 (2011), 169-174.  doi: 10.1557/mrs.2011.30.

[14]

J. Olsen and P. Jorgensen, Linear and nonlinear response functions for an exact state and for an MCSCF state, J. Chem. Phys., 82 (1985), 3235-3264.  doi: 10.1063/1.448223.

[15]

G. OnidaL. Reining and A. Rubio, Electronic excitations: Density-functional versus manybody Green's function approaches, Rev. Modern Phys., 74 (2002), 601-659.  doi: 10.1103/RevModPhys.74.601.

[16]

D. RoccaD. Lu and G. Galli, Ab initio calculations of optical absorpation spectra: Solution of the Bethe-Salpeter equation within density matrix perturbation theory, J. Chem. Phys., 133 (2010), 164109. 

[17]

Y. SaadJ. R. Chelikowsky and S. M. Shontz, Numerical methods for electronic structure calculations of materials, SIAM Rev., 52 (2010), 3-54.  doi: 10.1137/060651653.

[18]

Z. Teng and R. Li, Convergence analysis of Lanczos-type methods for the linear response eigenvalue problem, J. Comput. Appl. Math., 247 (2013), 17-33.  doi: 10.1016/j.cam.2013.01.003.

[19]

Z. TengY. Zhou and R. Li, A block Chebyshev-Davidson method for linear response eigenvalue problems, Adv. Comput. Math., 42 (2016), 1103-1128.  doi: 10.1007/s10444-016-9455-2.

[20]

Z. WenC. YangX. Liu and Y. Zhang, Trace-penalty minimization for large-scale eigenspace computation, J. Sci. Comput., 66 (2016), 1175-1203.  doi: 10.1007/s10915-015-0061-0.

[21]

H. Zhong and H. Xu, Weighted Golub-Kahan-Lanczos bidiagonalization algorithms, Electron. Trans. Numer. Anal., 47 (2017), 153-178.  doi: 10.1553/etna_vol47s153.

show all references

References:
[1]

Z. Bai and R. Li, Minimization principles for the linear response eigenvalue problem I: Theory, SIAM J. Matrix Anal. Appl., 33 (2012), 1075-1100.  doi: 10.1137/110838960.

[2]

Z. Bai and R. Li, Minimization principles for the linear response eigenvalue problem II: Computation, SIAM J. Matrix Anal. Appl., 34 (2013), 392-416.  doi: 10.1137/110838972.

[3]

Z. BaiR. Li and W. Lin, Linear response eigenvalue problem solved by extended locally optimal preconditioned conjugate gradient methods, Sci. China Math., 59 (2016), 1443-1460.  doi: 10.1007/s11425-016-0297-1.

[4]

P. BennerH. Fassbender and M. Stoll, A Hamiltonian Krylov-Schur-type method based on the symplectic Lanczos process, Linear Algebra Appl., 435 (2011), 578-600.  doi: 10.1016/j.laa.2010.04.048.

[5]

M. E. Casida, Time-dependent density-functional response theory for molecules, Recent Advances in Density Functional Methods, (1995), 155–192. doi: 10.1142/9789812830586_0005.

[6]

U. FlaschkaW. Lin and J. Wu, A KQZ algorithm for solving linear-response eigenvalue equations, Linear Algebra Appl., 165 (1992), 93-123.  doi: 10.1016/0024-3795(92)90231-X.

[7]

G. Golub and W. Kahan, Calculating the singular values and pseudo-inverse of a matrix, J. Soc. Indust. Appl. Math. Ser. B Numer. Anal., 2 (1965), 205-224.  doi: 10.1137/0702016.

[8]

M. GruningA. Marini and X. Gonze, Exciton-plasmon states in nanoscale materials: Breakdown of the Tamm-Dancoff approximation, Nano Letters, 9 (2009), 2820-2824.  doi: 10.1021/nl803717g.

[9]

W. Lin, P. van Dooren and Q. Xu, Equivalent Characterizations of Periodical Ininvariant Subspaces, NCTS Preprints Series 1998-8, National Center for Theoretical Sciences, Math. Division, National Tsing Hua University, 1998.

[10]

X. Liu, Z. Wen and Y. Zhang, Limited memory block Krylov subspace optimization for computing dominant singular value decompositions, SIAM J. Sci. Comput., 35 (2013), A1641–A1668. doi: 10.1137/120871328.

[11]

X. LiuZ. Wen and Y. Zhang, An efficient Gauss-Newton algorithm for symmetric low-rank product matrix approximations, SIAM J. Optim., 25 (2015), 1571-1608.  doi: 10.1137/140971464.

[12]

M. J. LuceroA. M. N. NiklassonS. Tretiak and M. Challacombe, Molecular-orbital-free algorithm for excited states in time-dependent perturbation theory, J. Chem. Phys., 129 (2008), 064114.  doi: 10.1063/1.2965535.

[13]

M. T. Lusk and A. E. Mattsson, High-performance computing for materials design to advance energy science, MRS Bulletin, 36 (2011), 169-174.  doi: 10.1557/mrs.2011.30.

[14]

J. Olsen and P. Jorgensen, Linear and nonlinear response functions for an exact state and for an MCSCF state, J. Chem. Phys., 82 (1985), 3235-3264.  doi: 10.1063/1.448223.

[15]

G. OnidaL. Reining and A. Rubio, Electronic excitations: Density-functional versus manybody Green's function approaches, Rev. Modern Phys., 74 (2002), 601-659.  doi: 10.1103/RevModPhys.74.601.

[16]

D. RoccaD. Lu and G. Galli, Ab initio calculations of optical absorpation spectra: Solution of the Bethe-Salpeter equation within density matrix perturbation theory, J. Chem. Phys., 133 (2010), 164109. 

[17]

Y. SaadJ. R. Chelikowsky and S. M. Shontz, Numerical methods for electronic structure calculations of materials, SIAM Rev., 52 (2010), 3-54.  doi: 10.1137/060651653.

[18]

Z. Teng and R. Li, Convergence analysis of Lanczos-type methods for the linear response eigenvalue problem, J. Comput. Appl. Math., 247 (2013), 17-33.  doi: 10.1016/j.cam.2013.01.003.

[19]

Z. TengY. Zhou and R. Li, A block Chebyshev-Davidson method for linear response eigenvalue problems, Adv. Comput. Math., 42 (2016), 1103-1128.  doi: 10.1007/s10444-016-9455-2.

[20]

Z. WenC. YangX. Liu and Y. Zhang, Trace-penalty minimization for large-scale eigenspace computation, J. Sci. Comput., 66 (2016), 1175-1203.  doi: 10.1007/s10915-015-0061-0.

[21]

H. Zhong and H. Xu, Weighted Golub-Kahan-Lanczos bidiagonalization algorithms, Electron. Trans. Numer. Anal., 47 (2017), 153-178.  doi: 10.1553/etna_vol47s153.

Figure 1.  Normalized residual norm vs iteration with $ k = 5 $ (upper left: $ n = 1000 $; upper right: $ n = 2000 $; lower left: $ n = 4000 $; lower right: $ n = 6000 $)
Figure 2.  Normalized residual norm vs iteration with $ k = 50 $ (upper left: $ n = 1000 $; upper right: $ n = 2000 $; lower left: $ n = 4000 $; lower right: $ n = 6000 $)
Figure 3.  Frobenius norm of gradient vs iteration with $ k = 5 $ (upper left: $ n = 1000 $; upper right: $ n = 2000 $; lower left: $ n = 4000 $; lower right: $ n = 6000 $)
Figure 4.  Frobenius norm of gradient vs iteration with $ k = 50 $ (upper left: $ n = 1000 $; upper right: $ n = 2000 $; lower left: $ n = 4000 $; lower right: $ n = 6000 $)
Figure 5.  Normalized residual norm via iteration with $ k = 5 $ (left: n = 1000; middle: n = 2000; right: n = 4000)
Figure 6.  Frobenius norm of gradient via iteration with $ k = 5 $ (left: n = 1000; middle: n = 2000; right: n = 4000)
Table 1.  Numerical results on random problems
($ n, k $) LOBP4dCG Bcheb-dav Alg. 1
NRN time NRN time NRN time
(1000, 5) 3.374e-7 5.158 4.370e-7 1.213 9.953e-7 1.391
(2000, 5) 2.792e-6 16.156 5.319e-7 5.425 9.973e-7 2.529
(4000, 5) 2.052e-7 46.707 7.597e-7 29.476 9.355e-7 4.848
(6000, 5) 2.964e-7 219.598 7.230e-7 127.189 6.736e-7 17.503
($ n, k $) LOBP4dCG Bcheb-dav Alg. 1
NRN time NRN time NRN time
(1000, 5) 3.374e-7 5.158 4.370e-7 1.213 9.953e-7 1.391
(2000, 5) 2.792e-6 16.156 5.319e-7 5.425 9.973e-7 2.529
(4000, 5) 2.052e-7 46.707 7.597e-7 29.476 9.355e-7 4.848
(6000, 5) 2.964e-7 219.598 7.230e-7 127.189 6.736e-7 17.503
Table 2.  Numerical results on random problems
($ n, k $) Bcheb-dav Alg. 1
NRN time NRN time
(1000, 50) 8.179e-7 1.924 6.617e-6 5.286
(2000, 50) 1.351e-7 10.493 9.445e-7 27.038
(4000, 50) 1.713e-7 45.975 9.239e-7 55.971
(6000, 50) 4.060e-7 237.142 9.587e-7 189.574
($ n, k $) Bcheb-dav Alg. 1
NRN time NRN time
(1000, 50) 8.179e-7 1.924 6.617e-6 5.286
(2000, 50) 1.351e-7 10.493 9.445e-7 27.038
(4000, 50) 1.713e-7 45.975 9.239e-7 55.971
(6000, 50) 4.060e-7 237.142 9.587e-7 189.574
Table 3.  Numerical results on random problems with smaller $ k $
($ n, k $) LOBP4dCG Bcheb-dav Alg. 1
NRN time NRN time NRN time
(1000, 2) 9.353e-10 1.034 2.347e-7 1.920 8.977e-7 0.522
(2000, 2) 2.639e-9 4.906 8.093e-7 5.481 9.122e-7 0.928
(4000, 2) 1.283e-9 21.372 9.518e-7 35.761 9.729e-7 1.159
(6000, 2) 2.050e-9 59.513 9.235e-7 218.249 6.868e-7 5.190
($ n, k $) LOBP4dCG Bcheb-dav Alg. 1
NRN time NRN time NRN time
(1000, 2) 9.353e-10 1.034 2.347e-7 1.920 8.977e-7 0.522
(2000, 2) 2.639e-9 4.906 8.093e-7 5.481 9.122e-7 0.928
(4000, 2) 1.283e-9 21.372 9.518e-7 35.761 9.729e-7 1.159
(6000, 2) 2.050e-9 59.513 9.235e-7 218.249 6.868e-7 5.190
Table 4.  Numerical results on random problems with larger $ k $
($ n, k $) Bcheb-dav Alg. 1
NRN time NRN time
(500, 50) 1.721e-8 0.572 9.607e-6 2.462
(750, 75) 2.133e-8 1.740 9.994e-6 6.769
(1000, 100) 1.299e-8 2.945 9.902e-6 16.409
(1500, 150) 4.218e-8 10.376 9.999e-6 24.900
(2000, 200) 2.782e-8 19.507 7.717e-6 64.872
($ n, k $) Bcheb-dav Alg. 1
NRN time NRN time
(500, 100) 1.713e-8 1.557 9.989e-6 7.355
(750, 150) 1.606e-8 2.310 9.996e-6 20.053
(1000, 200) 2.837e-8 6.128 9.993e-6 46.477
(1500, 300) 2.647e-8 15.524 9.815e-6 85.150
(2000, 400) 1.692e-8 28.886 4.970e-6 415.430
($ n, k $) Bcheb-dav Alg. 1
NRN time NRN time
(500, 50) 1.721e-8 0.572 9.607e-6 2.462
(750, 75) 2.133e-8 1.740 9.994e-6 6.769
(1000, 100) 1.299e-8 2.945 9.902e-6 16.409
(1500, 150) 4.218e-8 10.376 9.999e-6 24.900
(2000, 200) 2.782e-8 19.507 7.717e-6 64.872
($ n, k $) Bcheb-dav Alg. 1
NRN time NRN time
(500, 100) 1.713e-8 1.557 9.989e-6 7.355
(750, 150) 1.606e-8 2.310 9.996e-6 20.053
(1000, 200) 2.837e-8 6.128 9.993e-6 46.477
(1500, 300) 2.647e-8 15.524 9.815e-6 85.150
(2000, 400) 1.692e-8 28.886 4.970e-6 415.430
Table 5.  Numerical results on random problems ($ tol = 10^{-9} $)
($ n, k $) LOBP4dCG Bcheb-dav Alg. 2
NRN time NRN time NRN time
(1000, 5) 1.741e-6 4.556 5.682e-10 1.641 1.969e-8 29.810
(2000, 5) 5.263e-8 13.573 6.082e-9 6.988 9.740e-10 80.980
(4000, 5) 3.956e-8 77.154 6.694e-9 44.313 9.257e-10 315.360
($ n, k $) LOBP4dCG Bcheb-dav Alg. 2
NRN time NRN time NRN time
(1000, 5) 1.741e-6 4.556 5.682e-10 1.641 1.969e-8 29.810
(2000, 5) 5.263e-8 13.573 6.082e-9 6.988 9.740e-10 80.980
(4000, 5) 3.956e-8 77.154 6.694e-9 44.313 9.257e-10 315.360
[1]

Huan Gao, Yu-Hong Dai, Xiao-Jiao Tong. Barzilai-Borwein-like methods for the extreme eigenvalue problem. Journal of Industrial and Management Optimization, 2015, 11 (3) : 999-1019. doi: 10.3934/jimo.2015.11.999

[2]

Xing Li, Chungen Shen, Lei-Hong Zhang. A projected preconditioned conjugate gradient method for the linear response eigenvalue problem. Numerical Algebra, Control and Optimization, 2018, 8 (4) : 389-412. doi: 10.3934/naco.2018025

[3]

Yacine Chitour, Zhenyu Liao, Romain Couillet. A geometric approach of gradient descent algorithms in linear neural networks. Mathematical Control and Related Fields, 2022  doi: 10.3934/mcrf.2022021

[4]

Nora Merabet. Global convergence of a memory gradient method with closed-form step size formula. Conference Publications, 2007, 2007 (Special) : 721-730. doi: 10.3934/proc.2007.2007.721

[5]

Yu-Ning Yang, Su Zhang. On linear convergence of projected gradient method for a class of affine rank minimization problems. Journal of Industrial and Management Optimization, 2016, 12 (4) : 1507-1519. doi: 10.3934/jimo.2016.12.1507

[6]

Naoufel Ben Abdallah, Irene M. Gamba, Giuseppe Toscani. On the minimization problem of sub-linear convex functionals. Kinetic and Related Models, 2011, 4 (4) : 857-871. doi: 10.3934/krm.2011.4.857

[7]

Quanyi Liang, Kairong Liu, Gang Meng, Zhikun She. Minimization of the lowest eigenvalue for a vibrating beam. Discrete and Continuous Dynamical Systems, 2018, 38 (4) : 2079-2092. doi: 10.3934/dcds.2018085

[8]

Xiaming Chen. Kernel-based online gradient descent using distributed approach. Mathematical Foundations of Computing, 2019, 2 (1) : 1-9. doi: 10.3934/mfc.2019001

[9]

Ting Hu. Kernel-based maximum correntropy criterion with gradient descent method. Communications on Pure and Applied Analysis, 2020, 19 (8) : 4159-4177. doi: 10.3934/cpaa.2020186

[10]

Feng Bao, Thomas Maier. Stochastic gradient descent algorithm for stochastic optimization in solving analytic continuation problems. Foundations of Data Science, 2020, 2 (1) : 1-17. doi: 10.3934/fods.2020001

[11]

Shishun Li, Zhengda Huang. Guaranteed descent conjugate gradient methods with modified secant condition. Journal of Industrial and Management Optimization, 2008, 4 (4) : 739-755. doi: 10.3934/jimo.2008.4.739

[12]

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

[13]

David L. Russell. Trace properties of certain damped linear elastic systems. Evolution Equations and Control Theory, 2013, 2 (4) : 711-721. doi: 10.3934/eect.2013.2.711

[14]

Yoonsang Lee, Bjorn Engquist. Variable step size multiscale methods for stiff and highly oscillatory dynamical systems. Discrete and Continuous Dynamical Systems, 2014, 34 (3) : 1079-1097. doi: 10.3934/dcds.2014.34.1079

[15]

Yingying Li, Stanley Osher. Coordinate descent optimization for l1 minimization with application to compressed sensing; a greedy algorithm. Inverse Problems and Imaging, 2009, 3 (3) : 487-503. doi: 10.3934/ipi.2009.3.487

[16]

Wei-Zhe Gu, Li-Yong Lu. The linear convergence of a derivative-free descent method for nonlinear complementarity problems. Journal of Industrial and Management Optimization, 2017, 13 (2) : 531-548. doi: 10.3934/jimo.2016030

[17]

Miriam Kiessling, Sascha Kurz, Jörg Rambau. The integrated size and price optimization problem. Numerical Algebra, Control and Optimization, 2012, 2 (4) : 669-693. doi: 10.3934/naco.2012.2.669

[18]

Saman Babaie–Kafaki, Reza Ghanbari. A class of descent four–term extension of the Dai–Liao conjugate gradient method based on the scaled memoryless BFGS update. Journal of Industrial and Management Optimization, 2017, 13 (2) : 649-658. doi: 10.3934/jimo.2016038

[19]

Gaohang Yu, Lutai Guan, Guoyin Li. Global convergence of modified Polak-Ribière-Polyak conjugate gradient methods with sufficient descent property. Journal of Industrial and Management Optimization, 2008, 4 (3) : 565-579. doi: 10.3934/jimo.2008.4.565

[20]

Kazeem Olalekan Aremu, Chinedu Izuchukwu, Grace Nnenanya Ogwo, Oluwatosin Temitope Mewomo. Multi-step iterative algorithm for minimization and fixed point problems in p-uniformly convex metric spaces. Journal of Industrial and Management Optimization, 2021, 17 (4) : 2161-2180. doi: 10.3934/jimo.2020063

2020 Impact Factor: 1.801

Article outline

Figures and Tables

[Back to Top]