A spectrahedron in ${\mathbb R}^n$ is the solution set of a linear
matrix inequality $A_0+\sum_{i=1}^nx_iA_i\succeq0$. Linear
projections of spectrahedra are called semidefinitely representable
sets, or sdp sets. These sets are the feasible sets for semidefinite
optimization, which is known to perform very efficiently in
polynomial time. Every semidefinitely representable set is
semialgebraic and convex, but no other restrictions are known.
A basic technique for constructing sdp approximations to a given
convex set, called the relaxation method, is due to Lasserre. It
relates the problem to weighted sums of squares representations of
nonnegative polynomials. Nemirovsky (2006) asked for a
characterization of semidefinitely representable sets. Helton and Nie
(2010) conjectured that every convex semialgebraic set should be
semidefinitely representable, and provided much evidence for this
conjecture. After an introduction to the problem and an overview of
known results, I shall try to explain the main steps of the proof of
the conjecture in dimension two.
|
