{"id":"3c607d02-c144-453b-9d1f-6643c572e43f","arxiv_id":"2507.13776","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"DNN and SDP-RLT relaxations of mixed-binary quadratic programs are proved to give identical bounds, and the new hybrid Riemannian solver RiNNAL+ solves the smaller SDP-RLT form at n = 5000, typically 10 to 100 times faster than SDPNAL+ where the latter converges.","lead":"The paper proves that two popular semidefinite relaxations of hard 0-1 quadratic programs, the doubly nonnegative (DNN) and SDP-RLT relaxations, always give the same lower bound, while one formulation is much smaller than the other.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Random perturbation of M_r to M_{r,v} with no ε schedule breaks the link between Algorithm 1's iterates and the unperturbed KKT system; reported R_max<1e-6 is not supported by the stated convergence arguments.","rationale":"The reader and I identify the same weakest point: convergence of the implemented, perturbed algorithm is load-bearing and unproven. I checked the equivalence theorem independently: Lemma 1's bijection, the objective identity, and the preprocessing identities are consistent, so the theory section is not the source of risk. The empirical headline, however, requires that RiNNAL+ actually produces KKT points of the unperturbed SDP-RLT. The random perturbation is not cosmetic: it changes the constraint set by a fixed amount ε/4 in the binary diagonal constraints, and without an annealing schedule or a proof that the PG step restores unperturbed optimality, the reported residuals cannot be justified. This is more concrete than a generic missing-proof objection because it identifies the exact mechanism by which the algorithm and the residual metric can disagree: iterates feasible for M_{r,v} can satisfy a small residual only for a different problem. The proposed test, fixing ε and measuring the unperturbed diagonal residual, would settle whether the method is actually solving (P) or a nearby perturbed problem. Other concerns raised by the reader, such as the absence of a RiNNAL baseline, unreproducible speedups, and no released code, are real but secondary; they affect the strength of the empirical comparison rather than the logical connection between the algorithm and the claimed KKT residuals. The verdict remains CONDITIONAL: the theoretical equivalence is sound, but the solver's convergence guarantee needs either a proof with ε → 0 or a reported schedule and numerical verification.","tokens_in":48632,"tokens_out":10853,"duration_ms":130254,"concrete_test":"Re-run the n = 500 BIQ instance from Table 5 with ε fixed at 1e-4, 1e-6, and 1e-8, and record the unperturbed diagonal residual ||diag_B(RR^T) − R_B e_1||_∞ at termination. If R_max < 1e-6 is reached while this residual scales as ε/4, the algorithm is solving the perturbed problem, not (P); if ε is annealed, log ε_k over all outer iterations and verify that the annealing schedule, not an undocumented reset, drives the diagonal residual to zero.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The single most load-bearing concern is that Algorithm 1's convergence to a KKT point of the unperturbed problem (P) is not established for the algorithm as actually implemented. Section 3.1 cites [30] and [37] for outer and subproblem convergence 'under certain accuracy requirements,' but Section 4.2 replaces M_r by M_{r,v} with ||v|| = ε, and no ε schedule, annealing rule, or proof that limit points satisfy the unperturbed KKT conditions is provided. The perturbation is not asymptotically harmless: expanding the perturbed constraint diag_B((2R−ee_1^T)(2R−ee_1^T)^T) = e + v gives diag_B(RR^T) = R_B e_1 + v/4, so any R ∈ M_{r,v} violates the F-constraint diag_B(X) = x_B by ε/4. If ε remains positive at termination, the reported primal residual R_p < 1e-6 is inconsistent; if ε is removed or annealed, the paper does not say when or how, and the cited convergence theory does not cover switching between perturbed and unperturbed manifolds. The low-rank phase can therefore converge to a stationary point of the wrong problem, and the single PG step in line 7 of Algorithm 1 has no proven mechanism to repair this. The equivalence theorem itself is independent and appears sound; the gap lies in the solver convergence that supports the n = 5000 and speedup claims.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies SDP relaxations of mixed-binary quadratic programs (MBQP). Its main theoretical result (Theorem 1, Section 2.2) proves that the DNN relaxation at matrix dimension (n+l+1) and the SDP-RLT relaxation at dimension (n+1) have the same optimal value, via the explicit bijection Phi in Lemma 1. The paper then proposes RiNNAL+, an augmented Lagrangian method with a hybrid two-phase subproblem solver: a low-rank Riemannian gradient descent phase on the manifold M_r, and a convex lifting phase consisting of one projected gradient step. Acceleration techniques include preprocessing, random perturbation of M_r, and a warm start for the semismooth Newton solver. Extensive experiments compare RiNNAL+ with SDPNAL+ on BIQ, maximum stable set, quadratic knapsack, clustering, sparse StQP, and QMSTP instances, reporting speedups and also some failures (esym QMSTP, sparse COP instances).","tokens_in":48867,"tokens_out":4805,"duration_ms":53144,"significance":"The equivalence in Theorem 1 is a clean, parameter-free result with a constructive proof, and it is valuable: it shows that slack variables are unnecessary for DNN bound quality and reduces the matrix dimension from (n+l+1) to (n+1). The numerical study is unusually broad, uses public datasets, and honestly reports cases where the proposed solver fails to reach the target accuracy. If the convergence claims for the implemented algorithm were fully supported, the reported scalability to n=5000 with short runtimes would make this a significant algorithmic contribution. The main weakness is that the global-convergence argument for the algorithm as actually implemented is not established, and the paper gives no schedule or analysis for the random perturbation that is central to the low-rank phase.","major_comments":[{"comment":"The random perturbation of M_r to M_{r,v} with ||v||=epsilon is never accompanied by a value, a schedule, or a proof that limit points of the perturbed iteration satisfy the KKT conditions of the unperturbed problem (P). Expanding the perturbed constraint diag_B((2R-ee_1^T)(2R-ee_1^T)^T)=e+v gives diag_B(RR^T)=R_B e_1+v/4, so every R in M_{r,v} violates the F-constraint diag_B(X)=x_B by v/4. If epsilon remains positive at termination, the reported primal residuals R_p<1e-6 in Tables 5-9 are not supported; if epsilon is annealed to zero, the convergence theory cited in Section 3.1 does not cover switching between perturbed and unperturbed manifolds. The paper must either specify the epsilon schedule and prove convergence of the perturbed algorithm to a KKT point of (P), or substantially weaken the convergence claims.","section":"Section 4.2 (Lemma 4) and Section 5 (Implementation)"},{"comment":"The statement in Section 3.1 that convergence is inherited from [30] and [37] 'under certain accuracy requirements' is not matched to the implemented algorithm. Algorithm 1 as written applies the projected gradient step at line 7 in every inner iteration, whereas Remark 6 states that in practice the PG step is performed only at every 5 outer ALM iterations or when singularity issues occur. The 3 PG steps for 16 outer iterations in Table 5 are therefore incompatible with the displayed algorithm. No argument is given that skipping the convex lifting step preserves the global-convergence property or the rank-update safeguard of the hybrid method from [37]. Please provide either a proof for the implemented schedule or an algorithm description that matches it.","section":"Section 3.1 (Algorithm 1) and Remark 6"},{"comment":"The convergence of the Riemannian gradient descent inner loop on the nonconvex manifold M_r is asserted only by reference to [30] and the PG step, but the paper does not specify the required accuracy of the inner solve or how the switch between the low-rank phase and the convex lifting phase is controlled. Since the reported iteration counts for the BIQ problems show that the inner loop runs for hundreds of RGD iterations with only a handful of PG steps, the numerical behavior rests on properties of the low-rank phase that are not covered by any theorem in the paper. Please state the inner-loop accuracy criterion and prove that the resulting two-phase subproblem solver satisfies the accuracy requirements of the ALM outer loop.","section":"Section 3.2 (low-rank phase)"}],"minor_comments":[{"comment":"There is a typo in the abstract: 'tight lower bo und' should be 'tight lower bound'.","section":"Abstract"},{"comment":"The abbreviation for the Newton method is inconsistent: Section 1.4 uses 'SNN' while Section 3.3 and later use 'SSN'. Please standardize.","section":"Sections 1.4 and 3.3"},{"comment":"The perturbation size epsilon is described only as 'a given small scalar'; the experiments section never reports its value. Please report the value or the rule used to select it, since the numerical results depend on it.","section":"Section 4.2"},{"comment":"The text describes the n=5000 BIQ result as 'about 18 minutes'; the reported time is 1103.1 seconds, which is indeed about 18.4 minutes, but the wording is slightly loose and could be made exact.","section":"Section 5.3, Table 5"},{"comment":"For the COP instance with n=1000, RiNNAL+ reports Rmax=1.20e-04, which is above the stated tolerance, and its objective value differs substantially from SDPNAL+'s value. The text already excludes this instance from the 'consistently outperforms' claim, but the discrepancy should be explained more explicitly because it illustrates the high-rank failure mode of the method.","section":"Section 5.7, Table 10"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The result worth knowing: Theorem 1 is a clean, general equivalence between the SDP-RLT relaxation at matrix dimension (n+1) and the DNN relaxation at dimension (n+l+1) for mixed-binary quadratic programs with linear equalities and inequalities. The proof is constructive and self-contained. I checked the bijection Phi and the objective identity; they hold. This is a real generalization of earlier box-constrained results and a useful practical point: slack variables do not improve the bound. Credit where it is earned.\n\nThe solver story is shakier. The implemented algorithm perturbs the low-rank manifold M_r to M_{r,v} with ||v|| = epsilon to avoid nonsmoothness, but no schedule or value for epsilon is given, and the convergence analysis is imported from prior papers for the unperturbed problem. The stress-test algebra is correct: any R in M_{r,v} violates the original constraint diag_B(X) = x_B by epsilon/4. If epsilon stays positive at termination, the reported primal residuals below 1e-6 are inconsistent. If epsilon is annealed, the paper does not say when or how, and the cited convergence theory does not cover switching between perturbed and unperturbed manifolds. This is a genuine gap, not a nitpick.\n\nThe empirical claims also overreach. RiNNAL, the direct predecessor, is never benchmarked. Headline speedups of 180x, 350x, and 400x do not match the paper's own tables: the n=500 BIQ row gives 613s/8s, about 77x, and the other figures count time-limit failures of SDPNAL+ as completions. The sparse StQP tables show objective differences between solvers both reporting R_max below 1e-6; the paper honestly notes the objective only stabilizes below 1e-8, but that means the stopping criterion is not sufficient for those instances. No code is released.\n\nThat said, the paper does many things well. The experimental campaign is extensive, uses public datasets, and reports failures like the esym QMSTP instances. The preprocessing and warm-start techniques look practical and well-motivated. The random perturbation idea is sensible but needs a proof that limit points satisfy the unperturbed KKT conditions.\n\nWho is this paper for? Researchers working on SDP relaxations for discrete quadratic optimization. The equivalence theorem is a useful tool on its own and deserves to be in the literature. The solver needs a serious revision of the convergence section and a re-audited timing table before the performance narrative can be trusted.\n\nRecommendation: send it to peer review. The theory justifies that on its own. The referee should push hard on the epsilon perturbation and require reproducible timing comparisons, including a benchmark against RiNNAL.","headline":"Solid equivalence theorem for SDP-RLT vs DNN relaxations, but the solver's convergence theory has a real gap around random perturbation, and several headline speedups do not survive contact with the tables.","tokens_in":49523,"tokens_out":2011,"would_cite":true,"duration_ms":25160,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C22","90C20","90C26","65K05"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that the SDP-RLT relaxation of a mixed-binary quadratic program attains exactly the same lower bound as the much larger doubly nonnegative relaxation, and introduces a Riemannian augmented Lagrangian solver, RiNNAL+…","keywords":["mixed-binary quadratic programming","doubly nonnegative relaxation","SDP-RLT relaxation","Riemannian optimization","augmented Lagrangian method","low-rank semidefinite programming","reformulation-linearization technique","large-scale SDP"],"falsifier":"Two concrete tests appear in the paper's own tables: run RiNNAL+ on the OP esym quadratic-minimum-spanning-tree instances with $n = 435$ or on the COP sparse standard-quadratic-programming instance with $n = 1000$; in both reported runs RiNNAL+ hit the one-hour limit without reaching the $10^{-6}$ relative KKT residual, while SDPNAL+ converged. For the equivalence theorem itself, solve the SDP-RLT and DNN relaxations of a randomly generated MBQP with many inequalities to high precision and check that $v_{\\mathrm{SDP\\text{-}RLT}} = v_{\\mathrm{DNN}}$ numerically.","tokens_in":48289,"feed_emoji":"🧮","tokens_out":5949,"duration_ms":62117,"temperature":0.7,"pith_summary":"The paper's theoretical claim is that, for any mixed-binary quadratic program, solving the SDP-RLT relaxation at matrix dimension $(n+1)$ gives exactly the same lower bound as the doubly nonnegative (DNN) relaxation at dimension $(n+l+1)$, where $l$ is the number of inequality constraints. The practical consequence is that the slack variables used to build DNN relaxations are unnecessary: a smaller problem produces the same bound. The paper's algorithmic claim is that its new solver, RiNNAL+, solves these relaxations to a relative KKT residual below $10^{-6}$ at $n = 5000$ in roughly 18 minutes for binary quadratic problems, and is 10 to 400 times faster than SDPNAL+ on most tested problem classes. The method alternates a low-rank Riemannian gradient descent phase with occasional single projected gradient steps that adjust the rank automatically, avoiding the careful rank-tuning that earlier low-rank SDP solvers required.","feed_headline":"SDP-RLT matches DNN bounds with a smaller matrix","feed_subtitle":"New proof cuts the relaxation dimension and the RiNNAL+ solver reaches n = 5000 in about 18 minutes.","key_machinery":"The load-bearing object for the equivalence is the linear map $\\Phi$ of equation (6), which sends a matrix $Y$ to its slack-space image via multiplication by the block matrix $[1\\;0;\\;0\\;I_n;\\;d\\;-G]$, establishing the bijection between the two feasible regions. The load-bearing object for the algorithm is the low-rank manifold $\\mathcal{M}_r = \\{R \\in \\mathbb{R}^{n\\times r} : AR = be_1^\\top,\\; \\operatorname{diag}_B(RR^\\top) = R_B e_1\\}$, on which Riemannian gradient descent solves the ALM subproblem; a single projected gradient step on the convex subproblem (CVX) then automatically adjusts the rank. A random perturbation of the spherical constraints, with $\\|v\\| = \\varepsilon$, keeps the manifold smooth when the linear independence constraint qualification fails. The preprocessing change of variables $K = [1\\; e^\\top/2;\\; 0\\; I_n/2]$ recasts diagonal constraints into a max-cut-like structure, and the warm-start technique recovers dual variables from the low-rank phase to accelerate the semismooth Newton solver for the projection step.","core_discovery":"Theorem 1 characterizes the two feasible sets explicitly: the linear map $\\Phi$ defined in equation (6), which embeds an $(n+1)$-by-$(n+1)$ matrix into the slack space of dimension $n+l+1$, is a bijection between the feasible regions of (SDP-RLT) and (DNN) and preserves objective values, so $v_{\\mathrm{SHOR}} \\le v_{\\mathrm{DNN}} = v_{\\mathrm{SDP\\text{-}RLT}} \\le v_{P_1} = v_{P_2}$ holds for every instance. The paper then claims that RiNNAL+ solves the (SDP-RLT) relaxation at dimension $n = 5000$ to a relative KKT residual below $10^{-6}$ in about 18 minutes on binary quadratic problems, and that across the tested problem classes it is 10 to 400 times faster than SDPNAL+, including on maximum-stable-set and QMSTP instances whose optimal solution rank is near $n/3$ or $n/2$.","pith_inferences":["If the equivalence sketched for general QCQP with quadratic constraints in Remark 1 holds, then the $(n+1)$-dimensional relaxation replaces a much larger DNN whenever many quadratic constraints are present, widening every factor in the size comparison.","The preprocessing change of variables is a standalone subroutine: any SDP solver handling constraints of the form $\\operatorname{diag}(X) = x$, $z = 1$ could absorb it, based on the reported reduction in total time from 36 seconds to 5 seconds and the large drop in SSN and PCG iterations.","The perturbation size $\\varepsilon$ in the random perturbation technique is never specified or annealed, so a natural test is whether the solver's robustness depends on its schedule and whether limit points of the perturbed iterates satisfy the unperturbed KKT system, since that is currently unproven.","The paper announces as future work the use of RiNNAL+ inside branch-and-bound; its speed is the missing piece that would make the tight SDP-RLT bound affordable as a node relaxation."],"forward_implications":["For any mixed-binary quadratic program, the DNN bound is available without introducing slack variables: solving the $(n+1)$-dimensional SDP-RLT relaxation replaces the $(n+l+1)$-dimensional DNN problem, and the saving grows with the number of inequality constraints.","RiNNAL+ reaches problems with $n = 5000$ in about 18 minutes (BIQ-S) and about 30 minutes (QKP-S), where SDPNAL+ times out at one hour even for $n = 1000$ on most tested classes.","The single projected gradient step in the convex lifting phase identifies the correct rank after few steps and replaces hand-tuned rank schedules, which the paper identifies as a major practical obstacle in earlier low-rank solvers.","The method remains fast when optimal solution rank is high: speedups near $100\\times$ persist on maximum-stable-set instances with rank near $n/3$ and on QMSTP instances with rank near $n/2$.","The SDP-RLT relaxation of the QMSTP problem is strictly tighter than the partial RLT-type DNN relaxations previously proposed for that problem."],"supporting_citations":[{"why":"Supplies the low-rank manifold $\\mathcal{M}_r$, the Riemannian gradient descent machinery, and the ALM outer-loop convergence that RiNNAL+ inherits.","marker":"[30]"},{"why":"Introduces the two-phase hybrid strategy of a low-rank phase followed by one projected gradient step, whose convergence analysis Algorithm 1 relies on.","marker":"[37]"},{"why":"Provides the random perturbation lemma used as Lemma 4 to guarantee generic smoothness of the perturbed manifold $\\mathcal{M}_{r,v}$.","marker":"[56]"},{"why":"Defines the particular DNN formulation chosen for its sparsity structure and smallest duality gap, and the characterization of the set $\\mathcal{K}$ used in the projection.","marker":"[11]"},{"why":"The reformulation-linearization technique that generates the quadratic constraints defining the SDP-RLT relaxation.","marker":"[51]"},{"why":"Establishes the redundancy of the constraint $zd - Gx \\ge 0$ and earlier box-constrained equivalence results that Theorem 1 generalizes.","marker":"[52]"},{"why":"SDPNAL+, the baseline solver against which all numerical comparisons are run.","marker":"[63]"},{"why":"The PRSM solver and the DNN-type relaxations for the quadratic minimum spanning tree problem that the paper's SDP-RLT relaxation is shown to dominate.","marker":"[22]"}],"fun_headline_variants":["SDP-RLT equals DNN bounds at smaller matrix size","RiNNAL+ solver is 10-400x faster than SDPNAL+","Proven equivalence shrinks DNN relaxation to SDP-RLT","Hybrid method solves DNN relaxation at n=5000 in 18min"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The paper's convergence guarantee is inherited from an unperturbed two-phase method under accuracy requirements, but the implemented algorithm actually runs on randomly perturbed manifolds $\\mathcal{M}_{r,v}$ with an unspecified perturbation size $\\varepsilon$, and no proof shows that the limit point satisfies the KKT conditions of the original problem.","fun_headline_variants_meta":{"raw":{"variants":["SDP-RLT equals DNN bounds at smaller matrix size","RiNNAL+ solver is 10-400x faster than SDPNAL+","Proven equivalence shrinks DNN relaxation to SDP-RLT","Hybrid method solves DNN relaxation at n=5000 in 18min"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000556,"raw_usage":{"total_tokens":2709,"prompt_tokens":1070,"completion_tokens":1639,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":686,"completion_tokens_details":{"reasoning_tokens":1558}},"tokens_in":686,"tokens_out":1639,"duration_ms":12755,"temperature":1.0,"reasoning_tokens":1558,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T16:21:26.707195+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Two concrete tests appear in the paper's own tables: run RiNNAL+ on the OP esym quadratic-minimum-spanning-tree instances with $n = 435$ or on the COP sparse standard-quadratic-programming instance with $n = 1000$; in both reported runs RiNNAL+ hit the one-hour limit without reaching the $10^{-6}$ relative KKT residual, while SDPNAL+ converged. For the equivalence theorem itself, solve the SDP-RLT and DNN relaxations of a randomly generated MBQP with many inequalities to high precision and check that $v_{\\mathrm{SDP\\text{-}RLT}} = v_{\\mathrm{DNN}}$ numerically.","supporting_citations":[{"cited_title":"A low-rank augmented Lagrangian method for doubly nonnegative relaxations of mixed-binary quadratic programs","cited_arxiv_id":"2502.13849","evidence_quote":"Supplies the low-rank manifold $\\mathcal{M}_r$, the Riemannian gradient descent machinery, and the ALM outer-loop convergence that RiNNAL+ inherits."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces the two-phase hybrid strategy of a low-rank phase followed by one projected gradient step, whose convergence analysis Algorithm 1 relies on."},{"cited_title":"Tang and K.-C","cited_arxiv_id":null,"evidence_quote":"Provides the random perturbation lemma used as Lemma 4 to guarantee generic smoothness of the perturbed manifold $\\mathcal{M}_{r,v}$."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the particular DNN formulation chosen for its sparsity structure and smallest duality gap, and the characterization of the set $\\mathcal{K}$ used in the projection."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The reformulation-linearization technique that generates the quadratic constraints defining the SDP-RLT relaxation."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes the redundancy of the constraint $zd - Gx \\ge 0$ and earlier box-constrained equivalence results that Theorem 1 generalizes."},{"cited_title":"de Meijer, M","cited_arxiv_id":null,"evidence_quote":"The PRSM solver and the DNN-type relaxations for the quadratic minimum spanning tree problem that the paper's SDP-RLT relaxation is shown to dominate."}],"review_version":1}