A Friendly Smoothed Analysis of the Simplex Method

DOI10.1137/18M1197205zbMATH Open1451.90095arXiv1711.05667OpenAlexW3094140778MaRDI QIDQ5129232FDOQ5129232

Daniel Dadush, Sophie Huiberts

Publication date: 26 October 2020

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

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.

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)

Cites Work

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

Cited In (11)

• Smoothed analysis of algorithms
• Circuits in extended formulations
• What Tropical Geometry Tells Us about the Complexity of Linear Programming
• Title not available (Why is that?)
• 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
• The smoothed complexity of policy iteration for Markov decision processes
• Upper and lower bounds on the smoothed complexity of the simplex method
• Smoothed analysis of termination of linear programming algorithms
• Monotone paths on cross-polytopes

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)