Predictor-corrector interior-point algorithm for sufficient linear complementarity problems based on AET functions with bounded proportional growth rate

Illés, Tibor and Rigó, Petra Renáta and Török, Roland (2026) Predictor-corrector interior-point algorithm for sufficient linear complementarity problems based on AET functions with bounded proportional growth rate. EURO JOURNAL ON COMPUTATIONAL OPTIMIZATION, 14. No. 100133. ISSN 2192-4406

Preview

Text EJCO2026.pdf - Published Version Available under License Creative Commons Attribution Non-commercial No Derivatives. Download (2MB) | Preview

Abstract

In this paper we define the first class of algebraically equivalent transformation (AET) functions for predictor-corrector (PC) interior-point algorithms (IPAs) for sufficient linear complementarity problems (LCPs) and we provide the unified complexity analysis of the introduced PC IPA. This new class is called the class of AET functions with bounded proportional growth rate for PC IPAs. The main difference between our PC IPA and those from the literature is that the AET function is an input data of our algorithm. The new class of AET functions is defined by several inequalities that are directly used in the analysis of the new PC IPA. We show that the PC IPA using any function of the new class of AET functions has polynomial iteration complexity in the size of the problem, the starting point’s duality gap, the accuracy parameter and the handicap of the problem’s matrix. We also provide promising numerical results on a newly generated test set of problems that contain matrices with large handicap, as well.

Actions (login required)

View Item