#### Mengmeng Li, Mingwang Zhang, Zhengwei Huang, A primal-dual interior-point method for linear optimization based on a new parameterized kernel function, Vol. 2019 (2019), Article ID 38, pp. 1-20

Full TextPDF
DOI: 10.23952/jnfa.2019.38

Received January 22, 2019; Accepted August 8, 2019; Published August 23, 2019

Abstract. 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^{\frac{3}{4}}\log{\frac{n}{\epsilon}})$ to $O(\sqrt{n}\log{n}\log{\frac{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.