An algorithm for solving linear programming problems in \(O(n^ 3L)\) operations. (English) Zbl 0691.90053

Gonzaga, Clovis C.

Progress in mathematical programming. Interior-point and related methods, Proc. Conf., Pacific Grove/Calif. 1987, 1-28 (1989).

[For the entire collection see Zbl 0669.00026.]
This paper describes a short-step penalty function algorithm that solves linear programming problems in no more than \(O(n^{0.5}L)\) iterations. The total number of arithmetic operations is bounded by \(O(n^ 3L)\), carried on with the same precision as that in Karmarkar’s algorithm. Each iteration updates a penalty multiplier and solves a Newton-Raphson iteration on the traditional logarithmic barrier function using approximated Hessian matrices. The resulting sequence follows the path of optimal solutions for the penalized functions as in a predictor-corrector homotopy algorithm.

Reviewer: J.Abrham

MSC:

90C05	Linear programming
49M15	Newton-type methods
68Q25	Analysis of algorithms and problem complexity
65K05	Numerical mathematical programming methods
49M30	Other numerical methods in calculus of variations (MSC2010)

Keywords:

polynomial type algorithms; short-step penalty function; penalty multiplier; Newton-Raphson iteration; approximated Hessian matrices; predictor-corrector homotopy algorithm

Citations:

Zbl 0669.00026