Cours PGMO - Daniel Dadush - Straight line Complexity of Linear Programs: From Simplex to Interior Point Methods and Back Again

3 févr. 2025, 14:00 → 6 févr. 2025, 17:00 Europe/Paris

Ecole polytechnique

Two of the most important methods for solving linear programs are the simplex and interior point methods (IPM). Simplex traverses edges of the boundary of the feasible region, while interior point methods follow a path that stays as far away from the boundary as possible. While seemingly unrelated methods, this lecture series will highlight a remarkable connection between them: the minimum number of IPM iterations needed to reach an optimal solution can be approximately characterized by the complexity of shadow vertex simplex paths. This connection will be made through the concept of straight line complexity (SLC), which corresponds to the minimum number of pieces of any piecewise linear curve that suitably approximates either the IPM or simplex path.

The lecture series will begin with important results on the shadow vertex simplex method, including approachable aspects of its smoothed analysis as well as its application to upper bounding the combinatorial diameter of polyhedra. Following this, we will describe a primal dual interior point method with nearly optimal iteration complexity and sketch its high level analysis. We will then explain the relation between IPM iteration complexity and the SLC of shadow simplex curves, both in terms of upper bounds and lower bounds. Lastly, we will explain how to upper bound the SLC of combinatorial classes of linear programs as a function of the complexity of their circuits (minimal linear dependencies of the constraint matrix).

 

lundi 3 février

14:00 → 17:00 Lecture 1

mardi 4 février

14:00 → 17:00 Lecture 2

mercredi 5 février

14:00 → 17:00 Lecture 3

jeudi 6 février

14:00 → 17:00 Lecture 4