An efficient parameterized logarithmic kernel function for linear optimization

Mousaab Bouafia, et al.

 Volume 12, 2018

Optimization Letters

https://doi.org/10.1007/s11590-017-1170-5

Abstract

The introduction of kernel function in primal-dual interior point methods represents not only a measure of the distance between the iterate and the central path, but also plays an important role in the amelioration of the computational complexity of an interior point algorithm. In this work, we present a primal-dual interior point method for linear optimization problems based on a new kernel function with an efficient logarithmic barrier term. We derive the complexity bounds for large and small-update methods respectively. We obtain the best known complexity bound for large-update given by Peng et al., which improves significantly the so far obtained complexity results based on a logarithmic kernel function given by El Ghami et al. The results obtained in this paper are the first with respect to the kernel function with a logarithmic barrier term.

Keywords

Linear optimization,kernel function,interior point methods,complexity bound.