A PRIMAL-DUAL INTERIOR-POINT METHOD FOR LINEAR OPTIMIZATION BASED ON A NEW PARAMETERIZED KERNEL FUNCTION

As recently demonstrated by the study of the primal-dual interior-point methods based on kernel functions, a kernel function not only serves to determine the search direction and measure the distance of the current iteration point to the mu-center, but also affects the iteration complexity and the practical computational efficiency of the algorithm. In this paper, we propose a primal-dual interior-point method for a linear optimization based on a new parameterized kernel function. The construction of the new parameterized kernel function is motivated by the parameterized ways of existing kernel functions. By using properties of the new parameterized kernel function, we improve the iteration bound of the large-update method from O(n(3/4) log n/epsilon) to O(root nlognlog n/epsilon), which is the best theoretical iteration result currently known. Finally, some numerical results are given to present the efficiency and potential of our kernel function.