Optimization Online


Convex sets with semidefinite representation

Jean B. Lasserre (lasserre***at***laas.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. To also appear in Math. Prog.

Download: [PDF]

Entry Submitted: 12/21/2006
Entry Accepted: 12/21/2006
Entry Last Modified: 07/09/2008

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society