MIT OpenCourseWarehttp://ocw.mit.edu 6.854J / 18.415J Advanced Algorithms Fall 2008��For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms.18.415/6.854 Advanced Algorithms October 20, 2008 Lecture 12 - Ellipsoid algorithm Lecturer: Michel X. Goemans In this lecture we describe the ellipsoid algo rithm and show how it can be applied to the linear programming problem. 1 Ellipsoid algorithm 1.1 Definitions An ellipsoid is denoted by E(a, A) = {x ∈ Rn : (x − a)T A−1(x − a) ≤ 1}, with center a ∈ Rn and A ∈ Rn×m that is positive definite. Recall that A is symmetric if A = AT . A ma trix is positive definite if it is symmetric and ∀x 6= 0, we have xT Ax > 0. The inverse of a positive definite matrix is also positive definite. Symmetric matrices have only real eigenvalues, and positive definite matrices have only real positive eigenvalues. 1.2 Problem statement Given P ⊆ Rn bounded, closed, convex, find x ∈ P or show that P = ∅. 1.2.1 Assumption: Separation oracle The first issue is how the convex set P is given. We assume that we have a “separation oracle” for P which doe s the following. Given a, the oracle either 1. affirms that a ∈ P , or 2. outputs c ∈ Rn such that P ⊆ {x ∈ Rn : cT x < cT a}. Think of c as the normal vector of the plane separa ting a and P , pointing away from P . Such a hyperplane exists beca use P is c onvex and closed. An algorithm for our problem would be judged based on how many times it queries the orac le. We would like the number of quer ies to be polynomial in terms of the input data. 1.2.2 Assumption: Outer ball and minimum volume As such, the problem is hop e less, since we do not know where to search for a point x ∈ P , and P may even contain just a single point x. So we make two further assumptions. They are • P ⊆ “big ball”, i.e. P ⊆ B(0, R), a ball with center 0 and radius R > 0. This tell us where out search can be confined. • If P 6= ∅, P has “sufficient” volume. Let’s say we are given r > 0 such that we are guaranteed that P contains some ball of radius r if P is non-empty. We consider the size of our input to be n + log R − log r. 12 - Ellipsoid algorithm-11.3 Sketch of the algorithm Here is an outline of the ellipsoid a lgorithm: • Start with ellipsoid E0 = (a0, A0). • Maintain an e llipsoid Ek = (ak, Ak) ⊇ P . At iteration k, ask the oracle if ak belongs to P . – If answer is yes, then we are done. – If ak does not belong to P , then the oracle provides a ck such that P ⊆ {x ∈ Rn : cT x < c Tk ak}. Thus, the separating hyperplane slices Ek and P is on one side of this hype rplane. We then determine a smaller ellipsoid Ek+1 such that Ek+1 ⊇ Ek ∩ {x : c Tk x < cTk ak}. (1) – (Refer to Fig. (1)). – Notice that Ek ⊇ P and we iterate on. If we can show that volume of Ek+1 decays exp onentially, then in “few” iterations, we either find a point in P , or reach Vol(Ek+1) < Vol(B(0, r)) and co nclude that P = ∅. Ek Ek+1 ck P ak Figure 1: Diagram illustrating a single iteration of the ellipsoid algorithm. 1.4 Bounding volume of ellipsoids Proposition 1 Given Ek = E(ak, Ak) and ck, we can find Ek+1 such that Eq. (1) is satisfied and Vol(Ek+1) � 1 � < exp − . Vol(Ek ) 2(n + 1) Let us fir st focus on the simple case in which our ellipsoid is the unit ball centered at the origin. Claim 2 Proposition 1 holds for the special case where Ek = E(0, I) and ck = −e1. 12 - Ellipsoid algorithm-2� � � � � � Proof: By symmetry, Ek+1 is an axis-aligned ellipsoid with center along the x1 axis. It has to contain all points with x1 = 0. See Fig. (2). Formally, we want Ek+1 ⊇ Ek ∩ {x : x1 ≥ 0}, and one can show that it is enough to guar antee that (i) e1 ∈ Ek+1 and (ii) for all x with kxk = 1 and x1 = 0, we have x ∈ Ek+1. ck=−e1 P Ek=E(0,I) Ek+1 0 Figure 2: Diagram illustrating the case where Ek = E(0, I). We propose the following �� �2 � �2 n � n + 1 1 n 2 − 1 � 2Ek+1 = x : x1 − + xi ≤ 1 n n + 1 n2 i=2 � 1 n2 � 2 T �� = Ee1, I − e1e1 . n + 1 n2 − 1 n + 1 It is easy to verify that this ellipsoid satisfies the constraints above. Since the volume of an ellipsoid is proportional to the product of its axis lengths, we obtain: Vol(Ek+1) n n2 n−1 Vol(Ek )= n + 1 · ( n2 − 1) 2 11 n − 1 < exp − exp n + 1 n2 − 1 2 1 = exp − ,2(n + 1) where we have used the fact tha t 1 + x < ex whenever x =6 0 (for x = 0 we have equality). � Next, we do a slightly mor e general case. Claim 3 Proposition 1 holds when Ek = E(0, I), ck = d and kdk = 1. Proof: From the pr evious simple case, it is clear that the following Ek+1 works. � 2 � �� 1 n 2 Ek+1 = E − d, I − ddT . n + 1 n2 − 1 n + 1 12 - Ellipsoid algorithm-3� � Proof of Proposition 1: In general, we can transform E(ak, Ak) to E(0, I) and map ck into some d. We can then find an ′ellipsoid E as in the proof of Claims 2 and 3, and ma p it back to obtain Ek+1. Denote the linear transformation that maps E(ak, Ak) into E(0, I) as T . Here is a picture: T Ek → E(0, 1) ↓ T −1 ′ Ek+1 ← E Recall that we have E(a, A) = {x : (x − a)T A−1(x − a) ≤ 1}. By Cholesky decomposition (since A is positive definite), we can write A = BT B for some matr ix B. If we let y = (B−1)T (x − 1), then we have (x − a)T B−1(B−1)T (x − a) ≤ 1 (⇔) y T y ≤ 1, so we have a unit ball in the y space. Thus, our linear transfor mation T and its inverse are : T (x) = y = (B−1)T (x − ak), T −1(y) = ak + BT y. We need an equivalent “half-space” constraint after applying T . From Eq. (1), …