Warm-start strategies in interior-point methods for linear programming

E. Alper Yildirim and Stephen J. Wright

We study the situation in which, having solved a linear program with an interior-point method, we are presented with a new problem instance whose data is slightly perturbed from the original. We describe strategies for recovering a ``warm-start'' point for the perturbed problem instance from the iterates of the original problem instance. We obtain worst-case estimates of the number of iterations required to converge to a solution of the perturbed instance from the warm-start points, showing that these estimates depend on the size of the perturbation and on the conditioning and other properties of the problem instances.

Technical Report 1258, School of Operations Research and Industrial Engineering, Cornell University

Preprint MCS-P799-0300, Mathematics and Computer Science Division, Argonne National Laboratory.

Contact: yildirim@orie.cornell.edu, wright@mcs.anl.gov