Optimization Online


Warm start strategies in interior-point methods for linear programming

E. Alper Yildirim (yildirim***at***orie.cornell.edu)
Stephen J. Wright (swright***at***cs.wisc.edu)

Abstract: 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.

Keywords: Interior-Point Methods, Linear Programming, Condition, Complexity

Category 1: Linear, Cone and Semidefinite Programming (Linear Programming )

Citation: Preprint ANL/MCS-P799-0300, March, 2000. Published in SIAM Journal on Optimization 12 (2002), pp. 782--810.


Entry Submitted: 08/18/2000
Entry Last Modified: 05/29/2003

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society