An exponential worst-case algorithm that consistently outperforms polynomial alternatives. Three interlinked ideas — geometric exploitation, smoothed analysis, and shadow vertex pivoting — finally close the gap between theory and practice.
Linear programs have convex feasible regions — polytopes. Their optima always occur at vertices (corner points) of that polytope. Simplex exploits this by jumping directly from vertex to vertex along edges, never wasting time in the interior.
At each step, simplex picks a neighboring vertex that improves the objective. It never backtracks (in the basic non-degenerate case), so every pivot is progress. This is fundamentally different from exhaustive search — it never evaluates most vertices.
Each pivot step doesn't re-solve the whole system from scratch. Simplex maintains a factorization of the basis matrix (typically an LU decomposition) and updates it incrementally using the Sherman-Morrison-Woodbury formula.
Real-world LP matrices are almost always sparse — most constraints don't involve most variables. Revised simplex with sparse LU factorization keeps memory and arithmetic low, often making actual cost far below the theoretical bound.
Simplex can start from a known feasible vertex and incrementally update its basis. When re-solving a slightly modified problem — common in branch-and-bound, sensitivity analysis, and MIP solvers — it picks up almost where it left off. Interior-point methods generally cannot do this as naturally.
Interior-point methods have better theoretical complexity (polynomial), but simplex often beats them in practice because it has lower overhead per iteration, warm starting is natural, and the basis representation gives a clean, interpretable optimal solution directly usable by downstream algorithms.
Simplex has exponential worst-case complexity (Klee-Minty, 1972) yet works extremely fast in practice. Neither worst-case nor average-case analysis fully explained this gap.
Daniel Spielman and Shang-Hua Teng introduced smoothed analysis as a middle ground. The idea: take any adversarial input, then slightly perturb it with Gaussian noise. What is the expected complexity over that perturbation?
An adversary cannot stably construct a Klee-Minty instance in practice. Any near-adversarial input gets smoothed out by inherent real-world noise. The exponential worst case is fragile: it collapses under the slightest perturbation.
| Algorithm | Finding | Prior mystery |
|---|---|---|
| Simplex (shadow vertex) | O(n³/σ) smoothed complexity | Exponential worst-case, fast in practice |
| Gaussian elimination | Stable in expectation | Bad worst-case condition numbers |
| k-means clustering | Polynomial smoothed complexity | Slow on adversarial initializations |
| Local search heuristics | Explains practical speed | Worst-case exponential |
| Online algorithms | Smoothed competitive ratios | Poor worst-case competitive ratio |
Rather than moving through the polytope greedily in high-dimensional space, the shadow vertex rule works by projecting the polytope onto a 2D plane and tracing the boundary of that projection.
Consider a linear program with feasible polytope P ⊂ ℝⁿ. Choose two objective directions:
Project every point x ∈ P onto the plane spanned by c₁ and c₂:
Equivalently, consider a parameterized objective that continuously rotates from c₂ to c₁:
As λ increases from 0 to 1, the optimal vertex traces a path across the polytope. Shadow vertex simplex follows exactly this path — the sequence of vertices that are optimal for c(λ) at each transition point.
Exponential pivot sequences arise when many vertices of P project to the same edge of the shadow — a knife-edge geometric alignment. After Gaussian perturbation with noise σ, the expected number of shadow vertices is O(n²/σ). Even σ = 10⁻¹⁰ gives a polynomial bound.
| Analysis type | Complexity | Input model | Verdict |
|---|---|---|---|
| Worst-case | Exponential (Klee-Minty 1972) | Adversarial, exact | Too pessimistic — never seen in practice |
| Average-case | Polynomial (random inputs) | Uniformly random | Unrealistic — real inputs aren't random |
| Smoothed (Spielman-Teng) | O(n³/σ) — polynomial | Adversarial + tiny Gaussian noise | Matches observed practice precisely |
| Interior-point methods | Polynomial (worst-case) | Any | Better theory; often slower due to overhead & no warm-start |
Shadow vertex is primarily a theoretical tool, not a practical implementation choice. Real solvers use:
Simplex is fast in practice for a combination of reasons that reinforce each other: