In this talk, I will overview progress in our probabilistic understanding of the (shadow
vertex) simplex method in three different settings: smoothed polytopes (whose data is randomly perturbed), well-conditioned polytopes (e.g., TU systems), and random polytopes with constraints drawn uniformly from the sphere. I will first highlight improvements and simplifications in the complexity analysis of solving smoothed linear programs via the simplex method, whose study was initiated by Spielman and Teng (JACM 04). Secondly, I will tackle the (harder) question of polytope diameter. I will explain how randomly chosen shadow paths yield the best known diameter bounds for wellconditioned polytopes, and nearly tight diameter bounds (up to one factor of dimension) for random spherical polytopes when the number of constraints is (very) large compared to dimension. This is based on joint works with Sophie Huiberts, Nicolai H¨ahnle, Gilles Bonnet, Uri Grupel and Galyna Livshyts.
In terms of open problems, apart from the many sub-optimal dependencies, I would like to highlight two more general questions. Firstly, can we quantify why the simplex method is so effective at re-optimizing after adding additional constraints? This is the main reason simplex is dominant in
practice. Secondly, can smoothed analysis be used to explain the unreasonably low iteration counts
needed to solve most LPs via interior point methods (50-100 independent of dimension!)?
0 Comments