Pith. sign in

REVIEW 3 major objections 5 minor 1 cited by

RiNNAL+: a Riemannian ALM Solver for SDP-RLT Relaxations of Mixed-Binary Quadratic Programs

T0 review · 3 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash

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

Pith's one-line read 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+…

desk verdict 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. read the letter →

arxiv 2507.13776 v1 pith:IOR4UNEE submitted 2025-07-18 math.OC

Di Hou , Tianyun Tang , Kim-Chuan Toh This is my paper · ORCID
classification math.OC MSC 90C2290C2090C2665K05
keywords mixed-binaryquadraticprogrammingdoublynonnegativerelaxationSDP-RLTRiemannianoptimizationaugmentedLagrangianmethodlow-ranksemidefinitereformulation-linearizationtechniquelarge-scaleSDP
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'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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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$.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

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

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 5 minor

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).

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 (3)
  1. [Section 4.2 (Lemma 4) and Section 5 (Implementation)] 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.
  2. [Section 3.1 (Algorithm 1) and Remark 6] 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.
  3. [Section 3.2 (low-rank phase)] 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.
minor comments (5)
  1. [Abstract] There is a typo in the abstract: 'tight lower bo und' should be 'tight lower bound'.
  2. [Sections 1.4 and 3.3] The abbreviation for the Newton method is inconsistent: Section 1.4 uses 'SNN' while Section 3.3 and later use 'SSN'. Please standardize.
  3. [Section 4.2] 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.
  4. [Section 5.3, Table 5] 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.
  5. [Section 5.7, Table 10] 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.

Circularity Check

1 steps flagged · score 4.0 of 10

Theorem 1 is self-contained, but Algorithm 1's convergence rests on a self-citation chain ([30],[37]) that does not cover the perturbed implementation.

  1. self citation load bearing [Section 3.1, paragraph after Algorithm 1; Remark 6; Section 4.2]
    "Algorithm 1 is a double-loop method, where the outer loop follows the same structure as the ALM in [30], with convergence analysis conducted under certain accuracy requirements for the subproblems. ... This method was originally introduced in [37] for low-rank matrix optimization and is accompanied by a detailed convergence analysis."

    The convergence of the solver actually run is the load-bearing premise for the n=5000 and speedup claims. This paper does not prove it; it cites [30], a preprint by the identical author set, for the ALM outer loop, and [37] (same research group) for the two-phase subproblem strategy. The implemented iteration then changes the problem: Section 4.2 replaces M_r by the randomly perturbed M_{r,v} with ||v||=epsilon and epsilon unspecified, and Remark 6 permits skipping the PG step. The cited analyses do not cover these changes, and no argument is given that limit points of the perturbed or skipped iteration satisfy the unperturbed KKT conditions (10). Hence the reported termination at R_max<1e-6 is supported by the self-citation chain rather than by a theorem in this paper.

full rationale

The central theoretical contribution—Theorem 1 (vSDP-RLT = vDNN) with Lemma 1's explicit bijection Phi—is self-contained: both directions are proven constructively and the objective identity <C',Phi(Y)>=<C,Y> is verified directly. This part does not reduce to its inputs, and no fitted parameters are involved. The numerical benchmarks are external (BIQ, theta+, QKP, ccMSSC, StQP, QMSTP) with SDPNAL+ as an independent baseline, so the speed comparisons are not circular. The circularity burden is confined to the solver-convergence claim: Algorithm 1's convergence is imported from [30] (identical author set) and [37] (same group), while the implemented algorithm includes a random perturbation to M_{r,v} with no epsilon schedule and permits skipping the PG step, so the cited theory does not cover the executed iteration. This is load-bearing for the n=5000 termination reports, but it does not touch the equivalence theorem. Score 4 reflects 'some self-citation; central claim still has independent content.'

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

The equivalence theorem is parameter-free and self-contained, so the theoretical core adds no free parameters or invented entities. The solver section, however, relies on hand-set hyperparameters (initial rank, penalty schedule, PG frequency, inner iteration caps, perturbation size) and imports its entire convergence argument from the authors' prior work [30, 37], with the DNN-COMP equality cited to [32]. No new physical or mathematical entities are postulated; the random perturbation v is a numerical device on an existing manifold, and it has no independent evidential handle.

free parameters (5)
  • initial rank r0 = min{200, ceil(n/5)}
    Hand-set in Section 5 (Implementation). Controls the starting dimension of the low-rank manifold and affects all reported timings, though the PG steps later modify the rank.
  • penalty schedule (sigma0, factor) = sigma0 = 1, changes by factor 1.5 based on Rp/Rd
    Hand-set ALM schedule in Section 5 (Implementation). Standard practice, but it undercuts the 'minimal tuning' framing.
  • PG step frequency = every 5 outer ALM iterations, or on singularity
    Remark 6. The implemented frequency differs from the analyzed 'one PG step per subproblem', and the frequency is a free schedule parameter.
  • random perturbation size epsilon = not specified ('a given small scalar')
    Section 4.2. The perturbation v with ||v|| = epsilon is used to ensure LICQ; no value or decay rule is stated, affecting both convergence guarantees and reproducibility.
  • inner RGD iteration cap = 50 per ALM iteration
    Section 5 (Implementation). Caps the low-rank phase effort and is part of the hand-tuned inner loop budget.
assumptions (5)
  • domain assumption Assumption 1: problem (P) admits an optimal solution satisfying the KKT conditions (10), and its objective is bounded below.
    Section 3, stated at the start of the algorithm section; underpins the ALM framework.
  • domain assumption For a generic perturbation v, every point of the manifold M_{r,v} satisfies LICQ.
    Section 4.2, Lemma 4 cited to [56, Theorem 4]; needed so projection and retraction in the low-rank phase are well defined.
  • standard math K = {Y in S^{n+1}_+ : <PP^T, Y> = 0} equals {[z x^T; x X] in S^{n+1}_+ : Ax = b, AX = bx^T}.
    Section 3.3, imported from [11, Theorem 1]; used to derive the projection dual problem (18).
  • domain assumption v_DNN = v_COMP for the strengthened MBQP (SMBQP-E).
    Theorem 2 relies on this equality, cited to [32], which includes the senior author; not proved in this paper.
  • ad hoc to paper Global convergence of the two-phase subproblem solver transfers from [30] and [37] to the (SDP-RLT) setting, even with the random perturbation.
    Section 3.1 and Remark 6 state convergence follows under subproblem accuracy requirements but give no proof; Section 4.2 alters the manifold to M_{r,v}.

how reviews work

0 comments
Cite this review

Pith. "Pith review of RiNNAL+: a Riemannian ALM Solver for SDP-RLT Relaxations of Mixed-Binary Quadratic Programs." pith.science (2026). https://pith.science/paper/IOR4UNEE

@misc{pith2026250713776,
  author       = {Pith},
  title        = {Pith review of: RiNNAL+: a Riemannian ALM Solver for SDP-RLT Relaxations of Mixed-Binary Quadratic Programs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/IOR4UNEE}},
  note         = {Machine review of arXiv:2507.13776}
}
abstract

Doubly nonnegative (DNN) relaxation usually provides a tight lower bound for a mixed-binary quadratic program (MBQP). However, solving DNN problems is challenging because: (1) the problem size is $\Omega((n+l)^2)$ for an MBQP with $n$ variables and $l$ inequality constraints, and (2) the rank of optimal solutions cannot be estimated a priori due to the absence of theoretical bounds. In this work, we propose RiNNAL+, a Riemannian augmented Lagrangian method (ALM) for solving DNN problems. We prove that the DNN relaxation of an MBQP, with matrix dimension $(n+l+1)$, is equivalent to the SDP-RLT relaxation (based on the reformulation-linearization technique) with a smaller matrix dimension $(n+1)$. In addition, we develop a hybrid method that alternates between two phases to solve the ALM subproblems. In phase one, we apply low-rank matrix factorization and random perturbation to transform the feasible region into a lower-dimensional manifold so that we can use the Riemannian gradient descent method. In phase two, we apply a single projected gradient step to update the rank of the underlying variable and escape from spurious local minima arising in the first phase if necessary. To reduce the computation cost of the projected gradient step, we develop pre-processing and warm-start techniques for acceleration. Unlike traditional rank-adaptive methods that require extensive parameter tuning, our hybrid method requires minimal tuning. Extensive experiments confirm the efficiency and robustness of RiNNAL+ in solving various classes of large-scale DNN problems.

Figures

Figures reproduced from arXiv: 2507.13776 by the authors.

Figure 1
Figure 1. Comparison of rank evolution between PG and tradit [PITH_FULL_IMAGE:figures/full_fig_p007_1.png] view at source ↗
Figure 2
Figure 2. Performance profile comparison for different formul [PITH_FULL_IMAGE:figures/full_fig_p028_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Convex relaxation approaches for high-dimensional optimal transport

    math.OC 2025-11 conditional novelty 6.0 of 10

    High-dimensional optimal transport cost can be approximated by semidefinite programs built from sparse local moments, with exponentially decaying error for Gaussian measures with sparse precision.

Reference graph

Works this paper leans on

64 extracted references · 53 canonical work pages · cited by 1 Pith paper

  1. [30]

    D. Hou, T. Tang, and K.-C. Toh. A low-rank augmented Lagr angian method for doubly nonnegative relaxations of mixed-binary quadratic programs. arXiv preprint arXiv:2502.13849, 2025

    work page Pith review arXiv 2025

  2. [37]

    C.-p. Lee, L. Liang, T. Tang, and K.-C. Toh. Acceleratin g nuclear-norm regularized low-rank matrix optimization through burer-monteiro deco mposition. Journal of Ma- chine Learning Research, 25(379):1–52, 2024

    work page 2024

  3. [1]

    Absil, R

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

    2009

  4. [2]

    K. M. Anstreicher. On convex relaxations for quadratica lly constrained quadratic programming. Mathematical Programming, 136(2):233–251, 2012

    work page 2012

  5. [3]

    Arima, S

    N. Arima, S. Kim, and M. Kojima. Exact SDP relaxations for a class of quadratic pro- grams with finite and infinite quadratic constraints. arXiv preprint arXiv:2409.07213 , 2024

    arXiv 2024

  6. [4]

    Assad and W

    A. Assad and W. Xu. The quadratic minimum spanning tree pr oblem. Naval Research Logistics (NRL), 39(3):399–417, 1992

    work page 1992

  7. [5]

    Atamturk, A

    A. Atamturk, A. G´ omez, and S. Han. Sparse and smooth sign al estimation: Con- vexification of l0-formulations. Journal of Machine Learning Research , 22(52):1–43, 2021

    work page 2021

  8. [6]

    X. Bao, N. V. Sahinidis, and M. Tawarmalani. Semidefinite relaxations for quadrat- ically constrained quadratic programming: A review and com parisons. Mathematical Programming, 129:129–157, 2011

    work page 2011

Show all 64 references
  1. [7]

    J. E. Beasley. Heuristic algorithms for the unconstrain ed binary quadratic program- ming problem. Technical report, Working Paper, The Managem ent School, Imperial College, London, England, 1998

    1998

  2. [8]

    S. J. Benson and Y. Ye. Algorithm 875: DSDP5—software for semidefinite program- ming. ACM Transactions on Mathematical Software (TOMS) , 34(3):1–20, 2008

    2008

  3. [9]

    Billionnet and ´E

    A. Billionnet and ´E. Soutif. An exact method based on Lagrangian decompositio n for the 0–1 quadratic knapsack problem. European Journal of Operational Research , 157(3):565–575, 2004

    2004

  4. [10]

    Bomze, B

    I. Bomze, B. Peng, Y. Qiu, and E. A. Yildirim. Tighter yet more tractable relaxations and nontrivial instance generation for sparse standard qua dratic optimization. arXiv preprint arXiv:2406.01239, 2024

    2024 arXiv

  5. [11]

    I. M. Bomze, J. Cheng, P. J. Dickinson, and A. Lisser. A fr esh CP look at mixed-binary QPs: new formulations and relaxations. Mathematical Programming, 166:159–184, 2017. 39

    2017

  6. [12]

    I. M. Bomze, J. Cheng, P. J. Dickinson, A. Lisser, and J. L iu. Notoriously hard (mixed-) binary QPs: empirical evidence on new completely positive a pproaches. Computational Management Science , 16:593–619, 2019

    2019

  7. [13]

    I. M. Bomze and E. De Klerk. Solving standard quadratic o ptimization problems via linear, semidefinite and copositive programming. Journal of Global Optimization , 24:163–185, 2002

    2002

  8. [14]

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

    2023

  9. [15]

    Buchheim and A

    C. Buchheim and A. Wiegele. Semidefinite relaxations fo r non-convex quadratic mixed- integer programming. Mathematical Programming, 141:435–452, 2013

    2013

  10. [16]

    Bundfuss and M

    S. Bundfuss and M. D¨ ur. An adaptive linear approximati on algorithm for copositive programs. SIAM Journal on Optimization , 20(1):30–53, 2009

    2009

  11. [17]

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

    2009

  12. [18]

    S. Burer. Optimizing a polyhedral-semidefinite relaxa tion of completely positive pro- grams. Mathematical Programming Computation, 2(1):1–19, 2010

    2010

  13. [19]

    Burer and Y

    S. Burer and Y. Ye. Exact semidefinite formulations for a class of (random and non- random) nonconvex quadratic programs. Mathematical Programming, 181(1):1–17, 2020

    2020

  14. [20]

    Caprara, D

    A. Caprara, D. Pisinger, and P. Toth. Exact solution of t he quadratic knapsack prob- lem. INFORMS Journal on Computing , 11(2):125–137, 1999

    1999

  15. [21]

    L. Chen, D. Sun, and K.-C. Toh. An efficient inexact symmet ric Gauss–Seidel based majorized ADMM for high-dimensional convex composite coni c programming. Math- ematical Programming, 161:237–270, 2017

    2017

  16. [22]

    de Meijer, M

    F. de Meijer, M. Siebenhofer, R. Sotirov, and A. Wiegele . Spanning and splitting: Integer semidefinite programming for the quadratic minimum spanning tree problem. arXiv preprint arXiv:2410.04997 , 2024

    2024

  17. [23]

    E. D. Dolan and J. J. Mor´ e. Benchmarking optimization s oftware with performance profiles. Mathematical Programming, 91(2):201–213, 2002

    2002

  18. [24]

    Gallo, P

    G. Gallo, P. L. Hammer, and B. Simeone. Quadratic knapsa ck problems. Combinatorial Optimization, pages 132–149, 1980

    1980

  19. [25]

    B. Gao, N. T. Son, P.-A. Absil, and T. Stykel. Riemannian optimization on the symplectic Stiefel manifold. SIAM Journal on Optimization , 31(2):1546–1575, 2021

    2021

  20. [26]

    M. X. Goemans and D. P. Williamson. Improved approximat ion algorithms for max- imum cut and satisfiability problems using semidefinite prog ramming. Journal of the ACM (JACM) , 42(6):1115–1145, 1995. 40

    1995

  21. [27]

    Gurobi Optimizer Reference Manual, 2023

    Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2023

    2023

  22. [28]

    Gusmeroli, T

    N. Gusmeroli, T. Hrga, B. Luˇ zar, J. Povh, M. Siebenhofe r, and A. Wiegele. BiqBin: a parallel branch-and-bound solver for binary quadratic pro blems with linear constraints. ACM Transactions on Mathematical Software (TOMS) , 48(2):1–31, 2022

    2022

  23. [29]

    M. R. Hestenes. Multiplier and gradient methods. Journal of Optimization Theory and Applications, 4(5):303–320, 1969

    1969

  24. [31]

    Iannazzo and M

    B. Iannazzo and M. Porcelli. The Riemannian Barzilai–B orwein method with non- monotone line search and the matrix geometric mean computat ion. IMA Journal of Numerical Analysis, 38(1):495–517, 2018

    2018

  25. [32]

    N. Ito, S. Kim, M. Kojima, A. Takeda, and K.-C. Toh. Equiv alences and differences in conic relaxations of combinatorial quadratic optimizatio n problems. Journal of Global Optimization, 72:619–653, 2018

    2018

  26. [33]

    S. Kim, M. Kojima, and K.-C. Toh. Doubly nonnegative rel axations for quadratic and polynomial optimization problems with binary and box co nstraints. Mathematical Programming, pages 1–27, 2022

    2022

  27. [34]

    Krislock, J

    N. Krislock, J. Malick, and F. Roupin. BiqCrunch: A semi definite branch-and-bound method for solving binary quadratic problems. ACM Transactions on Mathematical Software (TOMS) , 43(4):1–23, 2017

    2017

  28. [35]

    J. B. Kruskal. On the shortest spanning subtree of a grap h and the traveling salesman problem. Proceedings of the American Mathematical society , 7(1):48–50, 1956

    1956

  29. [36]

    E. L. Lawler and D. E. Wood. Branch-and-bound methods: A survey. Operations research, 14(4):699–719, 1966

    1966

  30. [38]

    Locatelli, V

    M. Locatelli, V. Piccialli, and A. M. Sudoso. Fix and bou nd: an efficient approach for solving large-scale quadratic programming problems with b ox constraints. Mathemat- ical Programming Computation, pages 1–33, 2024

    2024

  31. [39]

    J. E. Mitchell. Branch-and-cut algorithms for combina torial optimization problems. Handbook of applied optimization , 1(1):65–77, 2002

    2002

  32. [40]

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

    2024 arXiv

  33. [41]

    ¨Oncan and A

    T. ¨Oncan and A. P. Punnen. The quadratic minimum spanning tree p roblem: A lower bounding procedure and an efficient search algorithm. Computers & Operations Research, 37(10):1762–1773, 2010

    2010

  34. [42]

    M. Padberg. The boolean quadric polytope: some charact eristics, facets and relatives. Mathematical Programming, 45:139–172, 1989

    1989

  35. [43]

    Piccialli and A

    V. Piccialli and A. M. Sudoso. Global optimization for c ardinality-constrained mini- mum sum-of-squares clustering via semidefinite programmin g. Mathematical Program- ming, pages 1–35, 2023

    2023

  36. [44]

    Pisinger

    D. Pisinger. The quadratic knapsack problem—a survey. Discrete Applied Mathemat- ics, 155(5):623–648, 2007

    2007

  37. [45]

    M. J. Powell. A method for nonlinear constraints in mini mization problems. Opti- mization, pages 283–298, 1969

    1969

  38. [46]

    R. C. Prim. Shortest connection networks and some gener alizations. The Bell System Technical Journal, 36(6):1389–1401, 1957

    1957

  39. [47]

    Qi and D

    H. Qi and D. Sun. A quadratically convergent Newton meth od for computing the near- est correlation matrix. SIAM Journal on Matrix Analysis and Applications , 28(2):360– 385, 2006

    2006

  40. [48]

    Qiu and E

    Y. Qiu and E. A. Yıldırım. Polyhedral properties of RLT r elaxations of nonconvex quadratic programs and their implications on exact relaxat ions. Mathematical Pro- gramming, pages 1–37, 2024

    2024

  41. [49]

    Z. Qu, T. Zeng, and Y. Lou. Globally solving concave quad ratic program via doubly nonnegative relaxation. arXiv preprint arXiv:2302.05930 , 2023

    2023 arXiv

  42. [50]

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

    1976

  43. [51]

    H. D. Sherali. Rlt: A unified approach for discrete and co ntinuous nonconvex opti- mization. Annals of Operations Research , 149(1):185, 2007

    2007

  44. [52]

    H. D. Sherali and W. P. Adams. A reformulation-linearization technique for solving discrete and continuous nonconvex problems , volume 31. Springer Science & Business Media, 2013

    2013

  45. [53]

    N. Z. Shor. Dual quadratic estimates in polynomial and b oolean programming. Annals of Operations Research, 25, 1990

    1990

  46. [54]

    J. F. Sturm. Using SeDuMi 1.02, a toolbox for optimizati on over symmetric cones. Optimization Methods and Software , 11(1-4):625–653, 1999

    1999

  47. [55]

    Sun, K.-C

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

    2020

  48. [56]

    Tang and K.-C

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

    2024

  49. [57]

    Tang and K.-C

    T. Tang and K.-C. Toh. A feasible method for solving an SD P relaxation of the quadratic knapsack problem. Mathematics of Operations Research , 49(1):19–39, 2024

    2024

  50. [58]

    Tang and K.-C

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

    2024

  51. [59]

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

    1999

  52. [60]

    A. L. Wang and F. Kılın¸ c-Karzan. On the tightness of SDP relaxations of QCQPs. Mathematical Programming, 193(1):33–73, 2022

    2022

  53. [61]

    Wang and L

    J. Wang and L. Hu. Solving low-rank semidefinite program s via manifold optimization. arXiv preprint arXiv:2303.01722v1 , 2023

    2023 arXiv

  54. [62]

    Y. Wang, K. Deng, H. Liu, and Z. Wen. A decomposition augm ented Lagrangian method for low-rank semidefinite programming. SIAM Journal on Optimization , 33(3):1361–1390, 2023

    2023

  55. [63]

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

    2015

  56. [64]

    X.-Y. Zhao, D. Sun, and K.-C. Toh. A Newton-CG augmented Lagrangian method for semidefinite programming. SIAM J. Optimization , 20(4):1737–1765, 2010. A Experiments on BIQ problems Table 13: Computational results for (SDP-RLT) relaxation o f (BIQ-S) problems. Problem Algorithm ...

    2010

Pith tools

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