##
This **preview** shows page *1*
out of 4 **pages**.

*View Full Document*

End of preview. Want to read all 4 pages?

Upload your study docs or become a GradeBuddy member to access this document.

View Full Document**Unformatted text preview:**

Hyperbolic polynomialsSDP representability� � � 1 MIT 6.972 Algebraic techniques and semideﬁnite optimization March 2, 2006 Lecture 7 Lecturer: Pablo A. Parrilo Scribe: ??? In this lecture we introduce a special class of multivariate polynomials, called hyperbolic. These polynomials were originally studied in the context of partial diﬀerential equations. As we will see, they have many surprising properties, and are intimately linked with convex optimization problems that have an algebraic structure. A few good references about the use of hyperbolic polynomials in optimization are [G ¨ul97, BGLS01, Ren].Hyperbolic polynomials Consider a homogeneous multivariate polynomial p ∈ R[x1, . . . , xn] of degree d. Here homogeneous of degree d means that the sum of degrees of each monomial is constant and equal to d, i.e., α p(x) = cαx , α|=d|where α = (α1, . . . , αn), αi ∈ N ∪ {0}, and α = + αn. A homogeneous polynomial satisﬁes α1 + · · · p(tw) = tdp(w) for all real t and vectors w ∈|R|n . We denote the set of such polynomials by Hn(d). By identifying a polynomial with its vector of coeﬃcients, we can consider Hn(d) as a normed vector space n+d−1of dimension .d Deﬁnition 1. Let e be a ﬁxed vector in Rn . A polynomial p ∈ Hn(d) is hyperbolic with respect to e if p(e) > 0 and, for all vectors x ∈ Rn, the univariate polynomial t �→ p(x − te) has only real roots. A natural geometric interpretation is the following: consider the hypersurface in Rn given by p(x) = 0. Then, hyperbolicity is equivalent to the condition that every line in Rn parallel to e intersects this hypersurface at exactly d points (counting multiplicities), where d is the degree of the polynomial. Example 2. The polynomial x1x2 · · · xn is hyperbolic with respect to the vector (1, 1, . . . , 1), since the univariate polynomial t �→ (x1 − t)(x2 − t) · · · (xn − t) has roots x1, x2, . . . , xn. Hyperbolic polynomials enjoy a very surprising property, that connects in an unexpected way algebra with convex analysis. Given a hyperbolic polynomial p(x), consider the set deﬁned as: Λ++ := {x ∈ Rn : p(x − te) = 0 ⇒ t > 0}. Geometrically, this condition says that if we start at the point x ∈ Rn, and slide along a line in the direction parallel to e, then we will never encounter the hypersurface p(x) = 0, while if we move in the opposite direction, we will cross it exactly n times. Figure 1 illustrates a particular hyperbolicity cone. ⇒ λx ∈ Λ++.It is immediate from homogeneity and the deﬁnition above that λ > 0, x ∈ Λ++ Thus, we call Λ++ the hyperbolicity cone associated to p, and denote its closure by Λ+. As we will see shortly, it turns out that these cones are actually convex cones. We prove this following the arguments in Renegar [Ren]; the original results are due to G˚ ar59].arding [G˚Lemma 3. The hyperbolicity cone Λ++ is the connected component of p(x) > 0 that includes e. Example 4. The hyperbolicity cone Λ++ associated with the polynomial x1x2 · · · xn discussed in Exam-ple 2 is the open positive orthant {x ∈ Rn xi > 0}.|The ﬁrst step is to show that we can replace e with any vector in the hyperbolicity cone. Lemma 5. If p(x) is hyperbolic with respect to e, then it is also hyperbolic with respect to every direction v ∈ Λ++. Furthermore, the hyperbolicity cones are the same. 7-1��3Figure 1: Hyperbolicity cone corresponding to the polynomial p(x, y, z) = 4xyz + xz2 + yz2 + 2z −2x3 − 3zx − y3 − 3zy2 . This polynomial is hyperbolic with resp ect to (0, 0, 1). Proof. By Lemma 3 we have p(v) > 0. We need to show that for every x ∈ Rn , the polynomial β �→ p(βv + x) has only real roots if v ∈ Λ++. Let α > 0 be ﬁxed, and consider the polynomial β �→ p(αie + βv + γx), where i is the imaginary unit. We claim that if γ ≥ 0, this polynomial has only roots in the lower half-plane. Let’s look at the γ = 0 case ﬁrst. It is clear that β �→ p(αie + βv) cannot have a root at β = 0, since p(αie) = (αi)dp(e) = 0. If β = 0, we can write p(αie + βv) = 0 p(αβ−1ie + v) = 0 αβ−1i < 0 ⇒ β ∈ iR−,⇔ ⇒ and thus the roots of this polynomial are on the strict negative imaginary axis (we have used v ∈ Λ++ in the second implication). If by increasing γ there is ever a root in the upper half-plane, then there must exist a γ� for which β �→ p(αie + βv + γ�x) has a real root β�, and thus p(αie + β�v + γ�x) = 0. However, this contradicts hyp erbolicity, s ince β�v+γ�x ∈ Rn. Thus, for all γ ≥ 0, the roots of β �→ p(αie+βv+γx) are in the lower half-plane. The conclusion above was true for any α > 0. Letting α → 0, by continuity of the roots we have that the polynomial β �→ p(βv + γx) must also have its roots in the lower closed half-plane. However, since it is a polynomial with real coeﬃcients (and therefore its roots always appear in complex-conjugate pairs), then all the roots must actually be real. Taking now γ = 1, we have that β �→ p(βv + x) has real roots for all x, or equivalently, p is hyperbolic in the direction v. The following result shows that this set is actually convex: Theorem 6 ([G˚ar59]). The hyperbolicity cone Λ++ is convex. Proof. We want to show that u, v ∈ Λ++, β, γ > 0 implies that βu + γv ∈ Λ++. The previous result implies that we can always assume v = e. But then the ro ots of t �→ p(βu+γe−te) are just a nonnegative aﬃne scaling of the roots of t �→ p(u − te), since p(u − t�e) = 0 ⇔ p(βu + γe − (βt� + γ)e) = 0, and u ∈ Λ++ implies that t� > 0, hence βt� + γ > 0, and as a consequence, βu + γe ∈ Λ++. 7-2�� � � � � � � � � � � � � � � � � Hyperbolic polynomials are of interest in convex optimization, b ecause they unify in a quite appealing way many facts about the most important tractable classes: linear, second order, and semideﬁnite programming. n 22Example 7 (SOCP). Let p(x) = xn+1 − k=1 xk . This is a homogeneous quadratic polynomial, hyper-bolic in the direction e = (0, . . . , 0, 1), since n n2 2 2 2 p(x − te) = (xn+1 − t)2 = t − 2txn+1 + xn+1 − ,xk xk− k=1 k=1 and the discriminant of this quadratic equation is equal to n n2 22

View Full Document