pith. sign in

arxiv: 2604.02968 · v1 · submitted 2026-04-03 · 🧮 math.OC

Separable QCQPs and Their Exact SDP Relaxations

Masakazu Kojima , Sunyoung Kim , Naohiko Arima This is my paper

Pith reviewed 2026-05-13 18:24 UTC · model grok-4.3

classification 🧮 math.OC
keywords separable QCQPsexact SDP relaxationsquadratically constrained quadratic programssemidefinite programmingnonconvex optimizationhorizontal connectionright-hand-side parameters
0
0 comments X

The pith

Separable QCQPs with exact SDP relaxations remain exact when combined through right-hand-side parameter connections.

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

The paper establishes a constructive way to form a larger separable QCQP from smaller ones that already possess exact semidefinite programming relaxations. Exactness carries over provided the subproblems are joined by a separable horizontal connection that couples them exclusively through the right-hand-side values of their constraints. This supplies a simple sufficient condition guaranteeing that the SDP relaxation of the combined problem solves it exactly. Readers would care because QCQPs arise in many nonconvex optimization settings, and exact relaxations turn the SDP into a global solver with no duality gap. The authors apply the condition to convex QCQPs, sign-pattern and graph-structured QCQPs, and separable homogeneous QCQPs with few constraints, and illustrate the method with two heterogeneous examples.

Core claim

We consider the construction of a larger separable QCQP from multiple QCQPs with exact SDPRs. We show that exactness is preserved when such QCQPs are combined through a separable horizontal connection, where the coupling is induced through the right-hand-side parameters of the constraints. The proposed framework provides a simple sufficient condition for exactness of the resulting SDPR. We then identify notable classes of QCQPs for which this condition holds, including convex QCQPs, QCQPs defined by sign-pattern and graph-structural conditions, and separable homogeneous QCQPs with a limited number of constraints.

What carries the argument

The separable horizontal connection, which couples multiple QCQPs solely by linking the right-hand-side parameters of their constraints in a separable manner.

If this is right

  • Convex QCQPs satisfy the sufficient condition and therefore have exact SDP relaxations.
  • QCQPs defined by sign-pattern and graph-structural conditions also satisfy the condition.
  • Separable homogeneous QCQPs with a limited number of constraints inherit exactness under the framework.
  • Heterogeneous QCQPs can be assembled into new instances that retain exact SDP relaxations, as shown by the two examples.

Where Pith is reading between the lines

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

  • The method offers a modular route to generate families of QCQPs whose exact relaxations are known by construction.
  • If separability can be maintained, analogous preservation arguments might apply to other convex relaxations beyond SDP.
  • Combined models arising in networked systems could be decomposed into smaller exact subproblems and reassembled without losing global optimality guarantees.

Load-bearing premise

The input QCQPs must already possess exact SDP relaxations and must be joined precisely by a separable horizontal connection induced through right-hand-side parameters.

What would settle it

Build one concrete combined QCQP from two known exact instances using the described horizontal connection, solve its SDP relaxation, and check whether the SDP optimal value equals the true optimum of the combined QCQP.

read the original abstract

This paper studies exact semidefinite programming relaxations (SDPRs) for separable quadratically constrained quadratic programs (QCQPs). We consider the construction of a larger separable QCQP from multiple QCQPs with exact SDPRs. We show that exactness is preserved when such QCQPs are combined through a separable horizontal connection, where the coupling is induced through the right-hand-side parameters of the constraints. The proposed framework provides a simple sufficient condition for exactness of the resulting SDPR. We then identify notable classes of QCQPs for which this condition holds, including convex QCQPs, QCQPs defined by sign-pattern and graph-structural conditions, and separable homogeneous QCQPs with a limited number of constraints. Two examples illustrate the constructive nature of the proposed framework, showing how heterogeneous QCQPs can be combined to yield new instances with exact SDP relaxations.

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

2 major / 3 minor

Summary. The paper studies exact semidefinite programming relaxations (SDPRs) for separable quadratically constrained quadratic programs (QCQPs). It shows that exactness is preserved when multiple QCQPs already possessing exact SDPRs are combined into a larger separable QCQP via a separable horizontal connection with coupling induced solely through the right-hand-side parameters of the constraints. A simple sufficient condition for exactness of the resulting SDPR is derived, and the framework is shown to apply to standard classes including convex QCQPs, those satisfying sign-pattern or graph-structural conditions, and separable homogeneous QCQPs with few constraints. Two constructive examples illustrate the approach.

Significance. If the central preservation result holds, the paper supplies a modular, constructive method for generating new families of QCQPs with provably exact SDP relaxations from known base cases. This is valuable for both theoretical understanding of SDP tightness in nonconvex quadratic optimization and for practical construction of benchmark instances in control, signal processing, and combinatorial optimization where exact relaxations are needed.

major comments (2)
  1. [§3.2, Theorem 3.1] §3.2, Theorem 3.1: The proof of exactness preservation relies on the horizontal connection being separable and RHS-only; however, the argument does not explicitly verify that the dual variables corresponding to the coupled constraints remain feasible under the original exactness assumptions when the number of blocks exceeds two. A short inductive step or explicit dual construction would strengthen the claim.
  2. [§4.3, Corollary 4.2] §4.3, Corollary 4.2: The claim that the condition applies to all separable homogeneous QCQPs with at most k constraints is stated without an explicit bound on k in terms of the dimension; the supporting argument in the homogeneous case appears to require k ≤ 2 for the rank-1 recovery to hold unconditionally, which should be clarified or corrected.
minor comments (3)
  1. [§2.3] The definition of 'separable horizontal connection' in §2.3 would benefit from an immediate small numerical example showing the block structure of the combined constraint matrices.
  2. [§5] In the examples of §5, the SDP solutions are reported only up to numerical tolerance; adding the exact recovered rank-1 solutions or the duality gap values would make the exactness verification more transparent.
  3. [Introduction] A few references to recent work on SDP exactness for QCQPs with sign patterns (e.g., post-2020 papers) appear to be missing from the introduction.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading, positive assessment of the paper's significance, and recommendation for minor revision. The comments on the proof and corollary are helpful for improving clarity. We respond to each major comment below and will incorporate the necessary revisions.

read point-by-point responses

  1. Referee: [§3.2, Theorem 3.1] §3.2, Theorem 3.1: The proof of exactness preservation relies on the horizontal connection being separable and RHS-only; however, the argument does not explicitly verify that the dual variables corresponding to the coupled constraints remain feasible under the original exactness assumptions when the number of blocks exceeds two. A short inductive step or explicit dual construction would strengthen the claim.

    Authors: We agree that an explicit verification for an arbitrary number of blocks would strengthen the presentation. The proof of Theorem 3.1 constructs the dual variables for the combined SDP relaxation by taking the direct sum of the individual dual solutions from each block (scaled by the separable RHS coupling). This aggregation preserves dual feasibility and complementarity for any finite number of blocks due to the block-diagonal structure of the SDP and the fact that coupling occurs only through the RHS parameters. Nevertheless, to address the referee's point directly, we will insert a short inductive step in the revised proof of Theorem 3.1 that explicitly verifies dual feasibility when extending from m to m+1 blocks. revision: yes

  2. Referee: [§4.3, Corollary 4.2] §4.3, Corollary 4.2: The claim that the condition applies to all separable homogeneous QCQPs with at most k constraints is stated without an explicit bound on k in terms of the dimension; the supporting argument in the homogeneous case appears to require k ≤ 2 for the rank-1 recovery to hold unconditionally, which should be clarified or corrected.

    Authors: We thank the referee for identifying this ambiguity. Upon re-examination, the argument for homogeneous QCQPs indeed guarantees unconditional rank-1 recovery only when k ≤ 2; for k > 2 the recovery holds only under additional sign-pattern or graph-structural conditions already covered in earlier sections. We will revise Corollary 4.2 to state the bound explicitly as k ≤ 2 (with a parenthetical note on the dimension-independent nature of this bound for the homogeneous case) and clarify the conditions required for larger k. This correction will appear in the revised manuscript. revision: yes

Circularity Check

0 steps flagged

No significant circularity in theoretical preservation result

full rationale

The paper derives a sufficient condition for exact SDP relaxations of combined separable QCQPs by showing preservation of exactness under a separable horizontal connection induced only through RHS parameters. This is a direct mathematical construction starting from the assumption that input QCQPs already have exact SDPRs, without any reduction to fitted parameters, self-definitional loops, or load-bearing self-citations that collapse the claim. The identified classes (convex QCQPs, sign-pattern/graph cases, homogeneous QCQPs with few constraints) follow from standard convex and structural properties in the literature, keeping the derivation self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on standard properties of SDP relaxations for QCQPs and the definition of separability; no free parameters or invented entities are introduced in the abstract.

axioms (1)
  • standard math Standard properties of semidefinite programming relaxations for quadratically constrained quadratic programs
    The paper builds directly on known results about when SDP relaxations are exact for certain QCQPs.

pith-pipeline@v0.9.0 · 5451 in / 1236 out tokens · 45338 ms · 2026-05-13T18:24:04.178624+00:00 · methodology

discussion (0)

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

Reference graph

Works this paper leans on

26 extracted references · 26 canonical work pages

  1. [1]

    C. J. Argue, F. Kilin¸ c-Karzan, and A.L. Wang. Necessary and sufficient conditions for rank-one-generated cones.Math. Oper. Res., 48(1):100–126, 2023

    work page 2023

  2. [2]

    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. Technical Report arXiv:2409.07213, September 2024

    work page arXiv 2024

  3. [3]

    Azuma, Fukuda M., S

    G. Azuma, Fukuda M., S. Kim, and M. Yamashita. Exact SDP relaxations for quadratic programs with bipartite graph structures.J. of Global Optim., 86:671–691, 2023

    work page 2023

  4. [4]

    Ben-Tal and A

    A. Ben-Tal and A. Nemirovski.Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications. SIAM, 2001

    work page 2001

  5. [5]

    Bengtsson and B

    M. Bengtsson and B. Ottersten.Optimum and Suboptimum Transmit Beamforming, volume Handbook of Antennas in Wireless Communications, chapter 18. CRC Press, 2002

    work page 2002

  6. [6]

    B. P. Bertsekas.Nonlinear Programming. Athena Scientific, Belmont, MA., second edition edition, 1999

    work page 1999

  7. [7]

    C. A. Floudas and V. Visweswaran.Quadratic Optimization, volume Quadratic Opti- mization ofNonconvex Optimization and Its Applications, pages 217–269. Springer

    work page

  8. [8]

    Fukuda, M

    M. Fukuda, M. Kojima, K. Murota, and K. Nakata. Exploiting sparsity in semidefinite programming via matrix completion. I: General framework.SIAM J. Optim., 11:647– 674, 2000

    work page 2000

  9. [9]

    Huang and D

    Y. Huang and D. P. Palomar. Rank-constrained separable semidefinite programming with applications to optimal beamforming.IEEE TRANSACTIONS ON SIGNAL PROCESSING, 58(2):664–678, 2010

    work page 2010

  10. [10]

    P. Jorion. Portfolio optimization with tracking-error constraints.Financial Analysts Journal, 59(5):70–82, 2003

    work page 2003

  11. [11]

    Joyse and B

    A. Joyse and B. Yang. Convex hull results on quadratic programs with non-intersecting constraints.Math. Program., 205:539–558, 2024

    work page 2024

  12. [12]

    Kim and M

    S. Kim and M. Kojima. Equivalent sufficient conditions for global optimality of quadrat- ically constrained quadratic program.Mathematical Methods of Operations Research, 101:73–94, 2025

    work page 2025

  13. [13]

    S. Kim, M. Kojima, and K. C. Toh. Doubly nonnegative relaxations are equivalent to completely positive reformulations of quadratic optimization problems with block- clique graph structures.Journal of Global Optimization, 77(3):513–541, 2020. 16

    work page 2020

  14. [14]

    S. Kim, M. Kojima, and K. C. Toh. A geometrical analysis of a class of nonconvex conic programs for convex conic reformulations of quadratic and polynomial optimization problems.SIAM J. Optim., 30:1251–1273, 2020

    work page 2020

  15. [15]

    Extending

    M. Kojima, S. Kim, and N. Arima. Extending exact convex relaxations of quadratically constrained quadratic programs. Technical Report arXiv:2504.03204, 2025

    work page arXiv 2025

  16. [16]

    Luo, W.-K

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

    work page 2010

  17. [17]

    M., de Abreu N.M.M., Boaventura-Netto P.O., Hahn P., and Querido T

    Loiola E. M., de Abreu N.M.M., Boaventura-Netto P.O., Hahn P., and Querido T. A survey for the quadratic assignment problem.European Journal of Operational Research, 176:657–690, 2007

    work page 2007

  18. [18]

    Murota, Y

    K. Murota, Y. Kanno, M. Kojima, and S. Kojima. A numerical algorithm for block- diagonal decomposition of matrix *-algebras with application to semidefinite program- ming.Japan J. Indust. Appl. Math., 27:125–160, 2010

    work page 2010

  19. [19]

    Pappas, N

    I. Pappas, N. A. Diangelakis, and E. N. Pistikopoulos. Multiparametric/explicit nonlin- ear model predictive control for quadratically constrained problems.Journal of Process Control, 103:55–66, 2021

    work page 2021

  20. [20]

    G. Pataki. On the rank of extreme matrices in semidefinite programs and the multi- plicity of optimal eigenvalues.Math. Oper. Res., 23(2):339–358, 1998

    work page 1998

  21. [21]

    B. T. Polyak. Convexity of quadratic transformations and its use in control and opti- mization.J. Optim. Theory Appl., 99(3):553–583, 1998

    work page 1998

  22. [22]

    Rendl, G

    F. Rendl, G. Rinaldi, and A. Wiegele. Solving max-cut to optimality by intersecting semidefinite and polyhedral relaxations.Math. Program., 121(307-335), 2010

    work page 2010

  23. [23]

    N. Z. Shor. Quadratic optimization problems.Soviet Journal of Computer and Systems Sciences, 25:1–11, 1987

    work page 1987

  24. [24]

    Sojoudi and J

    S. Sojoudi and J. Lavaei. Exactness of semidefinite relaxations for nonlinear optimiza- tion problems with underlying graph structure.SIAM J. Optim., 24(4):1746–1778, 2014

    work page 2014

  25. [25]

    B. Yang, K. Anstreiher, and S. Burer. Quadratic programs with hollows.Math. Pro- gram., 170:541–553, 2018

    work page 2018

  26. [26]

    Ye and S

    Y. Ye and S. Zhang. New results on quadratic minimization.SIAM J. Optim., 14:245– 267, 2003. 17

    work page 2003