  


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 semialgebraic 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 (Semidefinite Programming ) Citation: Technical report; LAASCNRS, Toulouse, France. December 2006. To also appear in Math. Prog. Download: [PDF] Entry Submitted: 12/21/2006 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  