| Two important classes of polynomial-time interior-point methods (IPMs) are small-a nd large-update methods, respectively. The theoretical complexity bound for small-update methods is a factor / sqrt{n} better than the bound for large-update methods, where n denotes the number of inequalities in the problem. In practice the situation is opposite: implementations of large-update methods are much more efficient than those of small-update methods. This so-called irony of IPMs motivated two preceding NWO projects. In these projects the factor \sqrt{n} was reduced to \log n, thus significantly reducing the gap between the theoretical behavior of large- and small-update methods. In the first project we developed new theory, new barrier functions, new search directions and new mathematical tools for the analysis of IPMs. These results were published in a research monograph by Princeton University Press. In the second project we further extended our theory. We were, however, not able to close the gap. In a late stage of the second project a remark of a referee made us realize that all existing methods, including our new methods, can be considered as steepest gradient methods in a scaled space, and that we equally well can apply a Newton method in this scaled space. This will lead to new search directions. |
