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

In this paper we present a 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

Counterexample to a Conjecture on an Infeasible Interior-Point Method

In [SIAM J. Optim., 16 (2006), pp. 1110–1136], Roos proved that the devised full-step infeasible algorithm has $O(n)$ worst-case iteration complexity. This complexity bound depends linearly on a parameter $\bar{\kappa}(\zeta)$, which is proved to be less than $\sqrt{2n}$. Based on extensive computational evidence (hundreds of thousands of...