COMPLEXITY ANALYSIS OF AN INTERIOR-POINT ALGORITHM FOR LINEAR OPTIMIZATION BASED ON A NEW PARAMETRIC KERNEL FUNCTION WITH A DOUBLE BARRIER TERM.

Kernel functions play an important role in the complexity analysis of the interior point methods (IPMs) for linear optimization (LO). In this paper, an interior-point algorithm for LO based on a new parametric kernel function is proposed. By means of some simple analysis tools, we prove that the primal-dual interior-point algorithm for solving LO problems meets (...log(n) log(...)), iteration complexity bound for large-update methods with the special choice of its parameters. [ABSTRACT FROM AUTHOR]