6.972 Lecture 8 Notes

MIT 6.972 Algebraic techniques and semidefinite optimization Lecture 8 1 SDP representability A few lectures ago, when discussing the set of nonnegative polynomials, we encountered convex sets in R2 that lacked certain desirable properties (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 ∈ S d . 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 y 1.5 1 0.5 -2 -1.5 -1 -0.5 0.5 1 1.5 2 x -0.5 -1 -1.5 Figure 1: Convex set defined by x4 + y 4 ≤ 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(x1 A1 + · · · + xn An ), (2) where Ai ∈ S d 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 } ⊂ S d 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 of �the set of hyperbolic polynomials in three � dimension � �d+2 variables (n = 3) and degree d is equal to n+d−1 = d 2 . On the other hand, for a polynomial of the form (2), by an appropriate similarity transform we can always assume without loss � of�generality A1 = a0 Id , and A2 = diag(a1 , . . . , ad ). The total number of parameters is then 1 + d + d+1 2 , which is �d+2� exactly equal to 2 . Of course, this by itself does not prove the result, but it shows that it is certainly 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 zero 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 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 representability: • 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 discard sets for which the previous conditions were satisfied. Example 3. Consider the set described by x4 + y 4 ≤ 1; see Figure 1. It clearly satisfies the first four necessary conditions. However, it we consider any line through the origin, it will intersect the defining polynomial only two times, instead of the four required by the rigid convexity condition. Thus, this set is not rigidly convex, and hence does not admit a (non­lifted) semidefinite representation. 5 Characterization It should be apparent that the rigid convexity condition looks very similar to the hyperbolicity property of a polynomial. In fact, they are exactly the same condition, provided we redefine things accordingly [LPR05]. As we will see, this equivalence will make explicit the connection between the Helton & Vinnikov characterization of SDP­representable sets and the Lax conjecture described earlier. Theorem 4 ([LPR05]). If p ∈ R[x, y, z] is a polynomial of degree d, hyperbolic with respect to e = (0, 0, 1) and that satisfies p(e) = 1, then the polynomial in R[x, y] defined by q(x, y) = p(x, y, 1) is a real zero polynomial of degree no more than d, and satisfying q(0, 0) = 1. Conversely, if q ∈ R[x, y] is a real zero polynomial of degree d satisfying q(0, 0) = 1, then the polynomial defined by �x y� , p(x, y, z) = z d q z z is a hyperbolic polynomial of degree d with respect to e = (0, 0, 1), and p(e) = 1. In their paper [HV], Helton and Vinnikov proved that the rigid convexity condition fully characterizes the plane sets that are semidefinite representable. Theorem 5 ([HV]). If p(x, y) is a real zero polynomial of degree d with p(0) > 0, then the closure of the connected component of p(x) > 0 containing the origin admits a representation as in (1). For hyperbolic cones, we have shown earlier that the specific hyperbolicity direction e does not matter too much (as long as it belong to the hyperbolicity cone). Similarly, it can be shown that when checking the real zero condition we can choose any point in the interior of the set, not necessarily the origin. Combining these two results, the truth of the Lax conjecture follows: Theorem 6. Every hyperbolic polynomial in three variables admits a determinantal representation of the type (2). If coordinates are chosen so that e = (1, 0, 0), then we can choose A1 = I. 1 The Zariski topology on Cn can be defined in terms of its closed sets, which are the algebraic varieties, i.e., the vanishing set of a finite set of polynomial equations. The Zariski topology is a very weak topology, and is quite different from the usual topology in Cn . For instance, the Zariski closure of the open interval (0, 1) is equal to C. The Zariski topology is not Hausdorff, i.e., distinct points do not always have disjoint neighborhoods. 8­3 y 3 2 1 -6 -5 -4 -3 -2 -1 1 2 x -1 -2 -3 Figure 2: Convex set defined by {3 + x − x3 − 3x2 − 2y 2 ≥ 0, x ≥ −1}. A semidefinite representation is given in (3). An interesting issue concerns the possibility of a constructive approach. In other words, given a hyperbolic polynomial in three variables, how to effectively obtain matrices Ai that give a determinantal representation? While “explicit” formulae for these matrices are given in [HV] in terms of objects that are quite complicated to compute (namely, theta functions of Jacobian varieties), it seems likely that a more elementary formulation exists. 5.1 Example As an illustration, consider the convex set shown in Figure 3, which corresponds to the “oval” of the elliptic curve given by 3 + x − x3 − 3x2 − 2y 2 = 0. This set satisfies the real zero condition, since every line that passes through a point in the interior of the set intersects the polynomial defining the boundary at exactly three points (if the lines are vertical, then the corresponding intersections are at infinity). Homogenizing this polynomial, we obtain p(x, y, z) = 3z 3 + xz 2 − x3 − 3x2 z − 2y 2 z; the corresponding zero set is given in Figure 3. As we can see (and proved earlier), the section corresponding to the plane z = 1 is exactly the zero set of the original polynomial. Furthermore, lines parallel to the hyperbolicity direction e are projectively mapped into lines in this plane that go through the origin. Hence, the number of intersections (and thus, real roots) is preserved. The theorem presented above promises the existence of a semidefinite representation. In this case, one such representation is: ⎡ ⎤ x+1 0 y ⎣ 0 2 −x − 1⎦ � 0, (3) y −x − 1 2 with the corresponding determinantal representation of the hyperbolic polynomial being: ⎡ ⎤ x+z 0 y 2z −x − z ⎦ . p(x, y, z) = det ⎣ 0 −x − z 2z y (4) References [HV] J.W. Helton and V. Vinnikov. Linear matrix inequality representation of sets. Preprint. Available from http://arxiv.org/abs/math.OC/0306180. 8­4 Figure 3: The polynomial 3z 3 + xz 2 − x3 − 3x2 z − 2y 2 z = 0 and corresponding hyperbolicity cone. [Lax58] P. D. Lax. Differential equations, difference equations and matrix theory. Comm. Pure Appl. Math., 11:175–194, 1958. [LPR05] A. S. Lewis, P. A. Parrilo, and M. V. Ramana. The Lax conjecture is true. Proc. Amer. Math. Soc., 133(9):2495–2499, 2005. 8­5