A wide neighborhood interior-point algorithm based on the trigonometric kernel function

摘要

In this paper, a wide neighborhood path-following interior point algorithm for linear optimization (LO) is proposed that uses a trigonometric kernel function to get search directions. The method treats the Newton direction as the sum of two other directions, according to the negative and positive parts of the right-hand-side based on the kernel function. By choosing different and appropriate step sizes for these two directions, the iterates stop in the Ai-Zhang's wide neighborhood. By an elegant analysis, we show that the method enjoys the low iteration bound of O(nlog(x0)Ts0 epsilon), where n is the dimension of the problem and (x0,s0) the initial interior point with epsilon the required precision. In our knowledge, this result is the first instance of a wide neighborhood interior point method for LO which involving the trigonometric kernel function.