When is Polynomial Optimization SoS-Exact? Sufficient Regularization and Strict Gram Representations
Source: arxiv.org/abs/2611.12697
Global minimization of multivariate polynomials is computationally difficult in general, and nonnegativity does not necessarily imply a sum-of-squares (SoS) representation. We show that adding sufficiently strong Euclidean regularization to a polynomial provides a general mechanism for overcoming such challenges. Namely, for any multivariate polynomial $P$ of degree at most $p$ with a nonzero linear coefficient, and any even integer $2d>p$, we prove that $m_σ(s)=P(s)+\fracσ{2d}\|s\|_2^{2d}$ is SoS exact for all sufficiently large $σ$. Furthermore, the shifted polynomial $m_σ-\min m_σ$ admits…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.12697
curl -X POST /api/v1/records/arxiv/2611.12697/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.12697/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'