Pith. sign in

REVIEW 2 minor 33 references

Sparsity-Cone SDP Relaxations and Applications to Variable Fixing for Sparse Quadratic Programs

T0 review · 0 major / 2 minor · reviewed 2026-06-26 · grok-4.3

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

Pith's one-line read The sparsity-cone SDP relaxation equals SDP-RLT in strength for sparse quadratic programs but uses only an (n+1)-dimensional matrix.

desk verdict SC-SDP matches SDP-RLT strength with a smaller matrix plus one cone constraint, plus dual presolving rules that look practical. read the letter →

arxiv 2606.22894 v1 pith:KL32Q235 submitted 2026-06-22 math.OC

Di Hou , Thai P.D. Nguyen , Kim-Chuan Toh , Guanyi Wang This is my paper · ORCID
classification math.OC
keywords sparsequadraticprogramssemidefiniteprogrammingrelaxationsparsityconevariablefixingpresolvingaugmentedLagrangianmethod
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 sparsity-cone semidefinite programming relaxation for quadratic programs with an l0-norm constraint on the decision variables. It proves that this SC-SDP formulation delivers the same relaxation strength as the standard SDP-RLT approach. SC-SDP replaces the usual (2n+1)-dimensional matrix with a smaller (n+1)-dimensional matrix plus one sparsity-cone constraint. The authors characterize the cone, show that projection onto it reduces to a one-dimensional subproblem, and extract dual-based presolving rules for variable fixing and support screening. They also give a Riemannian augmented Lagrangian solver that exploits the structure for faster computation on sparse QPs.

What carries the argument

The sparsity cone K that relaxes the l0-norm constraint inside the (n+1)-dimensional lifted space.

What would settle it

A concrete sparse quadratic program instance on which the optimal value of the SC-SDP relaxation is strictly weaker than the optimal value of the SDP-RLT relaxation.

Watch

Extended reading notes

Core claim

The central claim is that the SC-SDP relaxation, which employs an (n+1)-dimensional semidefinite matrix together with a single sparsity-cone constraint K to handle the l0-norm, is equivalent in strength to the SDP-RLT relaxation. The paper derives structural properties of K that permit efficient projection and uses the dual of SC-SDP to obtain explicit presolving mechanisms, including a dual-fixing rule for individual variables and a screening-cut rule for excluding larger support patterns.

Load-bearing premise

Projection onto the sparsity cone K can be computed efficiently via a one-dimensional subproblem.

Editorial extensions

If this is right

  • SC-SDP can replace SDP-RLT without loss of bound quality on sparse QPs.
  • Efficient projection onto K enables first-order and augmented Lagrangian solvers.
  • Dual information directly yields variable-fixing and support-screening rules that reduce problem size before optimization.
  • The two-phase Riemannian method solves the relaxation faster than standard interior-point methods on the tested instances.

Reading between the lines

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

  • The smaller matrix dimension may allow SC-SDP to handle larger n than SDP-RLT before memory or time limits are reached.
  • The derived presolving rules could be embedded inside branch-and-bound frameworks for global solution of sparse QPs.
  • Closed-form solutions for the one-dimensional projection subproblem might exist for special sparsity patterns.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

0 major / 2 minor

Summary. The paper proposes a sparsity-cone SDP (SC-SDP) relaxation for sparse indefinite quadratic programs. It replaces the standard SDP-RLT lifting (a (2n+1)-dimensional PSD matrix) with an (n+1)-dimensional PSD matrix plus a single constraint that the lifted vector lies in a new sparsity cone K. The central claims are that SC-SDP is equivalent in strength to SDP-RLT, that K admits useful structural characterizations, that projection onto K reduces to a one-dimensional subproblem, and that the dual of SC-SDP yields explicit presolving rules (variable fixing, screening cuts, dual refinement). A two-phase Riemannian augmented Lagrangian solver is developed that exploits the projection structure, and numerical tests on several sparse QP classes are reported.

Significance. If the equivalence and projection results hold, the work supplies a strictly smaller SDP formulation that preserves bound quality while enabling cheaper projection steps and dual-based presolving; both are practically relevant for global optimization of sparse QPs. The explicit derivation of presolving certificates from the dual and the structured solver constitute concrete algorithmic contributions.

minor comments (2)
  1. Abstract, last sentence: the clause 'and exploits the structured projection subproblems' is grammatically incomplete; rephrase for clarity.
  2. The manuscript would benefit from an explicit statement (early in the introduction or after the equivalence theorem) of the precise dimension reduction achieved and any hidden assumptions on the support pattern that are required for the cone K to be well-defined.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the manuscript, including the recognition of the equivalence between SC-SDP and SDP-RLT, the utility of the sparsity cone projection, and the value of the dual-based presolving and Riemannian solver. We appreciate the recommendation to accept.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; equivalence is a direct proof and cone is independently characterized

full rationale

The central claim is an explicit proof that the (n+1)-matrix SC-SDP with single sparsity-cone constraint K is equivalent in strength to the standard (2n+1)-matrix SDP-RLT relaxation; this equivalence is stated as a theorem and does not rely on fitting, self-citation chains, or renaming. The sparsity cone K is introduced as a new object whose structural properties and efficient projection (via one-dimensional subproblem) are derived separately and used only for solver implementation and dual-based presolving rules. No load-bearing step reduces by construction to its own inputs, no ansatz is smuggled via prior self-citation, and the presolving mechanisms follow from the dual without statistical forcing. The derivation chain is therefore self-contained against external benchmarks.

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

The paper introduces the sparsity cone K as a new modeling object; background SDP theory is standard.

assumptions (1)
  • standard math Standard properties of semidefinite programming and convex cones hold
    Invoked for the relaxation equivalence and dual derivations.
invented entities (1)
  • sparsity cone K
    purpose: Compact relaxation of the l0-norm constraint inside an (n+1)-dimensional SDP
    Newly defined cone whose projection and dual properties drive the algorithmic contributions

how reviews work

0 comments
Cite this review

Pith. "Pith review of Sparsity-Cone SDP Relaxations and Applications to Variable Fixing for Sparse Quadratic Programs." pith.science (2026). https://pith.science/paper/KL32Q235

@misc{pith2026260622894,
  author       = {Pith},
  title        = {Pith review of: Sparsity-Cone SDP Relaxations and Applications to Variable Fixing for Sparse Quadratic Programs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/KL32Q235}},
  note         = {Machine review of arXiv:2606.22894}
}
abstract

Quadratic programs (QPs) with sparsity constraint are generally NP-hard, and their efficient global solution depends crucially on tractable tight convex relaxations. In this paper, we propose a sparsity-cone semidefinite programming (SC-SDP) relaxation for sparse (indefinite) QPs. Unlike standard SDP liftings, such as the SDP--RLT relaxation, which involve a $(2n+1)$-dimensional semidefinite matrix, the proposed SC-SDP formulation uses only a $(n+1)$-dimensional matrix together with a single sparsity-cone constraint $\mathcal{K}$ to handle the relaxation of the $\ell_0$-norm constraint. We prove that SC-SDP is equivalent in strength to the SDP--RLT relaxation. We further study the sparsity cone $\mathcal{K}$, deriving structural characterizations and showing that projection onto $\mathcal{K}$ can be computed efficiently via a one-dimensional subproblem. Building on the dual of SC-SDP, we derive explicit presolving mechanisms, including a dual-fixing rule for individual variables, a screening-cut rule for excluding larger support patterns, and a dual-refinement step for improving presolving certificates. To solve the resulting relaxation SC-SDP efficiently, we develop a two-phase Riemannian-based augmented Lagrangian method and exploits the structured projection subproblems. Numerical experiments on several classes of sparse QPs show that SC-SDP preserves the bound quality of SDP--RLT while offering substantial computational advantages and practically effective presolving capabilities.

Figures

Figures reproduced from arXiv: 2606.22894 by the authors.

Figure 1
Figure 1. Geometry of K ∩ S 3 + for n = 2 and k = 1. 2.2 Projection onto K Projection onto K is required repeatedly in the algorithm. Since membership in K depends only on the first row and column and on the diagonal of the lower-right block, the off￾diagonal part of X¯ is preserved by the projection. The next result makes this reduction explicit. For Y¯ =  a¯ x¯ ⊤ x¯ X¯  ∈ S n+1 , ¯d := diag(X¯), projection onto K reduces … view at source ↗
Figure 2
Figure 2. Scalability for (SRR). 27 [PITH_FULL_IMAGE:figures/full_fig_p027_2.png] view at source ↗
Figure 3
Figure 3. Presolving and Gurobi performance for (SRR) under varying SNR. [PITH_FULL_IMAGE:figures/full_fig_p028_3.png] view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: Presolving and Gurobi performance for the equality-constrained sparse ridge regression model [PITH_FULL_IMAGE:figures/full_fig_p030_4.png]
Figure 5
Figure 5. Figure 5: Presolving and Gurobi performance for (S-StQP). [PITH_FULL_IMAGE:figures/full_fig_p032_5.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

33 extracted references · 3 canonical work pages

  1. [1]

    Achterberg, R

    T. Achterberg, R. E. Bixby, Z. Gu, E. Rothberg, and D. Weninger. Presolve reductions in mixed integer programming.INFORMS Journal on Computing, 32(2):473–506, 2020. 36

    2020

  2. [2]

    M. ApS. Mosek optimization toolbox formatlab.User’s Guide and Reference Manual, Version, 4, 2019

    2019

  3. [3]

    Atamturk and A

    A. Atamturk and A. G´ omez. Safe screening rules for l0-regression from perspective relaxations. InInternational Conference on Machine Learning, pages 421–430. PMLR, 2020

    2020

  4. [4]

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

    1998

  5. [5]

    Bertsimas, J

    D. Bertsimas, J. Pauphilet, and B. Van Parys. Sparse regression: Scalable algorithms and empirical performance.Statistical Science, 35(4):555–578, Nov. 2020

    2020

  6. [6]

    Billionnet and ´E

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

    2004

  7. [7]

    I. M. Bomze, B. Peng, Y. Qiu, and E. A. Yıldırım. Tighter yet more tractable relax- ations and nontrivial instance generation for sparse standard quadratic optimization. Mathematical Programming Computation, 17(4):617–651, 2025

    2025

  8. [8]

    Boyd and J

    S. Boyd and J. Mattingley. Branch and bound methods.Notes for EE364b, Stanford University, 2006:07, 2007

    2006

Show all 33 references
  1. [9]

    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

  2. [10]

    Caprara, D

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

    1999

  3. [11]

    Gallo, P

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

    1980

  4. [12]

    Gally, M

    T. Gally, M. E. Pfetsch, and S. Ulbrich. A framework for solving mixed-integer semidef- inite programs.Optimization Methods and Software, 33(3):594–632, 2018

    2018

  5. [13]

    Gamrath, T

    G. Gamrath, T. Koch, A. Martin, M. Miltenberger, and D. Weninger. Progress in presolving for mixed integer programming.Mathematical Programming Computation, 7(4):367–398, 2015

    2015

  6. [14]

    Gurobi Optimizer Reference Manual, 2023

    Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2023

    2023

  7. [15]

    S. Han, A. G´ omez, and A. Atamt¨ urk. The equivalence of optimal perspective formu- lation and Shor’s SDP for quadratic programs with indicator variables.Operations Research Letters, 50(2):195–198, 2022

    2022

  8. [16]

    D. Hou, T. Tang, and K.-C. Toh. A low-rank augmented Lagrangian method for doubly nonnegative relaxations of mixed-binary quadratic programs.Operations Research, 2025. 37

    2025

  9. [17]

    D. Hou, T. Tang, and K.-C. Toh. A low-rank augmented Lagrangian method for Polyhedral–SDP and Moment–SOS relaxations of polynomial optimization.arXiv preprint arXiv:2512.06359, 2025

    2025

  10. [18]

    D. Hou, T. Tang, and K.-C. Toh. RiNNAL+: a Riemannian ALM solver for SDP– RLT relaxations of mixed-binary quadratic programs.Mathematical Programming Computation, 2026

    2026

  11. [19]

    D. Hou, T. Tang, K.-C. Toh, and S. Wang. On the efficient computation of proximal operators of affine-constrained nonconvex functions.arXiv preprint arXiv:2602.23626, 2026

    2026

  12. [20]

    Land and A

    A. Land and A. Doig. An automatic method of solving discrete programming problems. Econometrica, 28(3):497–520, 1960

    1960

  13. [21]

    C.-p. Lee, L. Liang, T. Tang, and K.-C. Toh. Accelerating nuclear-norm regularized low-rank matrix optimization through Burer-Monteiro decomposition.Journal of Ma- chine Learning Research, 25(379):1–52, 2024

    2024

  14. [22]

    Matter and M

    F. Matter and M. E. Pfetsch. Presolving for mixed-integer semidefinite optimization. INFORMS Journal on Optimization, 5(2):131–154, 2023

    2023

  15. [23]

    L. Mitten. Branch-and-bound methods: General formulation and properties.Opera- tions research, 18(1):24–34, 1970

    1970

  16. [24]

    Pisinger

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

    2007

  17. [25]

    Sara¸ c and A

    T. Sara¸ c and A. Sipahioglu. Generalized quadratic multiple knapsack problem and two solution approaches.Computers & Operations Research, 43:78–89, 2014

    2014

  18. [26]

    H. D. Sherali. RLT: A unified approach for discrete and continuous nonconvex opti- mization.Annals of Operations Research, 149(1):185–193, 2007

    2007

  19. [27]

    N. Z. Shor. Dual quadratic estimates in polynomial and boolean programming.Annals of Operations Research, 25:163–168, 1990

    1990

  20. [28]

    Sun, K.-C

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

    2020

  21. [29]

    Tan and G

    H. Tan and G. Wang. Screening cut generation for sparse ridge regression.arXiv preprint arXiv:2505.01082, 2025

    2025

  22. [30]

    Tang and K.-C

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

    2024

  23. [31]

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

    2022

  24. [32]

    Yamada, S

    T. Yamada, S. Kataoka, and K. Watanabe. Heuristic and exact algorithms for the disjunctively constrained knapsack problem.Information Processing Society of Japan Journal, 43(9):2864–2870, 2002

    2002

  25. [33]

    L. Yang, D. Sun, and K.-C. Toh. SDPNAL+: a majorized semismooth Newton- CG augmented Lagrangian method for semidefinite programming with nonnegative constraints.Mathematical Programming Computation, 7(3):331–366, 2015. 39 A Support restrictions and strong branching This sectio...

    2015

Pith tools

Reviewed June 26, 2026 · model on record in the stance chip above.