Rank conditions for exactness of semidefinite relaxations in polynomial optimization
Аннотация
We consider the Moment-SOS hierarchy in polynomial optimization. We first provide a sufficient condition to solve the truncated $$\textbf{K}$$-moment problem associated with a given degree-2 n pseudo-moment sequence $$\varvec{\phi }^n$$ and a semi-algebraic set $$\textbf{K}\subset \mathbb {R}^d$$. Namely, let 2 v be the maximum degree of the polynomials that describe $$\textbf{K}$$. If the rank r of its associated moment matrix is less than $$n-v+1$$, then $$\varvec{\phi }^n$$ restricted to degree-$$2n-1$$ moments, has an atomic representing measure supported on at most r points of $$\textbf{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 $$\textbf{K}$$ for the representing measure.