• Previous Article
    The optimal pricing and service strategies of a dual-channel retailer under free riding
  • 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 & 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.  Google Scholar

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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.  Google Scholar

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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 & 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 & Optimization, 2018, 8 (4) : 389-412. doi: 10.3934/naco.2018025

[3]

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

[4]

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

[5]

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

[6]

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

[7]

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

[8]

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

[9]

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

[10]

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

[11]

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

[12]

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

[13]

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

[14]

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

[15]

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

[16]

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

[17]

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 & Management Optimization, 2017, 13 (2) : 649-658. doi: 10.3934/jimo.2016038

[18]

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

[19]

Yanfei Wang, Qinghua Ma. A gradient method for regularizing retrieval of aerosol particle size distribution function. Journal of Industrial & Management Optimization, 2009, 5 (1) : 115-126. doi: 10.3934/jimo.2009.5.115

[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 & Management Optimization, 2021, 17 (4) : 2161-2180. doi: 10.3934/jimo.2020063

2020 Impact Factor: 1.801

Metrics

  • PDF downloads (98)
  • HTML views (63)
  • Cited by (0)

Other articles
by authors

[Back to Top]