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

In this paper we present 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 an earlier paper. We show that the corresponding large-update algorithm improves the iteration complexity with a factor n^1/ε 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(√(n)log(n/ε)) which is currently the best-known bound for primal–dual IPMs.