Convex Sets with Lifted Semidefinite Representation
Presenter
January 20, 2007
Keywords:
- Convex sets
MSC:
- 46A55
Abstract
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
SDr
is explicitly expressed in terms of the polynomials that define
K.
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
Lagrangian
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
explicit
dependence of r with respect to a.