SDP representabilityConvex sets in R2Hyperbolicity and the Lax conjectureRelating SDP-representable sets and hyperbolic polynomialsCharacterizationExampleMIT 6.972 Algebraic techniques and semidefinite optimization March 7, 2006 Lecture 8 Lecturer: Pablo A. Parrilo Scribe: ??? 1 SDP representability A few lectures ago, when discussing the set of nonnegative polynomials, we encountered convex sets in R2 that lacked certain desirable prop e rties (namely, being basic semialgebraic, and facially exposed). As we will see, hyperbolic polynomials will play a fundamental role in the characterization of the properties a set in R2 must satisfy for it to be the feasible set of a semidefinite program. 2 Convex sets in R2 In this lecture we will study conditions that a set S ⊂ R2 must satisfy for it to be semidefinite repre-sentable, i.e., to admit a characterization of the type {(x, y) ∈ R2 I + xB + yC � 0}, (1)|where B, C ∈ Sd. Notice that we have assumed (without loss of generality) that 0 ∈ int S, and normalized the first matrix in the matrix pencil to be an identity matrix (this can always be achieved by left- and right-multiplying by an appropriate factor). Remark 1. We should not confuse the notion of semidefinite representability described above, with the much more general lifted SDP representability, that allows the representation of the original set as a projection of a higher-dimensional SDP set. In other words, here we are not allowed to use additional variables. Clearly, from (1), we have the following necessary conditions for SDP representability: • Closed: Every set of the form (1) is closed, in the standard topology. • Convex: Every set of the form (1) is necessarily convex, since it is (the projection of) the inter-section of an affine subspace and the convex set of PSD matrices. Of course, this is also easy to prove directly. • Basic semialgebraic: As we have discussed, the boundary of the set (1) is defined by d unquan-tified polynomial inequalities of degree at most equal to d. In fact, the interior of this set exactly corresponds to the connected component of det(I + xB + yC) > 0 that contains the origin. There is a less obvious additional condition, which we have also seen already: • Exposed faces: Every convex set of the form (1) has proper faces that are exposed. In other words, every face F must have a representation as F = S ∩ H, where H is a supporting hyperplane of the convex set S. A natural question, then, is the following: are the conditions listed above sufficient for SDP repre-sentability? If a set S ⊂ R2 satisfies these four conditions, do there always exist matrices B, C, for which the set (1) is exactly equal to S? To ask a concrete question: does the set in Figure 1 admit an SDP representation? Before settling this issue, let us discuss first an apparently different question, involving hyperbolic polynomials. 8-1� � � � � � � � -2-1.5 -1-0.5 0.51 1.52x-1.5-1-0.50.511.5y-2-1.5 -1-0.5 0.51 1.52x-1.5-1-0.50.511.5yFigure 1: Convex set defined by x4 + y4 ≤ 1. 3 Hyperbolicity and the Lax conjecture Recall from the previous lecture that a hyperbolic polynomial is a homogeneous polynomial p(x) of degree d, with the property that when restricted to lines parallel to a particular direction e, the resulting univariate polynomial has all its d roots real. Furthermore, we have also seen that every polynomial of the form p(x) = det(x1A1 + · · · + xnAn), (2) where Ai ∈ Sd and A1 � 0, is hyperbolic with respect to the (1, 0, . . . , 0) direction. A 1958 conjecture by Peter Lax [Lax58], asks whether the converse is true in the case n = 3 (i.e., trivariate polynomials). In other words, is it true that for every hyperbolic polynomial p(x) in three variables of degree d, there exist three symmetric matrices {A1, A2, A3} ⊂ Sd for which (2) holds? As a first step towards answering this question, let us verify that this at least makes sense in terms of dimension counting. As we have seen, the dimension of the set of hyperbolic polynomials in three n+d−1variables (n = 3) and degree d is equal to d = d+2 . On the other hand, for a polynomial of 2 the form (2), by an appropriate similarity transform we can always assume without loss of generality A1 = a0Id, and A2 = diag(a1, . . . , ad). The total number of parameters is then 1 + d + d+1 , which is 2 exactly equal to d+2 . Of course, this by itself does not prove the result, but it shows that it is certainly 2 possible. 4 Relating SDP-representable sets and hyperbolic polynomials As we will see shortly, these two apparently different problems are in fact one and the same. Before showing this, let us consider one additional necessary condition for a set in R2 to be SDP-representable. For later reference, we first define the following notion: Definition 2. A polynomial p ∈ R[x] is a real z ero polynomial if for every x ∈ Rn , p(tx) = 0 implies that t is real. Recall that the boundary of a set described by (1) is determined by the zero set of the polynomial det(I + xB + yC). Consider now any line passing through the origin, i.e., of the form (x, y) = (βt, γt). We have then det[I + (βB + γC)t] = 0, and this univariate polynomial in t has exactly d real roots (namely, the negative inverse of the eigenvalues of βB + γC). In terms of the notation just introduced, the polynomial defined by det(I + xB + yC) is 8-2� � 5 a real zero polynomial. Equivalently, for every set of the form (1), is it always the case that every line through the origin intersects (the Zariski closure1 of) the boundary of the set exactly d times. In the preceding, our starting point was directly a determinantal representation as in (1). It can be shown (see [HV]) that if we start directly from a given set that admits an SDP representation, we can precisely characterize a unique minimal polynomial that defines the boundary of the set. Hence, this gives us an additional necessary condition ([HV]) for SDP re presentability: • Rigid convexity: Consider a set in R2, with the origin in the interior. Every line that passes through the origin must intersect the polynomial defining the boundary exactly d times (counting multiplicities, and points at infinity), where d is the degree of the boundary polynomial. This additional requirement is quite strong, and immediately allows us to