A preconditioned augmented Lagrangian method for solving semidefinite programming problems

Kim-Chuan Toh; Tianyun Tang

arxiv: 2605.17089 · v1 · pith:BXPLTHTJnew · submitted 2026-05-16 · 🧮 math.OC

A preconditioned augmented Lagrangian method for solving semidefinite programming problems

Tianyun Tang , Kim-Chuan Toh This is my paper

Pith reviewed 2026-05-20 14:43 UTC · model grok-4.3

classification 🧮 math.OC

keywords semidefinite programmingaugmented Lagrangian methodpreconditioningtangent space projectionlow-rank solutionsconvex optimizationSDP solver

0 comments

The pith

A weighted penalty preconditioner from tangent space projection accelerates the augmented Lagrangian method for ill-conditioned semidefinite programs.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper proposes a preconditioned augmented Lagrangian method for semidefinite programming. The preconditioner modifies the penalty term in the subproblems using a weight matrix from the tangent space projection of the feasible region. This modification leads to faster convergence particularly when the problems are ill-conditioned. Integrating the preconditioned method with the SDPF feasible approach creates the SDPF+ solver, which can manage convex SDPs including those with nonlinear objectives. Tests show SDPF+ often beats competing solvers on large problems with low-rank optimal solutions.

Core claim

The central discovery is that incorporating a weight matrix derived from the projection onto the tangent space of the feasible region into a weighted penalty function within the augmented Lagrangian subproblems substantially speeds up the solution process for ill-conditioned semidefinite programming problems. Combining this preconditioned ALM with the previously developed SDPF method results in the SDPF+ solver that efficiently addresses large-scale convex SDPs possibly featuring nonlinear objective functions.

What carries the argument

The weighted penalty function in the ALM subproblem, with its weight matrix coming from the tangent space projection operator onto the feasible region.

Load-bearing premise

The projection onto the tangent space produces a weight matrix that can be applied cheaply and stays numerically stable for the ill-conditioned SDPs that occur in applications.

What would settle it

Running the preconditioned ALM and the standard ALM on the same set of ill-conditioned SDP test problems and finding no consistent reduction in iteration counts or runtime would indicate the preconditioning does not accelerate convergence as claimed.

Figures

Figures reproduced from arXiv: 2605.17089 by Kim-Chuan Toh, Tianyun Tang.

**Figure 1.** Figure 1: Cholesky factor of MR for the Lov´asz Theta problem G51. PALM with exact Cholesky decomposition uses 28.4s, PALM with incomplete Cholesky decomposition uses 7.49s. to construct. In our numerical test for this instance, PALM equipped with incomplete Cholesky preconditioning is approximately three times faster than that with the exact Cholesky decomposition. In our implementation, the weight matrix in PALM i… view at source ↗

**Figure 2.** Figure 2: Rank evolution of SDPF+ for the rank-1 tensor appro [PITH_FULL_IMAGE:figures/full_fig_p018_2.png] view at source ↗

**Figure 3.** Figure 3: Performance profile for the test results of 2RDM. [PITH_FULL_IMAGE:figures/full_fig_p019_3.png] view at source ↗

**Figure 4.** Figure 4: Performance profile for test results on Hans Mittel [PITH_FULL_IMAGE:figures/full_fig_p019_4.png] view at source ↗

read the original 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, 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The tangent-space weighted preconditioner is a practical tweak that speeds up ALM on ill-conditioned SDPs, and SDPF+ extends it usefully to nonlinear objectives with supporting numerics.

read the letter

This paper's key contribution is a preconditioned augmented Lagrangian method for semidefinite programming that derives its weight matrix from the tangent space projection operator. That modification seems to speed up the method on ill-conditioned problems, and combining it with the earlier SDPF gives SDPF+ for handling nonlinear objective functions as well. The new element is the specific preconditioner construction. It is not a standard extension of existing ALM approaches for SDPs. The tangent-space weighting targets the structure of the feasible region in a way that prior work did not emphasize. Integrating this into SDPF+ to cover nonlinear cases is also a distinct step. On the positive side, the numerical experiments indicate that SDPF+ performs well against other solvers for large-scale SDPs with low-rank solutions. This matches the needs in areas like control theory and combinatorial relaxations where such structure often appears. The approach stays within standard ALM theory while adding this practical acceleration. The main soft spot is in the level of detail on the experiments. The abstract talks about extensive testing and robustness but does not provide specifics on how the test problems were selected or what stopping criteria were used. This leaves some room for doubt on how general the outperformance is. The stress-test note suggests the results hold up on the tested cases and the projection overhead is manageable in the low-rank setting, so the concern is not central. This work is for optimization researchers and developers who solve SDPs in practice. Readers looking for algorithmic tweaks that improve convergence without heavy theoretical overhead would find it useful. It shows clear thinking on the problem and engages with the relevant literature on feasible methods. The paper deserves a serious referee. The algorithmic idea is concrete and the supporting numerics are there to justify review time. I recommend sending it for peer review. It is a useful piece of work that could see adoption in the field.

Referee Report

1 major / 2 minor

Summary. This paper proposes a preconditioned augmented Lagrangian method (ALM) for semidefinite programming (SDP) problems. The preconditioner is realized through a weighted penalty function in the ALM subproblem, with the weight matrix obtained from the projection operator onto the tangent space of the feasible region. The method is combined with the SDPF feasible method to create SDPF+, suitable for convex SDPs possibly with nonlinear objectives. The authors present extensive numerical experiments to illustrate the efficiency and robustness of SDPF+, particularly its ability to outperform other solvers on large-scale SDPs with low-rank optimal solutions.

Significance. If the performance claims hold under more detailed scrutiny, the work could meaningfully advance SDP solvers by accelerating ALM on ill-conditioned instances and delivering competitive results on large low-rank problems. The numerical results appear consistent with the claimed acceleration and outperformance on the tested instances, with the per-iteration overhead of the tangent-space projection remaining controlled in the low-rank regime; these constitute concrete strengths of the manuscript.

major comments (1)

Numerical Experiments section: the description of the test-set construction, stopping criteria, and any statistical assessment of performance differences is insufficient. This information is load-bearing for the central claim that SDPF+ generally outperforms other solvers on large-scale low-rank SDPs.

minor comments (2)

Abstract: the claim of 'extensive numerical experiments' would benefit from an explicit cross-reference to the relevant tables or figures.
Preconditioner construction: the discussion of numerical stability of the derived weight matrix across ill-conditioned instances could be expanded with a brief remark on observed condition numbers or failure modes.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful review and the positive assessment of the potential impact of our work on accelerating ALM for ill-conditioned SDPs. We address the single major comment below and will incorporate the suggested improvements in the revised manuscript.

read point-by-point responses

Referee: Numerical Experiments section: the description of the test-set construction, stopping criteria, and any statistical assessment of performance differences is insufficient. This information is load-bearing for the central claim that SDPF+ generally outperforms other solvers on large-scale low-rank SDPs.

Authors: We agree that additional detail in the Numerical Experiments section would strengthen the presentation and better support the central performance claims. In the revision we will expand the description of the test-set construction to clarify how the large-scale low-rank convex SDP instances were generated (including the specific random models and parameter ranges used), provide the precise stopping criteria and tolerances applied to SDPF+ as well as to the competing solvers, and include statistical summaries such as performance profiles or average runtime ratios across the instance collection. These additions will make the experimental evidence more transparent without altering the reported results. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper presents an algorithmic construction for a preconditioned ALM where the weight matrix is explicitly built from the tangent-space projection operator onto the feasible region. This modification is justified by reference to standard ALM convergence theory together with new numerical experiments on ill-conditioned instances. The subsequent combination with the authors' earlier SDPF method to produce SDPF+ is a straightforward composition that does not alter the independent status of the preconditioner derivation or the reported acceleration. No equation is shown to be equivalent by construction to a fitted parameter, no uniqueness theorem is imported from the authors' own prior work to forbid alternatives, and the performance claims rest on external experimental benchmarks rather than internal self-reference. The derivation chain therefore remains self-contained against the stated assumptions and observed results.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper relies on existing convergence theory for augmented Lagrangian methods and on the well-definedness of the tangent-space projection operator; no new free parameters, ad-hoc axioms, or invented entities are introduced in the abstract.

axioms (1)

standard math Standard convergence theory for augmented Lagrangian methods continues to apply after the introduction of the tangent-space-derived weighting.
The preconditioner is presented as a modification that preserves the outer ALM framework.

pith-pipeline@v0.9.0 · 5644 in / 1275 out tokens · 55203 ms · 2026-05-20T14:43:33.298048+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

53 extracted references · 53 canonical work pages

[1]

E. Abbe. Community detection and stochastic block model s: recent developments. Journal of Machine Learning Research , 18(177):1–86, 2018

work page 2018
[2]

Absil, R

P.-A. Absil, R. Mahony, and R. Sepulchre. Optimization a lgorithms on matrix man- ifolds. In Optimization Algorithms on Matrix Manifolds . Princeton University Press, 2009

work page 2009
[3]

A. I. Barvinok. Problems of distance geometry and convex properties of quadratic maps. Discrete & Computational Geometry , 13(2):189–202, 1995

work page 1995
[4]

H. H. Bauschke, P. L. Combettes, H. H. Bauschke, and P. L. C ombettes. Correction to: convex analysis and monotone operator theory in Hilbert spaces. Springer, 2017

work page 2017
[5]

Beck and M

A. Beck and M. Teboulle. A fast iterative shrinkage-thre sholding algorithm for linear inverse problems. SIAM J. on Imaging Sciences , 2(1):183–202, 2009

work page 2009
[6]

N. Boumal. An introduction to optimization on smooth manifolds . Cambridge Univer- sity Press, 2023

work page 2023
[7]

Bredies and H

K. Bredies and H. Sun. A proximal point analysis of the pre conditioned alternating direction method of multipliers. Journal of Optimization Theory and Applications , 173:878–907, 2017

work page 2017
[8]

S. Burer. On the copositive representation of binary and continuous nonconvex quadratic programs. Mathematical Programming, 120(2):479–495, 2009. 23

work page 2009
[9]

Burer and C

S. Burer and C. Choi. Computational enhancements in low- rank semideﬁnite program- ming. Optimisation Methods and Software , 21(3):493–512, 2006

work page 2006
[10]

Burer and R

S. Burer and R. D. Monteiro. A nonlinear programming alg orithm for solving semidef- inite programs via low-rank factorization. Mathematical Programming, 95(2):329–357, 2003

work page 2003
[11]

R. E. Burkard, S. E. Karisch, and F. Rendl. QAPLIB–a quad ratic assignment problem library. Journal of Global optimization , 10:391–403, 1997

work page 1997
[12]

Y. Cui, D. Sun, and K.-C. Toh. On the r-superlinear conve rgence of the KKT residuals generated by the augmented Lagrangian method for convex com posite conic program- ming. Mathematical Programming, 178(1):381–415, 2019

work page 2019
[13]

Giselsson and S

P. Giselsson and S. Boyd. Diagonal scaling in douglas-r achford splitting and admm. In 53rd IEEE Conference on Decision and Control , pages 5033–5039. IEEE, 2014

work page 2014
[14]

Graham, H

N. Graham, H. Hu, J. Im, X. Li, and H. Wolkowicz. A restric ted dual peaceman- rachford splitting method for a strengthened dnn relaxatio n for qap. INFORMS Jour- nal on Computing , 34(4):2125–2143, 2022

work page 2022
[15]

Q. Han, C. Li, Z. Lin, C. Chen, Q. Deng, D. Ge, H. Liu, and Y. Ye. A low-rank ADMM splitting approach for semideﬁnite programming. INFORMS J. on Computing, to appear, 2025

work page 2025
[16]

D. Hou, T. Tang, and K.-C. Toh. A low-rank augmented Lagr angian method for doubly nonnegative relaxations of mixed-binary quadratic progra ms. Operations Resarch, to appear., 2025

work page 2025
[17]

D. Hou, T. Tang, and K.-C. Toh. Rinnal+: a riemannian alm solver for sdp-rlt relax- ations of mixed-binary quadratic programs: Di hou et al. Mathematical Programming Computation, pages 1–57, 2026

work page 2026
[18]

Jiang, D

K. Jiang, D. Sun, and K.-C. Toh. An inexact accelerated p roximal gradient method for large scale linearly constrained convex SDP. SIAM J. on Optimization , 22(3):1042– 1064, 2012

work page 2012
[19]

Kontogiorgis and R

S. Kontogiorgis and R. R. Meyer. A variable-penalty alt ernating directions method for convex optimization. Mathematical Programming, 83(1):29–53, 1998

work page 1998
[20]

J. B. Lasserre. Global optimization with polynomials a nd the problem of moments. SIAM J. on Optimization , 11(3):796–817, 2001

work page 2001
[21]

X. Li, D. Sun, and K.-C. Toh. QSDPNAL: a two-phase augmen ted Lagrangian method for convex quadratic semideﬁnite programming. Mathematical Programming Compu- tation, 10(4):703–743, 2018

work page 2018
[22]

Y. Liu, Y. Xu, and W. Yin. Acceleration of primal–dual me thods by preconditioning and simple subproblem procedures. Journal of Scientiﬁc Computing , 86(2):21, 2021. 24

work page 2021
[23]

Marteau-Ferey, F

U. Marteau-Ferey, F. Bach, and A. Rudi. Non-parametric models for non-negative functions. Advances in Neural Information Processing Systems , 33:12816–12826, 2020

work page 2020
[24]

R. D. Monteiro, A. Sujanani, and D. Cifuentes. A low-ran k augmented Lagrangian method for large-scale semideﬁnite programming based on a h ybrid convex-nonconvex approach. arXiv preprint arXiv:2401.12490 , 2024

work page arXiv 2024
[25]

Nakata, B

M. Nakata, B. J. Braams, K. Fujisawa, M. Fukuda, J. K. Per cus, M. Yamashita, and Z. Zhao. Variational calculation of second-order reduced d ensity matrices by strong n-representability conditions and an accurate semideﬁnit e programming solver. The Journal of Chemical Physics , 128(16), 2008

work page 2008
[26]

Nakata, H

M. Nakata, H. Nakatsuji, M. Ehara, M. Fukuda, K. Nakata, and K. Fujisawa. Vari- ational calculations of fermion second-order reduced dens ity matrices by semideﬁnite programming algorithm. The Journal of Chemical Physics , 114(19):8282–8292, 2001

work page 2001
[27]

Nie and L

J. Nie and L. Wang. Semideﬁnite relaxations for best ran k-1 tensor approximations. SIAM J. on Matrix Analysis and Applications , 35(3):1155–1179, 2014

work page 2014
[28]

Nocedal and S

J. Nocedal and S. J. Wright. Numerical Optimization. Springer, 1999

work page 1999
[29]

G. Pataki. On the rank of extreme matrices in semideﬁnit e programs and the mul- tiplicity of optimal eigenvalues. Mathematics of Operations Research , 23(2):339–358, 1998

work page 1998
[30]

Pock and A

T. Pock and A. Chambolle. Diagonal preconditioning for ﬁrst order primal-dual algo- rithms in convex optimization. In 2011 International Conference on Computer Vision , pages 1762–1769, 2011

work page 2011
[31]

Povh and F

J. Povh and F. Rendl. Copositive and semideﬁnite relaxa tions of the quadratic assign- ment problem. Discrete Optimization, 6(3):231–241, 2009

work page 2009
[32]

Qi and D

H. Qi and D. Sun. An augmented Lagrangian dual approach f or the H-weighted nearest correlation matrix problem. IMA J. of Numerical Analysis , 31(2):491–511, 2011

work page 2011
[33]

F. Rendl. Semideﬁnite programming and combinatorial o ptimization. Applied Numer- ical Mathematics, 29(3):255–281, 1999

work page 1999
[34]

R. T. Rockafellar. Augmented Lagrangians and applicat ions of the proximal point algorithm in convex programming. Mathematics of Operations Research , 1(2):97–116, 1976

work page 1976
[35]

N. J. A. Sloane. Challenge problems: Independent sets i n graphs. http://www. research. att. com/˜ njas/doc/graphs. html , 2005

work page 2005
[36]

R. Sotirov. An eﬃcient semideﬁnite programming relaxa tion for the graph partition problem. INFORMS Journal on Computing , 26(1):16–30, 2014

work page 2014
[37]

Sun, K.-C

D. Sun, K.-C. Toh, Y. Yuan, and X.-Y. Zhao. SDPNAL+: A Mat lab software for semideﬁnite programming with bound constraints (version 1 .0). Optimization Methods and Software, 35(1):87–115, 2020. 25

work page 2020
[38]

D. Sun, Y. Yuan, G. Zhang, and X. Zhao. Accelerating prec onditioned ADMM via degenerate proximal point mappings. SIAM J. on Optimization , 35(2):1165–1193, 2025

work page 2025
[39]

Tang and K.-C

T. Tang and K.-C. Toh. Exploring chordal sparsity in sem ideﬁnite programming with sparse plus low-rank data matrices. arXiv preprint arXiv:2410.23849 , 2024

work page arXiv 2024
[40]

Tang and K.-C

T. Tang and K.-C. Toh. A feasible method for general conv ex low-rank SDP problems. SIAM J. on Optimization , 34(3):2169–2200, 2024

work page 2024
[41]

Tang and K.-C

T. Tang and K.-C. Toh. Solving graph equipartition SDPs on an algebraic variety. Mathematical Programming, 204(1):299–347, 2024

work page 2024
[42]

K.-C. Toh, M. J. Todd, and R. H. T¨ ut¨ unc¨ u. SDPT3—a Matl ab software package for semideﬁnite programming, version 1.3. Optimization Methods and Software , 11(1- 4):545–581, 1999

work page 1999
[43]

Wang and L

J. Wang and L. Hu. Solving low-rank semideﬁnite program s via manifold optimization. Journal of Scientiﬁc Computing , 104(1):1–33, 2025

work page 2025
[44]

Wang and C

S. Wang and C. Ding. Local convergence analysis of augme nted Lagrangian method for nonlinear semideﬁnite programming. Computational Optimization and Applications , 87(1):39–81, 2024

work page 2024
[45]

Y. Xu. Iteration complexity of inexact augmented Lagra ngian methods for constrained convex programming. Mathematical Programming, 185(1):199–244, 2021

work page 2021
[46]

L. Yang, D. Sun, and K.-C. Toh. SDPNAL+: a majorized semi smooth Newton- CG augmented Lagrangian method for semideﬁnite programmin g with nonnegative constraints. Mathematical Programming Computation, 7(3):331–366, 2015

work page 2015
[47]

X.-Y. Zhao, D. Sun, and K.-C. Toh. A Newton-CG augmented Lagrangian method for semideﬁnite programming. SIAM J. Optimization , 20(4):1737–1765, 2010. 26 A Proof of Theorem 1 In the following analysis, we always assume k≥ 2. From (19) and (20), we have that ∂zg(zk)−H ∗ (γ k) = ( ∂X δSn + (X k) +∇ f (X k)−A ∗ (λ k)−B ∗(µ k), ∂ yδP (yk) + µ k ) . (41) Becaus...

work page 2010
[48]

blk is a K× 2 cell array that speciﬁes the block structure of the variables, wh ere K is the number of blocks. For each k∈ [K], blk{k,1} is a character indicating the type of the k-th block, which can be one of the following: • ’s’: symmetric positive semideﬁnite matrix variable, 28 • ’l’: nonnegative vector variable, • ’f’: free vector variable. blk{k,2}...

work page
[49]

It has two columns when the user wants to make use of the sparse plus low- rank structure of the constraint matrices Ai’s described in [39]

At is a K× 1 or K× 2 cell array that describe the linear operator A in (SDPG1). It has two columns when the user wants to make use of the sparse plus low- rank structure of the constraint matrices Ai’s described in [39]. Suppose the k-th block is a matrix variable with dimension n and the constraint matrices {Ai}i∈ [m] have sparse plus low-rank decomposit...

work page
[50]

C is either a cell array or a function handle that describes the object ive function f in (SDPG1). When the SDP problem has linear objective function f (X) = ∑K i=1 ⟨ Ci, X i ⟩ such that the matrix blocks have sparse plus low-rank decomposition Ci = Cs i + Uidiag(di)U ⊤ i , we have that C{i, 1} = { Ci if blk{i,1}̸ = ’s’ Cs i if blk{i,1} = ’s’. (58) C{i, 2...

work page
[51]

b is an m-dimensional vector which is exactly the vector b in (SDPG1)

work page
[52]

The data structure of Bt is the same as At

Bt,l,u are used to denote the inequality constraint, l≤B (X)≤ u, in (SDPG1). The data structure of Bt is the same as At

work page
[53]

The user can refer to the main function sdpfplus.m for the complete list of available parameters

par is a struct-type array that contains the parameters and options for the so lver. The user can refer to the main function sdpfplus.m for the complete list of available parameters. Although there are many parameters, most of them are intended f or solver development and have been pre-tuned. Here, we highlight only a few important param eters that are co...

work page 2001

[1] [1]

E. Abbe. Community detection and stochastic block model s: recent developments. Journal of Machine Learning Research , 18(177):1–86, 2018

work page 2018

[2] [2]

Absil, R

P.-A. Absil, R. Mahony, and R. Sepulchre. Optimization a lgorithms on matrix man- ifolds. In Optimization Algorithms on Matrix Manifolds . Princeton University Press, 2009

work page 2009

[3] [3]

A. I. Barvinok. Problems of distance geometry and convex properties of quadratic maps. Discrete & Computational Geometry , 13(2):189–202, 1995

work page 1995

[4] [4]

H. H. Bauschke, P. L. Combettes, H. H. Bauschke, and P. L. C ombettes. Correction to: convex analysis and monotone operator theory in Hilbert spaces. Springer, 2017

work page 2017

[5] [5]

Beck and M

A. Beck and M. Teboulle. A fast iterative shrinkage-thre sholding algorithm for linear inverse problems. SIAM J. on Imaging Sciences , 2(1):183–202, 2009

work page 2009

[6] [6]

N. Boumal. An introduction to optimization on smooth manifolds . Cambridge Univer- sity Press, 2023

work page 2023

[7] [7]

Bredies and H

K. Bredies and H. Sun. A proximal point analysis of the pre conditioned alternating direction method of multipliers. Journal of Optimization Theory and Applications , 173:878–907, 2017

work page 2017

[8] [8]

S. Burer. On the copositive representation of binary and continuous nonconvex quadratic programs. Mathematical Programming, 120(2):479–495, 2009. 23

work page 2009

[9] [9]

Burer and C

S. Burer and C. Choi. Computational enhancements in low- rank semideﬁnite program- ming. Optimisation Methods and Software , 21(3):493–512, 2006

work page 2006

[10] [10]

Burer and R

S. Burer and R. D. Monteiro. A nonlinear programming alg orithm for solving semidef- inite programs via low-rank factorization. Mathematical Programming, 95(2):329–357, 2003

work page 2003

[11] [11]

R. E. Burkard, S. E. Karisch, and F. Rendl. QAPLIB–a quad ratic assignment problem library. Journal of Global optimization , 10:391–403, 1997

work page 1997

[12] [12]

Y. Cui, D. Sun, and K.-C. Toh. On the r-superlinear conve rgence of the KKT residuals generated by the augmented Lagrangian method for convex com posite conic program- ming. Mathematical Programming, 178(1):381–415, 2019

work page 2019

[13] [13]

Giselsson and S

P. Giselsson and S. Boyd. Diagonal scaling in douglas-r achford splitting and admm. In 53rd IEEE Conference on Decision and Control , pages 5033–5039. IEEE, 2014

work page 2014

[14] [14]

Graham, H

N. Graham, H. Hu, J. Im, X. Li, and H. Wolkowicz. A restric ted dual peaceman- rachford splitting method for a strengthened dnn relaxatio n for qap. INFORMS Jour- nal on Computing , 34(4):2125–2143, 2022

work page 2022

[15] [15]

Q. Han, C. Li, Z. Lin, C. Chen, Q. Deng, D. Ge, H. Liu, and Y. Ye. A low-rank ADMM splitting approach for semideﬁnite programming. INFORMS J. on Computing, to appear, 2025

work page 2025

[16] [16]

D. Hou, T. Tang, and K.-C. Toh. A low-rank augmented Lagr angian method for doubly nonnegative relaxations of mixed-binary quadratic progra ms. Operations Resarch, to appear., 2025

work page 2025

[17] [17]

D. Hou, T. Tang, and K.-C. Toh. Rinnal+: a riemannian alm solver for sdp-rlt relax- ations of mixed-binary quadratic programs: Di hou et al. Mathematical Programming Computation, pages 1–57, 2026

work page 2026

[18] [18]

Jiang, D

K. Jiang, D. Sun, and K.-C. Toh. An inexact accelerated p roximal gradient method for large scale linearly constrained convex SDP. SIAM J. on Optimization , 22(3):1042– 1064, 2012

work page 2012

[19] [19]

Kontogiorgis and R

S. Kontogiorgis and R. R. Meyer. A variable-penalty alt ernating directions method for convex optimization. Mathematical Programming, 83(1):29–53, 1998

work page 1998

[20] [20]

J. B. Lasserre. Global optimization with polynomials a nd the problem of moments. SIAM J. on Optimization , 11(3):796–817, 2001

work page 2001

[21] [21]

X. Li, D. Sun, and K.-C. Toh. QSDPNAL: a two-phase augmen ted Lagrangian method for convex quadratic semideﬁnite programming. Mathematical Programming Compu- tation, 10(4):703–743, 2018

work page 2018

[22] [22]

Y. Liu, Y. Xu, and W. Yin. Acceleration of primal–dual me thods by preconditioning and simple subproblem procedures. Journal of Scientiﬁc Computing , 86(2):21, 2021. 24

work page 2021

[23] [23]

Marteau-Ferey, F

U. Marteau-Ferey, F. Bach, and A. Rudi. Non-parametric models for non-negative functions. Advances in Neural Information Processing Systems , 33:12816–12826, 2020

work page 2020

[24] [24]

R. D. Monteiro, A. Sujanani, and D. Cifuentes. A low-ran k augmented Lagrangian method for large-scale semideﬁnite programming based on a h ybrid convex-nonconvex approach. arXiv preprint arXiv:2401.12490 , 2024

work page arXiv 2024

[25] [25]

Nakata, B

M. Nakata, B. J. Braams, K. Fujisawa, M. Fukuda, J. K. Per cus, M. Yamashita, and Z. Zhao. Variational calculation of second-order reduced d ensity matrices by strong n-representability conditions and an accurate semideﬁnit e programming solver. The Journal of Chemical Physics , 128(16), 2008

work page 2008

[26] [26]

Nakata, H

M. Nakata, H. Nakatsuji, M. Ehara, M. Fukuda, K. Nakata, and K. Fujisawa. Vari- ational calculations of fermion second-order reduced dens ity matrices by semideﬁnite programming algorithm. The Journal of Chemical Physics , 114(19):8282–8292, 2001

work page 2001

[27] [27]

Nie and L

J. Nie and L. Wang. Semideﬁnite relaxations for best ran k-1 tensor approximations. SIAM J. on Matrix Analysis and Applications , 35(3):1155–1179, 2014

work page 2014

[28] [28]

Nocedal and S

J. Nocedal and S. J. Wright. Numerical Optimization. Springer, 1999

work page 1999

[29] [29]

G. Pataki. On the rank of extreme matrices in semideﬁnit e programs and the mul- tiplicity of optimal eigenvalues. Mathematics of Operations Research , 23(2):339–358, 1998

work page 1998

[30] [30]

Pock and A

T. Pock and A. Chambolle. Diagonal preconditioning for ﬁrst order primal-dual algo- rithms in convex optimization. In 2011 International Conference on Computer Vision , pages 1762–1769, 2011

work page 2011

[31] [31]

Povh and F

J. Povh and F. Rendl. Copositive and semideﬁnite relaxa tions of the quadratic assign- ment problem. Discrete Optimization, 6(3):231–241, 2009

work page 2009

[32] [32]

Qi and D

H. Qi and D. Sun. An augmented Lagrangian dual approach f or the H-weighted nearest correlation matrix problem. IMA J. of Numerical Analysis , 31(2):491–511, 2011

work page 2011

[33] [33]

F. Rendl. Semideﬁnite programming and combinatorial o ptimization. Applied Numer- ical Mathematics, 29(3):255–281, 1999

work page 1999

[34] [34]

R. T. Rockafellar. Augmented Lagrangians and applicat ions of the proximal point algorithm in convex programming. Mathematics of Operations Research , 1(2):97–116, 1976

work page 1976

[35] [35]

N. J. A. Sloane. Challenge problems: Independent sets i n graphs. http://www. research. att. com/˜ njas/doc/graphs. html , 2005

work page 2005

[36] [36]

R. Sotirov. An eﬃcient semideﬁnite programming relaxa tion for the graph partition problem. INFORMS Journal on Computing , 26(1):16–30, 2014

work page 2014

[37] [37]

Sun, K.-C

D. Sun, K.-C. Toh, Y. Yuan, and X.-Y. Zhao. SDPNAL+: A Mat lab software for semideﬁnite programming with bound constraints (version 1 .0). Optimization Methods and Software, 35(1):87–115, 2020. 25

work page 2020

[38] [38]

D. Sun, Y. Yuan, G. Zhang, and X. Zhao. Accelerating prec onditioned ADMM via degenerate proximal point mappings. SIAM J. on Optimization , 35(2):1165–1193, 2025

work page 2025

[39] [39]

Tang and K.-C

T. Tang and K.-C. Toh. Exploring chordal sparsity in sem ideﬁnite programming with sparse plus low-rank data matrices. arXiv preprint arXiv:2410.23849 , 2024

work page arXiv 2024

[40] [40]

Tang and K.-C

T. Tang and K.-C. Toh. A feasible method for general conv ex low-rank SDP problems. SIAM J. on Optimization , 34(3):2169–2200, 2024

work page 2024

[41] [41]

Tang and K.-C

T. Tang and K.-C. Toh. Solving graph equipartition SDPs on an algebraic variety. Mathematical Programming, 204(1):299–347, 2024

work page 2024

[42] [42]

K.-C. Toh, M. J. Todd, and R. H. T¨ ut¨ unc¨ u. SDPT3—a Matl ab software package for semideﬁnite programming, version 1.3. Optimization Methods and Software , 11(1- 4):545–581, 1999

work page 1999

[43] [43]

Wang and L

J. Wang and L. Hu. Solving low-rank semideﬁnite program s via manifold optimization. Journal of Scientiﬁc Computing , 104(1):1–33, 2025

work page 2025

[44] [44]

Wang and C

S. Wang and C. Ding. Local convergence analysis of augme nted Lagrangian method for nonlinear semideﬁnite programming. Computational Optimization and Applications , 87(1):39–81, 2024

work page 2024

[45] [45]

Y. Xu. Iteration complexity of inexact augmented Lagra ngian methods for constrained convex programming. Mathematical Programming, 185(1):199–244, 2021

work page 2021

[46] [46]

L. Yang, D. Sun, and K.-C. Toh. SDPNAL+: a majorized semi smooth Newton- CG augmented Lagrangian method for semideﬁnite programmin g with nonnegative constraints. Mathematical Programming Computation, 7(3):331–366, 2015

work page 2015

[47] [47]

X.-Y. Zhao, D. Sun, and K.-C. Toh. A Newton-CG augmented Lagrangian method for semideﬁnite programming. SIAM J. Optimization , 20(4):1737–1765, 2010. 26 A Proof of Theorem 1 In the following analysis, we always assume k≥ 2. From (19) and (20), we have that ∂zg(zk)−H ∗ (γ k) = ( ∂X δSn + (X k) +∇ f (X k)−A ∗ (λ k)−B ∗(µ k), ∂ yδP (yk) + µ k ) . (41) Becaus...

work page 2010

[48] [48]

blk is a K× 2 cell array that speciﬁes the block structure of the variables, wh ere K is the number of blocks. For each k∈ [K], blk{k,1} is a character indicating the type of the k-th block, which can be one of the following: • ’s’: symmetric positive semideﬁnite matrix variable, 28 • ’l’: nonnegative vector variable, • ’f’: free vector variable. blk{k,2}...

work page

[49] [49]

It has two columns when the user wants to make use of the sparse plus low- rank structure of the constraint matrices Ai’s described in [39]

At is a K× 1 or K× 2 cell array that describe the linear operator A in (SDPG1). It has two columns when the user wants to make use of the sparse plus low- rank structure of the constraint matrices Ai’s described in [39]. Suppose the k-th block is a matrix variable with dimension n and the constraint matrices {Ai}i∈ [m] have sparse plus low-rank decomposit...

work page

[50] [50]

C is either a cell array or a function handle that describes the object ive function f in (SDPG1). When the SDP problem has linear objective function f (X) = ∑K i=1 ⟨ Ci, X i ⟩ such that the matrix blocks have sparse plus low-rank decomposition Ci = Cs i + Uidiag(di)U ⊤ i , we have that C{i, 1} = { Ci if blk{i,1}̸ = ’s’ Cs i if blk{i,1} = ’s’. (58) C{i, 2...

work page

[51] [51]

b is an m-dimensional vector which is exactly the vector b in (SDPG1)

work page

[52] [52]

The data structure of Bt is the same as At

Bt,l,u are used to denote the inequality constraint, l≤B (X)≤ u, in (SDPG1). The data structure of Bt is the same as At

work page

[53] [53]

The user can refer to the main function sdpfplus.m for the complete list of available parameters

par is a struct-type array that contains the parameters and options for the so lver. The user can refer to the main function sdpfplus.m for the complete list of available parameters. Although there are many parameters, most of them are intended f or solver development and have been pre-tuned. Here, we highlight only a few important param eters that are co...

work page 2001