Complexity analysis of interior point methods for linear programming based on a parameterized kernel function

Mousaab Bouafia, et al.

Volume 50,  4-5, 935-949, 2016

RAIRO - Operations Research

www.doi.org/10.1051/ro/2015056

Abstract

Kernel function plays an important role in defining new search directions for primaldual interior point algorithm for solving linear optimization problems. This problem has attracted the attention of many researchers for some years. The goal of their works is to find kernel functions that improve algorithmic complexity of this problem. In this paper, we introduce a real parameter p > 0 to generalize the kernel function (5) given by Bai et al. in [Y.Q. Bai, M El Ghami and C. Roos, SIAM J. Optim. 15 (2004) 101–128.], and give the corresponding primal-dual interior point methods for linear optimization. This parameterized kernel function yields the similar complexity bound given in [Y.Q. Bai, M El Ghami and C. Roos, SIAM J. Optim. 15 (2004) 101–128.] for both large-update and small-update methods.