Coauthor: Stephen Wright
Title: An Interior-Point Perspective on Reoptimization in Linear Programming

Karmarkar's discovery of interior-point methods (IPMs) for solving linear programs (LPs) in 1984 gave rise to a new field in mathematical programming. The polynomial complexity and the good practical performance of these methods put them at a clear advantage over the simplex method, especially for large-scale LPs. In 1994, Nesterov and Nemirovski extended the theory of IPMs to general convex programming without sacrificing polynomial complexity.

Despite their generality and practical efficiency, it was conjectured that these methods would not be suitable to perform reoptimization efficiently after a perturbation in the data of the original optimization problem.

We study the situation in which, having solved a linear program (LP) with an interior-point method, we are then presented with a new problem instance whose data is a small perturbation of the original problem data. We describe strategies for recovering a ``warm start'' point for the perturbed problem instance from the iterates of the original problem instance, and discuss the computational complexity of these strategies based on the perturbation size and the conditioning of the original instance.