Exactness of the DNN Relaxation for Random Standard Quadratic Programs
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2605.11456
curl -X POST /api/v1/records/arxiv/2605.11456/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2605.11456/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'