Complexity of interior-point methods for linear optimization based on a new trigonometric kernel function

摘要

In this paper, we propose a new kernel function with trigonometric barrier term for primal–dual interior point methods in linear optimization. Using an elegant and simple analysis and under some easy to check conditions, we explore the worst case complexity result for the large update primal–dual interior point methods. We obtain the worst case iteration bound for the large update primal–dual interior point methods as O(n23lognϵ) which improves the so far obtained complexity results for the trigonometric kernel function in [M. El Ghami, Z.A. Guennoun, S. Boula, T. Steihaug, Interior-point methods for linear optimization based on a kernel function with a trigonometric barrier term, Journal of Computational and Applied Mathematics 236 (2012) 3613–3623] significantly.