1. A new approach to nonnegativity
The SDP relaxations we have found up to now give lower bounds on the optimum. The new approach will give upper bounds.
Let be the convex cone of polynomials of degree which are on .
Previously, was given by a set of inequations . Recall that the quadratic module is a sum of squares. Since , replacing with leads to a lower bound on the optimum. If , then is the union of (Putinar’s Positivstellensatz), so the optima over converge to the optimum. When the optimal solution is unique, optimal solutions of SDP’s converge, and this can be seen directly on the moment matrices.
Now, we assume that a positive measure with support exactly equal to is given. This models inverse problems, i.e. situations in which is known only via measurements.
Then a continuous function on is iff the signed measure is nonnegative, and this needs be checked on open subsets on only.
Theorem 1 (Lasserre, 2010) Let be compact, let be a positive measure with support , let be a continuous function on . Let . Then
- on iff and this is equivalent to all moment matrices being positive semidefinite.
- If, in addition, is concave, then one may replace with its convex hull.
Proof: We use the following easy criterion when is compact.
Lemma 2 Let . Then is the set of moments of a positive measure on iff is bounded and all moment matrices are positive semidefinite.
As before, we know that as soon as the rank of stabilizes, one does not need consider higher degree moments.
In the non compact case, we use
Lemma 3 (Carleman) Let . If all moment matrices are positive semidefinite, and for all ,
then is the set of moments of a unique positive measure on .
In the space of degree -polynomials, the set
is a spectrahedron, i.e. the intersection of a linear subspace with the cone of positive semidefinite matrices. The spectrahedra decrease, and their intersection equals . They can be used to give a certificate that is not on . In other words,
1.2. A hierarchy of upper bounds
Theorem 4 Let be compact, let be a positive measure with support , with moments . let be a continuous function on . Consider the following hierarchies of SDP.
- minimize (over sums of squares of degree ) subject to constraints
- maximize (over real numbers ) subject to constraints
Then the optima of 1. (resp. 2.) decrease and converge as tends to infinity to .
Interpretation: 1. amounts to optimizing over measures which have a density w.r. t. which is a sum of squares of low degree. The speed of convergence depends on the quality of approximation of Dirac measures by such measures.
1.3. An example
The above method applies whenever comes with a measure with computable moments.
Say a symmetric matrix is copositive if for all vectors with nonnegative entries. It is known that every optimization problem can be expressed by minimization on the cone of copositive matrices. The moments of Gaussian measure on are known. The SDP upper bounds decrease fast in first steps, but then decrease slowly.
1.4. Quadrature formulae
Quadrature formulae, for a given measure are combinations of Dirac measures which give the same integral as on every polynomial of degree . They can be obtained from moment matrices as follows: in one variable, replace last line by . The points are the roots of the determinant of the obtained matrix, a determinant of degree . Alternating way to obtain an upper bound on the optimum is to compute these roots, evaluate there and pick the smallest value encountered.
For instance, for MAX CUT, this yields an alternate to Goemans-Williamson’s rounding procedure. The weakness is root extraction, of course.