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

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.