An efficient primal-dual interior point method for linear programming problems based on a new kernel function with a finite exponential-trigonometric barrier term

摘要

In this paper, we first propose a new finite exponential-trigonometric kernel function that has finite value at the boundary of the feasible region. Then by using some simple analysis tools, we show that the new kernel function has exponential convexity property. We prove that the large-update primal-dual interior-point method based on this kernel function for solving linear optimization problems has O(root n log n log n/epsilon) iteration bound in the worst case when the barrier parameter is taken large enough. Moreover, the numerical results reveal that the new finite exponential-trigonometric kernel function has better results than the other kernel functions.