Recent Advances in Interior Point Methods for Linear Programming

Linear programming (LP) is a fundamental optimization problem with broad applications across science, engineering, and business. One of the most widely used algorithms for solving LPs is interior point methods (IPM), which are known to converge fast both in theory and in practice.

In this talk, we will survey several recent theoretical developments in IPMs for LP. We will show how dynamic data structures can reduce the cost-per-iteration of an IPM, leading to faster and nearly-optimal solvers for general LPs. We will also give a brief overview of recent progress on maximum flow and other graph problems—important special cases of LP—achieved using IPM-based frameworks with efficient graph data structures.

The key tools used in these results include specialized matrix and graph data structures that exploit the stability and robustness guarantees of IPMs, and randomized dimension reduction techniques such as sketching and sampling.

This seminar is part of the Recent Progress and Open Directions in Matrix Computations series.