Generic primal-dual interior point methods based on a new kernel function

In this paper we present a generic primal-dual interior point methods (IPMs) for linear optimization in which the search direction depends on a univariate kernel function which is also used as proximity measure in the analysis of the algorithm. The proposed kernel function does not satisfy all the conditions proposed in [2]. We show that the corresponding large-update algorithm improves the iteration complexity with a factor n^(1/6) when compared with the method based on the use of the classical logarithmic barrier function. For small-update interior point methods the iteration bound is O(sqrt(n)log(n/epsilon)) which is currently the best-known bound for primal-dual IPMs.