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. To also appear in Math. Prog.
Entry Submitted: 12/21/2006
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|