Lecture 11: Polar of a Convex Body, Separating Hyperplanes, Norms and Convex Bodies, Banach-Mazur Distance, Fritz John’s Theorem

18.409 An Algorithmist’s Toolkit October 20, 2009 Lecture 11 Lecturer: Jonathan Kelner 1 Scribe: Chaithanya Bandi Outline Today we’ll introduce and discuss • Polar of a convex body. • Correspondence between norm functions and origin-symmetric bodies (and see how convex geometry can be a powerful tool for functional analysis). • Fritz-John’s Theorem 2 The Polar of a Polytope Given a bounded polytope C ⊂ Rn that contains the origin in its interior, we can represent C as C = {x|ai · x ≤ bi , i = 1, . . . , k}, where bi > 0. Without loss of generality, by appropriately scaling each constraint, we can assume bi = 1, ∀i = 1, . . . , k. Now the polar of C is given by C ∗ = conv(a1 , . . . , ak ). 2.1 Examples Let C be the square with corners at (1, 1), (1, −1), (−1, 1), (−1, −1). Then {ai } = {(1, 0), (0, 1), (−1, 0), (0, −1)}. The polar has corners at (1, 0), (0, 1), (−1, 0), (0, −1). Note that the polar is a square rotated and shrunk into a diamond. This polytope is also referred to as the ”cross polytope”. Note that the facets of C become the vertices of C ∗ and vice versa. For example, the three dimensional cube’s polar is the octahedron. Six facets and eight vertices correspond to eight facets and six vertices. The size and shape of a polar tends to be the reverse of that of the original set. For example, a short bulging rectangle with corners at (100, 3), (100, −3), (−100, 3), (−100, −3) would have a tall compressed polar with corners at (±1/100, 0), (0, ±1/3). Also note that polars of simplices are simplices. 2.2 Properties of a polar Some of the useful properties of a polar is summarised here. The properties will be illustrated using pictures. • (C ∗ )∗ = C (proof later). • If C is origin-symmetric, then so is C ∗ . • If A ⊆ B then B ∗ ⊆ A∗ . • If A is scaled up, then A∗ is scaled down. • If the polar is low-dimensional, that would mean the original polytope had to be unbounded in some directions. 11-1 • Translation has a very drastic effect on the polar. It can become unbounded just by translating the polytope. All these properties can be illustrated using the pictures below. 3 Polars of General Convex Bodies Any convex body can be thought of as the intersection of a (possibly infinite) set of half spaces. These are called ”‘suporting hyperplanes”’. Therefore, the polar of a convex body can be seen as the convex hull of a (possibly infinite) set of points, coming from all of the supporting hyperplanes. With this intuition one can guess about the following : • Polar of a sphere is a sphere. • Polar of a sphere of radius r is a sphere of radius 1/r. • Polar of an ellipse is an ellipse with axes reversed. Definition 1 The polar of a convex body C is given by C ∗ = {x ∈ Rn |x · c ≤ 1∀c ∈ C} We observe that this definition is equivalent to the previous definition. Proposition 2 For a polytope C given by C = {x|ai · x ≤ bi , i = 1, . . . , k}, the sets C1 = C2 where C1 = {x ∈ Rn |x · c ≤ 1∀c ∈ C} and C2 == conv(a1 , . . . , ak ). We skip the proof as it is easy to verify that if x ∈ C1 then x ∈ C2 and vice versa. We will now prove that (C ∗ )∗ = C. We would be needing the concept of a separating hyperplane for the proof which we introduce now. 3.1 Separating Hyperplanes Given a convex body K ⊆ Rn and a point p, a separating hyperplane for K and p is a hyperplane that has K on one side of it and p on the other. More formally, for a vector ν, the hyperplane H = {x|ν · x = 1} is a separating hyperplane for K and p if 1. ν · x ≤ 1 for all x ∈ K, and 2. ν · p ≥ 1. Note that if we replace the right hand side of both the above conditions by 0 or any other constant, we get an equivalent formulation. We call a separating hyperplane H a strongly separating hyperplane if the second inequality is strict. Theorem 3 Separating Hyperplane Theorem: If K is a convex body and p is a point not contained in K, then there exists a hyperplane that strongly separates them. Proof We’ll sketch an outline of the proof. It can be made rigorous. Consider a point x ∈ K that is the closest to p in �2 distance. Consider the plane H that is perpendicular to the line joining x to p and is passing through the midpoint of x and p. H must separate K from p because if there is some point of K, say y, that is on the same side of H as p, then we can use the convexity of K to conclude that the point x� which is the intersection of the hyperplane with the line joining x and y is also in K. x� is closer to p that x since px� forms the side of a right angled triangle of which xp is the hypotenuse. This contradicts the assumption that x is the point closest to p. 11-2 3.2 Polar of a Polar We’ll use the above result to show why the polar of the polar of a convex body is the body itself. Recall that for a convex body K, we had defined its polar K ∗ to be {p|k · p ≤ 1∀k ∈ K}. Theorem 4 Let K be a convex body. Then K ∗∗ = K. Proof We know that K ∗ = {p|k · p ≤ 1∀k ∈ K}. Similarly K ∗∗ = {y|p · y ≤ 1∀p ∈ k ∗ }. Let y be any point in K. Then, by the definition of the polar, for all p ∈ K ∗ we have that p · y ≤ 1. The definition of the polar of K ∗ implies that y ∈ k ∗∗ . Since this is true for every y ∈ K, we conclude that K ⊆ K ∗∗ . The other direction of the proof is the nontrivial one and we’ll have to use the convexity of the body and the separating hyperplane theorem. If possible, let y be such that y ∈ K ∗∗ and y �∈ K. Since y ∈ K ∗∗ , we have that P · y ≤ 1∀p ∈ K ∗ . Since y �∈ K, there exists a strongly separating hyperplane for y and K. Let it be H = {x|v · x = 1}. By the definition of separating hyperplane, we have v · k ≤ 1∀k ∈ K. Hence, v ∈ K ∗ . Also, v · y > 1 (since H is a separating hyperplane), and we just showed that v ∈ K ∗ . This contradicts our assumption that y ∈ K ∗∗ . Hence K ∗∗ ⊆ K. 4 Norms and Symmetric Convex Bodies We will show how norms and symmetric convex bodies co-exist. This provides us a way to use the results of Convex Geometry in Functional Analysis and vice versa. Recall that a norm on Rn is a map q : Rn → R such that: 1. q(ax) = aq(x) for a ∈ R (homogeneity) 2. q(x + y) ≤ q(x) + q(y) (triangle inequality) 3. q(x) ≥ 0 for all x (nonnegativity) (actually implied by 1 and 2) 4. q(x) = 0 if and only if x = 0 (positivity) (without this conditions, q is a ”seminorm”) Note that given a norm, one can construct a convex body. The simplest being the unit ball Bq = {x ∈ Rn |q(x) ≤ 1}. It is an easy exercise to verify the convexity of Bq . Also as we will show now, given a convex body C, we can come up with a norm under which C is the unit ball. Note that C has to be origin symmetric. Definition 5 The Minkowski functional of an origin symmetric convex body C is the map pC : Rn → R defined by pC (x) = inf {x ∈ λC} λ>0 (We will sometimes denote this by ||x||C , because it is a norm.) To prove that this is a norm, one needs to verify the properties of homogeneity, triangle inequality etc. These follow from the convexity of the body. 4.1 Norms, Duals, and the Polar For any norm q, we can define its dual by q ∗ (x) = supv=0 | qv(·vx) |. It is an exercise to see that the unit ball � with respect to the dual norm of q is the polar of the unit ball with respect to q. This provides us a direct relation between convex geometry and functional analysis. 11-3 The following pictures allow us to have a geometric intuition of the norms and their duals. 11-4 11-5 5 Banach–Mazur Distance Recall from last time the definition of the Banach–Mazur distance between two convex bodies: Definition 6 Let K and L be two convex bodies. The Banach–Mazur distance d(K, L) is the least positive d ∈ R for which theres a linear image L� of L such that L� ⊆ K ⊆ dL� , where dL� is the convex body obtained by multiplying every vector in L� by the scalar d. Observe that the above definition takes into consideration only the intrinsic shape of the body, and it is independent of any particular choice of coordinate system. Also observe that the Banach–Mazur distance is symmetric in it’s input arguments. If L ⊆ K ⊆ dL, then by scaling everything by d, we get that dL� ⊆ dK. Hence K ⊆ dL� ⊆ dK, which implies the symmetry property. 6 Fritz John’s Theorem Let B2n denote the n-dimensional unit ball. For any two convex bodies K and K � , let d(K, K � ) denote the Banach–Mazur distance between them. In the rest of this lecture, we’ll state and prove the Fritz John’s theorem. √ Theorem 7 For any n-dimensional, origin-symmetric convex body K, d(K, B2n ) ≤ n. 11-6 In other words, the theorem√states that for every origin-symmetric convex body K, there exists some ellipsoid E such that E ⊆ K ⊆ nE. We’ll prove that the ellipsoid of maximal volume that is contained in K will satisfy the above containment. √ Informally, √ the theorem says that up to a factor of n, every convex body looks like a ball. The above bound of n is tight for the cube. If we didn’t require the condition that K is origin symmetric, then the bound would be n, which would be tight for a simplex. The theorem can √ also be rephrased as the following: There exists a change of the coordinate basis for which B2n ⊆ K ⊆ nB2n . Theorem 8 Let K be an origin-symmetric convex body. Then K contains a unique ellipsoid of maximal volume. Moreover, this largest ellipsoid is B2n if and only if the following conditions hold: • B2n ⊆ K • There are unit vectors u1 , u2 , . . . , um on the boundary of K and positive real numbers c1 , c2 , . . . , cm such that �m 1. i=1 ci ui = 0, and �m 2. for all vectors x, i=1 ci �x, ui �2 = |x|2 . n Since the ui are unit vectors, �m they are points on the convex body K that also belong to the sphere B2 . Also, the first identity, i.e. i=1 ci ui = 0, is actually redundant, since for origin symmetric bodies it can be derived from the second identity. This is because for every ui , it’s reflection in the origin is also contained in K ∩ B2n . The second identity says that the contact points (of the sphere with K) act somewhat like an orthonormal basis. They can be weighted so that they are completely isotropic. In other words, the points are not concentrated near some proper subspace, but are pretty evenly spread out in all directions. Together they mean that the ui can be weighted so that their center of mass is the origin and their inertia tensor is the identity. Also, a simple rank argument shows that there need to be at least n such contact points, since the second identity can only hold for x in the span of the ui . 6.1 Proof Proof of John’s Theorem As part of the proof of John’s Theorem, we’ll prove the following things: 1. If there exist contact points {ui } as required in the statement of Theorem 8, then B2n is the unique ellipsoid of maximal volume that is contained in K. 2. If B2n is the unique ellipsoid of maximal volume that is contained in K, then there exist points {ui } such that they satisfy the two identities in Theorem 8. Proof of 1: We are given of K and positive real numbers �m unit vectors u1 , u2 , . . . , um on the �boundary m c1 , c2 , . . . , cm such that i=1 ci ui = 0, and for all vectors x, i=1 ci �x, ui �2 = |x|2 . We wish to show that B2n is the unique ellipsoid of maximal volume that is contained in K. Observe that it suffices to show that among all axis-aligned ellipsoids contained in K, B2n is the unique ellipsoid of maximal volume. This is because what we are trying to prove doesn’t mention any basis and is only in terms of dot-products. Hence, since the statement will remain true under rotations, proving it for axis-aligned ellipsoids is enough. For each ui we have that for all k ∈ K, ui · k ≤ 1. Hence ui ∈ K ∗ . Let E be any axis-aligned ellipsoid such that E ∈ K. Then K ∗ ⊆ E ∗ . Hence {u1 , u2 , . . . , um } ⊆ E ∗ . Since E is axis-aligned, it is of the form �n x2 {x| i=1 αi2 ≤ 1}. i �n �n V ol(E)/V ol(B2n ) = i=1 αi . Therefore, to show that V ol(E) < V ol(B2n ), we must show that i=1 αi < 1 for any such E which is not B2n . 11-7 �n ∗ 2 2 Observe �m thatT E = {Y | i=1 αi yi ≤ 1}. Also, condition 2 of Theorem 8 is equivalent to the follow­ ing: �i=1 ci ui ui = Id since ui · ui = 1, we have �nn, where Idn is the identity matrix of size n. �Now, m n Trace( i=1 ci ui uTi ) = i=1 ci . Since Trace(Idn ) = n, this implies that i=1 ci = n. the other coordinates. Clearly Let ej denote the vector which has a 1 in the ith coordinate and 0 in � n �ui , ej � is the j th coordinate of ui . For i ≤ i ≤ m, since ui ∈ E ∗ , we get that j=1 αi2 �ui , ej �2 ≤ 1. Summing it over all i, we get m � n n � � αi2 �ui , ej �2 ≤ ci = n. i=1 j=1 i=1 �m �n However, since by condition 2 of Theorem 8, i=1 �ui , ej �2 = |ej |2 , we get i=1 αi2 ≤ n. By the AM-GM P n 2 �n �n i=1 αi inequality, we get that ( i=1 αi2 )1/n ≤ ≤ 1, which implies that i=1 αi ≤ 1. Equality only holds if �n n all the αi are equal. This shows that i=1 αi < 1 for any such E which is not B2n , completing the first part of the proof. Proof of 2: Assume that we are give that B2n is the unique ellipsoid of maximal volume that is contained in K. We want to show that for some �m m, there exist ci and ui for 1 ≤ i ≤ m (as in the statement of Theorem 8), such that for all vectors x, i=1 ci �x, ui �2 = |x|2 . This is equivalent to showing that m � ci ui uTi = Idn . i=1 �m Also, taking trace of both � sides, we get that i=1 ci = n. We already observed that for origin-symmetric m bodies, the condition that i=1 ci ui = 0, is implied by the previous condition. T Let Ui = ui ui . Also, observe that we can view the space of n × n matrices as a vector of n2 real numbers. �m 2 Hence we can parametrize the space of n × n matrices by Rn . Hence i=1 ci ui uTi = Idn means that Idn /n is in the convex hull of the Ui (recall that the�ci are positive and sum to 1). m If possible, let there be no ci , ui such that i=1 ci ui uTi = Idn . This means that Idn /n is not in the convex hull of the Ui . Hence, there must be a separating hyperplane H in the space of matrices that separates Idn /n from the convex hull of the Ui . � 2 For two n × n matrices A and B, let A • B denote their dot product in Rn , i.e. A • B = i,j Aij · Bij . Thus, the separating hyperplane is a matrix H such that ∀A ∈ conv(Ui ), A • H ≥ 1, and Idn /n • H < 1. Let t = Trace(H) = H • Idn . Let H � = H − t/n(Idn ). Then Idn /n • H � = Idn /n • (H − t/nIdn ) = t/n − (Idn /n • t/nIdn ) = 0. Similarly, since ∀A ∈ conv(Ui ), Trace(A) = 1, we get that A • H � > 0. Hence, H � is such that: 1. Trace(H � ) = 0, and 2. H � • (ui uTi ) > 0 for all i. Now, let Eδ = {x ∈ Rn |xT (Idn + δH � )x ≤ 1. For all i, we have uTi (Idn + δH � )ui = 1 + δuTi H � ui > 1, since H • (ui uTi ) > 0 ⇒ uTi H � ui > 0. Hence ui �∈ Eδ . Also, since H � • (ui uTi ) > 0 for all i, by compactness, there exists � > 0 such that for all matrices w in the �-neighborhood of the set of all ui satisfy H � • (wwT ) > 0. Hence, by the previous argument, any such w is not contained in Eδ . Note that when δ = 0, we get the unit ball B2n . For every δ > 0 we have that for all w in the �­ neighborhood of the contact points of B2n , w �∈ Eδ . Hence, as we increase δ continuously starting from 0, the continuity of the transformation of Eδ implies that for sufficiently small δ, boundary(K) ∩ Eδ = φ. Hence ∃�� > 0 such that (1 + �� )Eδ ⊆ K. Therefore, to conclude the proof, it suffices to show that V ol(Eδ ≥ V ol(B2n ). �n −1 Let λ1 , λ2 , . . . , λn be the eigenvalues of Idn + δH � . Since V ol(Eδ = ( i=1 � �nλi ) , to show that V ol(E� δ ≥ n n V ol(B2 ), we need to show that i=1 λi ≤ 1.�However we know n + δH ) = i=1 λi = Trace(Id �n that �n n Trace(Idn ) = n. By the AM-GM inequality, ( i=1 λi )1/n ≤ ( i=1 λi )/n = 1. Hence i=1 λi ≤ 1. This concludes the proof of part 2. To wrap up the proof of John’s Theorem, assume without loss of generality that B2n is the ellipsoid of maximal volume contained in K. We can make this assumption since the particular choice of basis is not � 11-8 √ important for the proof. We need to show that B2n ⊆ K ⊆ nB2n . Now, for all x ∈ K, we√have x · ui ≤ 1 for � � √ n all i. Hence, |x|2 = ci (x · ui )2 ≤ ci = n. This shows that |x| ≤ n, and hence K ⊆ B 2 . Thus, we have proven the existence of an ellipse E such that √ E ⊆ K ⊆ nE. 11-9