A Class of Large- and small-update Primal-dual Interior-point Algorithms for Linear Optimization

In this paper we present a class of polynomial primal-dual interior-point algorithms for linear optimization based on a new class of kernel functions. This class is fairly general and includes the classical logarithmic function, the prototype self-regular function, and non-self-regular kernel functions as special cases. The analysis of the algorithms in the paper follows the same line of arguments as in comparative study for LO by Y.Q. Bai M. El Ghami and C.Roos published in SIAM Journal of Optimization for linear optimization , where a variety of non-self-regular kernel functions were considered including the ones with linear and quadratic growth terms. However, the important case when the growth term is between linear and quadratic was not considered. The goal of this paper is to introduce such class of kernel functions and to show that the interior-point methods based on these functions have favorable complexity results. In order to achieve these complexity results, several new arguments had to be used. We obtain iteration bounds of O(qn^{\frac{p+q}{q(p+1)}}\log \frac{n}{\epsilon}) for large-update methods and O(q^2 \sqrt{n}\log\frac{n}{\epsilon}) for small-update methods, where p\in[0,1] and q >= 1 are the growth and barrier parameters of the new class of kernel functions, respectively. These iteration bounds match the currently best known iteration bounds. Examples are the prototype self-regular function with quadratic growth term (when p=1, q > 1), a simple non-self-regular function with linear growth term (when p=0, q =2), and the classical logarithmic kernel function (when p=1,q=1).