Primal-dual interior-point method for linear optimization based on a kernel function with trigonometric growth term

摘要

In this paper, we propose a large-update primal-dual interior-point algorithm for linear optimization problems based on a new kernel function with a trigonometric growth term. By simple analysis, we prove that in the large neighbourhood of the central path, the worst case iteration complexity of the new algorithm is bounded above by O(root n log n log (n/epsilon)) , which matches the currently best known iteration bound for large-update methods. Moreover, we show that, most of the so far proposed kernel functions can be rewritten as a kernel function with trigonometric growth term. Finally, numerical experiments on some test problems confirm that the new kernel function is well promising in practice in comparison with some existing kernel functions in the literature.