|
Abstract
|
This paper presents an interior point algorithm for solving linear optimization problems
in a wide neighborhood of the central path introduced by Ai and Zhang (SIAM J Optim
16:400–417, 2005). In each iteration, the algorithm computes the new search directions
by using a specific kernel function. The convergence of the algorithm is shown and it is
proved that the algorithm has the same iteration bound as the best short-step algorithms.We
demonstrate the computational efficiency of the proposed algorithm by testing some Netlib
problems in standard form. To best our knowledge, this is the first wide neighborhood pathfollowing
interior-point method with the same complexity as the best small neighborhood
path-following interior-point methods that uses the kernel function.
|