×

zbMATH — the first resource for mathematics

An accelerated active-set algorithm for a quadratic semidefinite program with general constraints. (English) Zbl 1462.65071
Summary: In this paper, we are concerned with efficient algorithms for solving the least squares semidefinite programming which contains many equalities and inequalities constraints. Our proposed method is built upon its dual formulation and is a type of active-set approach. In particular, by exploiting the nonnegative constraints in the dual form, our method first uses the information from the Barzlai-Borwein step to estimate the active/inactive sets, and within an adaptive framework, it then accelerates the convergence by switching the L-BFGS iteration and the semi-smooth Newton iteration dynamically. We show the global convergence under mild conditions, and furthermore, the local quadratic convergence under the additional nondegeneracy condition. Various types of synthetic as well as real-world examples are tested, and preliminary but promising numerical experiments are reported.
MSC:
65K05 Numerical mathematical programming methods
90C22 Semidefinite programming
90C30 Nonlinear programming
Software:
L-BFGS; KELLEY; SDPT3; SeDuMi
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Barzilai, J.; Borwein, JM, Two point step size gradient methods, IMA J. Numer. Anal., 8, 141-148 (1988) · Zbl 0638.65055
[2] Boyd, S.; Xiao, L., Least squares covariance matrix adjustment, SIAM J. Matrix Anal. Appl., 27, 532-546 (2005) · Zbl 1099.65039
[3] Chen, X.; Qi, H.; Tseng, P., Analysis of nonsmooth symmetric-matrix-valued functions with applications to semidefinite complementarity problems, SIAM J. Optim., 13, 960-985 (2003) · Zbl 1076.90042
[4] Clarke, FH, Optimization and Nonsmooth Analysis (1983), New York: Wiley, New York · Zbl 0582.49001
[5] Dai, YH, Alternate step gradient method, Optimization, 52, 395-415 (2003) · Zbl 1056.65055
[6] Facchinei, F., Minimization of \(SC^1\) functions and the Maratos effect, Oper. Res. Lett., 17, 3, 131-137 (1995) · Zbl 0843.90108
[7] Facchinei, F.; Fischer, A.; Kanzow, C., On the accurate identification of active constraints, SIAM J. Optim., 9, 1, 14-32 (1998) · Zbl 0960.90080
[8] 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
[9] 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
[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] Han, RQ; Xie, WJ; Xiong, X., 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)
[12] He, BS; Xu, MH; Yuan, XM, Solving large-scale least squares covariance matrix problems by alternating direction methods, SIAM J. Matrix Anal. Appl., 32, 136-152 (2011) · Zbl 1243.49039
[13] Kupiec, PH, Stress testing in a value-at-risk framework, J. Deriv., 6, 7-24 (1998)
[14] Kelley, CT, Iterative Methods for Optimization, 102-104 (1999), Philadelphia: SIAM, Philadelphia · Zbl 0934.90082
[15] Li, QN; Li, DH, A projected semi-smooth Newton method for problems of calibrating least squares covariance matrix, Oper. Res. Lett., 39, 103-108 (2011) · Zbl 1218.90220
[16] Liu, DC; Nocedal, J., On the limited memory BFGS method for large-scale optimization, Math. Program., 45, 503-528 (1989) · Zbl 0696.90048
[17] Malick, J., A dual approach to semidefinite least squares problems, SIAM J. Matrix Anal. Appl., 26, 272-284 (2004) · Zbl 1080.65027
[18] Nobi, A.; Maeng, SE; Ha, GG; Lee, JW, Random matrix theory and cross-correlations in global financial indices and local stock market indices, J. Korean Phys. Soc., 62, 4, 569-574 (2013)
[19] Nobi, A.; Maeng, SE; Ha, GG; Lee, JW, Effects of global financial crisis on network structure in a local stock market, Phys. A, 407, 135-143 (2014)
[20] Nocedal, J.; Wright, SJ, Numerical Optimization (2006), Berlin: Springer, Berlin · Zbl 1104.65059
[21] Qi, LQ, Convergence analysis of some algorithms for solving nonsmooth equations, Math. Oper. Res., 18, 227-244 (1993) · Zbl 0776.65037
[22] Qi, LQ, Superlinearly convergent approximate Newton methods for \(LC^1\) optimization problems, Math. Program., 64, 1-3, 277-294 (1994) · Zbl 0820.90102
[23] Qi, LQ; Sun, J., A nonsmooth version of Newton’s method, Math. Program., 58, 353-367 (1993) · Zbl 0780.90090
[24] Qi, HD; Sun, DF, A quadratically convergent Newton method for computing the nearest correlation matrix, SIAM J. Matrix Anal. Appl., 28, 360-385 (2006) · Zbl 1120.65049
[25] Rockafellar, RT, Conjugate Duality and Optimization (1974), Philadelphia: SIAM, Philadelphia · Zbl 0296.90036
[26] Schwertman, NC; Allen, DM, Smoothing an indefinite variance-covariance matrix, J. Stat. Comput. Simul., 9, 183-194 (1979)
[27] Shen, CG; Fan, CX; Wang, YL; Xue, WJ, Limited memory BFGS algorithm for the matrix approximation problem in Frobenius norm, Comput. Appl. Math., 39, 43 (2020) · Zbl 1449.65123
[28] So, MKP; Wang, J.; Asai, M., Stress testing correlation matrices for risk management, North Am. J. Econ. Finance, 26, 310-322 (2013)
[29] Sornette, D., Critical market crashes, Phys. Rep., 378, 1, 1-98 (2003) · Zbl 1011.91036
[30] Sornette, D., Why Stock Markets Crash: Critical Events in Complex Financial Systems (2017), Princeton: Princeton University Press, Princeton · Zbl 1126.91001
[31] Sturm, JF, Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones, Optim. Methods Softw., 11, 625-653 (1999) · Zbl 0973.90526
[32] Sun, DF; Sun, J., Semi-smooth matrix valued functions, Math. Oper. Res., 27, 150-169 (2002) · Zbl 1082.49501
[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] Tütüncü, RH; Toh, KC; Todd, MJ, Solving semidefinite-quadratic-linear programs using SDPT3, Math. Program., 95, 189-217 (2003) · Zbl 1030.90082
[35] Ye, CH; Yuan, XM, A descent method for structured monotone variational inequalities, Optim. Methods Softw., 22, 329-338 (2007) · Zbl 1196.90118
[36] Zhang, H.; Hager, WW, A nonmonotone line search technique and its application to unconstrained optimization, SIAM J. Optim., 14, 1043-1056 (2004) · Zbl 1073.90024
[37] Zhou, B.; Gao, L.; Dai, YH, Gradient methods with adaptive step-sizes, Comput. Optim. Appl., 35, 69-86 (2006) · Zbl 1121.90099
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.