Convex sets with semidefinite representation

Jean B. Lasserre (lasserrelaas.fr)

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 L_f 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 K_a in sandwich between K and K+aB (where B is the unit ball), and K_a has 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 the size of the SDr of K_a with respect to a.

Keywords: Convex sets; semidefinite representation; representation of positive polynomials; sum of squares

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Category 2: Global Optimization

Category 3: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Citation: Technical report; LAAS-CNRS, Toulouse, France. December 2006.

Download: [PDF]

Entry Submitted: 12/21/2006
Entry Accepted: 12/21/2006
Entry Last Modified: 01/30/2008

Modify/Update this entry