Full-Newton step polynomial-time methods for LO based on locally self-concordant barrier functions

Recently several new search directions for interior-point methods have been introduced, based on kernel functions. Some of these function are so-called self-regular, others not. The best known iteration bounds methods based on kernel functions are [latex]O(sqrt{n} ln (n/epsilon))[/latex] for small-update methods and [latex]O(sqrt{n}(ln n) ln (n/epsilon))[/latex] for large-update methods, respectively. Our work is motivated by the question whether or not such bounds also can be obtained by applying the more elegant theory of self-concordant functions to barrier functions based on kernel functions. A major difficulty that arises when dealing with this question is that in general these barrier functions are not self-concordant. As we will show, however, on the central path and in its neighborhood they behave as being self-concordant; we call them locally self-concordant. As a consequence, for full-Newton step methods the answer to the above question is positive. We show that for a wide class of such barrier functions these methods have the best known iteration bound, the same bound as for the classical logarithmic barrier function.