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(m~(3m+1)/_(2m) n ~(m+1)/_(2m) log~n/_ε), which are at least as good as the best known bounds so far, O(√n log n log ~n/_ε), 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.