Subexponential Lower Bound for Randomized Pivot Rules!

Oliver Friedmann, Thomas Dueholm Hansen, and Uri Zwick have managed to prove subexponential lower bounds of the form for the following two basic randomized pivot rules for the simplex algorithm! This is the first result of its kind and deciding if this is possible was an open problem for several decades. Here is a link to the paper.

Update: Oliver Friedmann have managed to use similar methods to find similar lower bounds also for Zadeh’s deterministic pivot rule. See this paper.

We can regard the simplex algorithm as starting from an arbitrary vertex of the feasible polytope and repeatedly moving to a neighboring vertex with a higher value of the objective function according to some pivot rule.

The pivot rules considered in the paper are

RANDOM EDGE– Choose an improving pivoting step uniformly at random.

RANDOM FACET– Choose at random a facet containing your vertex and apply the algorithm in that facet.

RANDOM FACET and closely related variants which appeared in the early 90s in the works by Matousek, Sharir and Welzl and by me.

Some background:

In the early days of linear programming it was  believed that the common pivot rules
reach the optimum in a number of steps that is polynomial or perhaps even close to linear
in – the number of variables and -the number of inequalities. This belief turned out to be false: Klee and Minty found in 1972  that one of the most common variants of the simplex algorithm is exponential in the worst case. In fact, the number of  pivot steps was quite close to the total number of  vertices of the feasible polytope. Similar results for other pivot rules were subsequently found by many authors. And no deterministic pivot rule which requires less than exponential number of pivot steps is known.

Randomized pivot rules improved matters somewhat. RANDOM FACET and its variations had led to the the first subexponential upper bounds of the form for the expected number of pivot steps for linear programming problems with inequalities and variables. No such result for RANDOM EDGE is known.

For some background on linear programming and a description of  more abstract settings for linear programming  see also this post. Finding (possibly random) pivot rules which require a small number of steps for every LP problem and even for various abstract versions of LP problem is a very interesting problem. It was mentioned among quite a few other problems in the “grand plan” for “polymath3”.

Lower bounds for RANDOM EDGE and RANDOM FACET were known before only in abstract settings, and not for concrete linear programs.

The connection to games

The path toward the proof by Friedmann, Hansen, and Zwick is exciting as well. Quoting from the abstract: The new lower bounds are obtained by utilizing connections between pivoting steps performed by simplex-based algorithms and improving switches performed by policy iteration algorithms for 1-player and 2-player games. We start by building 2-player parity games (PGs) on which suitable randomized policy iteration algorithms perform a subexponential number of iterations. We then transform these 2-player games into 1-player Markov Decision Processes (MDPs) which correspond almost immediately to concrete linear programs.