pith. sign in

arxiv: 2508.18435 · v2 · submitted 2025-08-25 · 🧮 math.OC

A second-order cone representable class of nonconvex quadratic programs

Santanu S. Dey , Aida Khajavirad This is my paper

Pith reviewed 2026-05-18 20:56 UTC · model grok-4.3

classification 🧮 math.OC
keywords nonconvex quadratic programmingsecond-order cone programmingreformulation-linearization techniquesparse optimizationconvex hullunit hypercubeexact relaxation
0
0 comments X

The pith

Under specific sparsity and structure conditions, nonconvex quadratic programs over the unit hypercube have the same optimal value as polynomial-size second-order cone programs.

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

The authors consider minimizing sparse nonconvex quadratic functions over the unit hypercube. They extend the reformulation-linearization technique to create a second-order cone relaxation for this problem. Exploiting sparsity, they find conditions where the convex hull of the lifted set is second-order cone representable. Further conditions ensure this formulation is polynomial-sized and constructible in polynomial time, making the relaxation exact for the original problem.

Core claim

By developing an extension of the Reformulation-Linearization Technique to continuous quadratic sets, the authors propose a novel second-order cone representable relaxation for minimizing a sparse nonconvex quadratic function over the unit hypercube. They establish a sufficient condition based on the sparsity of the quadratic function under which the convex hull of the feasible region of the lifted quadratic program is SOC-representable. Additional structural conditions guarantee a polynomial-size SOC-representable formulation constructible in polynomial time, under which the optimal value of the nonconvex quadratic program coincides with that of the polynomial-size second-order cone program

What carries the argument

Extension of the Reformulation-Linearization Technique to continuous quadratic sets that yields a second-order cone representable relaxation tight under sparsity and structural conditions

If this is right

  • The relaxation is exact for the nonconvex problem under the given conditions
  • A polynomial-time constructible formulation solves the problem exactly via SOCP
  • This connects sparse Boolean quadric polytopes to their continuous versions
  • The approach provides a way to solve certain nonconvex QPs efficiently

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • These conditions might be verifiable in practice for problems with known sparsity patterns like in graphical models
  • Similar lifting techniques could be developed for other nonconvex optimization problems with structure
  • The method may scale to larger problems than current global solvers for quadratic programming

Load-bearing premise

The sparsity pattern of the quadratic function and additional structural conditions suffice to make the convex hull of the lifted feasible set second-order cone representable

What would settle it

Find a sparse nonconvex quadratic program over the unit hypercube that satisfies the sparsity and structural conditions but whose true minimum differs from the optimal value of the corresponding polynomial-size second-order cone program

read the original abstract

We consider the problem of minimizing a sparse nonconvex quadratic function over the unit hypercube. By developing an extension of the Reformulation-Linearization Technique (RLT) to continuous quadratic sets, we propose a novel second-order cone (SOC) representable relaxation for this problem. By exploiting the sparsity of the quadratic function, we establish a sufficient condition under which the convex hull of the feasible region of the lifted quadratic program is SOC-representable. While the proposed formulation may be of exponential size in general, we identify additional structural conditions that guarantee the existence of a polynomial-size SOC-representable formulation, which can be constructed in polynomial time. Under these conditions, the optimal value of the nonconvex quadratic program coincides with that of a polynomial-size second-order cone program. Our results serve as a starting point for bridging the gap between the Boolean quadric polytope of sparse problems and its continuous counterpart.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The manuscript considers minimization of a sparse nonconvex quadratic over the unit hypercube. It extends the Reformulation-Linearization Technique to continuous quadratic sets to obtain an SOC-representable relaxation. Exploiting sparsity, the authors give sufficient conditions under which the convex hull of the lifted feasible region is SOC-representable; under further structural conditions they construct an explicit polynomial-size SOCP formulation in polynomial time whose optimal value equals that of the original nonconvex QP.

Significance. If the derivations hold, the work supplies an explicit, polynomial-time constructible tight SOC relaxation for a nontrivial class of sparse nonconvex QPs. The emphasis on sparsity patterns and the explicit construction of the polynomial-size formulation are concrete strengths that could be useful for applications and for further study of continuous relaxations of sparse Boolean quadric polytopes.

minor comments (3)
  1. [Abstract] Abstract: the phrase 'additional structural conditions' is used without even a one-sentence indication of their nature; a short parenthetical description would improve readability.
  2. [§2] §2 (Preliminaries): the notation for the lifted variables and the precise definition of the sparsity graph should be introduced earlier so that the subsequent RLT extension is easier to follow.
  3. [§4.3] §4.3: the polynomial-time construction algorithm is stated at a high level; adding a short pseudocode block or explicit complexity bound in terms of the number of nonzero quadratic terms would strengthen the claim.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the careful reading and positive assessment of our manuscript. The summary accurately captures the main contributions regarding the extension of RLT to continuous quadratic sets and the sparsity-based conditions for SOC-representable convex hulls. We are pleased with the recommendation for minor revision and the recognition of the explicit polynomial-size construction as a strength.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The derivation proceeds by extending the Reformulation-Linearization Technique to continuous quadratic sets over the unit hypercube, then proving a sufficient condition (sparsity plus additional structural conditions) under which the lifted convex hull is SOC-representable. The paper further identifies conditions guaranteeing a polynomial-size explicit SOC formulation constructible in polynomial time, under which the nonconvex QP optimum equals the SOCP optimum. These steps are presented as new mathematical constructions and proofs rather than reductions of outputs to fitted inputs, self-definitions, or load-bearing self-citations; the claims rest on explicit extensions and conditions supplied in the manuscript, rendering the central equivalence self-contained once the stated premises hold.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claims rest on standard results from convex analysis and quadratic programming together with the authors' new extensions; no free parameters, new entities, or ad-hoc axioms are introduced in the abstract.

axioms (1)
  • standard math Standard assumptions of convex optimization, including properties of second-order cones and the Reformulation-Linearization Technique for quadratic sets.
    The paper builds directly on these background results to derive the new relaxation and representability conditions.

pith-pipeline@v0.9.0 · 5684 in / 1309 out tokens · 42720 ms · 2026-05-18T20:56:42.660103+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

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

  1. Copositive Matrices with Ordered Off-Diagonal Entries

    math.OC 2026-05 unverdicted novelty 7.0

    Copositive matrices with nondecreasing off-diagonal entries admit a PSD plus nonnegative decomposition, which implies exactness of a natural relaxation for separable quadratic optimization over the simplex.

Reference graph

Works this paper leans on

31 extracted references · 31 canonical work pages · cited by 1 Pith paper · 1 internal anchor

  1. [1]

    Aboulker, S

    P. Aboulker, S. Fiorini, T. Huynh, M. Macchia, and J. Seif. Extension complexity of the correlation polytope. Operations Research Letters, 47(1):47–51, 2019

    work page 2019

  2. [2]

    K. M. Anstreicher and D. Puges. Extended triangle inequalities for nonconvex box-constrained quadratic programming. arXiv:2501.09150, 2025

    work page arXiv 2025

  3. [3]

    Anstreicher and S

    K.M. Anstreicher and S. Burer. Computable representations for convex hulls of low- dimensional quadratic forms. Mathematical Programming, 124:33—-43, 2010. 26

    work page 2010

  4. [4]

    E. Balas. Disjunctive programming and a hierarchy of relaxations for discrete optimization problems. SIAM Journal on Algebraic and Discrete Methods , 6:466–486, 1985

    work page 1985

  5. [5]

    Bao, N.V

    X. Bao, N.V. Sahinidis, and M. Tawarmalani. Semidefinite relaxations for quadratically con- strained quadratic programming: A review and comparisons. Mathematical Programming, 129:129–157, 2011

    work page 2011

  6. [6]

    Bienstock and G

    D. Bienstock and G. Mu˜ noz. LP formulations for polynomial optimization problems. SIAM Journal on Optimization , 28(2):1121–1150, 2018

    work page 2018

  7. [7]

    A linear time algorithm for finding tree-decompositions of small treewidth

    Hans L Bodlaender. A linear time algorithm for finding tree-decompositions of small treewidth. In Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, pages 226– 234, 1993

    work page 1993

  8. [8]

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

    work page 2009

  9. [9]

    Burer and A

    S. Burer and A. N. Letchford. On nonconvex quadratic programming with box constraints. SIAM Journal on Optimization , 20(2):1073–1089, 2009

    work page 2009

  10. [10]

    On the Semidefinite Representability of Continuous Quadratic Submodular Minimization With Applications to Moment Problems

    S. Burer and K. Natarajan. On the semidefinite representability of continuous quadratic submodular minimization with applications to moment problems. arXiv:2504.03996, 2025

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  11. [11]

    Chekuri and J

    C. Chekuri and J. Chuzhoy. Polynomial bounds for the grid-minor theorem. Journal of the ACM (JACM), 63(5):1–65, 2016

    work page 2016

  12. [12]

    Cifuentes, S

    D. Cifuentes, S. S. Dey, and J. Xu. Sensitivity analysis for mixed binary quadratic program- ming. In International Conference on Integer Programming and Combinatorial Optimization , pages 446–459. Springer, 2024

    work page 2024

  13. [13]

    Del Pia and A

    A. Del Pia and A. Khajavirad. A polyhedral study of binary polynomial programs. Mathe- matics of Operations Research, 42(2):389–410, 2017

    work page 2017

  14. [14]

    Del Pia and A

    A. Del Pia and A. Khajavirad. The multilinear polytope for acyclic hypergraphs. SIAM Journal on Optimization , 28(2):1049–1076, 2018

    work page 2018

  15. [15]

    Del Pia and A

    A. Del Pia and A. Khajavirad. On decomposability of multilinear sets. Mathematical Pro- gramming, Series A , 170(2):387–415, 2018

    work page 2018

  16. [16]

    Del Pia and A

    A. Del Pia and A. Khajavirad. A polynomial-size extended formulation for the multilinear polytope of beta-acyclic hypergraphs. Mathematical Programming Series A, pages 1–33, 2023

    work page 2023

  17. [17]

    X. Gu, S. S. Dey, and J.P. Richard. Solving sparse separable bilinear programs using lifted bilinear cover inequalities. INFORMS Journal on Computing , 36(3):884–899, 2024

    work page 2024

  18. [18]

    Horst and H

    R. Horst and H. Tuy. Global Optimization, Deterministic Approaches . Springer, 1996

    work page 1996

  19. [19]

    Khajavirad and N

    A. Khajavirad and N. V. Sahinidis. A hybrid LP/NLP paradigm for global optimization relaxations. Mathematical Programming Computation, 10(3):383–421, May 2018

    work page 2018

  20. [20]

    Kim and M

    S. Kim and M. Kojima. Exact solutions of some nonconvex quadratic optimization problems via SDP and SOCP relaxations. Computational optimization and applications , 26(2):143–154, 2003. 27

    work page 2003

  21. [21]

    Kolman and M

    P. Kolman and M. Kouteck` y. Extended formulation for CSP that is compact for instances of bounded treewidth. The Electronic Journal of Combinatorics , pages P4–30, 2015

    work page 2015

  22. [22]

    M. Laurent. Sums of squares, moment matrices and optimization over polynomials. In M. Putinar and S. Sullivant (eds.), Emerging applications of algebraic geometry, The IMA Volumes in Mathematics and its Applications, vol 149 Springer, New York, NY, pages 157–270, 2009

    work page 2009

  23. [23]

    Z. Luo, W. Ma, A. M. So, Y. Ye, and S. Zhang. Semidefinite relaxation of quadratic optimiza- tion problems. IEEE Signal Processing Magazine , 27(3):20–34, 2010

    work page 2010

  24. [24]

    McCormick

    G.P. McCormick. Computability of global solutions to factorable nonconvex programs: Part I: convex underestimating problems. Mathematical Programming, 10:147–175, 1976

    work page 1976

  25. [25]

    M. Padberg. The Boolean quadric polytope: Some characteristics, facets and relatives. Math- ematical Programming, 45(1–3):139–172, 1989

    work page 1989

  26. [26]

    Rockafellar

    R.T. Rockafellar. Convex Analysis. Princeton University Press, Princeton, 1970

    work page 1970

  27. [27]

    Santana and S

    A. Santana and S. S. Dey. The convex hull of a quadratic constraint over a polytope. SIAM Journal on Optimization , 30(4):2983–2997, 2020

    work page 2020

  28. [28]

    H. D. Sherali and C. H. Tuncbilek. A reformulation-convexification approach for solving non- convex quadratic programming problems. Journal of Global Optimization , 7(1):1–31, 1995

    work page 1995

  29. [29]

    Sherali and W.P

    H.D. Sherali and W.P. Adams. A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM Journal of Discrete Mathe- matics, 3(3):411–430, 1990

    work page 1990

  30. [30]

    Tardella

    F. Tardella. On a class of functions attaining their maximum at the vertices of a polyhedron. Discrete applied mathematics, 22(2):191–195, 1988

    work page 1988

  31. [31]

    J. Zhen, D. de Moor, and D. den Hertog. An extension of the reformulation-linearization technique to nonlinear optimization. Available at Optimization Online , 2021. 28

    work page 2021