Rank conditions for exactness of semidefinite relaxations in polynomial optimization
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915097350242304 |
|---|---|
| author | Lasserre, Jean B |
| author_facet | Lasserre, Jean B |
| contents | We consider the Moment-SOS hierarchy in polynomial optimization. We first provide a sufficient condition to solve the truncated K-moment problem associated with a given degree-$2n$ pseudo-moment sequence $ϕ$ n and a semi-algebraic set $K \subset \mathbb{R}^d$. Namely, let $2v$ be the maximum degree of the polynomials that describe $K$. If the rank $r$ of its associated moment matrix is less than $nv + 1$, then $ϕ^n$ has an atomic representing measure supported on at most $r$ points of $K$. When used at step-$n$ of the Moment-SOS hierarchy, it provides a sufficient condition to guarantee its finite convergence (i.e., the optimal value of the corresponding degree-n semidefinite relaxation of the hierarchy is the global minimum). For Quadratic Constrained Quadratic Problems (QCQPs) one may also recover global minimizers from the optimal pseudo-moment sequence. Our condition is in the spirit of Blekherman's rank condition and while on the one-hand it is more restrictive, on the other hand it applies to constrained POPs as it provides a localization on $K$ for the representing measure. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_06052 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Rank conditions for exactness of semidefinite relaxations in polynomial optimization Lasserre, Jean B Optimization and Control We consider the Moment-SOS hierarchy in polynomial optimization. We first provide a sufficient condition to solve the truncated K-moment problem associated with a given degree-$2n$ pseudo-moment sequence $ϕ$ n and a semi-algebraic set $K \subset \mathbb{R}^d$. Namely, let $2v$ be the maximum degree of the polynomials that describe $K$. If the rank $r$ of its associated moment matrix is less than $nv + 1$, then $ϕ^n$ has an atomic representing measure supported on at most $r$ points of $K$. When used at step-$n$ of the Moment-SOS hierarchy, it provides a sufficient condition to guarantee its finite convergence (i.e., the optimal value of the corresponding degree-n semidefinite relaxation of the hierarchy is the global minimum). For Quadratic Constrained Quadratic Problems (QCQPs) one may also recover global minimizers from the optimal pseudo-moment sequence. Our condition is in the spirit of Blekherman's rank condition and while on the one-hand it is more restrictive, on the other hand it applies to constrained POPs as it provides a localization on $K$ for the representing measure. |
| title | Rank conditions for exactness of semidefinite relaxations in polynomial optimization |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2501.06052 |