Long steps in an O(n
3
L) algorithm for linear programming |
| |
Authors: | Kurt M Anstreicher Robert A Bosch |
| |
Institution: | (1) Department of Operations Research, Yale University, 06520 New Haven, CT, USA |
| |
Abstract: | 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(n
3
L) 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(m
1.5
n
1.5
L). |
| |
Keywords: | Linear programming Karmarkar's algorithm potential function standard form modified method rank-one updates |
本文献已被 SpringerLink 等数据库收录! |