A preconditioned augmented Lagrangian method for solving semidefinite programming problems
Tianyun Tang, Kim-Chuan Toh · 2026
Read A preconditioned augmented Lagrangian method for solving semidefinite programming problems by Tianyun Tang, Kim-Chuan Toh (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-17089.txt.
Introduction
Tang and Toh speed up a classic solver for semidefinite programming, a class of optimization with matrix constraints. They add a preconditioner built from a projection onto the feasible region's tangent space, which helps most when problems are badly conditioned. Paired with their earlier feasible solver, the result is SDPF+, a tool that also handles curved objectives. Tests show it usually beats rivals on large low-rank problems.
Catalog record
| CREATOR | Tianyun Tang, Kim-Chuan Toh |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 107301 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.17089
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A preconditioned augmented Lagrangian method for solving semidefinite programming problems Tianyun Tang, Kim-Chuan Toh Abstract In this work, we propose a preconditioned augmented Lagrangian method (ALM) for solving semidefinite programming (SDP) problems. The preconditioner is implemented via a weighted penalty function in the ALM subproblem, with the weight matrix derived from the projection operator onto the tangent space of the feasible region. This simple yet effective modification significantly accelerates ALM, particularly for ill-conditioned SDPs. By combining the preconditioned ALM with our previously developed feasible method, SDPF [T. Tang and K.-C. Toh, SIAM J. Optim., 34 (2024), pp. 2169–2200], we develop SDPF+, an SDP solver capable of handling convex problems with possibly nonlinear objective functions. Extensive numerical experiments demonstrate the efficiency and robustness of SDPF+, showing that it can generally outperform other solvers on large-scale SDPs whose optimal solutions exhibit low-rank structure. keywords: Semidefinte programming, Augmented Lagrangian method, Preconditioner Mathematics subject classification: 90C06, 90C22, 90C30 1 Introduction Let \mathbb{S}^{n} be the set of n\times n real symmetric matrices, \mathbb{S}^{n}_{+} the set of n\times n symmetric positive semidefinite matrices, and [m]:=\{1,2,\ldots,m\}. Consider the following standard form linearly constrained SDP problem: \min\left\{f(X):\ \mathcal{A}(X)=b,\ X\in\mathbb{S}^{n}_{+}\right\} (SDP) where f:\mathbb{S}^{n}\rightarrow\mathbb{R} is a convex continuously differentiable function, \mathcal{A}:\mathbb{S}^{n}\rightarrow\mathbb{R}^{m} is a linear map: \mathcal{A}(X):=[\big\langle A_{1},X\big\rangle;\ldots;\big\langle A_{m},X\big\rangle] such that A_{i}\in\mathbb{S}^{n} for any i\in[m] and b\in\mathbb{R}^{m}. For simplicity of presentation, we consider the standard form SDP expressed in the form ( SDP ) first. In Section 2.3 , we will consider more general forms of SDP. For large-scale SDP problems with low-rank optimal solutions, the Burer–Monteiro method [ 9 ] reduces the dimensionality by solving ( SDP ) in the following factorized form: \min\left\{f(RR^{\top})\;:\;\mathcal{A}(RR^{\top})=b,\;R\in\mathbb{R}^{n\times r}\right\}, (SDPR) with r\leq n. Numerous algorithms have been proposed for solving low-rank SDPs, including the augmented Lagrangian method (ALM) [ 9 ] , the alternating direction method of multipliers (ADMM) [ 15 ] , and feasible methods [ 39 ] . Among these, ALM is the most widely used due to its simplicity and strong empirical performance. Several SDP solvers based on ALM have been developed in the literature, such as SDPLR [ 8 ] , ManiSDP [ 43 ] , HALLaR [ 24 ] , and RiNNAL [ 16 ] . ALM is a primal–dual method in which the primal variable is updated by solving the following subproblem: \min\left\{f(RR^{\top})-\langle\lambda,\,\mathcal{A}(RR^{\top})-b\rangle+\frac{\beta}{2}\|\mathcal{A}(RR^{\top})-b\|^{2}:\ R\in\mathbb{R}^{n\times r}\right\}, (1) for some given penalty parameter \beta>0 and Lagrange multiplier \lambda\in\mathbb{R}^{m} . After obtaining R^{+} from ( 1 ), the multiplier is updated via \lambda^{+}\leftarrow\lambda-\beta\big(\mathcal{A}(R^{+}(R^{+})^{\top})-b\big) . Since ( 1 ) is an unconstrained problem, it can be solved by simple first-order methods, potentially with a rank-adaptive strategy [ 39 ] , to obtain a global minimizer. However, when ( SDPR ) is nearly primal degenerate, that is, when the Jacobian of the constraint map is ill-conditioned, solving ( 1 ) becomes difficult. In this case, the penalty term in ( 1 ) inherits the ill-conditioning difficulty, causing first order methods such as gradient descent or limited memory BFGS to converge very slowly. In our implementation, the ALM subproblem often requires tens of thousands of gradient descent iterations before the gradient norm becomes sufficiently small to guarantee convergence of the outer ALM iteration. Some ALM-based solvers, such as ManiSDP, limit the maximum number of iterations for the subproblem and update the multiplier once this limit is reached. Nevertheless, if the subproblem is not solved with sufficient accuracy, ALM may require a large number of outer iterations or even fail to converge. Table 1 reports the performance of several algorithms on the Lovász Theta SDP problem for the graph G51 from the Gset dataset 1 1 1 Dataset available at https://web.stanford.edu/~yyye/yyye/Gset/ . . Although this problem admits a low-rank optimal solution, the interior-point method (IPM) based solver SDPT3 [ 42 ] significantly outperforms both ManiSDP and SDPLR in terms of computational speed. This advantage stems from the primal degeneracy of the SDP, which severely limits the efficiency of low-rank ALM approaches. Note that the ill-conditioning issue affects not only ALM but also all of the aforementioned algorithms. While IPM is generally more robust for solving ill-conditioned SDP problems, its high computational complexity renders it unsuitable for large-scale instances. Table 1: Test results on Lovász Theta SDP problem for graph G51. The condition number of the constraint Jacobian at the optimal solution is around 10^{7} . problem algorithm pfeas dfeas comp fval ttime G51 SDPT3 3.59e-13 0.00e+00 8.05e-08 -3.4899993e+02 3.08e+01 n=1000 ManiSDP 7.51e-06 2.62e-06 2.21e-17 -3.4902483e+02 3.60e+03 m=5910 SDPLR 9.99e-07 4.51e-06 1.82e-08 -3.4900065e+02 2.74e+03 rank=109 SDPF 3.41e-07 8.77e-07 6.43e-08 -3.4900017e+02 5.13e+01 SDPF+ 4.67e-07 9.59e-07 2.36e-09 -3.4899975e+02 2.30e+01 In order to address the impact of ill-conditioning on ALM, we develop a preconditioned ALM (PALM) for solving ( SDP ). In the ALM subproblem, the constraints \mathcal{A}(X)=b are penalized using a weighted term in the penalty function. The weight matrix, derived from the preconditioner for the projection onto the tangent space of the feasible region, effectively mitigates primal ill-conditioning. The resulting algorithm, implemented in the solver SDPF+, substantially accelerates ALM and outperforms SDPT3 on ill-conditioned instances (see Table 1 ). Note that SDPF is a feasible method [ 39 ] and employs preconditioning. Table 1 shows that PALM outperforms the feasible method on this instance. We further discuss extensions of the PALM to more general SDP problems with inequality and other conic constraints. The remainder of the paper is organized as follows. Section 2 introduces the PALM and establishes its convergence analysis. Section 3 presents the algorithmic framework of SDPF+, which employs a two-stage approach that combines the feasible method in [ 39 ] with the PALM; details on its usage and data structure are provided in Appendix B . Section 4 reports numerical results comparing SDPF+ with other state-of-the-art SDP solvers, with additional tables given in Appendix C . Finally, Section 5 concludes the paper with a brief summary. 2 Algorithmic design In this section, we present the PALM. Before introducing the algorithm, we first review the feasible method SDPF, which motivates the design of our preconditioner. 2.1 Feasible method In [ 39 ] , we have designed a rank-adaptive feasible method called SDPF to solve ( SDP ) via a low-rank factorization approach by solving ( SDPR ). To make the presentation self-contained, we briefly restate the algorithm. It is based on Riemannian optimization [ 2 , 6 ] . Under the linear independence constraint qualification (LICQ) [ 28 ] , namely, when the Jacobian of the constraint map has full row rank, the feasible set of ( SDPR ) forms a Riemannian manifold. \mathcal{M}:=\left\{R\in\mathbb{R}^{n\times r}:\mathcal{A}(RR^{\top})=b\right\}, (2) whose tangent space at R is given by {\rm T}_{R}\mathcal{M}:=\left\{H\in\mathbb{R}^{n\times r}:\mathcal{A}(RH^{\top}+HR^{\top})=0_{m\times 1}\right\}. (3) Let {\rm Proj}_{{\rm T}_{R}\mathcal{M}}:\mathbb{R}^{n\times r}\to{\rm T}_{R}\mathcal{M} denote the orthogonal projection onto the tangent space, and let {\rm Rtr}_{R}:{\rm T}_{R}\mathcal{M}\to\mathcal{M} be a retraction satisfying {\rm Rtr}_{R}(tH)=R+tH+o(t), (4) where t\in\mathbb{R} is a parameter that controls the stepsize. In SDPF, the retraction is implemented via a Gauss–Newton procedure initialized at R+tH . At each iteration, SDPF performs a Riemannian gradient descent step: R^{+}\leftarrow{\rm Rtr}_{R}\left(R-t\,{\rm Proj}_{{\rm T}_{R}\mathcal{M}}\big[2\nabla f(RR^{\top})R\big]\right), (5) where t>0 is a stepsize parameter. In each of the update step ( 5 ), the main computational cost lies in evaluating the projection and the retraction, both of which require