# 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

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

L

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

K

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.

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

L

_{f}associated withK 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

K

_{r}insandwich 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.

MSC Code:

46A55

Keywords: