Exactness of the DNN Relaxation for Random Standard Quadratic Programs
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909040548773888 |
|---|---|
| author | Chen, Xin |
| author_facet | Chen, Xin |
| contents | We study the doubly nonnegative (DNN) relaxation of the standard quadratic optimization problem \[ \min\{x^\top Qx:\ x\inΔ^{n-1}\},\qquad Δ^{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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_11456 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Exactness of the DNN Relaxation for Random Standard Quadratic Programs Chen, Xin Optimization and Control We study the doubly nonnegative (DNN) relaxation of the standard quadratic optimization problem \[ \min\{x^\top Qx:\ x\inΔ^{n-1}\},\qquad Δ^{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. |
| title | Exactness of the DNN Relaxation for Random Standard Quadratic Programs |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2605.11456 |