Pith. sign in

REVIEW 3 major objections 4 minor 12 references

The Augmented Mixing Method: Computing High-Accuracy Primal-Dual Solutions to Large-Scale SDPs via Column Updates

T0 review · 3 major / 4 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A block-coordinate SDP solver claims high accuracy past ten million constraints

desk verdict A practical high-accuracy SDP solver with strong empirical results and honest limitations; the heuristic penalty update and missing convergence theory are real but not disqualifying. read the letter →

arxiv 2507.20386 v2 pith:OJT3XBD2 submitted 2025-07-27 math.OC

Daniel Brosch , Jan Schwiddessen , Angelika Wiegele This is my paper · ORCID
classification math.OC MSC 90C2290C0690C26
keywords semidefiniteprogrammingBurer-MonteirofactorizationaugmentedLagrangianmethodblockcoordinatedescentcolumnupdateslarge-scaleoptimizationlow-rankmethodsprimal-dualaccuracy
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper introduces a semidefinite programming algorithm built on a low-rank factorization $X=V^\top V$, solving one column of $V$ at a time inside an inexact augmented Lagrangian loop. It is designed for SDPs with huge numbers of inequality constraints, which are handled directly rather than through slack variables. The authors' central claim is that this combination yields primal-dual solutions with errors usually below $10^{-9}$, and often near working precision, on instances where interior-point methods cannot run at all or run out of time. If true, practitioners get accurate certificates for large convex relaxations, not merely feasible points.

What carries the argument

The central object is the column update: with all columns of $V$ except $v_i$ fixed, the restricted augmented Lagrangian is minimized in $\mathbb{R}^k$ by a warm-started quasi-Newton method, stopping at criterion (10). The named innovation is the dynamic penalty-parameter rule: after each sweep, a ratio (12) compares the primal residual with the primal change, and $\mu$ is multiplied or divided by $\tau=1.03$ to keep the ratio inside $[0.8, 1.2]$. This mechanism is what lets the method refine dual variables instead of freezing them once primal feasibility is nearly reached.

What would settle it

Compute the cosine of the angle between $A(X_{\text{new}}-X_{\text{old}})$ and $A(X_{\text{new}})-a$ during later sweeps: if it is far from 1, the geometric-decay premise behind the ratio rule is violated. A direct experiment is the Section 4.5 two-block SDP started from $v_1=0$, $v_2=\sqrt{1.5}$, $y=(2,-2)^\top$, where the paper itself shows both column updates leave the point fixed, so no choice of $\mu$ can make progress; this refutes any claim of guaranteed progress on Slater-regular SDPs, and for the practical headline a single large-scale instance with more than ten million constraints that fails to reach $10^{-9}$ under default parameters would also falsify it.

Watch

Extended reading notes

Core claim

On its own terms, the paper claims that a solver alternating single-column updates of the low-rank factor $V$ with multiplier updates solves large-scale SDPs to high primal-dual accuracy. Inequality constraints enter through the augmented Lagrangian without slack variables, and the dynamic penalty update keeps the ratio of primal residual to primal change near 1, which under the paper's direct-movement assumption gives geometric decay of primal infeasibility by a factor $1-(\mu+1)^{-1}$. The numerical evidence spans Max-Cut triangle relaxations, stability-number bounds, facility-layout SDPs, edge-expansion bounds, and random SDPs, including instances with over ten million inequality constraints; most solved instances report errors below $10^{-9}$, and extended-precision runs reach $10^{-20}$. The paper states explicitly that no convergence guarantee is proved, and it exhibits a small Slater-regular SDP where the algorithm provably stagnates at a non-optimal first-order critical point.

Load-bearing premise

The dynamic penalty update assumes that, each sweep, the primal iterate moves directly toward feasibility, so the change $A(X_{\text{new}}-X_{\text{old}})$ is parallel to the residual $A(X_{\text{new}})-a$ (and likewise for $B$); if that geometric premise fails, the ratio-based balancing of $\mu$ does not guarantee progress.

Editorial extensions

If this is right

  • SDPs whose affine-constraint count dwarfs the matrix size, such as triangle-inequality-strengthened Max-Cut and facility-layout relaxations, can be solved to accuracies that standard first-order conic solvers do not reach.
  • The ratio-based penalty update removes most sensitivity to the initial choice of $\mu$, since the algorithm adjusts the penalty in both directions automatically.
  • The two-phase warm-starting strategy reaches relative accuracy near $10^{-20}$ on random SDPs, beyond the usual double-precision ceiling of interior-point methods.
  • Because per-column work is dominated by sparse matrix-vector products, the method carries over to arbitrary-precision arithmetic with predictable cost.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A consequence the paper leaves implicit is that the ratio rule could be transplanted into other low-rank augmented-Lagrangian solvers, since it is the component that makes the starting penalty unimportant; nothing in the paper limits it to this particular column-update scheme.
  • The slow-convergence example suggests a concrete diagnostic for users: monitor the cosine of the angle between $A(X_{\text{new}}-X_{\text{old}})$ and $A(X_{\text{new}})-a$; if it drifts away from 1, the geometric-decay premise fails and further increases of $\mu$ will only stall dual progress.
  • An active-set treatment of inequality constraints, which the paper names only as future work, would likely matter more for cutting-plane settings than for the all-at-once triangle relaxations tested here, because the method currently re-scans every inequality at each evaluation.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper introduces the Augmented Mixing Method, an SDP solver that combines a Burer–Monteiro factorization with an inexact augmented Lagrangian framework and block coordinate descent on individual columns of the factor matrix V. Inequality constraints are handled through Rockafellar's augmented Lagrangian without explicit slack variables, and a dynamic penalty parameter update based on a ratio of primal residual to primal change is proposed as the main algorithmic novelty. The method has no convergence guarantees; the authors explicitly exhibit a Slater-feasible SDP where the method stagnates at a non-optimal first-order critical point (Section 4.5, problem (18)) and another instance requiring over one million iterations for 10^-8 accuracy. Extensive numerical experiments on Max-Cut with triangle inequalities, stability-number relaxations, single-row facility layout, edge expansion, randomly generated SDPs, and extended-precision computations show that the method often achieves primal-dual errors below 10^-10 on large instances, frequently outperforming MOSEK, SCS, SDPLR, and Hypatia in accuracy and sometimes in runtime. The paper provides open-source Julia code, reports all four KKT errors, and is candid about its limitations.

Significance. If the empirical claims hold, the method is a practically valuable contribution, particularly for SDPs with very large numbers of inequality constraints, a regime in which interior-point methods scale poorly. The paper's strengths include reproducible open-source code, a broad benchmark suite covering several SDP classes, comprehensive reporting of all four KKT error metrics, honest disclosure of failure modes, and support for arbitrary-precision arithmetic. The principal weakness is that the central novel ingredient, the dynamic penalty update, is a heuristic whose failure modes are not quantified, and the claim of strong performance 'across a wide range of SDP instances' is broader than the tested classes, especially given the stagnation examples in Section 4.5 that are structurally relevant to moment-SOS relaxations.

major comments (3)
  1. [Section 3.4, Eqs. (12)-(13)] The dynamic penalty update is justified by the statement that 'the iterates move directly towards feasibility', meaning A(X_new - X_old) is a scalar multiple of A(X_new) - a and analogously for B. This assumption is not proved, and Section 4.5 shows it fails for the simple Slater-feasible SDP (18), where the column updates leave X unchanged and the ratio in (12) becomes degenerate. Because this update rule is the paper's main methodological novelty and is credited with enabling high-accuracy solutions, the authors should either state and verify sufficient conditions for the geometric-decay premise, add a safeguard for the degenerate-ratio case, or substantially qualify the rule's role.
  2. [Section 4.5 vs. abstract] The abstract claims strong practical performance with default parameters 'across a wide range of SDP instances', but Section 4.5 admits that the method provably stagnates on the 2-variable SDP (18) and that 'similar stagnation often occurs, though not always, when starting from random initializations' for problems whose objective depends only on a single 1x1 block, a structure the authors state is common in moment-SOS relaxations. No moment-SOS or polynomial-optimization instances appear in the Section 5 experiments, so the tested range does not cover a class for which the authors themselves report frequent failure. The 'wide range' claim should be either substantiated with experiments and failure-rate statistics on such instances or restricted to the tested problem classes.
  3. [Section 4.5, slow-convergence example] The paper reports that the slow-convergence SDP requires over one million iterations to reach 10^-8 accuracy and that the penalty update 'continues to increase the penalty parameter µ, even when such increases are no longer beneficial'. This demonstrates that update rule (13) does not reliably balance primal and dual progress in all cases, and the paper proposes no mechanism to detect this regime or stop the increase of µ. A quantitative study of when this behaviour occurs, for example as a function of the spectral properties of the constraint data, would clarify the practical limitations of the heuristic.
minor comments (4)
  1. [Section 5.1, Tables 2-10] Several rows report status 'tol' while the unscaled primal infeasibility is above the nominal tolerance (e.g., Table 2, g05_60.0: pinf = 1.5e-10). The text correctly explains that stopping is based on the internally scaled problem, but a footnote or column-header note would help readers avoid misinterpreting the tables as reporting scaled errors.
  2. [Section 4.5, problem (18)] The notation 'x2 =1' and 'v 2 2 =1' is rendered in a way that is easy to misread as multiplication; using explicit subscripts (e.g., x_2 = 1 and v_2^2 = 1) would improve clarity.
  3. [Sections 3.2 and 3.4] The index set I is used twice with different meanings: first for the gradient-active inequalities near Eq. (7), and later for the active set in the ratio definition (12). Renaming one of these sets would eliminate confusion.
  4. [Section 5.2] The sentence excluding MOSEK and SDPLR from the Max-Cut comparison says only that 'neither is suited to handle the very large number of inequalities'; a brief explanation, such as memory requirements or algorithmic limitations, would make the exclusion more transparent.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: algorithm evaluated on external benchmarks with fixed defaults and honest failure reporting.

full rationale

The paper's central claims are empirical: the Augmented Mixing Method computes high-accuracy primal-dual solutions on a range of SDP instances. There is no fitted parameter renamed as a prediction. The hyperparameters in Table 1 (mu_start, tau, rat_min, rat_max, delta, epsilon, tol) are fixed default values chosen before the experiments and are not re-fit to the reported benchmark outputs; the same defaults are used across all problem classes and are disclosed explicitly. The benchmark instances come from external public collections (Biq Mac, DIMACS, SRFLP libraries, network repositories) or are generated by standard random constructions, and the comparisons are against independent solvers (MOSEK, SCS, SDPLR, Hypatia) with errors computed on the original unscaled problems, so the reported accuracies are not forced by construction. The dynamic penalty update in Section 3.4 is a stated heuristic based on an explicit geometric-decay assumption; it is not derived from the target result and the paper openly documents instances where it fails (Section 4.5), which would be incompatible with a circularly enforced outcome. No load-bearing argument reduces to a self-citation: the cited theoretical results (Burer-Monteiro, Barvinok-Pataki bound, augmented Lagrangian theory) are standard external results, and the paper does not invoke any uniqueness theorem from the authors' own prior work to forbid alternative choices. The acknowledged lack of convergence guarantees and the reported stagnation examples are correctness/completeness limitations, not circularity. The derivation chain from problem reformulation to algorithm to benchmark results is self-contained: each numerical output is generated by the algorithm applied to an external input, not by definitional equivalence to an earlier fit. Accordingly, no circular step is present.

Assumptions & free parameters 6 free parameters · 5 assumptions · 0 invented entities

The central algorithmic claims rest on standard SDP assumptions and heuristic parameter choices. No new physical or mathematical entities are introduced.

free parameters (6)
  • epsilon = 0.01
    Absolute subproblem stopping tolerance in criterion (10).
  • delta = 0.01
    Relative subproblem stopping tolerance in criterion (10).
  • p = 1.0
    Dual update step size in (11).
  • tau = 1.03
    Multiplicative factor for penalty increase/decrease in (13).
  • rat_min, rat_max = 0.8, 1.2
    Lower and upper thresholds for the ratio-based penalty update in (13).
  • mu_start = sqrt(n)
    Initial penalty parameter set to the square root of the largest block size (Section 4.7).
assumptions (5)
  • domain assumption Constraint matrices are linearly independent
    Stated in Section 1 before the problem formulation.
  • domain assumption Primal and dual Slater's conditions hold
    Stated in Section 1 to ensure strong duality and attainment.
  • standard math Barvinok-Pataki bound: rank k = ceil(sqrt(2(ma+mb))) suffices for equivalence
    Used in equation (6) to choose the factorization rank; is a known theorem from the cited literature.
  • ad hoc to paper Primal iterates move directly toward feasibility so the ratio-based penalty update gives geometric decay
    Assumed in Section 3.4 to justify the dynamic penalty rule; not proven and contradicted by the stagnation example in Section 4.5.
  • domain assumption L-BFGS returns an approximate minimizer satisfying the stopping rule (10) for each column subproblem
    The subproblem solver in Section 3.3 is assumed to find adequate solutions despite nonconvexity; no global convergence is established.

how reviews work

0 comments
Cite this review

Pith. "Pith review of The Augmented Mixing Method: Computing High-Accuracy Primal-Dual Solutions to Large-Scale SDPs via Column Updates." pith.science (2026). https://pith.science/paper/OJT3XBD2

@misc{pith2026250720386,
  author       = {Pith},
  title        = {Pith review of: The Augmented Mixing Method: Computing High-Accuracy Primal-Dual Solutions to Large-Scale SDPs via Column Updates},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/OJT3XBD2}},
  note         = {Machine review of arXiv:2507.20386}
}
read the original abstract

The Burer-Monteiro factorization has become a powerful tool for solving large-scale semidefinite programs (SDPs), enabling recently developed low-rank solvers to tackle problems previously beyond reach. However, existing methods are typically designed to prioritize scalability over solution accuracy. We introduce the Augmented Mixing Method, a new algorithm that combines the Burer-Monteiro factorization with an inexact augmented Lagrangian framework and a block coordinate descent scheme. Our method emphasizes solving low-dimensional subproblems efficiently and to high precision. Inequality constraints are handled directly, without explicitly maintaining slack variables in the algorithm. A novel dynamic update strategy for the penalty parameter ensures that primal and dual feasibility progress remain balanced. This approach enables our method to compute highly accurate primal-dual solutions, even for large-scale SDPs with over ten million inequality constraints. Despite lacking theoretical convergence guarantees, the Augmented Mixing Method shows strong practical performance with default parameters across a wide range of SDP instances. It often produces more accurate primal-dual solutions than state-of-the-art interior-point methods and scales significantly better. Our open-source Julia implementation is memory-efficient, customizable, and supports arbitrary-precision arithmetic.

Figures

Figures reproduced from arXiv: 2507.20386 by the authors.

Figure 1
Figure 1. Performance profiles comparing the Augmented Mixing Method (with [PITH_FULL_IMAGE:figures/full_fig_p019_1.png] view at source ↗
Figure 2
Figure 2. Performance profiles comparing the Augmented Mixing Method (with [PITH_FULL_IMAGE:figures/full_fig_p019_2.png] view at source ↗
Figure 3
Figure 3. Performance profiles comparing the Augmented Mixing Method (with [PITH_FULL_IMAGE:figures/full_fig_p021_3.png] view at source ↗
Figures from the paper (3 more)
Figure 4
Figure 4. Figure 4: Performance profiles comparing the Augmented Mixing Method (with [PITH_FULL_IMAGE:figures/full_fig_p022_4.png]
Figure 5
Figure 5. Figure 5: Performance profiles comparing the Augmented Mixing Method (with [PITH_FULL_IMAGE:figures/full_fig_p022_5.png]
Figure 6
Figure 6. Figure 6: Performance profiles comparing the Augmented Mixing Method (with [PITH_FULL_IMAGE:figures/full_fig_p023_6.png]

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

12 extracted references · 7 canonical work pages

  1. [1]

    Aguirre, Diego Cifuentes, Vincent Guigues, Renato D

    [1]Jacob M. Aguirre, Diego Cifuentes, Vincent Guigues, Renato D. C. Monteiro, Victor Hugo Nasci- mento, and Arnesh Sujanani. cuHALLaR: a GPU accelerated low-rank augmented Lagrangian method for large-scale semidefinite programming. Preprint, arXiv:2505.13719[math.OC],

    arXiv

  2. [6]

    Connectivity via convexity: Bounds on the edge expansion in graphs

    [32]Timotej Hrga, Melanie Siebenhofer, and Angelika Wiegele. Connectivity via convexity: bounds on the edge expansion in graphs. Preprint, arXiv:2410.02526[math.OC],

    work page Pith review arXiv

  3. [10]

    Zico Kolter

    [60]Po-Wei Wang, Wei-Cheng Chang, and J. Zico Kolter. The mixing method: low-rank coordinate descent for semidefinite programming with diagonal constraints. Preprint, arXiv:1706.00476 [math.OC],

    arXiv

  4. [2003]

    28 Instancen m a mb Status Time[s]Itergap pinf dinf compl brock200_1 200 5067 0 tol 28.7 900 2.0e-13 1.5e-14 4.7e-11 4.4e-13 brock200_2 200 10025 0 tol 13.8 300 7.1e-14 3.3e-14 1.2e-11 5.5e-13 brock200_3 200 7853 0 tol 27.8 1250 2.8e-13 5.0e-14 1.5e-11 1.1e-12 brock200_4 200 6812 0 tol 21.0 500 8.2e-15 3.6e-15 1.3e-11 8.6e-14 brock400_1 400 20078 0 tol 17...

    work page 1991

  5. [2005]

    Burer-Monteiro ADMM for Large-scale SDPs

    [12]Yuwen Chen and Paul Goulart. Burer–Monteiro ADMM for large-scale SDPs. Preprint, arXiv:2302.04016[math.OC],

    work page Pith review arXiv

  6. [2006]

    [49]Michael J. D. Powell. A method for nonlinear constraints in minimization problems. InOpti- mization (Sympos., Univ. Keele, Keele, 1968), pages 283–298. Academic Press, London-New York,

    work page 1968

  7. [2013]

    Momentum-inspired Low-Rank Coordinate Descent for Diagonally Constrained SDPs

    [34]Junhyung Lyle Kim, Jose Antonio Lara Benitez, Mohammad Taha Toghani, Cameron Wolfe, Zhi- wei Zhang, and Anastasios Kyrillidis. Momentum-inspired low-rank coordinate descent for diag- onally constrained SDPs. Preprint, arXiv:2106.08775[math.OC],

    work page Pith review arXiv

  8. [2016]

    Leijenhorst, and Willem H

    25 [18]David de Laat, Nando M. Leijenhorst, and Willem H. H. de Muinck Keizer. Optimality and unique- ness of theD 4 root system. Preprint, arXiv:2404.18794[math.MG],

    arXiv

Show all 12 references
  1. [2017]

    [61]Yifei Wang, Kangkang Deng, Haoyang Liu, and Zaiwen Wen

    Version 4 (last revised 10 May 2026; first posted 1 Jun 2017). [61]Yifei Wang, Kangkang Deng, Haoyang Liu, and Zaiwen Wen. A decomposition augmented La- grangian method for low-rank semidefinite programming.SIAM J. Optim., 33(3):1361–1390,

    2026

  2. [2018]

    [39]Renato D. C. Monteiro, Arnesh Sujanani, and Diego Cifuentes. A low-rank augmented La- grangian method for large-scale semidefinite programming based on a hybrid convex-nonconvex approach. Preprint, arXiv:2401.12490[math.OC],

    arXiv

  3. [2022]

    On the Turing model complexity of interior point methods for semidefinite programming.SIAM J

    [17]Etienne de Klerk and Frank Vallentin. On the Turing model complexity of interior point methods for semidefinite programming.SIAM J. Optim., 26(3):1944–1961,

    1944

  4. [2025]

    Ac- celerating low-rank factorization-based semidefinite programming algorithms on GPU

    [28]Qiushi Han, Zhenwei Lin, Hanwen Liu, Caihua Chen, Qi Deng, Dongdong Ge, and Yinyu Ye. Ac- celerating low-rank factorization-based semidefinite programming algorithms on GPU. Preprint, arXiv:2407.15049[math.OC],

    arXiv

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.