**1. Back to bounds for positivstellenstatz **

In Schmüdgen’s Positivstellensatz,

Theorem 1 (Schmüdgen 1991)Let be a basic semi-algebraic set, defined by . Then a polynomial is positive on iff .

there are bounds (due to Marie-Fran\c coise Roy, possibly unpublished), but very large.

Putinar’s theorem

Theorem 2 (Putinar, Jacobi, Prestel 1993)Let be a basic semi-algebraic set. Assume that there exists a constant such that . Then a polynomial is positive on iff .

is an improvement, since the number of terms in the expression is instead of . Apart from that, the apriori bounds are even worse than for Schmüdgen’s theorem.

Linial: are there examples which tell that bounds have to be so bad ? Answer: Not that I know. My personal view is that bad instances (very small coefficients…) lead to terrible computation times, as is common in symbolic computation.

** 1.1. An alternative representation **

Again due to Krivine.

Theorem 3 (Krivine)Let be a basic semi-algebraic set, defined by . Assume that generates the algebra . Assume that is compact, and that all on . If on , then there exist nonnegative constants such that

If one fixes an apriori bound on the degrees , , finding the decomposition is solving an LP (note that existing LP software is efficient on instances involving millions of variables). However, the computation is ill-conditioned due to binomial coefficients in the expansion of .

Remark 1Theorem 3 does not apply if instead of .

Indeed, let be linear (so that is a polyhedron) but non linear, achieving an absolute minimum at an interior point of some face with only one active constraint, , but not constant on the that face, i.e. there exists a point where and . Assume a decomposition as in Theorem 3 exists. Then all monomials vanish at , so have a positive degree in . So the polynomial vanishes at as well, contradiction.

**2. Dual side: the moment problem **

**Problem**: Given a set and numbers , , does there exist a positive measure supported on such that

Positive answers when : Hamburger (), Stieltjes ().

Here is some notation

Definition 4The linear functional is defined byThe

moment matrixhas entriesGiven a polynomial , the

localizing matrixis

The moment matrix encodes

The localizing matrix encodes

** 2.1. Schmüdgen dual conditions **

Let be a basic semi-algebraic set, defined by . For , let .

Theorem 5Assume is compact. Then a sequence has a representing measure if and only if

If one restricts to degree polynomials, this amounts to checking that the matrices are positive semidefinite for all . It is a set of linear matrix inequalities, i.e. an SDP.

** 2.2. Putinar dual conditions **

Let be a basic semi-algebraic set, defined by .

Theorem 6Assume is compact. Assume that there exists a constant such that on . Then a sequence has a representing measure if and only if

If one restricts to degree polynomials, this amounts to checking that the matrices are positive semidefinite for all . It is a set of linear matrix inequalities, i.e. an SDP.

** 2.3. Krivine dual conditions **

Let be a basic semi-algebraic set, defined by . For , let .

Theorem 7Assume is compact. Assume that the ‘s and generate . Assume that on . Then a sequence has a representing measure if and only if

If one restricts to degree polynomials, this amounts to checking that a finite set of linear inequalities has a nonnegative solution, i.e. solving an LP.

**3. SDP relaxations **

Now we have tools to solve the global optimization problem on a basic semialgebraic set defined by .

Recall the dual formulation: to minimize on , minimize under constraints for some probability measure supported on . Note that the unknown is . Also, ideally, the measure is a Dirac measure.

Substitute the Putinar dual conditions. Minimize under constraints

- , is positive semidefinite.
- , , is positive semidefinite.
- .

Our relaxation consists in bounding the degree . Let degree or .

Minimize under constraints

- is positive semidefinite.
- , , is positive semidefinite.
- .

The dual SDP is

Maximize under constraints

- each is a sum of squares.
- degree, degree.

Example 1The Goemans-Williamson relaxation for MAX CUT.

Let be defined by , , where is the adjacency matrix of the given (weighted) graph. The primal SDP constraints and positive semidefinite imply that For , we find the Goemans-Williamson relaxation. The dual amounts to maximizing subject to

Here, is a sum of squares of linear forms. Instead of rounding, one could study the dual problem and show it is not feasible beyond 0.878… This is pure algebra, but does not seem easy.

Linial: in 1995, I tried to prove Bourgain’s embedding in this way (search for embeddings is an SDP), but did not succeed.

Kindler: can one stop with a finite ? Answer: yes, at , the SDP stabilizes.