×

zbMATH — the first resource for mathematics

Limited memory BFGS algorithm for the matrix approximation problem in Frobenius norm. (English) Zbl 1449.65123
Summary: This paper proposes an L-BFGS algorithm based on the active set technique to solve the matrix approximation problem: given a symmetric matrix, find a nearest approximation matrix in the sense of Frobenius norm to make it satisfy some linear equalities, inequalities and a positive semidefinite constraint. The problem is a convex optimization problem whose dual problem is a nonlinear convex optimization problem with non-negative constraints. Under the Slater constraint qualification, it has zero duality gap with the dual problem. To handle large-scale dual problem, we make use of the active set technique to estimate the active constraints, and then the L-BFGS method is used to accelerate free variables. The global convergence of the proposed algorithm is established under certain conditions. Finally, we conduct some preliminary numerical experiments, and compare the L-BFGS method with the inexact smoothing Newton method, the projected BFGS method, the alternating direction method and the two-metric projection method based on the L-BFGS. The numerical results show that our algorithm has some advantages in terms of CPU time when a large number of linear constraints are involved.

MSC:
65K05 Numerical mathematical programming methods
90C55 Methods of successive quadratic programming type
90C30 Nonlinear programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Borsdorf, R.; Higham, Nj, A preconditioned Newton algorithm for the nearest correlation matrix, IMA J Numer Anal, 30, 94-107 (2010) · Zbl 1188.65055
[2] Boyd, S.; Xiao, L., Least squares covariance matrix adjustment, SIAM J Matrix Anal Appl, 27, 532-546 (2005) · Zbl 1099.65039
[3] Byrd, Rh; Lu, P.; Nocedal, J.; Zhu, C., A limited memory algorithm for bound constrained optimization, SIAM J Sci Comput, 16, 1190-1208 (1995) · Zbl 0836.65080
[4] Cristofari, A.; De Santis, M.; Lucidi, S.; Rinaldi, F., A two-stage active-set algorithm for bound-constrained optimization, J Optim Theory Appl, 172, 2, 369-401 (2017) · Zbl 1398.90170
[5] Dykstra, Rl, An algorithm for restricted least squares regression, J Am Stat Assoc, 78, 837-842 (1983) · Zbl 0535.62063
[6] FEAST solver (2009-2015). http://www.feast-solver.org/. Accessed 17 June 2018
[7] Gabay, D.; Fortin, M.; Glowinski, R., Application of the method of multipliers to variational inequalities, Augmented Lagrangian methods: application to the numerical solution of boundary-value problems, 299-331 (1983), Amsterdam: North-Holland, Amsterdam
[8] Gabay, D.; Mercier, B., A dual algorithm for the solution of nonlinear variational problems via finite element approximations, Comput Math Appl, 2, 17-40 (1976) · Zbl 0352.65034
[9] Gafni, Em; Bertsekas, Dp, Two-metric projection methods for constrained optimization, SIAM J Control Optim, 22, 6, 936-964 (1984) · Zbl 0555.90086
[10] Gao, Y.; Sun, Df, Calibrating least squares semidefinite programming with equality and inequality constraints, SIAM J Matrix Anal Appl, 31, 1432-1457 (2009) · Zbl 1201.49031
[11] Hager, Ww; Zhang, H., A new conjugate gradient method with guaranteed descent and an efficient line search, SIAM J Optim, 16, 170-192 (2005) · Zbl 1093.90085
[12] Hager, Ww; Zhang, H., A new active set algorithm for box constrained optimization, SIAM J Optim, 17, 526-557 (2006) · Zbl 1165.90570
[13] Han, Rq; Xie, Wj; Xiong, X.; Zhang, W.; Zhou, Wx, Market correlation structure changes around the great crash: a random matrix theory analysis of the Chinese stock market, Fluct Noise Lett, 16, 2, 1750018 (2017)
[14] He, Bs; Xu, Mh; Yuan, Xm, Solving large-scale least squares semidefinite programming by alternating direction methods, SIAM J Matrix Anal Appl, 32, 136-152 (2011) · Zbl 1243.49039
[15] Higham, Nj, Computing the nearest correlation matrix-a problem from finance, IMA J Numer Anal, 22, 329-343 (2002) · Zbl 1006.65036
[16] Kelley, Ct, Iterative methods for optimization, 102-104 (1999), Philadelphia: SIAM, Philadelphia
[17] Kupiec, Ph, Stress testing in a value-at-risk framework, J Deriv, 6, 7-24 (1998)
[18] Li, Qn; Li, Dh, A projected semismooth Newton method for problems of calibrating least squares covariance matrix, Oper Res Lett, 39, 103-108 (2011) · Zbl 1218.90220
[19] Lin, C-J; Moré, Jj, Newtons method for large bound-constrained optimization problems, SIAM J Optim, 9, 1100C1127 (1999) · Zbl 0957.65064
[20] Liu, Dc; Nocedal, J., On the limited memory BFGS method for large-scale optimization, Math Program, 45, 503-528 (1989) · Zbl 0696.90048
[21] Malick, J., A dual approach to semidefinite least squares problems, SIAM J Matrix Anal Appl, 26, 272-284 (2004) · Zbl 1080.65027
[22] Ni, Q.; Yuan, Y., A subspace limited memory quasi-Newton algorithm for large-scale nonlinear bound constrained optimization, Math Comp, 66, 1509-1520 (1997) · Zbl 0886.65065
[23] Nocedal, J.; Wright, Sj, Numerical optimization (2006), New York: Springer, New York
[24] Polanco-Martínez, Jm; Fernández-Macho, J.; Neumann, Mb; Faria, Sh, A pre-crisis vs. crisis analysis of peripheral EU stock markets by means of wavelet transform and a nonlinear causality test, Phys A, 490, 1211-1227 (2018)
[25] Polizzi, E., Density-matrix-based algorithms for solving eigenvalue problems, Phys Rev B, 79, 115112 (2009)
[26] Qi, Hd; Sun, D., A quadratically convergent Newton method for computing the nearest correlation matrix, SIAM J Matrix Anal Appl, 28, 360-385 (2006) · Zbl 1120.65049
[27] Qi, Hd; Sun, D., Correlation stress testing for value-at-risk: an unconstrained convex optimization approach, Comput Optim Appl, 45, 427-462 (2010) · Zbl 1198.91091
[28] Rahpeymaii, F.; Kimiaei, M.; Bagheri, A., A limited memory quasi-Newton trust-region method for box constrained optimization, J Comput Appl Math, 303, 105-118 (2016) · Zbl 1381.90097
[29] Rebonato, R.; Jäckel, P., The most general methodology for creating a valid correlation matrix for risk management and option pricing purposes, J Risk, 2, 17-27 (1999)
[30] Rockafellar RT (1974) Conjugate duality and optimization. BMS-NSF Regional Conference Series in Applied Mathematics 16, SIAM, Philadelphia · Zbl 0296.90036
[31] Schwertman, Nc; Allen, Dm, Smoothing an indefinite variance-covariance matrix, J Stat Comput Simul, 9, 183-194 (1979)
[32] So, Mkp; Wong, J.; Asai, M., Stress testing correlation matrices for risk management, N Am J Econ Finan, 26, 310-322 (2013)
[33] Sun, Yf; Vandenberghe, L., Decomposition methods for sparse matrix nearness problems, SIAM J Matrix Anal Appl, 36, 1691-1717 (2015) · Zbl 1342.90128
[34] Werner R, Schöttle K (2007) Calibration of correlation matrices-SDP or not SDP. Technical report, Munich University of Technology, Munich
[35] Xiao, Y.; Wei, Z., A new subspace limited memory BFGS algorithm for large-scale bound constrained optimization, Appl Math Comput, 185, 1, 350-359 (2007) · Zbl 1114.65069
[36] Xiao, Y.; Li, Dh, An active set limited memory BFGS algorithm for large-scale bound constrained optimization, Math Methods Oper Res, 67, 3, 443-454 (2008) · Zbl 1145.90084
[37] Xue WJ, Shen CG (2018) Limited memory BFGS method for least squares semidefinite programming with banded structure. Technical Report, University of Shanghai for Science and Technology, Shanghai
[38] Yuan, G.; Lu, X., An active set limited memory BFGS algorithm for bound constrained optimization, Appl Math Model, 35, 7, 3561-3573 (2011) · Zbl 1221.90082
[39] Yuan, G.; Wei, Z., Convergence analysis of a modified BFGS method on convex minimizations, Comput Optim Appl, 47, 237-255 (2010) · Zbl 1228.90077
[40] Ye, Ch; Yuan, Xm, A descent method for structured monotone variational inequalities, Optim Methods Softw, 22, 329-338 (2007) · Zbl 1196.90118
[41] Zarantonello, Eh; Zarantonello, Eh, Projections on convex sets in Hilbert space and spectral theory I and II, Contributions to nonlinear functional analysis, 237-424 (1971), New York: Academic Press, New York
[42] Zhang, Hc; Hager, Ww, A nonmonotone line search technique and its application to unconstrained optimization, SIAM J Optim, 14, 1043-1056 (2004) · Zbl 1073.90024
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.