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.   [3] ;  [4] ;  [5] ;  [6] ;  [7] ;  [8]  ;   [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    ϵ              to             O       n    log  n  log    n    ϵ             . 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       n    log  n  log    n    ϵ              iteration bound for large-update and             O       n    log    n    ϵ              for small-update methods which are currently the best known bounds, respectively.
['Gyeong-Mi Cho']
An interior-point algorithm for linear optimization based on a new barrier function