PRIMAL-DUAL INTERIOR-POINT ALGORITHM FOR LO BASED ON A NEW KERNEL FUNCTION

Abstract

Based on a new kernel function, a large-update primal-dual interior-point algorithm for solving linear optimization is proposed.  The kernel function is used both for determining the search directions and for measuring the distance between the given iterate and the µ-center for the algorithm.  By using several new technical lemmas, the iteration complexity bound as O(\(\sqrt{n}\) log n log \(\frac{n}{ε}\)) is obtained, which coincides with the currently  best iteration complexity bounds for large-update methods.  In addition, we present some preliminary numerical results.