×

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.

MSC:

90C51 Interior-point methods
90C05 Linear programming
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)