|
Abstract
|
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(√n log (x0)T s0
ε ), where n is the
dimension of the problem and (x0, s0) the initial interior point with ε 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.
|