A new kind of simple kennel function yielding good iteration bounds for primal-dual interior-point methods

摘要

We introduce a new kind of kernel function, which yields efficient large-update primal-dual interior-point methods. We conclude that in some situations its iteration bounds are O(m3m+12mnm+12mlognϵ), which are at least as good as the best known bounds so far, O(nlognlognϵ), for large-update primal-dual interior-point methods. The result decreases the gap between the practical behavior of the large-update algorithms and their theoretical performance results, which is an open problem. Numerical results show that the algorithms are feasible.