Semidefinite Representation of Convex Sets and Convex Hulls

J. William Helton () and Jiawang Nie ()
Additional contact information
J. William Helton: University of California at San Diego
Jiawang Nie: University of California at San Diego

Chapter Chapter 4 in Handbook on Semidefinite, Conic and Polynomial Optimization, 2012, pp 77-112 from Springer

Abstract: Abstract Semidefinite programming (SDP) (Ben-Tal and Nemirovski: Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications. MPS-SIAM Series on Optimization, SIAM, Philadelphia (2001); Nesterov and Nemirovskii: Interior-point polynomial algorithms in convex programming. SIAM Studies in Applied Mathematics 13. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA (1994); Nemirovskii, A.: Advances in convex optimization: conic programming. Plenary Lecture at the International Congress of Mathematicians (ICM), Madrid, Spain, 22-30 August 2006; Wolkowicz et al.: Handbook of semidefinite programming. Kluwer’s, Boston, MA (2000)) is one of the main advances in convex optimization theory and applications. It has a profound effect on combinatorial optimization, control theory and nonconvex optimization as well as many other disciplines. There are effective numerical algorithms for solving problems presented in terms of Linear Matrix Inequalities (LMIs). A fundamental problem in semidefinite programming concerns the range of its applicability. What convex sets S can be represented by using LMI? This question has several natural variants; the main one is to represent S as the projection of a higher dimensional set that is representable by LMI; such S is called SDP representable (SDr). Here we shall describe these variants and what is known about them. The chapter is a survey of the existing results of (Helton and Nie: Mathematical Programming 122(1):21–64 (2010); Helton and Nie: SIAM Journal on Optimization 20(2):759–791 (2009); Lasserre: Mathematical Programming 120:457–477 (2009)) and related work.

Keywords: Convex Hull; Fundamental Form; Positive Curvature; Real Zero; Semidefinite Programming (search for similar items in EconPapers)
Date: 2012
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:isochp:978-1-4614-0769-0_4

Ordering information: This item can be ordered from
http://www.springer.com/9781461407690

DOI: 10.1007/978-1-4614-0769-0_4

Access Statistics for this chapter

More chapters in International Series in Operations Research & Management Science from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().