Primal-Dual Algorithm for Linear Optimization Problems Based on a New Class of Kernel Functions

In this paper we present a class of polynomial primal-dual interior-point algorithms for LO based on a new class of kernel functions. This class is fairly general and includes the class of finite kernel functions by Y.Q. Bai M. El Ghami and C.Roos published in SIAM Journal of Optimization, 13(3):766–782, 2003. The proposed functions have a finite value at the boundary of the feasible region. They are not exponentially convex and also not strongly convex like the usual barrier functions. The goal of this paper is to investigate such class of kernel functions and to show that the interior-point methods based on these functions have favorable complexity results. The iteration bound of largeupdate interior-point methods based on these functions, are shown to be O(n^(1/1+p) log n log n/∈), where p is a parameter, p ∈ [0, 1]. We present also some numerical results which show that by using a new kernel function, the best iteration numbers was achieved in most of the test problems.