Insights on Linear Programming and Pivoting Rules in Optimization
Linear programming involves maximizing a linear objective function within a set of linear constraints to find the optimal point in a polytope. The simplex algorithm, introduced by Dantzig in 1947, navigates through vertices to reach the optimal solution. Deterministic and randomized pivoting rules, like Random-Edge and Random-Facet, influence the efficiency of optimization processes. Concepts like the Hirsch Conjecture, Random-Facet as the fastest pivoting rule, and abstract objective functions contribute to understanding optimization in various domains.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Random-Edge is slower than Random-Facet on abstract cubes Thomas Dueholm Hansen Aarhus Univ. Uri Zwick Tel Aviv Univ. Hebrew University April 11, 2016
Linear Programming Maximize a linear objective function subject to a set of linear equalities and inequalities Find the highest point in a polytope/polyhedron
The Simplex Algorithm [Dantzig (1947)] Move up, from vertex to vertex, along edges, until reaching the top.
Deterministic pivoting rules Largest improvement Largest slope Dantzig s rule Largest modified cost Bland s rule avoids cycling Lexicographic rule also avoids cycling Zadeh s rule least recently entered All known to require an exponential number of steps, in the worst-case [Klee-Minty (1972)] , , [Amenta-Ziegler (1996)] [Friedmann (2011)]
Randomized pivoting rules Random-Edge Choose a random improving edge Random-Facet [Kalai (1992)] [Matou ek-Sharir-Welzl (1992)] To be described shortly Random-Facet is sub-exponential! Is Random-Edgesub-exponential??? Is Random-Edgefaster than Random-Facet?
Random-Facet Fastest known (randomized) pivoting rule ? = number of inequalities ? = number of variables = dimension Assume ? 2? ? ln? ? ? ln? ? ? ? ? ? 2 2 [Hansen-Z (2015)] (following [Kalai (1992)]) [Kalai (1992)] [MSW (1992)]
Hirsch Conjecture (1957) The diameter of a d-dimensional, n-faceted polytope is at most n d Refuted by [Santos (2010)]. Diameter is still believed to be polynomial. Quasi-polynomial upper bound [Kalai-Kleitman (1992)] ([Todd (2014)])
Abstract objective functions (AOFs) Acyclic Unique Sink Orientations (AUSOs) Every face has a unique sink
Klee-Minty cubes (1972) Figure taken from a paper by G rtner-Henk-Ziegler
AUSOs of n-cubes 2n facets 2n vertices AUSOs Williamon-Hoke (1988) Kalai (1998) Szab , Welzl (2001) G rtner (2002) Every subcube has a unique sink The diameter is exactly n No diameter issue!
Klee-Minty cubes (1972) 011 111 001 ??? 1 101 010 110 ??? 1 000 100 ???has a Hamiltonian path (Gray code). Random-Edge on ???takes (?2), w.h.p. [Balogh-Pemantle (2007)]
Turn-based 2-Player 0-Sum Stochastic Games [Shapley 53] [Gillette 57] [Condon 92] Total cost Discounted cost Limiting average cost Both players have optimal positional strategies. Can optimal strategies be found in polynomial time? Game (two actions per state) AUSO (of a cube) Random-Facet is the fastest known algorithm.
Random-Facet on the ?-cube [Ludwig (1995)] [G rtner (2002)] ?-th coordinate Start at some vertex ? of the ?-cube ?. Split the ?-cube into two (? 1)-cubes ?0 along a random coordinate ?. ?,?1 ? ? ? ? ? Recursively find the sink ? of the (? 1)-cube ?? ? containing ?. ? ? ?1 ?0 If ? is not the global sink, move to ? = ? e?. Recursively find the sink ? of the (? 1)-cube ?1 ? starting from ? . Exponential? Sub-exponential! The starting point ? of the second recursive call contains valuable information. ? containing ? ,
Random-Facet on the ?-cube [Ludwig (1995)] [G rtner (2002)] ? ? (After reordering the coordinates according to the hidden order.) All correct ! Would never be switched ! There is a hidden order of the indices under which the sink returned by the first recursive call correctly fixes the first i bits. The algorithm does not know the hidden order. But, choosing a coordinate that was fixed has no effect. Thus, the second recursive call is effectively on an (? ?)-cube.
Random-Facet on the ?-cube [Ludwig (1995)] [G rtner (2002)] ? ? (After reordering the coordinates according to the hidden order.) All correct ! Would never be switched ! ? 1 ? ? = ? ? 1 +1 1 + ? ? ? ? ?=1 ? ? ? 2? ?? ?!2= 1 ?! ? ? ? e2 ? ? ? = ?! ?=0 ?=0 ?=0
Lower bounds for Random-Edge 2 ?1/3 for AUSOs [Matou ek-Szab (2006)] 2 ?1/4 for LPs [Friedmann-Hansen-Z (2011)] 2 ?1/2 for AUSOs [here] The new lower bound is a simplification of the lower bound of Matou ek and Szab obtained by replacing the Klee-Minty cube, used as a building block, by a path AUSO. Two main building blocks: Product of AUSOs, Hypersink replacement Main part of the technical analysis: Random Walk with reshuffles (on a path AUSO)
A product (blowup) construction ? outmap vertex ?: 0,1? 0,1? ??: 0,1? 0,1? ? = ? ?? ? ?,? = (? ? ,??(y)) ?000 Adaptation of a slide by Tibor Szab .
Hypersink replacement Slide by Tibor Szab .
Randomized product + hypersink replacement outmap vertex ? ?: 0,1? 0,1? ?: 0,1? 0,1? ???? ? = 1? ? ? ? = ? ?? = ? ?? ?? obtained from ? by randomly permuting the indices. The copy of ? corresponding to ? = 1? is a hypersink. Replace it by a random translation? of ?. ? ? 11 Adaptation of a slide by Tibor Szab .
Random-Edge on a random product [Matou ek-Szab (2006)] Each step in ? = ? ?? is either a step in ?, i.e., ?,? (? ,?), or a step in ?x, i.e., ?,? ?,? . A step ?,? (? ,?) in ?, does not change ?, but changes the cube ? is in from ?? to ?? . As ?? is a random permutation of ?? , this corresponds to randomly permuting ?, a reshuffle. The induced process on ?, until ? = ???? ? , is exactly Random-Edge on ?. The induced process on ?, is a Random Walk with Reshuffles on ?. Once ? = ???? ? , the orientation on ? changes from ? to ? . As ? is a random translation of ? , ? is a completely random in ? . If ? reaches ????(?) before ? reaches ???? ? , we get two Random-Edge walks on ?.
Random-Edge on a random product [Matou ek-Szab (2006)] The probability of reshuffle in each step of Random-Reshuffle on ? depends on ?. (To be discussed later.) Lemma: If the probability that Random-Edge on ? makes less than ?steps is at most ?, and the probability that Random-Reshuffle on ? makes less than ? steps is at most ?, both starting from a random vertex, then the probability that Random-Edge, starting at a random vertex, makes less than 2? steps on ? ?? is at most 2? + ?.
Lower bound Construction [Matou ek-Szab (2006)] Let ? be an ?-AUSO. Compute randomized powers of ?. ?0= ? , ??= ?? 1 ?? ? = ??, where ? = ??, for some ? > 0. If Random-Reshuffle on ? is slow enough, then Random-Edge on ?, which is an ??2-AUSO, makes at least 2? steps, with high probability. In the last step, we need Random-Reshuffle on ? to make at least 2?? steps, with high probability. Matou ek-Szab take ? = ??? to be the Klee-Minty cube. Random-Reshuffle on Klee-Minty cubes is not slow enough Further complications. Lower bound becomes 2 ?1/3. Our modification: Take ? = ?? to be the path AUSO.
A path AUSO ? = ? + 1 ? ? ? 0 0 0 1 1 1 1 2 3 ? 1 1 1 1 1 A shortest paths problem gives rise to an AUSO. A vertex of the AUSO corresponds to a choice of an outgoing edge from each vertex of the graph. In this particular case, the ?-th bit wants to stay or become a 1 iff all preceding bits are 1.
Random-Reshuffle on a path AUSO ?in ? ?in ? 111100101 ? outdegree of ? in ? ? 1 ? number of leading 1s ? number of non-leading 1s Outdegree = ? + 1 ? 1 With probability ? = j+2, reshuffle ?. ?+?+1 1 ?+1, change the first 0 to 1, ?+1, change a random non-leading 1 to 0. Otherwise, with probability ? and probability 1 The reshuffle probability ? ?+2 chosen by an adversary.
Random-Reshuffle on a path AUSO ? number of leading 1s ? number of non-leading 1s type =(?,?) weight =? = ? + ? ?in ? 111100101 ? ? + 1 A reshuffle on a state of weight ? creates a state of type (?,?), where ? + ? = ?, with probability ? ? ? All states of type (?,?) are obtained with equal probabilities. The probability of increasing or decreasing ? depends only on (?,?). We thus obtain induced random walks on types, and then on weights.
?-cube 0,1? Types (?,?) Weights ? = ? + ? 0 1 2 3 ? Constant drift to the left Exponential time to reach ?.
Induced random walk on the line Slight complication: From (?,0), the probability of +1 is greater than . Solution: Consider two steps together. Basic step: Zero or more reshuffles, followed by a step in ?. Several reshuffles in a row are equivalent to a single reshuffle. The worst type of weight ? is (?,0).
Induced random walk on the line Probability of weight increase in one step from (?,?) ? is the reshuffle probability ? ? + ? 1 ? ? ? ? 1 1 ?? ,?= 1 ? ? + 1+ ? ? + 1 ? =0 1 ? ? 1 = 1 ? ? + 1+ ? (? + 1)(? ? 1) ? ? (? ? 1) 1 8 , 8 ? ? 9
Induced random walk on the line Probability of weight decreasing by 2: ? ? + ? 1 ? ? ? ? ? ? 1 ? + ?2 ?1 ? ?1+ 1 ? + 1 ? =0 ? ? + ? ? ? ? 1 ?2 ? + ? + ?2 ? + 1 ? =0
Concluding remarks and open problems We presented an 2 ? lower bound for Random-Edge. The bound can be slightly improved to 2 thus Random-Edge is slower than Random-Facet. ? log ?, This is the best that can be obtained using hierarchical constructions. Best upper bound known for Random-Edge is ?(1.8?). Is Random-Edge sub-exponential? Is there an algorithm that beats Random-Facet? Is there a polynomial time algorithm? (The algorithm does not necessarily have to follow a path. It may jump around.)
