Question? Leave a message!




ellipsoid algorithm

ellipsoid algorithm
Dr.TomHunt Profile Pic
Dr.TomHunt,United States,Teacher
Published Date:23-07-2017
Website URL
Comment
LINEAR PROGRAMMING III ellipsoid algorithm ‣ combinatorial optimization ‣ matrix games ‣ open problems ‣ Lecture slides by Kevin Wayne Last updated on 5/15/17 10:36 AMLINEAR PROGRAMMING III ellipsoid algorithm ‣ Combinatorial optimization ‣ Matrix games ‣ Open problems ‣ Lecture notes on the ellipsoid algorithm by Michel X. Goemans
 http://math.mit.edu/goemans/18433S07/ellipsoid.pdfGeometric divide-and-conquer To find a point in P: P 3Geometric divide-and-conquer To find a point in P: Maintain ellipsoid E containing P. ・ E P 4Geometric divide-and-conquer To find a point in P: and consider corresponding
 half-ellipsoid ½ E = E ∩ H Maintain ellipsoid E containing P. ・ If center of ellipsoid z is in P stop;
 ・ otherwise find hyperplane separating z from P. separating
 hyperplane H E P z 5Geometric divide-and-conquer To find a point in P: Maintain ellipsoid E containing P. ・ If center of ellipsoid z is in P stop;
 ・ otherwise find hyperplane separating z from P. Find smallest ellipsoid E' containing half-ellipsoid. ・ separating
 Lowner–John ellipsoid hyperplane H E' E P z 6Geometric divide-and-conquer To find a point in P: Maintain ellipsoid E containing P. ・ If center of ellipsoid z is in P stop;
 ・ otherwise find hyperplane separating z from P. Find smallest ellipsoid E' containing half-ellipsoid. ・ Repeat. ・ E' P 7Optimization to feasibility Standard form. T maxc x s. t. Ax = b x ≥ 0 € Ax ≤ b form. ∃ x, y s. t. Ax ≤ b Ax ≤ b −Ax ≤ −b x ≥ 0 −x ≤ 0 T dual feasible A y ≤ c T T optimal c x − b y ≤ 0 € 8Ellipsoid algorithm m×n m n Goal. Given A ∈ ℜ and b ∈ ℜ , find x ∈ ℜ such that Ax ≤ b. P Ellipsoid algorithm. Let E be an ellipsoid containing P. ・ 0 enumerate constraints k = 0. ・ k k While center z of ellipsoid E is not in P : ・ k - find a constraint, say a⋅ x ≤ β, that is violated by z k+1 k k - let E be min volume ellipsoid containing E ∩ x : a⋅ x ≤ a⋅ z - k = k + 1 easy to compute half-ellipsoid ½ E a · x ≤ β k a · x ≤ a · z k+1 E P k z k E 9Shrinking lemma n×n n Ellipsoid. Given D ∈ ℜ positive definite and z ∈ ℜ , then n T −1 E = x∈ℜ : (x−z) D (x−z) ≤ 1 is an ellipsoid centered on z with vol(E) = det(D) × vol(B(0, 1)) € unit sphere € Key lemma. Every half-ellipsoid ½ E is contained in an ellipsoid E'
 – 1/(2n+1) with vol(E') / vol(E) ≤ e . H E' ½ E z 10Shrinking lemma: unit sphere Special case. E = unit sphere, H = x : x ≥ 0 . 1 n n 2 2 2 2 2 n+1 1 n − 1 E = x : (x ) ≤ 1 E " = x : (x − ) + (x ) ≤ 1 ∑ ∑ ( ) i 1 2 i n n+1 n i=1 i=2 Claim. E' is an ellipsoid containing ½ E = E ∩ H. € € Pf. If x ∈ ½ E: 2 2 2 n " % " % n +1 1 n −1 2 x − + x ' ' ∑ 1 i 2 & & n n+1 n i=2 x ≥ 0 1 2 2 2 n " % n + 2n +1 n +1 2x 1 n −1 2 2 1 = x − + + x ' ∑ 1 i 2 2 2 & n n n+1 n n i=2 2 n 2n + 2 2n + 2 1 n −1 2 2 = x − x + + x ∑ 1 1 i 2 2 2 2 n n n n i=1 2 n ½ E 2n + 2 1 n −1 2 = x (x −1) + + x ∑ 1 1 i 2 2 2 n n n i=1 2 1 n −1 E ≤ 0 + + 2 2 n n = 1 2 ∑ x ≤ 1 0 ≤ x ≤ 1 i 1 E' 11 € Shrinking lemma: unit sphere Special case. E = unit sphere, H = x : x ≥ 0 . 1 n n 2 2 2 2 2 n+1 1 n − 1 E = x : (x ) ≤ 1 E " = x : (x − ) + (x ) ≤ 1 ∑ ∑ ( ) i 1 2 i n n+1 n i=1 i=2 Claim. E' is an ellipsoid containing ½ E = E ∩ H. € € Pf. Volume of ellipsoid is proportional to side lengths: n−1 vol(E ") 2 2 n n = 2 ( ) ( ) x ≥ 0 n − 1 n +1 1 vol(E) n−1 2 1 1 = 1 + 1 − ( 2 ) ( ) n − 1 n +1 1 n−1 −1 2 n −1 2 n+1 ≤ e e −1 ½ E 2( n+1) = e x 1 + x ≤ e E € E' 12Shrinking lemma Shrinking lemma. The min volume ellipsoid containing the
 half-ellipsoid ½ E = E ∩ x : a⋅ x ≤ a⋅ z is defined by: 2 T ' 1 Da n 2 Daa D z " = z − , D " = D − & ) 2 T T n +1 n −1 n +1 a Da % ( a Da n T −1 E " = x∈ℜ : (x− z ") (D ") (x− z ") ≤ 1 – 1/(2n+1) Moreover, vol(E') / vol(E) e . € € Pf sketch. We proved E = unit sphere, H = x : x ≥ 0 ・ 1 Ellipsoids are affine transformations of unit spheres. ・ Volume ratios are preserved under affine transformations. ・ H E' z ½ E 13Shrinking lemma Shrinking lemma. The min volume ellipsoid containing the
 half-ellipsoid ½ E = E ∩ x : a⋅ x ≤ a⋅ z is defined by: 2 T ' 1 Da n 2 Daa D z " = z − , D " = D − & ) 2 T T n +1 n −1 n +1 a Da % ( a Da n T −1 E " = x∈ℜ : (x− z ") (D ") (x− z ") ≤ 1 – 1/(2n+1) Moreover, vol(E') / vol(E) e . € € Corollary. Ellipsoid algorithm terminates after at most
 2(n+1) ln (vol(E ) / vol(P)) steps. 0 14Ellipsoid algorithm Theorem. LP is in P. Pf sketch. Shrinking lemma. ・ cnL Set initial ellipsoid E so that vol(E ) ≤ 2 . ・ 0 0 -cnL Perturb Ax ≤ b to Ax ≤ b + ε ⇒ either P is empty or vol(P) ≥ 2 . ・ Bit complexity (to deal with square roots). ・ Purify to vertex solution. ・ Caveat. This is a theoretical result. Do not implement. 3 O(mn L) arithmetic ops on numbers of size O(L),
 where L = number of bits to encode input 15LINEAR PROGRAMMING III ellipsoid algorithm ‣ combinatorial optimization ‣ matrix games ‣ open problems ‣ Lecture notes on the ellipsoid algorithm by Michel X. Goemans
 http://math.mit.edu/goemans/18433S07/ellipsoid.pdfSeparation oracle n Separation oracle. Given x ∈ ℜ , assert x is in P or return a
 separating hyperplane. n n Theorem. Let S ⊆ 0, 1 , P = conv(S), and c ∈ Z . Assume that P is full- T dimensional. There exists an algorithm that finds min c x : x ∈ P using a poly number of ops and calls to separation oracle for P. Remark. Don't need a polynomial representation of P. 17Min s-t cut problem Min s-t cut. Given digraph G = (V, E), distinguished vertices s and t, and edge costs c 0, find a min weight set of edges that intersects every s-t e path. T min c x s. t. x ≥ 1 ∀ s−t paths P ∑ e e ∈ P x ≥ 0 e exponentially
 many constraints € Separation oracle. Shortest s-t path with weights x . e 18Min cost arborescence problem Min cost arborescene. Given digraph G = (V, E), distinguished vertex r, and edge costs c 0, find a subgraph of G that contains a directed path from r e to all other vertices. T min c x s. t. x ≥ 1 ∀S⊆V where r∈S ∑ e e = (i, j) ∈ E i∈S, j∉S exponentially
 x ≥ 0 many constraints e € Separation oracle. Perform at most n – 1 min cut procedures with r as the source and edge weights x . e Note. Faster combinatorial algorithm exist. 19Ellipsoid and combinatorial optimization Grötschel–Lovász–Schrijver. Poly-time algorithms for: Network synthesis. ・ Matroid intersection. ・ Chinese postman problem. ・ Min weight perfect matching. ・ Minimize submodular set function. ・ Stability number of a perfect graph. ・ Covering of directed cuts of a digraph. ・ … ・ 20