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

¹ LabCAV, Laboratory of Advanced Control, University of 8 May 1945 Guelma. BP 401, 24000 Guelma, Algeria.
mousaab84@yahoo.fr
² Normandie Univ, LMAH – ULH, FR CNRS 3335, 25 rue Philippe Lebon, 76600 Le Havre, France.
adnan.yassine@univ-lehavre.fr
³ L.M.F.N, Laboratory of Fundamental and Numerical Mathematics, University Setif 1, 19000 Setif, Algeria.
djbenterki@yahoo.fr

Received: 26 October 2014
Accepted: 12 November 2015

Abstract

Kernel function plays an important role in defining new search directions for primal-dual 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.