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

作者：Liu Liying^*; Li Shaoyong

来源：Journal of Computational and Applied Mathematics, 2011, 235(9): 2944-2955.

DOI：10.1016/j.cam.2010.12.012

• Kernel function
• Interior-point methods
• Large-update methods
• Iteration bounds

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/epsilon), which are at least as good as the best known bounds so far, O(root n log n log n/epsilon), 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.

• 出版日期2011-3-1
• 单位聊城大学