A primal-dual interior-point algorithm based on a new kernel function

Abstract

We propose a new primal-dual interior-point algorithm based on a new kernel function for linear optimization problems. New search directions and proximity functions are proposed based on the kernel function. We show that the new algorithm has $\mathcal{O}(\sqrt{n}\log n\log(n/\epsilon))$ and $\mathcal{O}(\sqrt{n}\log(n/\epsilon))$ iteration bounds for large-update and small-update methods, respectively, which are currently the best known bounds for such methods. doi:10.1017/S1446181110000908