Convex Sets with Lifted Semidefinite Representation

Saturday, January 20, 2007 - 2:30pm - 3:20pm
EE/CS 3-180
Jean Lasserre (Centre National de la Recherche Scientifique (CNRS))
We provide a sufficient condition on a class of
compact basic semialgebraic sets K for their convex hull
to have a lifted semidefinite representation (SDr). This lifted
is explicitly expressed in terms of the polynomials that define
Examples are provided. For convex and compact basic
semi-algebraic sets
K defined by concave polynomials,
we also provide an explicit lifted SDr when the nonnegative
Lf associated with
K and any linear polynomial f, is a sum of squares. We then
provide an approximate lifted SDr in the general convex case.
By this we mean that for every fixed a>0, there is a convex set
Kr in
sandwich between K and K+aB
(where B is the unit ball), with an explicit lifted SDr in
terms of the
polynomials that define K.
For a special class of convex sets K, we also provide the
dependence of r with respect to a.
MSC Code: