A Primal-dual Interior-Point Method for Linear Optimization Based on a New Proximity Function∗

In this paper we present a generic primal-dual interior-point algorithm for linear op-timization in which the search direction depends on a univariate kernel function which is also used as proximity measure in the analysis of the algorithm. We present some power-ful tools for the analysis of the algorithm under the assumption that the kernel function satisfies three easy to check and mild conditions (i.e., exponential convexity, superconvexity and monotonicity of the second derivative). The approach is demonstrated by introducing a new kernel function and showing that the corresponding large-update algorithm improves the iteration complexity with a factor n 1 4 when compared with the classical method, which is based on the use of the logarithmic barrier function