Source-linked AI summary
SDPNAL$+$: A Majorized Semismooth Newton-CG Augmented Lagrangian Method for Semidefinite Programming with Nonnegative Constraints
Liuqin Yang, Defeng Sun, Kim-Chuan Toh
TL;DR
The paper addresses numerical difficulty of SDPNAL on degenerate semidefinite programs with nonnegative constraints. It introduces SDPNAL+, combining majorized semismooth Newton-CG augmented-Lagrangian iterations with ADMM+ warm starts, and reports robust large-scale performance. SDPNAL+ solved all 95 tested QAP-relaxation SDP problems to 10^-6, versus 30 for SDPAD and 16 for 2EBD-HPE.
Problem
SDPNAL can encounter numerical difficulty on degenerate SDPs, particularly problems with additional matrix nonnegativity constraints.
Method
SDPNAL+ directly solves SDP+ problems with a majorized semismooth Newton-CG augmented Lagrangian method coupled with ADMM+ warm starts.
Results
95 QAP-relaxation SDP problems were solved to accuracy 10^-6 by SDPNAL+, compared with 30 by SDPAD and 16 by 2EBD-HPE.
Takeaways & Limitations
SDPNAL+ is reported as fast and robust for obtaining accurate solutions on large-scale SDP and SDP+ problems.
Takeaways & Limitations
SDPAD, one comparison method, has no theoretical convergence guarantee because it directly extends ADMM to the multi-block case.
Abstract
from arXiv · showhide
In this paper, we present a majorized semismooth Newton-CG augmented Lagrangian method, called SDPNAL$+$, for semidefinite programming (SDP) with partial or full nonnegative constraints on the matrix variable. SDPNAL$+$ is a much enhanced version of SDPNAL introduced by Zhao, Sun and Toh [SIAM Journal on Optimization, 20 (2010), pp.~1737--1765] for solving generic SDPs. SDPNAL works very efficiently for nondegenerate SDPs but may encounter numerical difficulty for degenerate ones. Here we tackle this numerical difficulty by employing a majorized semismooth Newton-CG augmented Lagrangian method coupled with a convergent 3-block alternating direction method of multipliers introduced recently by Sun, Toh and Yang [arXiv preprint arXiv:1404.5378, (2014)]. Numerical results for various large scale SDPs with or without nonnegative constraints show that the proposed method is not only fast but also robust in obtaining accurate solutions. It outperforms, by a significant margin, two other competitive publicly available first order methods based codes: (1) an alternating direction method of multipliers based solver called SDPAD by Wen, Goldfarb and Yin [Mathematical Programming Computation, 2 (2010), pp.~203--230] and (2) a two-easy-block-decomposition hybrid proximal extragradient method called 2EBD-HPE by Monteiro, Ortiz and Svaiter [Mathematical Programming Computation, (2013), pp.~1--48]. In contrast to these two codes, we are able to solve all the 95 difficult SDP problems arising from the relaxations of quadratic assignment problems tested in SDPNAL to an accuracy of $10^{-6}$ efficiently, while SDPAD and 2EBD-HPE successfully solve 30 and 16 problems, respectively.
1 Introduction
The paper studies SDP with additional polyhedral, including nonnegative, matrix constraints and introduces SDPNAL+ to address SDPNAL's difficulty on degenerate instances. The method directly works on the constrained formulation and is evaluated against first-order alternatives.
- Problem setting: SDP+ adds a polyhedral cone constraint to the semidefinite constraint, including full elementwise nonnegativity as a special case.The framework also permits no additional polyhedral constraint.
- Motivation: SDPNAL performs well on nondegenerate SDPs but can be inefficient on degenerate problems with matrix nonnegativity constraints.The paper motivates SDPNAL+ by this numerical difficulty.
- Contribution: SDPNAL+ directly solves the SDP+ formulation using a majorized semismooth Newton-CG augmented Lagrangian method.This avoids the standard-SDP reformulation used by SDPNAL.
- Evaluation: The method is compared with SDPAD, 2EBD-HPE, and convergent three-block ADMM in numerical experiments.The comparison targets large-scale SDP+ and SDP problems.
- Evaluation: 95 difficult QAP-relaxation SDP problems were solved to accuracy 10^-6 by SDPNAL+, compared with 30 by SDPAD and 16 by 2EBD-HPE.The result is reported for the QAP problems tested in SDPNAL.
2 A Majorized Semismooth Newton-CG Method for Inner Problems
The inner augmented-Lagrangian problems are handled by majorization and semismooth Newton-CG steps involving cone projections. Under a generalized Slater condition, the method has boundedness and convergence guarantees, with stronger convergence under nondegeneracy.
- Inner problem: The inner problem is an augmented-Lagrangian minimization over y, S ∈ K∗, and Z ∈ P∗.The formulation is equivalent to a reduced optimization problem after projecting Z onto P∗.
- Regularity: A generalized Slater condition assumes a positive definite matrix in the relative interior of the polyhedral cone.This condition ensures bounded convex level sets for the inner objective.
- Majorization: The majorized method replaces part of the objective with a convex quadratic majorization and updates S and Z through cone projections.The majorization agrees with the original objective at the current iterate and upper-bounds it globally.
- Newton-CG step: SNCG solves a nonsmooth equation involving the projection ΠK, using generalized Hessian information and conjugate-gradient directions.Strong semismoothness of ΠK supports expected superlinear or quadratic local behavior.
- Convergence: Under Assumption 2, SNCG generates a bounded sequence whose accumulation points solve the inner problem.With an additional constraint-nondegeneracy condition and achieved CG tolerances, the whole sequence converges.
- Convergence: Under Assumption 2, MSNCG generates bounded iterates and every accumulation point solves the inner problem, while successive Z updates vanish.The stated result includes ∥Zl+1 − Zl∥ → 0.
3 A Majorized Semismooth Newton-CG Augmented Lagrangian Method
SDPNAL+ combines ADMM+ warm starts with majorized semismooth Newton-CG inner solves inside an augmented Lagrangian framework. Its convergence is established globally under stated assumptions and locally more strongly under second-order conditions.
- Algorithm: SDPNAL+ uses ADMM+ to generate an initial point before applying MSNCG within each augmented-Lagrangian iteration.The method then updates the primal multiplier X using the constraint residual.
- Relation to SDPNAL: When the SDP is reformulated as a standard SDP, SDPNAL+ reduces to the earlier SDPNAL method.The enhanced method is therefore consistent with the predecessor on the reformulated problem.
- Global convergence: The global convergence result gives bounded primal iterates converging to an optimal solution, with dual iterates asymptotically minimizing the dual problem.It also establishes strong duality in the stated setting.
- Global convergence: If the primal sequence is bounded, the dual sequence is bounded and all its accumulation points are dual optimal solutions.This supplements the primal convergence statement.
- Local convergence: Under condition (43) and second-order sufficient conditions, SDPNAL+ converges to the unique primal optimum with a local linear rate.The rate factor θ∞ lies in [0, 1) and may become small for sufficiently large limiting penalties.
4 Numerical Experiments
The experiments cover diverse SDP+ and SDP problem classes and compare SDPNAL+ with ADMM+, SDPAD, and 2EBD under an accuracy target of 10^-6. SDPNAL+ solves the tested problems efficiently and outperforms the other methods, including on difficult QAP and large-scale R1TA instances.
- 4.1 SDP+ and SDP Problem Sets: The test suite includes BIQ, maximum stable set, QAP, clustering, FAP, and rank-1 tensor approximation SDP or SDP+ problems.The experiments draw instances from sources including the UCI Machine Learning Repository, QAP Library, Biq Mac Library, and graph-instance collections.
- 4.2 Numerical Results: SDPNAL+ is compared with ADMM+, SDPAD, and 2EBD on large-scale SDP+ and SDP problems.ADMM+ is also run alone to demonstrate the contribution of the majorized semismooth Newton-CG algorithm.
- 4.2 Numerical Results: All 95 difficult QAP SDP+ problems are solved by SDPNAL+ to accuracy 10^-6, compared with 39 by ADMM+, 30 by SDPAD, and 16 by 2EBD.The comparison uses a maximum of 25,000 iterations or 99 hours.
- 4.2 Numerical Results: SDPNAL+ solves the tested problems to tolerance ε = 10^-6 efficiently, including the tested QAPs.Tables report iterations, objective values, infeasibilities, gap, and computation times.
- 4.2 Numerical Results: For R1TA problems, SDPNAL+ is significantly faster than the other three methods and appears to be the only efficient solver for instances with n ≥2000.This result concerns the large-scale rank-1 tensor approximation problems tested.
- 4.2 Numerical Results: SDPNAL+ outperforms ADMM+, SDPAD, and 2EBD by a significant margin in the performance profiles.The profiles measure the fraction of tested problems solved within a factor x of the best method.