pith. machine review for the scientific record. sign in

arxiv: 2605.11456 · v1 · submitted 2026-05-12 · 🧮 math.OC

Recognition: 2 theorem links

· Lean Theorem

Exactness of the DNN Relaxation for Random Standard Quadratic Programs

Xin Chen

Pith reviewed 2026-05-13 02:19 UTC · model grok-4.3

classification 🧮 math.OC
keywords standard quadratic programmingdoubly nonnegative relaxationcompletely positive conerandom matricesdefect graphexact relaxationrank-one solution
0
0 comments X

The pith

For random symmetric matrices with independent entries, the DNN relaxation of the standard quadratic program over the simplex is exact with probability tending to one and yields a unique rank-one optimizer.

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

The paper shows that a certain defect graph built from the negative off-diagonal entries of a shifted random matrix has only small connected components with high probability. Because the doubly nonnegative and completely positive cones coincide in dimensions up to four, the relaxation decomposes into exact low-dimensional subproblems on these components. Absolute continuity and a KKT argument then guarantee uniqueness of the global solution, which must be rank one. This matters for turning a nonconvex quadratic minimization into a reliably solvable convex program whose solution can be recovered quickly by examining the graph structure.

Core claim

Under entrywise independence, absolute continuity, and the tail-decay condition n^5 E[F_O(m_n)^4]→0, with probability tending to one every defect component has size at most 4. On this event the shifted DNN value decomposes over defect components. Since the DNN and completely positive cones coincide in dimensions at most four, each local relaxation is exact. A finite KKT-candidate argument together with absolute continuity rules out ties, so the global DNN optimizer is unique and rank one. For Gaussian orthogonal ensemble data the probability is at least 1 minus K (ln n)^2 / n^3. The exact optimizer is recovered in O(n^2) time by constructing the defect graph and solving constant-size local K

What carries the argument

The defect graph G_n^- on n vertices whose edges correspond to the negative off-diagonal entries of the shifted matrix M = Q - m_n E; its connected components of size at most 4 permit decomposition of the DNN relaxation into subproblems where DNN equals the completely positive cone.

If this is right

  • The true quadratic minimum equals the DNN value with high probability.
  • The global optimizer is recovered by building the defect graph and solving a constant number of small KKT systems.
  • For Gaussian orthogonal ensemble matrices the success probability is bounded below by 1 minus O((ln n)^2 / n^3).
  • The same exactness holds for variance-tuned Gaussian Wigner models, heavy-tailed laws, and finite-lower-endpoint distributions once the tail condition is verified.

Where Pith is reading between the lines

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

  • If the tail condition can be relaxed, the exactness result would apply to wider families of random quadratic programs.
  • The rank-one property suggests the relaxation selects an extreme point of the simplex without additional rounding steps.
  • Empirical checks of defect-graph component sizes on real-world quadratic instances could indicate when the method succeeds in practice.

Load-bearing premise

The tail-decay condition n^5 E[F_O(m_n)^4]→0 together with entrywise independence and absolute continuity of the entry distributions, because large defect components would prevent the decomposition into exact low-dimensional relaxations.

What would settle it

Generate instances of the random matrix Q such that the associated defect graph contains a connected component of five or more vertices with probability bounded away from zero; if such large components occur with non-vanishing probability the exactness and uniqueness claims fail.

read the original abstract

We study the doubly nonnegative (DNN) relaxation of the standard quadratic optimization problem \[ \min\{x^\top Qx:\ x\in\Delta^{n-1}\},\qquad \Delta^{n-1}:=\{x\in\mathbb{R}_+^n:\ \mathbb{1}^\top x=1\}, \] for random symmetric matrices with independent diagonal and off-diagonal entries. Let $m_n:=\min_{1\le i\le n} Q_{ii}$ and set $M:=Q-m_nE$, where $E$ is the all-ones matrix. The negative off-diagonal entries of $M$ define a defect graph $G_n^-$. Under entrywise independence, absolute continuity, and the tail-decay condition $n^5\mathbb{E}[F_O(m_n)^4]\to 0$, where $F_O$ is the off-diagonal distribution function, we prove that with probability tending to one every defect component has size at most $4$. On this event, the shifted DNN value decomposes over defect components. Since the DNN and completely positive cones coincide in dimensions at most four, each local relaxation is exact. A finite KKT-candidate argument gives local uniqueness, and absolute continuity rules out ties, so the global DNN optimizer is unique and rank one. The graph estimate uses the fact that every connected component of size at least five contains a tree on exactly five vertices. For Gaussian orthogonal ensemble data, we prove the explicit bound \[ \mathbb{P}\bigl(\text{the DNN optimizer is unique and rank one}\bigr) \ge 1-K\frac{(\ln n)^2}{n^3}. \] On the same event, the exact optimizer can be recovered in $O(n^2)$ time by constructing the defect graph and solving constant-size local KKT systems. We also verify the tail condition for variance-tuned Gaussian Wigner models, heavy-tailed laws, and finite-lower-endpoint laws.

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 proves that under entrywise independence, absolute continuity of the off-diagonal entries, and the tail-decay condition n^5 E[F_O(m_n)^4] → 0, the DNN relaxation of a random standard quadratic program is exact with probability tending to 1. This follows from showing that the defect graph G_n^- (edges where shifted off-diagonals are negative) has all connected components of size at most 4 w.h.p. (via Markov inequality and union bound over 5-vertex trees using Cayley's formula), allowing the shifted objective <M, X> to decompose as a convex combination of local objectives over these components. Since DNN = CP in dimension ≤4, each local problem is exact; a finite KKT-candidate argument plus absolute continuity then yields uniqueness and rank-1 of the global DNN optimizer. Explicit high-probability bounds are given for Gaussian orthogonal ensembles, and the tail condition is verified for several distribution families. An O(n^2) recovery algorithm is also provided.

Significance. If the results hold, the work provides a clean probabilistic certificate for exactness of the DNN relaxation on a broad class of random instances, together with an efficient recovery procedure. The graph-theoretic tail bound, the decomposition exploiting non-negativity of cross terms between components, and the reduction to low-dimensional exactness are technically sound and of interest to the optimization community. Explicit rates for Gaussians and verification across light- and heavy-tailed models add concrete applicability.

minor comments (3)
  1. The definition of the defect graph G_n^- (negative off-diagonals of M) and the precise statement of the decomposition <M,X> = ∑_C s_C² · (local value on C) should be stated as a numbered lemma or proposition with a short proof sketch, rather than only in the narrative of §3.
  2. In the Gaussian case, the constant K in the bound 1 - K (ln n)^2 / n^3 should be made explicit (or at least shown to be independent of n) so that the rate is fully quantitative.
  3. The absolute-continuity argument ruling out ties between distinct local minima (different components having identical local values) is only sketched; a one-sentence reference to the fact that the set of ties has measure zero under the product measure would improve clarity.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the careful reading of the manuscript and for the positive assessment. We are pleased that the referee found the probabilistic certificate for exactness of the DNN relaxation, the graph-theoretic arguments, and the efficient recovery procedure to be of interest.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The derivation proceeds from an explicit tail-decay assumption n^5 E[F_O(m_n)^4]→0 together with entrywise independence and absolute continuity. It applies the elementary Markov inequality and a union bound over 5-vertex trees (invoking only Cayley's formula, a standard combinatorial fact) to conclude that defect components have size at most 4 with high probability. On that event the shifted DNN objective is shown to decompose additively over components by non-negativity of cross terms and quadratic scaling; each local problem on dimension ≤4 is then exact by the classical equality of the DNN and completely positive cones in low dimension, with uniqueness following from a finite KKT enumeration and absolute continuity to break ties. All steps rely on external, independently verifiable mathematical facts rather than any self-referential definition, fitted parameter renamed as prediction, or load-bearing self-citation. The explicit probability bound for the Gaussian orthogonal ensemble is likewise obtained directly from the same tail estimate without circular reduction.

Axiom & Free-Parameter Ledger

0 free parameters · 3 axioms · 1 invented entities

The central claim rests on standard probabilistic assumptions plus a paper-specific tail condition that controls component sizes; the defect graph is a modeling device defined directly from the matrix entries.

axioms (3)
  • domain assumption Entrywise independence of the matrix entries
    Used throughout to obtain concentration and independence of defect events
  • domain assumption Absolute continuity of the off-diagonal distributions
    Invoked to rule out ties in the KKT conditions and ensure uniqueness
  • ad hoc to paper Tail-decay condition n^5 E[F_O(m_n)^4] → 0
    Required to guarantee that defect components are of size at most 4 with high probability
invented entities (1)
  • Defect graph G_n^- no independent evidence
    purpose: To capture the locations of negative off-diagonal entries in the shifted matrix M and enable decomposition of the DNN value
    Defined directly from the sign pattern of M; no external falsifiable prediction is supplied

pith-pipeline@v0.9.0 · 5644 in / 1568 out tokens · 61459 ms · 2026-05-13T02:19:02.712545+00:00 · methodology

discussion (0)

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

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

Reference graph

Works this paper leans on

19 extracted references · 19 canonical work pages

  1. [1]

    Springer, New York (2010).https://doi.org/10.1007/978-1-4419-0661-8

    Bai, Z., Silverstein, J.W.:Spectral Analysis of Large Dimensional Random Matrices, 2nd edn. Springer, New York (2010).https://doi.org/10.1007/978-1-4419-0661-8

    work page doi:10.1007/978-1-4419-0661-8 2010

  2. [2]

    World Scientific, Singapore (2003).https://doi.org/10.1142/5273

    Berman, A., Shaked-Monderer, N.:Completely Positive Matrices. World Scientific, Singapore (2003).https://doi.org/10.1142/5273

    work page doi:10.1142/5273 2003

  3. [3]

    Bomze, I.M.: On standard quadratic optimization problems.Journal of Global Optimization 13, 369–387 (1998).https://doi.org/10.1023/A:1008369322970

    work page doi:10.1023/a:1008369322970 1998

  4. [4]

    https://doi.org/10.1023/A:1020209017701

    Bomze, I.M., de Klerk, E.: Solving standard quadratic optimization problems via linear, semidefinite and copositive programming.Journal of Global Optimization24, 163–185 (2002). https://doi.org/10.1023/A:1020209017701

    work page doi:10.1023/a:1020209017701 2002

  5. [5]

    https://doi.org/10.1016/j.laa.2009.05.021

    Burer, S., Anstreicher, K.M., Dür, M.: The difference between5 × 5doubly nonnegative and completely positive matrices.Linear Algebra and its Applications431, 1539–1552 (2009). https://doi.org/10.1016/j.laa.2009.05.021

    work page doi:10.1016/j.laa.2009.05.021 2009

  6. [6]

    Burer, S., Ye, Y.: Exact semidefinite formulations for a class of (random and non-random) nonconvex quadratic programs.Mathematical Programming181, 1–17 (2020).https://doi.or g/10.1007/s10107-019-01367-2

    work page doi:10.1007/s10107-019-01367-2 2020

  7. [7]

    https://doi.org/10.1007/s10107-021-01684-5

    Burer, S., Ye, Y.: Correction to: Exact semidefinite formulations for a class of (random and non-random) nonconvex quadratic programs.Mathematical Programming190, 845–848 (2021). https://doi.org/10.1007/s10107-021-01684-5

    work page doi:10.1007/s10107-021-01684-5 2021

  8. [8]

    Cayley, A.: A theorem on trees.Quarterly Journal of Mathematics23, 376–378 (1889). 17

    work page

  9. [9]

    Chen, X., Peng, J.: New analysis on sparse solutions to random standard quadratic optimization problems and extensions.Mathematics of Operations Research40, 725–738 (2015).https: //doi.org/10.1287/moor.2014.0692

    work page doi:10.1287/moor.2014.0692 2015

  10. [10]

    Chen, X., Peng, J., Zhang, S.: Sparse solutions to random standard quadratic optimization problems.Mathematical Programming141, 273–293 (2013).https://doi.org/10.1007/s101 07-012-0519-x

    work page doi:10.1007/s101 2013

  11. [11]

    Mathematical Programming186, 309–336 (2021).https://doi.org/10.1007/s10107-019-0 1456-2

    Chen, X., Pittel, B.: On sparsity of the solution to a random quadratic optimization problem. Mathematical Programming186, 309–336 (2021).https://doi.org/10.1007/s10107-019-0 1456-2

    work page doi:10.1007/s10107-019-0 2021

  12. [12]

    Springer, New York (2006)

    de Haan, L., Ferreira, A.:Extreme Value Theory: An Introduction. Springer, New York (2006). https://doi.org/10.1007/0-387-34471-3

    work page doi:10.1007/0-387-34471-3 2006

  13. [13]

    Proceedings of the Cambridge Philosophical Society58, 17–25 (1962).https://doi.org/10.1 017/S0305004100036185

    Diananda, P.H.: On non-negative forms in real variables some or all of which are non-negative. Proceedings of the Cambridge Philosophical Society58, 17–25 (1962).https://doi.org/10.1 017/S0305004100036185

    work page 1962

  14. [14]

    Gordon, R.D.: Values of Mills’ ratio of area to bounding ordinate and of the normal probability integral for large values of the argument.The Annals of Mathematical Statistics12, 364–366 (1941).https://doi.org/10.1214/aoms/1177731721

    work page doi:10.1214/aoms/1177731721 1941

  15. [15]

    Lavaei, J., Low, S.H.: Zero duality gap in optimal power flow problem.IEEE Transactions on Power Systems27, 92–107 (2012).https://doi.org/10.1109/TPWRS.2011.2160974

    work page doi:10.1109/tpwrs.2011.2160974 2012

  16. [16]

    Springer, New York (1983).https://doi.org/10.1007/978-1-461 2-5449-2

    Leadbetter, M.R., Lindgren, G., Rootzén, H.:Extremes and Related Properties of Random Sequences and Processes. Springer, New York (1983).https://doi.org/10.1007/978-1-461 2-5449-2

    work page doi:10.1007/978-1-461 1983

  17. [17]

    Biometrika18, 395–400 (1926).https://doi.org/10.1093/biomet/18.3-4.395

    Mills, J.P.: Table of the ratio: area to bounding ordinate, for any portion of normal curve. Biometrika18, 395–400 (1926).https://doi.org/10.1093/biomet/18.3-4.395

    work page doi:10.1093/biomet/18.3-4.395 1926

  18. [18]

    Springer, New York (1987).https://doi.org/10.1007/978-0-387-75953-1

    Resnick, S.I.:Extreme Values, Regular Variation, and Point Processes. Springer, New York (1987).https://doi.org/10.1007/978-0-387-75953-1

    work page doi:10.1007/978-0-387-75953-1 1987

  19. [19]

    Wang, A.L., Kılınç-Karzan, F.: On the tightness of SDP relaxations of QCQPs.Mathematical Programming193, 287–336 (2022).https://doi.org/10.1007/s10107-020-01589-9 18

    work page doi:10.1007/s10107-020-01589-9 2022