Gonzaga, Clovis C. An algorithm for solving linear programming problems in \(O(n^ 3L)\) operations. (English) Zbl 0691.90053 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 Cited in 1 ReviewCited in 25 Documents 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 × Cite Format Result Cite Review PDF