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

Marianna E. Nagy and Anita Varga
Authors registered in the RePEc Author Service: Marianna Eisenberg-Nagy

Corvinus Economics Working Papers (CEWP) from Corvinus University of Budapest

Abstract: 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.

Keywords: linear programming; interior point methods; algebraically equivalent transformation technique (search for similar items in EconPapers)
JEL-codes: C61 (search for similar items in EconPapers)
Date: 2024-07-15
References: Add references at CitEc
Citations:

Downloads: (external link)
https://unipub.lib.uni-corvinus.hu/10192/ original version (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cvh:coecwp:2024/01

Access Statistics for this paper

More papers in Corvinus Economics Working Papers (CEWP) from Corvinus University of Budapest 1093 Budapest, Fõvám tér 8.. Contact information at EDIRC.
Bibliographic data for series maintained by Adam Hoffmann ().