pith. sign in

arxiv: 2606.21823 · v1 · pith:L2MAK646new · submitted 2026-06-20 · 🧮 math.OC

Local-to-Global Exactness of SDP Relaxations for Sparse QCQPs

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

Pith reviewed 2026-06-26 12:13 UTC · model grok-4.3

classification 🧮 math.OC
keywords SDP relaxationsparse QCQPchordal extensionclique-wise SDPlocal-to-global exactnessexactness certificationquadratic constraints
0
0 comments X

The pith

If local sub-SDPs are exact then the global SDP relaxation is exact for sparse QCQPs.

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

The paper develops a framework that decomposes the SDP relaxation of a sparse QCQP into clique-wise matrix variables drawn from the maximal cliques of a chordal extension of the aggregate sparsity pattern graph. It constructs, for each clique, a local sub-SDP whose right-hand side and consistency matrix are taken directly from an optimal solution of the global clique-wise formulation. The central theorem states that exactness of every such local sub-SDP implies that the original SDP relaxation admits a rank-at-most-one optimal solution corresponding to an optimum of the QCQP. Under the further restriction that any two cliques share at most one node, the framework incorporates three known families of small exact QCQPs: convex instances, instances obeying sign-pattern conditions, and separable instances with few constraints.

Core claim

The main theorem shows that if the local sub-SDPs are exact, then the original SDP relaxation is exact. The SDP is first rewritten in clique-wise variables; each local sub-SDP receives a right-hand-side vector and a consistency matrix taken from an optimal solution of this global formulation; exactness of the locals forces the existence of a rank-at-most-one global solution that solves the QCQP.

What carries the argument

Local sub-SDP parameterized by a local right-hand-side vector and a consistency matrix that fixes shared entries across overlapping cliques.

If this is right

  • Convex local QCQPs on each clique yield an exact global SDP relaxation.
  • Local QCQPs satisfying sign-pattern conditions can be combined to certify global exactness.
  • Separable local QCQPs with a limited number of constraints likewise produce an exact global relaxation.
  • The three local classes can be mixed within one sparse QCQP provided the intersection condition holds.

Where Pith is reading between the lines

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

  • Verification can be reduced to independent checks on the individual cliques once a candidate global solution is known.
  • The single-node intersection restriction may be removable for some of the local classes without losing the local-to-global implication.
  • The same decomposition could be applied to certify exactness of other convex relaxations that admit clique-wise formulations.

Load-bearing premise

Any two distinct cliques intersect in at most one node.

What would settle it

A sparse QCQP obeying the single-node intersection condition whose local sub-SDPs are all exact yet whose global SDP relaxation has no rank-one optimal solution.

Figures

Figures reproduced from arXiv: 2606.21823 by Masakazu Kojima, Naohiko Arima, Sunyoung Kim.

Figure 1
Figure 1. Figure 1: An example of the aggregate sparsity pattern matrix (left), where * de [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: An example of the aggregate sparsity pattern matrix of a block diagonal (or [PITH_FULL_IMAGE:figures/full_fig_p016_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: The aggregate sparsity pattern graph G(N, E 0 ) of QCQP (1) of Example 5.3. Here Fq (q = 1, . . . , 4) and Cp (p = 2, . . . , 5) are cliques of G(N, E 0 ), whereas C1 is a clique of a chordal extension of the graph. Separable QCQPs with a limited number of constraints are assigned to C1 = F1 ∪ F2 ∪ F3 ∪ F4, QCQPs characterized by sign-pattern conditions to C2 and C3, and convex QCQPs to C4 and C5. Example … view at source ↗
read the original abstract

We study exact semidefinite programming (SDP) relaxation for a given sparse quadratically constrained quadratic program (QCQP). The SDP relaxation is exact if, whenever it has an optimal solution, it admits a rank-at-most-one optimal solution that corresponds to an optimal solution of the QCQP. Using the maximal cliques of a chordal extension of the aggregate sparsity pattern graph of the data matrices, we formulate the SDP relaxation in terms of clique-wise matrix variables and develop a local-to-global framework for certifying exactness. For each clique-wise matrix variable, we introduce a local sub-SDP with two parameters: a local right-hand-side vector and a consistency matrix specifying the values of entries shared by overlapping clique-wise matrix variables. In the main theorem, these parameters are determined by an optimal solution of the global clique-wise SDP. The theorem shows that if the resulting local sub-SDPs are exact, then the original SDP relaxation is exact. Under the additional assumption that any two distinct cliques intersect in at most one node, we present three classes of local QCQPs that can be incorporated into this framework: convex local QCQPs, local QCQPs characterized by sign-pattern conditions, and separable local QCQPs with a limited number of constraints. Examples illustrate how these different local QCQP classes can be combined in sparse QCQPs.

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 paper develops a local-to-global framework for exactness of SDP relaxations of sparse QCQPs. It reformulates the global SDP using clique-wise matrix variables from the maximal cliques of a chordal extension of the aggregate sparsity pattern. Local sub-SDPs are introduced for each clique, parameterized by a local right-hand-side vector and a consistency matrix whose values are taken from an optimal solution of the global clique-wise SDP. The central theorem asserts that exactness of these parameterized local sub-SDPs implies exactness of the original global SDP relaxation. Under the additional assumption that any two distinct cliques intersect in at most one node, three classes of local QCQPs (convex, sign-pattern, and separable with limited constraints) are identified whose known exactness can be plugged into the framework, with examples showing combinations.

Significance. If the main theorem is correct, the framework supplies a modular certification route: global exactness follows from local exactness once parameters are fixed by a global solution. This is potentially useful for large-scale sparse QCQPs, where the global SDP may be intractable but local subproblems on small cliques are tractable or already known to be exact. The approach leverages standard chordal-graph properties without introducing new free parameters or circular reductions, and the concrete local classes (convex, sign-pattern, separable) provide immediate applicability. The separation of the core implication from the intersection assumption is a strength.

minor comments (3)
  1. [Abstract] The abstract states the main theorem but does not indicate its section or theorem number; a forward reference (e.g., "Theorem 3.2") would help readers locate the precise statement.
  2. The consistency matrix is introduced as specifying shared entries, but its construction from the global solution (including how overlapping entries are aggregated when more than two cliques meet) would benefit from an explicit formula or pseudocode in the framework section.
  3. The three concrete local QCQP classes are presented under the intersection-at-most-one assumption; a brief remark on whether the main theorem itself requires this assumption or only the examples would clarify the logical structure.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of the paper, the accurate summary of our local-to-global framework, and the recommendation for minor revision. No specific major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The central result is a mathematical implication (local sub-SDP exactness implies global SDP exactness) whose parameters are explicitly taken from a global optimal solution; this is a standard theoretical reduction and does not reduce the claimed exactness to a fitted quantity or self-citation by construction. The intersection-at-most-one-node condition is stated as an additional assumption needed only to exhibit concrete local QCQP classes, not to support the main theorem. No load-bearing step relies on a self-citation chain or renames a known result; the derivation remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The framework rests on standard properties of chordal graphs and SDP rank conditions already present in the literature; no new free parameters, ad-hoc axioms, or invented entities are introduced in the abstract.

axioms (1)
  • standard math Maximal cliques of a chordal extension of the aggregate sparsity pattern graph can be used to decompose the SDP relaxation
    Invoked to formulate the clique-wise SDP variables

pith-pipeline@v0.9.1-grok · 5778 in / 1334 out tokens · 23601 ms · 2026-06-26T12:13:40.810748+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

27 extracted references · 3 canonical work pages · 2 internal anchors

  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

    2023

  2. [2]

    Exact SDP relaxations for a class of quadratic programs with finite and infinite quadratic constraints

    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, To appear inSIAM J. Optim., September 2024

    work page internal anchor Pith review Pith/arXiv arXiv 2024

  3. [3]

    Arima, S

    N. Arima, S. Kim, and M. Kojima. Further development in convex conic reformulation of geometric nonconvex conic optimization problems.SIAM J. Optim., 34(4):3194– 3211, 2024

    2024

  4. [4]

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

    2011

  5. [5]

    Ben-Tal and A

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

    2001

  6. [6]

    J. R. S. Blair and B. Peyton. An introduction to chordal graphs and clique trees. In Liu J.W.H. George A., Gilbert J. R., editor,Graph Theory and Sparse Matrix Computation. Springer-Verlag, New York, 1993

    1993

  7. [7]

    J. Dancis. Positive semidefinite completions of partial Hermitian matrices.Linear Algebra Appl., 175:91–114, 1992

    1992

  8. [8]

    Fujie and M

    T. Fujie and M. Kojima. Semidefinite programming relaxation for nonconvex quadratic programs.J. of Global Optim., 10:367–368, 1997

    1997

  9. [9]

    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

    2000

  10. [10]

    Grone, C

    R. Grone, C. R. Johnson, E. M. S´ a, and H. Wolkowicz. Positive definite completions of partial hermitian matrices.Linear Algebra Appl., 58:109–124, 1984

    1984

  11. [11]

    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

    2010

  12. [12]

    Jiang, Y

    X. Jiang, Y. Sun, M. S. Andersen, and L. Vandenberghe. Minimum-rank positive semidefinite matrix completion with chordal patterns and applications to semidefinite relaxations.Appl. Set-Valued Anal. Optim., 5(2):265–283, 2023

    2023

  13. [13]

    Johnson and R.I

    C.R. Johnson and R.I. Smith. The completion problem for m-matrices and inverse m-matrices.Linear Algebr. Appl., 241–243:655–667, 1996

    1996

  14. [14]

    Joyce and B

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

    2024

  15. [15]

    Kim and M

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

    2003

  16. [16]

    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

    2020

  17. [17]

    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

    2020

  18. [18]

    Kojima, S

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

    work page arXiv 2025

  19. [19]

    Separable QCQPs and Their Exact SDP Relaxations

    M. Kojima, S. Kim, and N. Arima. Separable QCQPs and their exact SDP relaxations. Technical Report arXiv:2604.02968, April 2026. 25

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  20. [20]

    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

    2010

  21. [21]

    Nakata, K

    K. Nakata, K. Fujisawa, M. Fukuda, M. Kojima, and K. Murota. Exploiting sparsity in semidefinite programming via matrix completion. II: Implementation and numerical results.Math. Program., 95:303–327, 2003

    2003

  22. [22]

    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

    1998

  23. [23]

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

    1998

  24. [24]

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

    1987

  25. [25]

    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

    2014

  26. [26]

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

    2018

  27. [27]

    Ye and S

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

    2003