A polynomial predictor-corrector trust-region algorithm for linear programming. (English) Zbl 1179.65068
A scaling-invariant interior-point algorithm is presented for linear programming whose iteration-complexity and arithmetic-complexity are bounded by a polynomial of the dimension and the logarithm of a certain condition number of the linear programming constraint matrix. In the iteration of the algorithm, the affine scaling direction is computed and a test involving this direction is performed to determine whether the trust-region step is needed.
If the trust-region direction is not needed then a step along the affine scaling direction is taken followed by a standard corrector step. Otherwise, the affine scaling direction determines a scaling-invariant bipartition of the variables which allows to construct a pair of primal and dual trust-region subproblems whose optimal solutions yield the trust-region direction. Then the algorithm takes a step along either the affine scaling or the trust-region direction whichever yields the largest duality gap reduction.
If the trust-region direction is not needed then a step along the affine scaling direction is taken followed by a standard corrector step. Otherwise, the affine scaling direction determines a scaling-invariant bipartition of the variables which allows to construct a pair of primal and dual trust-region subproblems whose optimal solutions yield the trust-region direction. Then the algorithm takes a step along either the affine scaling or the trust-region direction whichever yields the largest duality gap reduction.
Reviewer: Hang Lau (Montréal)
MSC:
65K05 | Numerical mathematical programming methods |
90C05 | Linear programming |
90C51 | Interior-point methods |
90C60 | Abstract computational complexity for mathematical programming problems |
65Y20 | Complexity and performance of numerical algorithms |