×

zbMATH — the first resource for mathematics

QSDPNAL: a two-phase augmented Lagrangian method for convex quadratic semidefinite programming. (English) Zbl 1411.90213
Summary: In this paper, we present a two-phase augmented Lagrangian method, called QSDPNAL, for solving convex quadratic semidefinite programming (QSDP) problems with constraints consisting of a large number of linear equality and inequality constraints, a simple convex polyhedral set constraint, and a positive semidefinite cone constraint. A first order algorithm which relies on the inexact Schur complement based decomposition technique is developed in QSDPNAL-Phase I with the aim of solving a QSDP problem to moderate accuracy or using it to generate a reasonably good initial point for the second phase. In QSDPNAL-Phase II, we design an augmented Lagrangian method (ALM) wherein the inner subproblem in each iteration is solved via inexact semismooth Newton based algorithms. Simple and implementable stopping criteria are designed for the ALM. Moreover, under mild conditions, we are able to establish the rate of convergence of the proposed algorithm and prove the R-(super)linear convergence of the KKT residual. In the implementation of QSDPNAL, we also develop efficient techniques for solving large scale linear systems of equations under certain subspace constraints. More specifically, simpler and yet better conditioned linear systems are carefully designed to replace the original linear systems and novel shadow sequences are constructed to alleviate the numerical difficulties brought about by the crucial subspace constraints. Extensive numerical results for various large scale QSDPs show that our two-phase algorithm is highly efficient and robust in obtaining accurate solutions. The software reviewed as part of this submission was given the DOI (Digital Object Identifier) doi:10.5281/zenodo.1206980.

MSC:
90C06 Large-scale problems in mathematical programming
90C20 Quadratic programming
90C22 Semidefinite programming
90C25 Convex programming
65F10 Iterative numerical methods for linear systems
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Alfakih, AY; Khandani, A.; Wolkowicz, H., Solving Euclidean distance matrix completion problems via semidefinite programming, Comput. Optim. Appl., 12, 13-30, (1999) · Zbl 1040.90537
[2] Bauschke, HH; Borwein, JM; Li, W., Strong conical hull intersection property, bounded linear regularity, Jameson’s property (G), and error bounds in convex optimization, Math. Program., 86, 135-160, (1999) · Zbl 0998.90088
[3] Biswas, P.; Liang, TC; Toh, K-C; Wang, TC; Ye, Y., Semidefinite programming approaches for sensor network localization with noisy distance measurements, IEEE Trans. Autom. Sci. Eng., 3, 360-371, (2006)
[4] Bonnans, J.F., Shapiro, A.: Perturbation Analysis of Optimization Problems. Springer, New York (2000)
[5] Burkard, RE; Karisch, SE; Rendl, F., QAPLIB—a quadratic assignment problem library, J. Global Optim., 10, 391-403, (1997) · Zbl 0884.90116
[6] Chen, L.; Sun, DF; Toh, K-C, An efficient inexact symmetric Gauss-Seidel based majorized ADMM for high-dimensional convex composite conic programming, Math. Program., 161, 237-270, (2017) · Zbl 1356.90105
[7] Cui, Y., Sun, D.F., Toh, K.-C.: On the asymptotic superlinear convergence of the augmented Lagrangian method for semidefinite programming with multiple solutions, arXiv:1610.00875 (2016)
[8] Clarke, F.: Optimization and Nonsmooth Analysis. Wiley, New York (1983) · Zbl 0582.49001
[9] Facchinei, F., Pang, J.-S.: Finite-Dimensional Variational Inequalities and Complementarity Problems. Springer, New York (2003) · Zbl 1062.90001
[10] Han, Deren; Sun, Defeng; Zhang, Liwei, Linear Rate Convergence of the Alternating Direction Method of Multipliers for Convex Composite Programming, Mathematics of Operations Research, 43, 622-637, (2018)
[11] Higham, NJ, Computing the nearest correlation matrix—a problem from finance, IMA J. Numer. Anal., 22, 329-343, (2002) · Zbl 1006.65036
[12] Hiriart-Urruty, J-B; Strodiot, J-J; Nguyen, VH, Generalized Hessian matrix and second-order optimality conditions for problems with \({C}^{1,1}\) data, Appl. Math. Optim., 11, 43-56, (1984) · Zbl 0542.49011
[13] Jiang, K.; Sun, DF; Toh, K-C, An inexact accelerated proximal gradient method for large scale linearly constrained convex SDP, SIAM J. Optim., 22, 1042-1064, (2012) · Zbl 1401.90120
[14] Jiang, K.; Sun, DF; Toh, K-C, A partial proximal point algorithm for nuclear norm regularized matrix least squares problems, Math. Program. Comput., 6, 281-325, (2014) · Zbl 1327.90109
[15] Krislock, N.; Lang, J.; Varah, J.; Pai, DK; Seidel, H-P, Local compliance estimation via positive semidefinite constrained least squares, IEEE Trans. Robot., 20, 1007-1011, (2004)
[16] Li, L.; Toh, K-C, An inexact interior point method for l1-regularized sparse covariance selection, Math. Program. Comput., 2, 291-315, (2010) · Zbl 1208.90131
[17] Li, X.D.: A Two-Phase Augmented Lagrangian Method for Convex Composite Quadratic Programming, PhD thesis, Department of Mathematics, National University of Singapore (2015)
[18] Li, XD; Sun, DF; Toh, K-C, A Schur complement based semi-proximal ADMM for convex quadratic conic programming and extensions, Math. Program., 155, 333-373, (2016) · Zbl 1342.90134
[19] Nie, JW; Yuan, YX, A predictor-corrector algorithm for QSDP combining Dikin-type and Newton centering steps, Ann. Oper. Res., 103, 115-133, (2001) · Zbl 1169.90457
[20] Pang, J-S; Sun, DF; Sun, J., Semismooth homeomorphisms and strong stability of semidefinite and Lorentz complementarity problems, Math. Oper. Res., 28, 39-63, (2003) · Zbl 1082.90115
[21] Povh, J.; Rendl, F., Copositive and semidefinite relaxations of the quadratic assignment problem, Discrete Optim., 6, 231-241, (2009) · Zbl 1167.90597
[22] Qi, HD, Local duality of nonlinear semidefinite programming, Math. Oper. Res., 34, 124-141, (2009) · Zbl 1218.90193
[23] 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
[24] Rockafellar, R.T.: Conjugate Duality and Optimization, CBMS-NSF Regional Conf. Ser. Appl. Math. vol. 16. SIAM, Philadelphia (1974)
[25] Rockafellar, RT, Monotone operators and the proximal point algorithm, SIAM J. Control Optim., 14, 877-898, (1976) · Zbl 0358.90053
[26] Rockafellar, RT, Augmented Lagrangians and applications of the proximal point algorithm in convex programming, Math. Oper. Res., 1, 97-116, (1976) · Zbl 0402.90076
[27] Sun, DF; Sun, J., Semismooth matrix-valued functions, Math. Oper. Res., 27, 150-169, (2002) · Zbl 1082.49501
[28] Sun, DF; Toh, K-C; Yang, L., A convergent 3-block semiproximal alternating direction method of multipliers for conic programming with 4-type constraints, SIAM J. Optim., 25, 882-915, (2015) · Zbl 1328.90083
[29] Sun, DF; Toh, K-C; Yang, L., An efficient inexact ABCD method for least squares semidefinite programming, SIAM J. Optim., 26, 1072-1100, (2016) · Zbl 1346.90658
[30] Sun, J.; Zhang, S., A modified alternating direction method for convex quadratically constrained quadratic semidefinite programs, Eur. J. Oper. Res., 207, 1210-1220, (2010) · Zbl 1229.90119
[31] Toh, K-C, An inexact primal-dual path following algorithm for convex quadratic SDP, Math. Program., 112, 221-254, (2008) · Zbl 1136.90027
[32] Toh, K-C; Tütüncü, R.; Todd, M., Inexact primal-dual path-following algorithms for a special class of convex quadratic SDP and related problems, Pac. J. Optim., 3, 135-164, (2007) · Zbl 1136.90026
[33] Yang, L.; Sun, DF; Toh, K-C, SDPNAL+: a majorized semismooth Newton-CG augmented Lagrangian method for semidefinite programming with nonnegative constraints, Math. Program. Comput., 7, 331-366, (2015) · Zbl 1321.90085
[34] Zhao, X.Y.: A Semismooth Newton-CG Augmented Lagrangian Method for Large Scale Linear and Convex Quadratic SDPs, PhD thesis, Department of Mathematics, National University of Singapore (2009)
[35] Zhao, XY; Sun, DF; Toh, K-C, A Newton-CG augmented Lagrangian method for semidefinite programming, SIAM J. Optim., 20, 1737-1765, (2010) · Zbl 1213.90175
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.