Long steps in an O(n3L) algorithm for linear programming
Long steps in an O(n3L) algorithm for linear programming
复制标题
线性规划 O(n3L) 算法中的长步
DOI：
10.1007/bf01586053
复制
发表时间：
1992
影响因子：
2.7
通讯作者：
R. Bosch
中科院分区：
文献类型：
--
作者：
K. Anstreicher;R. Bosch
我们考虑线性规划的叶（Ye）仿射势下降算法中的部分更新。我们表明，在原始步中使用戈尔茨坦 - 阿米霍（Goldstein - Armijo）规则来保障势函数的线搜索足以控制更新的次数。我们还将对偶步的构造推广到适用于部分更新的情况。结果是得到了第一个用于线性规划的$O(n^3L)$算法，其步长不受需要保持近似中心的限制。该算法具有严格的“仅原始”初始化这一事实实际上将复杂度降低到小于$O(m^{1.5}n^{1.5}L)$。
We consider partial updating in Ye's affine potential reduction algorithm for linear programming. We show that using a Goldstein—Armijo rule to safeguard a linesearch of the potential function during primal steps is sufficient to control the number of updates. We also generalize the dual step construction to apply with partial updating. The result is the first O(n3L) algorithm for linear programming whose steps are not constrained by the need to remain approximately centered. The fact that the algorithm has a rigorous “primal-only” initialization actually reduces the complexity to less than O(m1.5n1.5L).