An algorithm for solving linear programming problems in $O\left({n}^{3}L\right)$ operations.

*(English)*Zbl 0691.90053Progress 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\left({n}^{0\xb75}L\right)$ iterations. The total number of arithmetic operations is bounded by $O\left({n}^{3}L\right)$, 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 in calculus of variations |

68Q25 | Analysis of algorithms and problem complexity |

65K05 | Mathematical programming (numerical methods) |

49M30 | Other numerical methods in calculus of variations |