A friendly smoothed analysis of the simplex method

DOI10.1137/18M1197205MaRDI QIDQ5129232zbMATH OpenOpenAlexFDO

Authors Daniel Dadush, Sophie Huiberts

Publication date 26 October 2020

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1711.05667

zbMATH Keywords

linear programmingsmoothed analysisshadow vertex simplex method

Mathematics Subject Classification ID

Linear programming (90C05) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Analysis of algorithms (68W40)

Abstract: Explaining the excellent practical performance of the simplex method for linear programming has been a major topic of research for over 50 years. One of the most successful frameworks for understanding the simplex method was given by Spielman and Teng (JACM `04), who developed the notion of smoothed analysis. Starting from an arbitrary linear program with $d$ variables and $n$ constraints, Spielman and Teng analyzed the expected runtime over random perturbations of the LP (smoothed LP), where variance $sigm{a}^2$ Gaussian noise is added to the LP data. In particular, they gave a two-stage shadow vertex simplex algorithm which uses an expected $widetildeO(d^{55}{n}^{86}sigm{a}^{-30})$ number of simplex pivots to solve the smoothed LP. Their analysis and runtime was substantially improved by Deshpande and Spielman (FOCS `05) and later Vershynin (SICOMP `09). The fastest current algorithm, due to Vershynin, solves the smoothed LP using an expected $O(d^{3}sigm{a}^{-4}lo{g}^{3}n+d^{9}lo{g}^{7}n)$ number of pivots, improving the dependence on $n$ from polynomial to poly-logarithmic. While the original proof of Spielman and Teng has now been substantially simplified, the resulting analyses are still quite long and complex and the parameter dependencies far from optimal. In this work, we make substantial progress on this front, providing an improved and simpler analysis of shadow simplex methods, where our algorithm requires an expected [ O(d^2 sqrt{log n} sigma^{-2} + d^3 log^{3/2} n) ] number of simplex pivots. We obtain our results via an improved emph{shadow bound}, key to earlier analyses as well, combined with improvements on algorithmic techniques of Vershynin. As an added bonus, our analysis is completely modular, allowing us to obtain non-trivial bounds for perturbations beyond Gaussians, such as Laplace perturbations.

Recommendations

• A friendly smoothed analysis of the simplex method
• Beyond Hirsch Conjecture: Walks on Random Polytopes and Smoothed Complexity of the Simplex Method
• Linear optimization with the shadow vertex algorithm in the context of probabilistic analyses. Studies on the transition from phase 1 to phase 2 in the average-case analysis and in the smoothing analysis of the simplex method
• Smoothed analysis of algorithms
• Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time

Cites work

• Title not available (Why is no real title available?)
• scientific article; zbMATH DE number 3644821 (Why is no real title available?)
• scientific article; zbMATH DE number 3648423 (Why is no real title available?)
• scientific article; zbMATH DE number 4022030 (Why is no real title available?)
• scientific article; zbMATH DE number 45785 (Why is no real title available?)
• scientific article; zbMATH DE number 3466805 (Why is no real title available?)
• scientific article; zbMATH DE number 3538744 (Why is no real title available?)
• scientific article; zbMATH DE number 3626518 (Why is no real title available?)
• scientific article; zbMATH DE number 1241836 (Why is no real title available?)
• scientific article; zbMATH DE number 1149836 (Why is no real title available?)
• scientific article; zbMATH DE number 1749054 (Why is no real title available?)
• scientific article; zbMATH DE number 803180 (Why is no real title available?)
• scientific article; zbMATH DE number 3894831 (Why is no real title available?)
• scientific article; zbMATH DE number 3069632 (Why is no real title available?)
• A Sharp Upper Bound for the Expected Number of Shadow Vertices in LP-Polyhedra Under Orthogonal Projection on Two-Dimensional Planes
• A brief history of linear and mixed-integer programming computation
• A computational analysis of alternative algorithms and labeling techniques for finding shortest path trees
• A counterexample to the Hirsch conjecture
• A friendly smoothed analysis of the simplex method
• A linear bound on the diameter of the transportation polytope
• A new polynomial-time algorithm for linear programming
• A polynomial-time algorithm, based on Newton's method, for linear programming
• A primal simplex algorithm that solves the maximum flow problem in at most nm pivots and O(n^ 2m) time
• A quasi-polynomial bound for the diameter\\of graphs of polyhedra
• A randomized polynomial-time simplex algorithm for linear programming
• A simplex algorithm whose average number of steps is bounded between two quadratic functions of the smaller dimension
• A simplex variant solving an m\(\times d\) linear program in O(min(m 2,d 2)) expected number of pivot steps
• A subexponential bound for linear programming
• A subexponential lower bound for Zadeh's pivoting rule for solving linear programs and games
• Algorithms – ESA 2004
• An Improved Version of the Random-Facet Pivoting Rule for the Simplex Algorithm
• An asymptotically improved upper bound on the diameter of polyhedra
• An improved Kalai-Kleitman bound for the diameter of a polyhedron
• An upper bound for the diameter of a polytope
• Beyond Hirsch Conjecture: Walks on Random Polytopes and Smoothed Complexity of the Simplex Method
• Bimatrix Equilibrium Points and Mathematical Programming
• Computational complexity of parametric linear programming
• Efficient Shortest Path Simplex Algorithms
• Erratum: ``A sharp upper bound for the expected number of shadow vertices in LP-polyhedra under orthogonal projection on two-dimensional planes
• Geometric random edge
• Graphs of transportation polytopes
• Improved asymptotic analysis of the average number of steps performed by the self-dual simplex algorithm
• MIP: Theory and practice -- closing the gap
• On the Implementation of a Primal-Dual Interior Point Method
• On the average number of steps of the simplex method of linear programming
• On the shadow simplex method for curved polyhedra
• On the smoothed complexity of convex hulls
• Paths on Polytopes
• Polynomial dual network simplex algorithms
• Polynomial expected behavior of a pivoting algorithm for linear complementarity and linear programming problems
• Polynomial-time primal simplex algorithms for the minimum cost network flow problem
• Probabilistic analysis of optimization algorithms - some aspects from a practical point of view
• Random walks, totally unimodular matrices, and a randomised dual simplex algorithm
• Smoothed Analysis of the Condition Numbers and Growth Factors of Matrices
• Smoothed analysis of algorithms
• Smoothed analysis of termination of linear programming algorithms
• Smoothed analysis of the \(k\)-means method
• Smoothed analysis of the successive shortest path algorithm
• Smoothed complexity of convex hulls by witnesses and collectors
• Solving totally unimodular LPs with the shadow vertex algorithm
• Steepest-edge simplex algorithms for linear programming
• Subexponential lower bounds for randomized pivoting rules for the simplex algorithm
• Technical Note—A Polynomial Simplex Method for the Assignment Problem
• The Average number of pivot steps required by the Simplex-Method is polynomial
• The Efficiency of the Simplex Method: A Survey
• The Hirsch Conjecture for Dual Transportation Polyhedra
• The Hirsch conjecture holds for normal flag complexes
• The Hirsch conjecture is true for (0,1)-polytopes
• The diameters of network-flow polytopes satisfy the Hirsch conjecture
• The simplex algorithm with the pivot rule of maximizing criterion improvement
• The simplex and policy-iteration methods are strongly polynomial for the Markov decision problem with a fixed discount rate
• The simplex method is strongly polynomial for deterministic Markov decision processes
• The width of five-dimensional prismatoids
• Use of dynamic trees in a network simplex algorithm for the maximum flow problem
• Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP
• Worst case behavior of the steepest edge simplex method

Cited in

(15)

• Smoothed analysis of algorithms
• Circuits in extended formulations
• What Tropical Geometry Tells Us about the Complexity of Linear Programming
• Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time
• A friendly smoothed analysis of the simplex method
• scientific article; zbMATH DE number 2119754 (Why is no real title available?)
• The Polyhedral Geometry of Pivot Rules and Monotone Paths
• On the integrality gap of binary integer programs with Gaussian data
• A spectral approach to polytope diameter
• Linear optimization with the shadow vertex algorithm in the context of probabilistic analyses. Studies on the transition from phase 1 to phase 2 in the average-case analysis and in the smoothing analysis of the simplex method
• Smoothed analysis of termination of linear programming algorithms
• The smoothed complexity of policy iteration for Markov decision processes
• Upper and lower bounds on the smoothed complexity of the simplex method
• Monotone paths on cross-polytopes
• The work of Daniel A. Spielman

This page was built for publication: A friendly smoothed analysis of the simplex method

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5129232)