Videos

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.