Interior-point algorithms for solving linear complementarity problems and their applications

Kivonat, rövid leírás

In this thesis, we present the theory of linear complementarity prob-lems (LCPs), with a particular focus on problems whose matrix belongs to the class of P∗(κ)-matrices. In the introduction, we also provide a brief historical background of the theory of interior-point algorithms (IPAs). We discuss the concept of algebraically equivalent transforma-tion technique (AET) and outline the role of this method in the theory of IPAs. To motivate our research, we present several problems that can be written as LCPs. We consider the Arrow-Debreu competitive market equilibrium problem with linear and Leontief utility functions, which can also be formulated as an LCP. The main body of the thesis focuses on our research results. In Chapter 2, we introduce a new class of AET functions that defines a primal-dual (PD) IPA for P∗(κ)-LCPs. We also prove that the IPA has polynomial iteration complexity in the size of the problem, the parameter κ, the accuracy parameter and the starting point’s duality gap. In Chapter 3, we propose another class of AET functions leading to a predictor-corrector (PC) IPA for solving P∗(κ)-LCPs and prove that it has the same complexity as the currently known best ones for IPAs. Chapter 4 extends our research results by presenting a new PC IPA operating in a wide neighborhood of the central path. We generalize the concept of the wide neighborhood of the central path by using the AET technique. Furthermore, we present the complexity analysis of this IPA, as well. Finally, the thesis includes extensive numerical experiments for both the PD and PC IPAs, along with newly generated test cases to demonstrate the efficiency of the algorithms. The concluding chapter summarizes the obtained results and outlines several promising directions for future research.