A long-step interior point framework and a related function class for linear optimization

In this paper, we introduce a general long-step algorithmic framework for solving linear programming problems based on the algebraically equivalent transformation technique proposed by Darvay. The main characteristics of the proposed general interior point algorithm are based on the long-step method of Ai and Zhang, which was one of the first long-step algorithms with the best known theoretical complexity. We investigate a set of sufficient conditions on the transformation function applied in the algebraically equivalent transformation technique, under which the convergence and best known iteration complexity of the examined general algorithmic framework can be proved. As a result, we propose the first function class in connection with the algebraically equivalent transformation technique that can be used to introduce new long-step interior point methods. Furthermore, we propose construction rules that can be used to determine new elements of this function class. Additionally, we generalize Darvay’s algebraically equivalent transformation technique to piecewise continuously differentiable transformation functions. We implemented the general algorithmic framework in MATLAB and tested its performance for six different transformation functions on a set of linear programming problem instances from the Netlib library.