{"id":"5e0ed7ee-0ebc-4d78-a1f8-c6ca33929e52","arxiv_id":"2507.20386","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":6,"one_line_summary":"The Augmented Mixing Method computes high-accuracy primal-dual solutions to large-scale SDPs via Burer-Monteiro factorization, inexact augmented Lagrangian, and block coordinate descent.","lead":"This paper presents a new algorithm that solves large-scale semidefinite programs by combining low-rank factorization with an augmented Lagrangian method and column-by-column updates. The method reports high-accuracy primal-dual solutions on problems with up to ten million inequality constraints, often beating interior-point solvers in accuracy.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The penalty-ratio heuristic is unproven and provably stalls on simple Slater SDPs; the 'wide range' claim needs a quantified failure-rate study.","rationale":"The reader identified the dynamic penalty update and its unproven geometric-decay assumption as the weakest point, and Section 4.5 confirms that this assumption can fail catastrophically even for Slater-feasible SDPs. My reading agrees: the paper's contribution is empirical, and the evidence is substantial and reproducible, but the absence of convergence guarantees plus a documented stagnation example means the central 'wide range' claim is conditional on how often such stagnation occurs. The proposed failure-rate study would settle whether the known pathologies are rare enough to preserve the practical claim. Since the reader already assigned CONDITIONAL, no verdict change is needed.","tokens_in":40842,"tokens_out":6638,"duration_ms":81615,"concrete_test":"Using the released AugmentedMixing.jl package, generate 100 random SDPs from the Section 5.6 generator but with C supported only on one 1x1 diagonal block (the structure Section 4.5 identifies as stagnation-prone), with Slater's condition ensured. Run each with default parameters and tol=1e-12, and count the fraction that reach the tolerance versus those that stall with max primal-dual error above 1e-6. Also rerun pw09_80 from Table 2 from 10 random seeds. If a large fraction of these instances fails, the claim of robust performance across a wide range of SDPs is not supported; if nearly all succeed, the Section 4.5 failure is an isolated pathology.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central empirical claim—default parameters solve a wide range of SDPs to high accuracy—depends on the dynamic penalty update in Section 3.4. The update (13) keeps ratio (12) near 1, motivated by the assumption that 'the iterates move directly towards feasibility', i.e., 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 explicitly exhibits a Slater-feasible SDP where it fails: the two-block example (18) has column updates that leave V unchanged, so X_new=X_old, the ratio in (12) is degenerate, and the authors show no update rule for µ can force progress. The same section reports a second SDP requiring over one million iterations for 10^-8 accuracy, with µ increasing even when it stops helping. Thus the method provably has non-optimal first-order critical points and can stagnate. The paper is honest about this, but it never quantifies how often such stagnation occurs. Since the pathological structure singled out in Section 4.5 (objective supported on a single 1x1 block, common in moment-SOS relaxations) is absent from most benchmark tables, the 'wide range of SDP instances' assertion is broader than the evidence.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":41221,"tokens_out":7054,"duration_ms":75121,"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":[{"comment":"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.","section":"Section 3.4, Eqs. (12)-(13)"},{"comment":"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.","section":"Section 4.5 vs. abstract"},{"comment":"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.","section":"Section 4.5, slow-convergence example"}],"minor_comments":[{"comment":"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.","section":"Section 5.1, Tables 2-10"},{"comment":"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.","section":"Section 4.5, problem (18)"},{"comment":"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.","section":"Sections 3.2 and 3.4"},{"comment":"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.","section":"Section 5.2"}],"recommendation":"major_revision","confidential_remarks":"The paper is honest and the numerical study is extensive. The main risk is overclaiming robustness: the failure modes in Section 4.5 are structurally relevant to moment-SOS relaxations, a major application area that is absent from the benchmarks. I would ask the authors to either add experiments on such instances with reported failure rates, or soften the 'wide range' claim. The dynamic penalty update is heuristic, but the paper already disclaims convergence theory; however, the degenerate-ratio case should be handled explicitly. No novelty-disclosure issues were identified."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The headline: this is a genuine algorithmic contribution, not a theoretical one. The Augmented Mixing Method combines Burer–Monteiro factorization, an inexact augmented Lagrangian, and column-wise block coordinate descent in a way I have not seen before, and the dynamic penalty update in Section 3.4 is a specific heuristic aimed at balancing primal and dual progress. What earns the paper its keep is the experimental section: a broad set of SDP classes, all four KKT errors reported, comparisons against MOSEK, SCS, SDPLR, and Hypatia, and a clear demonstration that the method often reaches 1e-10 or better on problems with millions of inequality constraints. The Julia code and data are on Zenodo, which makes the reproducibility a real asset.\n\nThe authors are also honest about the method's limits. Section 4.5 gives a simple Slater-feasible example with a 1x1 block where the algorithm provably stagnates at a non-optimal first-order critical point, and another instance that takes over a million iterations. That is a load-bearing caveat: the penalty update in (13) rests on the unproven assumption that iterates move directly toward feasibility, and the paper does not quantify how often stagnation occurs. The stress-test note is right that the pathological structure is not represented in the benchmark tables, even though it is common in moment-SOS relaxations. So the 'wide range of instances' claim is broader than the evidence, and a failure-rate analysis over a more representative class would materially strengthen the paper.\n\nThat said, I do not think these issues undermine the main empirical claim. On the tested problem classes—max-cut with triangle inequalities, DNN relaxations, SRFLP, edge expansion, random SDPs—the method consistently delivers high accuracy, often competitive with or better than MOSEK in runtime when the constraint count is large. The absence of convergence guarantees is fully disclosed, and the paper explicitly points to future work on that front. The gradient and augmented Lagrangian derivations are standard and check out.\n\nMy verdict: send to peer review, with a request for careful revision that quantifies failure rates and gives some sensitivity analysis for the penalty parameters. The paper deserves serious referee time; a good referee will push on the heuristic but should not reject a well-executed practical contribution just because it is not a theorem-proving paper.\n\nWould I bring it to reading group? Maybe—the algorithm is interesting, but the paper is long and the value is mostly in the experiments.","headline":"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.","tokens_in":41600,"tokens_out":2263,"would_cite":true,"duration_ms":23856,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C22","90C06","90C26"],"pacs":[],"model":"deepseek-v4-flash","headline":"A block-coordinate SDP solver claims high accuracy past ten million constraints","keywords":["semidefinite programming","Burer-Monteiro factorization","augmented Lagrangian method","block coordinate descent","column updates","large-scale optimization","low-rank methods","primal-dual accuracy"],"falsifier":"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.","tokens_in":40630,"feed_emoji":"🎯","tokens_out":7633,"duration_ms":73572,"temperature":0.7,"pith_summary":"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.","feed_headline":"SDP solver hits high accuracy past ten million constraints","feed_subtitle":"Column-by-column updates keep large semidefinite programs precise enough to rival interior-point methods.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Introduces the low-rank factorization $X=V^\\top V$ that the whole algorithm is built on.","marker":"[10, 11]"},{"why":"Supplies the mixing-method idea of updating one column of $V$ at a time, extended here to general affine constraints.","marker":"[60]"},{"why":"Gives the rank bound $k=\\min\\{n,\\lceil\\sqrt{2(m_a+m_b)}\\rceil\\}$ used to fix the factorization rank.","marker":"[5, 46]"},{"why":"Provides the augmented-Lagrangian treatment of inequality constraints that lets the method avoid explicit slack variables.","marker":"[51]"},{"why":"Supplies the classical multiplier-update framework that the dual and penalty updates extend.","marker":"[30, 49]"}],"fun_headline_variants":["SDP solver skips slacks, hits 1e-9 errors","No convergence proof, yet 1e-9 accuracy on huge SDPs","Column updates solve SDPs with 10M constraints precisely","Balanced penalty, no slacks: SDP accuracy without proof","Primal-dual precision rivals interior-point, scales better"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["SDP solver skips slacks, hits 1e-9 errors","No convergence proof, yet 1e-9 accuracy on huge SDPs","Column updates solve SDPs with 10M constraints precisely","Balanced penalty, no slacks: SDP accuracy without proof","Primal-dual precision rivals interior-point, scales better"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000195,"raw_usage":{"total_tokens":1360,"prompt_tokens":952,"completion_tokens":408,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":568,"completion_tokens_details":{"reasoning_tokens":315}},"tokens_in":568,"tokens_out":408,"duration_ms":4552,"temperature":1.0,"reasoning_tokens":315,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T17:43:18.085848+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":2}