Warm-Start Strategies in Interior-Point Methods for Linear Programming
Warm-Start Strategies in Interior-Point Methods for Linear Programming
复制标题
DOI：
10.1137/s1052623400369235
复制
发表时间：
2002-03
期刊：
影响因子：
--
通讯作者：
E. Yıldırım;Stephen J. Wright
中科院分区：
文献类型：
--
作者：
E. Yıldırım;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.