Warm start strategies in interior-point methods for linear programming
E. Alper Yildirim (yildirimorie.cornell.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
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|