New version page

MIT 6 972 - Hyperbolic polynomials

This preview shows page 1 out of 4 pages.

View Full Document
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 semidefinite 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 differential 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 satisfies α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 coefficients, we can consider Hn(d) as a normed vector space n+d−1of dimension .d Definition 1. Let e be a fixed 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 defined 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 definition 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 first 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 fixed, 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 first. 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 coefficients (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 affine 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 semidefinite 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
Loading Unlocking...
Login

Join to view Hyperbolic polynomials and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Hyperbolic polynomials and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?