# ellipsoid algorithm

###### ellipsoid algorithm
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 divideandconquer To find a point in P: P 3Geometric divideandconquer To find a point in P: Maintain ellipsoid E containing P. ・ E P 4Geometric divideandconquer To find a point in P: and consider corresponding  halfellipsoid ½ 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 divideandconquer 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 halfellipsoid. ・ separating  Lowner–John ellipsoid hyperplane H E' E P z 6Geometric divideandconquer 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 halfellipsoid. ・ 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 halfellipsoid ½ 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 halfellipsoid ½ 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  halfellipsoid ½ 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  halfellipsoid ½ 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 st cut problem Min st 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 st 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 st 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. Polytime 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. ・ … ・ 20Totally unimodular matrices m×n Def. A matrix A ∈ ℜ is totally unimodular if the determinant of each square submatrix is 0, +1, or −1. " 1 1 0 0 1 0 1 −1 −1 ' 1 0 1 1 ( ' −1 1 0 0 0 ( 0 1 1 0' ( 0 −1 −1 0 1 ' ' 1 1 0 1 yes no € € 21Totally unimodular matrices Theorem. If A is totally unimodular and b is integral, then every vertex of Ax = b, x ≥ 0 is integral. Pf. Each vertex is a solution to A x = b for invertible A .  B B Apply Cramer's rule. n n n × Cramer's rule. For B ∈ ℜ invertible, b ∈ ℜ ,  the solution to Bx = b is given by: det(B ) i x = i det(B) replace ith column of B with b 22 € Totally unimodular matrices Theorem. A (0, +1, −1) matrix is totally unimodular if it contains at most  one +1 and at most one −1 in each column. 1 0 1 −1 −1 ( −1 1 0 0 0 ( ( 0 −1 −1 0 1 ' € Pf. induction on size of a square submatrix B Base case: 1by1 matrix. ・ Case 1: a column of B is all 0s. ・ Case 2: a column of B has exactly one 1 (or one −1). ・ Case 3: all columns of B have exactly one 1 and one −1. ・ Ex. Network flow matrices. 23Assignment problem Assignment problem. Assign n jobs to n machines to minimize total cost, where c = cost of assignment job j to machine i. ij 1' 2' 3' 4' 5' 1' 2' 3' 4' 5' 1 1 3 8 9 15 10 3 8 9 15 10 2 2 4 10 7 16 14 4 10 7 16 14 3 3 9 13 11 19 10 9 13 11 19 10 4 4 8 13 12 20 13 8 13 12 20 13 5 5 1 7 5 11 9 1 7 5 11 9 cost = 3 + 10 + 11 + 20 + 9 = 53 cost = 8 + 7 + 20 + 8 + 11 = 44 24Assignment problem: LP formulation n n (P) min c x ∑ ∑ ij ij i=1 j=1 Interpretation: if x = 1,  n ij s. t. x = 1 1≤ i≤ n ∑ then assign job j to machine i ij j=1 m x = 1 1≤ j≤ n ∑ ij i=1 x ≥ 0 1≤ i, j ≤ n ij € Theorem. Birkhoff 1946, von Neumann 1953 All vertices of the above polyhedron are 0–1valued. Pf. Total unimodularity. Corollary. There exist polytime algorithm for assignment problem. 25LINEAR PROGRAMMING III ellipsoid algorithm ‣ combinatorial optimization ‣ matrix games ‣ open problems ‣Matrix games m n × Matrix game. For A ∈ ℜ , define a game for two players. ■ Row player A selects one of rows i = 1, 2, …, m. ■ Column player B selects one of columns j = 1, 2, …, n. ■ Payoff to row player is a . ij column player B 1 2 1 2 +3 row player A 2 +3 4 Ex. A plays row 2: B plays column 2; A loses 4. Ex. A plays row 1: B plays column 1; A loses 2. A can guarantee to lose at most 2. 27Matrix games m n × Matrix game. For A ∈ ℜ , define a game for two players. ■ Row player A selects one of rows i = 1, 2, …, m. ■ Column player B selects one of columns j = 1, 2, …, n. ■ Payoff to row player is a . ij column player B 1 2 1 2 +3 row player A 2 +3 4 Ex. A plays row 1 with prob 3/5 and row 2 with prob 2/5. B plays column 1: A wins = 2(3/5) + 3(2/5) = 0. ・ B plays column 2: A wins = +3(3/5) 4(2/5) = 1/5. ・ A can guarantee to lose at most 0 (in expectation). 28Matrix games m n × Matrix game. For A ∈ ℜ , define a game for two players. ■ Row player A selects one of rows i = 1, 2, …, m. ■ Column player B selects one of columns j = 1, 2, …, n. ■ Payoff to row player is a . ij column player B 1 2 1 2 +3 row player A 2 +3 4 Ex. A plays row 1 with prob 7/12 and row 2 with prob 5/12. B plays column 1: A wins = 2(7/12) + 3(5/12) = 1/12 on average. ・ B plays column 2: A wins = +3(7/12) 4(5/12) = 1/12 on average. ・ A can guarantee to win 1/12 in expectation. 29Matrix games m n × Matrix game. For A ∈ ℜ , define a game for two players. ■ Row player A selects one of rows i = 1, 2, …, m. ■ Column player B selects one of columns j = 1, 2, …, n. ■ Payoff to row player is a . ij column player B 1 2 1 2 +3 row player A 2 +3 4 Ex. B plays column 1 with prob 7/12 and column 2 with prob 5/12. A plays row 1: B loses = 2(7/12) + 3(5/12) = 1/12 on average. ・ A plays row 2: B loses = +3(7/12) 4(5/12) = 1/12 on average. ・ B can guarantee to lose at most 1/12. 30Matrix games m n × Matrix game. For A ∈ ℜ , define a game for two players. ■ Row player A selects one of rows i = 1, 2, …, m. ■ Column player B selects one of columns j = 1, 2, …, n. ■ Payoff to row player is a . ij Pure strategy. Player chooses a given row (or column). Mixed strategy. Player chooses a row (or column) at random, according to some probability distribution x ∈ Δ (or y ∈ Δ ). m n m n T p ' a x y = y Ax ∑ ∑ p ij i j Expected payoff. Δ = z∈ℜ : z =1, z ≥ 0 ( + ∑ p k k i=1 j=1 ) , k=1 stochastic vector € € 31Matrix games: LP formulation Row player strategy. If row player uses strategy x, he guarantees an T T expected payoff of so, goal is to find min y Ax max min y Ax y∈Δ x∈Δ y∈Δ n m n nested min max not linear in x, y € € Observation. If row player uses fixed strategy x, then column player wants to solve linear program: fixed vector T min y Ax n s. t. y = 1 ∑ j j=1 y ≥ 0 € All vertices of this LP are unit vectors (pure strategies). Thus m T min y Ax = min a x ∑ ij i y∈Δ j n i=1 32 € Matrix games: LP formulation Optimal strategy for row player: m (P) max min a x ∑ ij i x j i=1 m s. t. x = 1 ∑ i i=1 x ≥ 0 every optimal solution (x, z)  to (P) satisfies at least of one  these constraints with equality,  € Equivalent to following linear program: so z = ∑ a x ij j (P' ) max z x, z m s. t. a x ≥ z (j =1,2,...,n) ∑ ij i i=1 m x = 1 ∑ i i=1 x ≥ 0 (i =1,2,...,m) i 33 € Matrix games Optimal strategy for row player: (P' ) max z x, z m s. t. a x ≥ z ∑ ij i i=1 m x = 1 ∑ i i=1 x ≥ 0 i Optimal strategy for column player: € (D') min t y, t n s. t. a y ≤ t ∑ ij j j=1 n y = 1 ∑ j j=1 y ≥ 0 j € Observation. (P') and (D') are LP duals 34Minimax theorem m×n Theorem. von Neumann 1928 For every A ∈ ℜ , T T max min y Ax = min max y Ax x∈Δ y∈Δ y∈Δ x∈Δ m n n m Pf. LP duality. € Consequence. As long as your mixed strategy is optimal,  you can reveal it to your opponent. Theorem. Nash equilibrium exist for 2person zerosum games.  Moreover, they are polytime computable. 35Application: poker Kuhn's simplified poker. Deck of 3 cards, numbered 1, 2, and 3. ・ Each player antes 1. ・ One round of betting (1 bet). ・ If passpass, passbetbet, or betbet, player with higher card wins;  ・ otherwise player that bet wins. Strategies for X. Strategies for Y. 1. Pass no matter what X did. 1. Pass; if Y bets; pass. 2. If X passes, pass; if X bets, bet. 2. Pass; if Y bets, bet. 3. If X passes, bet; if X bets, pass. 3. Bet. 4. Bet no matter what X did. X Y 36Application: poker bluff 17 of time Optimal strategy for X. When dealt 1, mix strategies 1 and 3 in ratio 5:1. ・ When dealt 2, mix strategies 1 and 2 in ratio 1:1. ・ When dealt 3, mix strategies 2 and 3 in ratio 1:1. ・ trap 50 of time Optimal strategy for Y. When dealt 1, mix strategies 1 and 3 in ratio 2:1. ・ When dealt 2, mix strategies 1 and 2 in ratio 2:1. ・ bluff 33 of time When dealt 3, use strategy 4. ・ Value of game. −1/18 for X. Gambling lessons. Optimal strategies involve bluffing and trapping.  Player who acts last has advantage. 37LINEAR PROGRAMMING III ellipsoid algorithm ‣ combinatorial optimization ‣ matrix games ‣ open problems ‣Strongly polynomial An algorithm is strongly polynomial if: Elementary ops: +, –, , /, comparison. ・ ops is polynomial in the dimension of input. ・ Polynomial space on a classic TM. ・ Ex. Mergesort: O(n lg n). 2 Ex. Edmonds–Karp maxflow: O(m n ). 3 Ex. Gaussian elimination: O(n ) arithmetic ops. weakly polynomial 3 Ex. Ellipsoid: O(m n L ) arithmetic ops. 3 Ex. Ye's interior point method: O(n L ) arithmetic ops. Open problem. Stronglypolynomial algorithm for LP Open problem. Is LP in P ℜ 39New York Times article 40
Website URL
Comment
Presentations
Free
Category:
Presentations
User Name:
Dr.TomHunt
User Type:
Teacher
Country:
United States