A new and efficient large-update interior-point method for linear optimization. (English. Russian summary) Zbl 0987.90089
The authors start with an observation that there is still a gap between the practical behavior of interior-point algorithms for linear optimization problems and the theoretical performance results. The aim of the article is to show that, by slightly modifying the classical primal-dual Newton search direction, the complexity of large-update methods can be improved. The result is an \(O\bigl(\sqrt{n}\log n\log (n/\varepsilon)\bigr)\) iteration bound.
Reviewer: N.I.Alexandrova (Novosibirsk)
MSC:
90C51 | Interior-point methods |
90C05 | Linear programming |
90C33 | Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) |