Interior-point algorithm for linear programming based on a new descent direction

¹ Laboratory of Fundamental and Numerical Mathematics, Department of Mathematics, Faculty of Sciences Setif-1 Ferhat Abbas University, Setif 19000, Algeria.
² Department of Mathematics, Faculty of Sciences, Setif-1 Ferhat Abbas University, Setif 19000, Algeria.

^* Corresponding author: billel.zaoui@univ-setif.dz

Received: 26 September 2022
Accepted: 12 August 2023

Abstract

We present a full-Newton step feasible interior-point algorithm for linear optimization based on a new search direction. We apply a vector-valued function generated by a univariate function on a new type of transformation on the centering equations of the system which characterizes the central path. For this, we consider a new function ψ(t) = t7\4. Furthermore, we show that the algorithm finds the ϵ-optimal solution of the underlying problem in polynomial time, namely O(√nlog(n+3\7√2)) iterations. Finally, a comparative numerical study is reported in order to analyze the efficiency of the proposed algorithm.