An interior-point algorithm for linear optimization based on a new barrier function

Primal-dual interior-point methods (IPMs) are the most efficient methods for a computational point of view. At present the theoretical iteration bound for small-update IPMs is better than the one for large-update IPMs. However, in practice, large-update IPMs are much more efficient than small-update IPMs. Peng et al. [14,15] proposed new variants of IPMs based on self-regular barrier functions and proved so far the best known complexity, e. g. O(root n log n log n/epsilon), for large-update IPMs with some specific self-regular barrier functions. Recently, Roos et al. [2-9] proposed new primal-dual IPMs based on various barrier functions to improve the iteration bound for large-update methods from O(n log n/epsilon) to O(root n log n log n/epsilon). Motivated by their works we define a new barrier function and propose a new primal-dual interior point algorithm based on this function for linear optimization (LO) problems. We show that the new algorithm has O(root n log n log n/epsilon) iteration bound for large-update and O(root n log n/epsilon) for small-update methods which are currently the best known bounds, respectively. (C) 2011 Elsevier Inc. All rights reserved.