A bounded degree SOS hierarchy for polynomial optimization

We consider a new hierarchy of semidefinite relaxations for the general polynomial optimization problem (P) : f* = min{f(x) : x is an element of K} on a compact basic semi-algebraic set K subset of R-n. This hierarchy combines some advantages of the standard LP-relaxations associated with Krivine's positivity certificate and some advantages of the standard SOS-hierarchy. In particular it has the following attractive features: (a) in contrast to the standard SOS-hierarchy, for each relaxation in the hierarchy, the size of the matrix associated with the semidefinite constraint is the same and fixed in advance by the user; (b) in contrast to the LP-hierarchy, finite convergence occurs at the first step of the hierarchy for an important class of convex problems; and (c) some important techniques related to the use of point evaluations for declaring a polynomial to be zero and to the use of rank-one matrices make an efficient implementation possible. Preliminary results on a sample of non convex problems are encouraging.