pith. sign in

arxiv: 2503.20142 · v4 · pith:SQ5XYRQ2new · submitted 2025-03-26 · 🧮 math.OC

Local Linear Convergence of the Alternating Direction Method of Multipliers for Semidefinite Programming under Strict Complementarity

Shucheng Kang , Xin Jiang , Heng Yang This is my paper

Pith reviewed 2026-05-22 23:31 UTC · model grok-4.3

classification 🧮 math.OC
keywords alternating direction method of multiplierssemidefinite programminglocal linear convergencestrict complementarityprojection onto positive semidefinite coneerror boundADMM
0
0 comments X

The pith

ADMM attains local linear convergence for semidefinite programming whenever the optimal primal-dual solutions satisfy strict complementarity.

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

The paper shows that the alternating direction method of multipliers reaches local linear convergence near the solution for semidefinite programming as long as the optimal primal-dual pair satisfies strict complementarity. This holds without any nondegeneracy conditions required by earlier analyses. A sympathetic reader would care because the result accounts for the method's frequent ability to reach high accuracy in practice despite its known sublinear worst-case complexity. The argument also ties observed slow convergence to near violations of the complementarity condition.

Core claim

The alternating direction method of multipliers applied to semidefinite programming attains local linear convergence provided that the converged primal-dual optimal solutions satisfy strict complementarity. This convergence is independent of nondegeneracy conditions. The argument proceeds by direct local linearization of the ADMM iteration operator together with a refined error bound on the projection onto the positive semidefinite cone that improves on prior estimates by exposing the anisotropic character of the residuals.

What carries the argument

Direct local linearization of the ADMM operator together with a refined error bound for the projection onto the positive semidefinite cone; this pair produces a contraction whose rate is controlled by the strict complementarity gap.

If this is right

  • ADMM reaches high-accuracy solutions on SDP instances where strict complementarity holds at optimality.
  • Local linear rates appear even when nondegeneracy conditions fail.
  • Convergence slows when strict complementarity is nearly violated, matching patterns seen in linear programming.
  • The anisotropic residuals in the projection bound explain direction-dependent error decay.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The linearization technique could extend to other first-order splitting methods on conic programs.
  • A diagnostic that measures the strict complementarity gap at a candidate solution could predict attainable accuracy before running the method.
  • The refined projection bound may apply to related matrix cones beyond the positive semidefinite case.

Load-bearing premise

Strict complementarity must hold exactly at the optimal solutions so that the refined projection error bound produces a contraction factor strictly less than one.

What would settle it

Run ADMM on an SDP instance whose optimal solutions satisfy strict complementarity and check whether the tail of the sequence shows only sublinear error reduction; linear reduction would support the claim while persistent sublinear reduction would refute it.

Figures

Figures reproduced from arXiv: 2503.20142 by Heng Yang, Shucheng Kang, Xin Jiang.

Figure 1
Figure 1. Figure 1: Four representative SDP instances. (a) A toy structure-from-motion problem from [ [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: MAXCUT problems with with random (standard Gaussian) initial guess. In all cases, the con [PITH_FULL_IMAGE:figures/full_fig_p027_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Additional Hamming graph problems with with random (standard Gaussian) initial guess. In all [PITH_FULL_IMAGE:figures/full_fig_p027_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Maximum stable set problems with with random (standard Gaussian) initial guess. In all cases, [PITH_FULL_IMAGE:figures/full_fig_p028_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Structure-from-motion problems with with random (standard Gaussian) initial guess. In all cases, [PITH_FULL_IMAGE:figures/full_fig_p028_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Random BQP problems with c ∼ N (0, In) with random (standard Gaussian) initial guess. In all cases, the converging Z⋆ is nonsingular. BQP-r1-20-1 BQP-r1-30-1 BQP-r1-40-1 [PITH_FULL_IMAGE:figures/full_fig_p029_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Random BQP problems with c ∼ N (0, In) with all-zero initial guess. In all cases, the converging Z⋆ is singular. BQP-r2-20-1 BQP-r2-30-1 BQP-r2-40-1 [PITH_FULL_IMAGE:figures/full_fig_p029_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: random BQP problems with c = 0 with random (standard Gaussian) initial guess, under which both primal and dual nondegeneracy fail. In all cases, the converging Z⋆ is nonsingular. 29 [PITH_FULL_IMAGE:figures/full_fig_p029_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: Quasar problems with random (standard Gaussian) initial guess. In all cases, the converging [PITH_FULL_IMAGE:figures/full_fig_p030_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: Random QS problems with random (standard Gaussian) initial guess. In all cases, the converg [PITH_FULL_IMAGE:figures/full_fig_p030_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: Demonstration of numerical rates. (a) Plot of [PITH_FULL_IMAGE:figures/full_fig_p031_11.png] view at source ↗
Figure 12
Figure 12. Figure 12: Cases from datasets [14, 42]. For these SDPs, ADMM fails to achieve rmax ≤ 10−10 within the stated budget, and no clear linear convergence is observed. 9 Discussion: Rank Identification and Linear Convergence First-order methods (e.g., PDHG) for LP (a special case of SDP) are known to have an intriguing two-stage phenomenon [40]. The first stage identifies the basis and finishes in a finite number of iter… view at source ↗
Figure 13
Figure 13. Figure 13: Six representative SDP instances illustrating rank identification: almost at the same time [PITH_FULL_IMAGE:figures/full_fig_p034_13.png] view at source ↗
Figure 14
Figure 14. Figure 14: More Hamming graph problems with with random (standard Gaussian) initial guess. In all cases, [PITH_FULL_IMAGE:figures/full_fig_p055_14.png] view at source ↗
Figure 15
Figure 15. Figure 15: Additional Random BQP problems with c ∼ N (0, In) and random (standard Gaussian) initial￾ization. In all cases, the converging Z⋆ is nonsingular. 55 [PITH_FULL_IMAGE:figures/full_fig_p055_15.png] view at source ↗
Figure 16
Figure 16. Figure 16: Additional Random BQP problems with c ∼ N (0, In) and all-zeros initialization. In all cases, the converging Z⋆ is singular. BQP-r2-20-2 BQP-r2-30-2 BQP-r2-40-2 BQP-r2-20-3 BQP-r2-30-3 BQP-r2-40-3 [PITH_FULL_IMAGE:figures/full_fig_p056_16.png] view at source ↗
Figure 17
Figure 17. Figure 17: Additional random BQP problems with c = 0 and random (standard Gaussian) initialization. In all cases, the converging Z⋆ is nonsingular. 56 [PITH_FULL_IMAGE:figures/full_fig_p056_17.png] view at source ↗
read the original abstract

We investigate the local linear convergence properties of the Alternating Direction Method of Multipliers (ADMM) when applied to Semidefinite Programming (SDP). A longstanding belief suggests that ADMM is only capable of solving SDPs to moderate accuracy, primarily due to its sublinear worst-case complexity and empirical observations of slow convergence. We challenge this notion by introducing a new sufficient condition for local linear convergence: as long as the converged primal-dual optimal solutions satisfy strict complementarity, ADMM attains local linear convergence, independent of nondegeneracy conditions. Our proof is based on a direct local linearization of the ADMM operator and a refined error bound for the projection onto the positive semidefinite cone, improving previous bounds and revealing the anisotropic nature of projection residuals. Extensive numerical experiments confirm the significance of our theoretical results, demonstrating that ADMM achieves local linear convergence and computes high-accuracy solutions in a variety of SDP instances, including those cases where nondegeneracy fails. Furthermore, we identify where ADMM struggles, linking these difficulties with near violations of strict complementarity-a phenomenon that parallels recent findings in linear programming.

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.

Referee Report

0 major / 3 minor

Summary. The manuscript proves local linear convergence of ADMM applied to semidefinite programming whenever a primal-dual optimal solution pair satisfies strict complementarity. The argument proceeds by direct local linearization of the ADMM operator together with a refined, anisotropic error bound on the projection onto the positive-semidefinite cone; the resulting rate is independent of nondegeneracy. Numerical experiments on a range of SDP instances, including those violating nondegeneracy, are presented as corroboration, and the authors link observed slow convergence to near-violations of strict complementarity.

Significance. If the linearization and projection bound are valid, the result is significant: it supplies an explicit, checkable sufficient condition for linear convergence of ADMM on SDPs and removes the need for nondegeneracy, thereby addressing a longstanding practical limitation. The refined projection analysis and the explicit identification of failure modes near strict-complementarity boundaries constitute clear advances over prior work.

minor comments (3)
  1. [Introduction / Section 3] The abstract states that the projection bound 'improves previous bounds,' but no explicit comparison (e.g., to the bound in reference X) appears in the main text; adding a short remark or table entry would strengthen the claim.
  2. [Numerical Experiments] In the numerical section the authors report iteration counts and residual decay but do not tabulate the observed linear rates against the theoretically predicted constant; a single additional table or plot would make the validation more quantitative.
  3. [Preliminaries] Notation for the dual variable and the projection residual is introduced without a consolidated list; a short notation table would aid readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary and significance assessment of our manuscript on local linear convergence of ADMM for SDPs under strict complementarity. The recommendation of minor revision is noted. No major comments appear in the report, so we have no points to address point-by-point at this stage and will handle any minor issues in the revision.

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained

full rationale

The paper's central result (local linear convergence of ADMM on SDP under strict complementarity) is established via direct linearization of the iteration map and a refined anisotropic error bound on the PSD projection operator. No equations reduce by construction to fitted parameters, self-defined quantities, or load-bearing self-citations. The argument relies on standard operator properties and the strict complementarity hypothesis without importing uniqueness theorems or ansatzes from prior author work. Numerical experiments are presented as corroborative only. This matches the default case of an independent theoretical derivation.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper relies on standard convex-analysis facts about the projection onto the PSD cone and on the local behavior of the ADMM fixed-point operator; no free parameters or new entities are introduced.

axioms (1)
  • standard math Standard properties of the metric projection onto the positive semidefinite cone
    Invoked to obtain the refined anisotropic error bound used in the linearization argument.

pith-pipeline@v0.9.0 · 5730 in / 1268 out tokens · 35843 ms · 2026-05-22T23:31:41.466153+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

69 extracted references · 69 canonical work pages · 1 internal anchor

  1. [1]

    Complementarity and nondegeneracy in semidefinite programming.Mathematical Programming, 77(1):111–128, 1997

    Farid Alizadeh, Jean-Pierre A Haeberly, and Michael L Overton. Complementarity and nondegeneracy in semidefinite programming.Mathematical Programming, 77(1):111–128, 1997

    work page 1997

  2. [2]

    Primal–dual interior-point methods for semidefinite programming: Convergence rates, stability and numerical results.SIAM Journal on Optimization, 8(3):746–768, 1998

    Farid Alizadeh, Jean-Pierre A Haeberly, and Michael L Overton. Primal–dual interior-point methods for semidefinite programming: Convergence rates, stability and numerical results.SIAM Journal on Optimization, 8(3):746–768, 1998

    work page 1998

  3. [3]

    Faster first-order primal–dual methods for linear programming using restarts and sharpness.Mathematical Programming, 201(1):133–184, 2023

    David Applegate, Oliver Hinder, Haihao Lu, and Miles Lubin. Faster first-order primal–dual methods for linear programming using restarts and sharpness.Mathematical Programming, 201(1):133–184, 2023. 54 hamming-10-2 hamming-8-3-4 hamming-9-5-6 Figure 14: More Hamming graph problems with with random (standard Gaussian) initial guess. In all cases, the conve...

    work page 2023

  4. [4]

    MOSEK optimization toolbox for MATLAB.User’s Guide and Reference Manual, Version, 4(1), 2019

    Mosek ApS. MOSEK optimization toolbox for MATLAB.User’s Guide and Reference Manual, Version, 4(1), 2019

    work page 2019

  5. [5]

    Optimal rates of linear convergence of relaxed alternating projections and generalized Douglas–Rachford methods for two subspaces.Numerical Algorithms, 73:33–76, 2016

    Heinz H Bauschke, JY Bello Cruz, Tran TA Nghia, Hung M Pha, and Xianfu Wang. Optimal rates of linear convergence of relaxed alternating projections and generalized Douglas–Rachford methods for two subspaces.Numerical Algorithms, 73:33–76, 2016

    work page 2016

  6. [6]

    Springer, Berlin, Heidelberg, 2017

    Heinz H Bauschke and Patrick L Combettes.Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Springer, Berlin, Heidelberg, 2017

    work page 2017

  7. [7]

    The non-convex Burer–Monteiro approach works on smooth semidefinite programs.Advances in Neural Information Processing Systems, 29, 2016

    Nicolas Boumal, Vlad Voroninski, and Afonso Bandeira. The non-convex Burer–Monteiro approach works on smooth semidefinite programs.Advances in Neural Information Processing Systems, 29, 2016

    work page 2016

  8. [8]

    A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization.Mathematical Programming, 95(2):329–357, 2003

    Samuel Burer and Renato DC Monteiro. A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization.Mathematical Programming, 95(2):329–357, 2003

    work page 2003

  9. [9]

    Constraint nondegeneracy, strong regularity, and nonsingularity in semidefinite programming.SIAM Journal on Optimization, 19(1):370–396, 2008

    Zi Xian Chan and Defeng Sun. Constraint nondegeneracy, strong regularity, and nonsingularity in semidefinite programming.SIAM Journal on Optimization, 19(1):370–396, 2008

    work page 2008

  10. [10]

    On the equivalence of inexact proximal ALM and ADMM for a class of convex composite programming.Mathematical Programming, 185(1):111–161, 2021

    Liang Chen, Xudong Li, Defeng Sun, and Kim-Chuan Toh. On the equivalence of inexact proximal ALM and ADMM for a class of convex composite programming.Mathematical Programming, 185(1):111–161, 2021

    work page 2021

  11. [11]

    An efficient inexact symmetric Gauss–Seidel based ma- jorized ADMM for high-dimensional convex composite conic programming.Mathematical Programming, 161:237–270, 2017

    Liang Chen, Defeng Sun, and Kim-Chuan Toh. An efficient inexact symmetric Gauss–Seidel based ma- jorized ADMM for high-dimensional convex composite conic programming.Mathematical Programming, 161:237–270, 2017

    work page 2017

  12. [12]

    On the Asymptotic Superlinear Convergence of the Augmented Lagrangian Method for Semidefinite Programming with Multiple Solutions

    Ying Cui, Defeng Sun, and Kim-Chuan Toh. On the asymptotic superlinear convergence of the aug- mented Lagrangian method for semidefinite programming with multiple solutions. arXiv preprint arXiv:1610.00875, 2016

    work page internal anchor Pith review Pith/arXiv arXiv 2016

  13. [13]

    Faster convergence rates of relaxed Peaceman-Rachford and ADMM under regularity assumptions.Mathematics of Operations Research, 42(3):783–805, August 2017

    Damek Davis and Wotao Yin. Faster convergence rates of relaxed Peaceman-Rachford and ADMM under regularity assumptions.Mathematics of Operations Research, 42(3):783–805, August 2017

    work page 2017

  14. [14]

    Davis and Yifan Hu

    Timothy A. Davis and Yifan Hu. The University of Florida sparse matrix collection.ACM Transactions on Mathematical Software (TOMS), 38(1):1–25, 2011

    work page 2011

  15. [15]

    On the global and linear convergence of the generalized alternating direction method of multipliers.Journal of Scientific Computing, 66(3):889–916, March 2016

    Wei Deng and Wotao Yin. On the global and linear convergence of the generalized alternating direction method of multipliers.Journal of Scientific Computing, 66(3):889–916, March 2016

    work page 2016

  16. [16]

    Revisiting spectral bundle methods: Primal–dual (sub) linear convergence rates.SIAM Journal on Optimization, 33(2):1305–1332, 2023

    Lijun Ding and Benjamin Grimmer. Revisiting spectral bundle methods: Primal–dual (sub) linear convergence rates.SIAM Journal on Optimization, 33(2):1305–1332, 2023

    work page 2023

  17. [17]

    A strict complementarity approach to error bound and sensitivity of solution of conic programs.Optimization Letters, 17(7):1551–1574, 2023

    Lijun Ding and Madeleine Udell. A strict complementarity approach to error bound and sensitivity of solution of conic programs.Optimization Letters, 17(7):1551–1574, 2023

    work page 2023

  18. [18]

    Dmitriy Drusvyatskiy and Adrian S. Lewis. Optimality, identifiability, and sensitivity.Mathematical Programming, 147(1):467–498, 2014

    work page 2014

  19. [19]

    Global minimization of polynomial integral functionals.SIAM Journal on Scientific Computing, 46(4):A2123–A2149, 2024

    Giovanni Fantuzzi and Federico Fuentes. Global minimization of polynomial integral functionals.SIAM Journal on Scientific Computing, 46(4):A2123–A2149, 2024

    work page 2024

  20. [20]

    Cosmo: A conic operator splitting method for convex conic problems.Journal of Optimization Theory and Applications, 190(3):779–810, 2021

    Michael Garstka, Mark Cannon, and Paul Goulart. Cosmo: A conic operator splitting method for convex conic problems.Journal of Optimization Theory and Applications, 190(3):779–810, 2021

    work page 2021

  21. [21]

    Many photonic design problems are sparse QCQPs.Science Advances, 11(1):eadl3237, 2025

    Shai Gertler, Zeyu Kuang, Colin Christie, Hao Li, and Owen D Miller. Many photonic design problems are sparse QCQPs.Science Advances, 11(1):eadl3237, 2025. 57

    work page 2025

  22. [22]

    Linear rate convergence of the alternating direction method of multipliers for convex composite programming.Mathematics of Operations Research, 43(2):622–637, 2018

    Deren Han, Defeng Sun, and Liwei Zhang. Linear rate convergence of the alternating direction method of multipliers for convex composite programming.Mathematics of Operations Research, 43(2):622–637, 2018

    work page 2018

  23. [23]

    Building rome with convex optimization.arXiv preprint arXiv:2502.04640, 2025

    Haoyu Han and Heng Yang. Building rome with convex optimization.arXiv preprint arXiv:2502.04640, 2025

    work page arXiv 2025

  24. [24]

    A low-rank ADMM splitting approach for semidefinite programming.arXiv preprint arXiv:2403.09133, 2024

    Qiushi Han, Chenxi Li, Zhenwei Lin, Caihua Chen, Qi Deng, Dongdong Ge, Huikang Liu, and Yinyu Ye. A low-rank ADMM splitting approach for semidefinite programming.arXiv preprint arXiv:2403.09133, 2024

    work page arXiv 2024

  25. [25]

    A spectral bundle method for semidefinite programming.SIAM Journal on Optimization, 10(3):673–696, 2000

    Christoph Helmberg and Franz Rendl. A spectral bundle method for semidefinite programming.SIAM Journal on Optimization, 10(3):673–696, 2000

    work page 2000

  26. [26]

    Alan J. Hoffman. On approximate solutions of systems of linear inequalities. InSelected Papers Of Alan J Hoffman: With Commentary, pages 174–176. World Scientific, Singapore, 2003

    work page 2003

  27. [27]

    On the linear convergence of the alternating direction method of multipliers

    Mingyi Hong and Zhi-Quan Luo. On the linear convergence of the alternating direction method of multipliers. Mathematical Programming, 162(1):165–199, 2017

    work page 2017

  28. [28]

    Sparse polynomial optimization with unbounded sets

    Lei Huang, Shucheng Kang, Jie Wang, and Heng Yang. Sparse polynomial optimization with unbounded sets. arXiv preprint arXiv:2401.15837, 2024

    work page arXiv 2024

  29. [29]

    Bregman primal–dual first-order method and application to sparse semidefinite programming.Computational Optimization and Applications, 81(1):127–159, 2022

    Xin Jiang and Lieven Vandenberghe. Bregman primal–dual first-order method and application to sparse semidefinite programming.Computational Optimization and Applications, 81(1):127–159, 2022

    work page 2022

  30. [30]

    Global contact-rich planning with sparsity-rich semidefi- nite relaxations

    Shucheng Kang, Guorui Liu, and Heng Yang. Global contact-rich planning with sparsity-rich semidefi- nite relaxations. arXiv preprint arXiv:2502.02829, 2025

    work page arXiv 2025

  31. [31]

    Fast and certifiable trajectory optimization

    Shucheng Kang, Xiaoyang Xu, Jay Sarva, Ling Liang, and Heng Yang. Fast and certifiable trajectory optimization. In International Workshop on the Algorithmic Foundations of Robotics, 2024

    work page 2024

  32. [32]

    Lasserre

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

    work page 2001

  33. [33]

    Activesets, nonsmoothness, andsensitivity

    AdrianS.Lewis. Activesets, nonsmoothness, andsensitivity. SIAM Journal on Optimization, 13(3):702– 725, 2002

    work page 2002

  34. [34]

    A semismooth newton method for semidef- inite programs and its applications in electronic structure calculations

    Yongfeng Li, Zaiwen Wen, Chao Yang, and Ya-Xiang Yuan. A semismooth newton method for semidef- inite programs and its applications in electronic structure calculations. SIAM Journal on Scientific Computing, 40(6):A4131–A4157, 2018

    work page 2018

  35. [35]

    Local convergence properties of Douglas–Rachford and alternating direction method of multipliers.Journal of Optimization Theory and Applications, 172:874– 913, 2017

    Jingwei Liang, Jalal Fadili, and Gabriel Peyré. Local convergence properties of Douglas–Rachford and alternating direction method of multipliers.Journal of Optimization Theory and Applications, 172:874– 913, 2017

    work page 2017

  36. [36]

    An overview and comparison of spectral bundle methods for primal and dual semidefinite programs.arXiv preprint arXiv:2307.07651, 2023

    Feng-Yi Liao, Lijun Ding, and Yang Zheng. An overview and comparison of spectral bundle methods for primal and dual semidefinite programs.arXiv preprint arXiv:2307.07651, 2023

    work page arXiv 2023

  37. [37]

    Inexact augmented Lagrangian methods for conic optimiza- tion: Quadratic growth and linear convergence.Advances in Neural Information Processing Systems, 37:41013–41050, 2024

    Feng-Yi Liao, Lijun Ding, and Yang Zheng. Inexact augmented Lagrangian methods for conic optimiza- tion: Quadratic growth and linear convergence.Advances in Neural Information Processing Systems, 37:41013–41050, 2024

    work page 2024

  38. [38]

    A bundle-based augmented Lagrangian framework: Algorithm, conver- gence, and primal–dual principles.arXiv preprint arXiv:2502.08835, 2025

    Feng-Yi Liao and Yang Zheng. A bundle-based augmented Lagrangian framework: Algorithm, conver- gence, and primal–dual principles.arXiv preprint arXiv:2502.08835, 2025. 58

    work page arXiv 2025

  39. [39]

    Partial error bound conditions and the linear convergence rate of the alternating direction method of multipliers.SIAM Journal on Numerical Analysis, 56(4):2095–2123, January 2018

    Yongchao Liu, Xiaoming Yuan, Shangzhi Zeng, and Jin Zhang. Partial error bound conditions and the linear convergence rate of the alternating direction method of multipliers.SIAM Journal on Numerical Analysis, 56(4):2095–2123, January 2018

    work page 2095

  40. [40]

    On the geometry and refined rate of primal–dual hybrid gradient for linear programming

    Haihao Lu and Jinwen Yang. On the geometry and refined rate of primal–dual hybrid gradient for linear programming. Mathematical Programming, pages 1–39, 2024

    work page 2024

  41. [41]

    World Scientific, Singapore, 2023

    Victor Magron and Jie Wang.Sparse Polynomial Optimization: Theory and Practice. World Scientific, Singapore, 2023

    work page 2023

  42. [42]

    Mittelmann

    Hans D. Mittelmann. Several SDP-codes on sparse and other SDP problems, 2006

    work page 2006

  43. [43]

    SIAM, Philadelphia, PA, 2023

    Jiawang Nie.Moment and Polynomial Optimization. SIAM, Philadelphia, PA, 2023

    work page 2023

  44. [44]

    Ageneralanalysis of the convergence of ADMM

    RobertNishihara, LaurentLessard, BenRecht, AndrewPackard, andMichaelJordan. Ageneralanalysis of the convergence of ADMM. InInternational Conference on Machine learning, pages 343–352. PMLR, 2015

    work page 2015

  45. [45]

    On the equivalence of the primal–dual hybrid gradient method and Douglas–Rachford splitting.Mathematical Programming, 179(1-2):85–108, 2020

    Daniel O’Connor and Lieven Vandenberghe. On the equivalence of the primal–dual hybrid gradient method and Douglas–Rachford splitting.Mathematical Programming, 179(1-2):85–108, 2020

    work page 2020

  46. [46]

    SCS: Splitting conic solver, version 3.2.4

    Brendan O’Donoghue, Eric Chu, Neal Parikh, and Stephen Boyd. SCS: Splitting conic solver, version 3.2.4. https://github.com/cvxgrp/scs, November 2023

    work page 2023

  47. [47]

    Parlett.The symmetric eigenvalue problem

    Beresford N. Parlett.The symmetric eigenvalue problem. SIAM, Philadelphia, PA, 1998

    work page 1998

  48. [48]

    The DIMACS library of semidefinite-quadratic-linear programs

    Gabor Pataki and Stefan Schmieta. The DIMACS library of semidefinite-quadratic-linear programs. 1999

    work page 1999

  49. [49]

    Michael J. D. Powell. A method for nonlinear constraints in minimization problems.Optimization, pages 283–298, 1969

    work page 1969

  50. [50]

    Augmented lagrangians and applications of the proximal point algorithm in convex programming.Mathematics of operations research, 1(2):97–116, 1976

    R Tyrrell Rockafellar. Augmented lagrangians and applications of the proximal point algorithm in convex programming.Mathematics of operations research, 1(2):97–116, 1976

    work page 1976

  51. [51]

    Cambridge University Press, Cambridge, 2022

    Ernest K Ryu and Wotao Yin.Large-scale convex optimization: algorithms & analyses via monotone operators. Cambridge University Press, Cambridge, 2022

    work page 2022

  52. [52]

    On the Kronecker product

    Kathrin Schacke. On the Kronecker product. Master’s thesis, University of Waterloo, 2004

    work page 2004

  53. [53]

    Jos F. Sturm. Error bounds for linear matrix inequalities.SIAM Journal on Optimization, 10(4):1228– 1248, 2000

    work page 2000

  54. [54]

    Semismooth matrix-valued functions.Mathematics of Operations Research, 27(1):150–169, 2002

    Defeng Sun and Jie Sun. Semismooth matrix-valued functions.Mathematics of Operations Research, 27(1):150–169, 2002

    work page 2002

  55. [55]

    A feasible method for general convex low-rank SDP problems

    Tianyun Tang and Kim-Chuan Toh. A feasible method for general convex low-rank SDP problems. arXiv preprint arXiv:2312.07908, 2023

    work page arXiv 2023

  56. [56]

    Solving low-rank semidefinite programs via manifold optimization.arXiv preprint arXiv:2303.01722, 2023

    Jie Wang and Liangbing Hu. Solving low-rank semidefinite programs via manifold optimization.arXiv preprint arXiv:2303.01722, 2023

    work page arXiv 2023

  57. [57]

    Certifying global optimality of ac-opf solutions via sparse polynomial optimization.Electric Power Systems Research, 213:108683, 2022

    Jie Wang, Victor Magron, and Jean B Lasserre. Certifying global optimality of ac-opf solutions via sparse polynomial optimization.Electric Power Systems Research, 213:108683, 2022

    work page 2022

  58. [58]

    Alternating direction augmented Lagrangian methods for semidefinite programming.Mathematical Programming Computation, 2(3):203–230, 2010

    Zaiwen Wen, Donald Goldfarb, and Wotao Yin. Alternating direction augmented Lagrangian methods for semidefinite programming.Mathematical Programming Computation, 2(3):203–230, 2010. 59

    work page 2010

  59. [59]

    Springer Science & Business Media, Berlin, Heidelberg, 2012

    Henry Wolkowicz, Romesh Saigal, and Lieven Vandenberghe.Handbook of semidefinite programming: theory, algorithms, and applications, volume 27. Springer Science & Business Media, Berlin, Heidelberg, 2012

    work page 2012

  60. [60]

    Stephen J. Wright. Identifiable surfaces in constrained optimization.SIAM Journal on Control and Optimization, 31(4):1063–1079, 1993

    work page 1993

  61. [61]

    A quaternion-based certifiably optimal solution to the wahba problem with outliers

    Heng Yang and Luca Carlone. A quaternion-based certifiably optimal solution to the wahba problem with outliers. InInternational Conference on Computer Vision, pages 1665–1674, 2019

    work page 2019

  62. [62]

    Certifiably optimal outlier-robust geometric perception: Semidefinite relaxations and scalable global optimization

    Heng Yang and Luca Carlone. Certifiably optimal outlier-robust geometric perception: Semidefinite relaxations and scalable global optimization. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(3):2816–2834, 2022

    work page 2022

  63. [63]

    An inexact projected gradient method with rounding and lifting by nonlinear programming for solving rank-one semidefinite relaxation of polynomial optimization

    Heng Yang, Ling Liang, Luca Carlone, and Kim-Chuan Toh. An inexact projected gradient method with rounding and lifting by nonlinear programming for solving rank-one semidefinite relaxation of polynomial optimization. Mathematical Programming, 201(1):409–472, 2023

    work page 2023

  64. [64]

    Liuqin Yang, Defeng Sun, and Kim-Chuan Toh. SDPNAL+: A majorized semismooth Newton-CG aug- mented Lagrangian method for semidefinite programming with nonnegative constraints.Mathematical Programming Computation, 7(3):331–366, 2015

    work page 2015

  65. [65]

    Discerning the linear convergence of ADMM for structured convex optimization through the lens of variational analysis.Journal of Machine Learning Research, 21(83):1–75, 2020

    Xiaoming Yuan, Shangzhi Zeng, and Jin Zhang. Discerning the linear convergence of ADMM for structured convex optimization through the lens of variational analysis.Journal of Machine Learning Research, 21(83):1–75, 2020

    work page 2020

  66. [66]

    The exact worst-case convergence rate of the alternating direction method of multipliers.Mathematical Programming, 208(1):243–276, 2024

    Moslem Zamani, Hadi Abbaszadehpeivasti, and Etienne de Klerk. The exact worst-case convergence rate of the alternating direction method of multipliers.Mathematical Programming, 208(1):243–276, 2024

    work page 2024

  67. [67]

    A linearly convergent majorized ADMM with indefinite prox- imal terms for convex composite programming and its applications

    Ning Zhang, Jia Wu, and Liwei Zhang. A linearly convergent majorized ADMM with indefinite prox- imal terms for convex composite programming and its applications. Mathematics of Computation, 89(324):1867–1894, 2020

    work page 2020

  68. [68]

    A Newton-CG augmented Lagrangian method for semidefinite programming.SIAM Journal on Optimization, 20(4):1737–1765, 2010

    Xin-Yuan Zhao, Defeng Sun, and Kim-Chuan Toh. A Newton-CG augmented Lagrangian method for semidefinite programming.SIAM Journal on Optimization, 20(4):1737–1765, 2010

    work page 2010

  69. [69]

    Fast ADMM for homogeneous self-dual embedding of sparse SDPs.IFAC-PapersOnLine, 50(1):8411–8416, 2017

    Yang Zheng, Giovanni Fantuzzi, Antonis Papachristodoulou, Paul Goulart, and Andrew Wynn. Fast ADMM for homogeneous self-dual embedding of sparse SDPs.IFAC-PapersOnLine, 50(1):8411–8416, 2017. 60

    work page 2017