Interior Point Algorithms for General Linear Complementarity Problems

作     者：Marianna Nagy 

作者单位：Eotvos Lorand University 

学位级别：博士

导师姓名：Associate Professor Tibor Illes

授予年度：2009年

摘      要：The thesis is concerned with the interior point methods for linear complementarity prob- lems (LCP). The LCP is an NP-complete problem, when we have no information about the coe cient matrix of the problem. In the literature there are e cient algorithms to solve the LCP, but only when the matrix of the problem belongs to a certain special matrix class. An arbitrary LCP problem can not be solved in polynomial time, not even if the coe cient matrix belongs to the su cient matrix class, since it can not be decided in polynomial time. Our aim was to construct an algorithm, which provides some kind of information about the LCP problem in polynomial time it gives a solution in the best case. We take well-known interior point methods (for LCPs with P ( )-matrices) for the basis of the new algorithm. The modi ed algorithms are polynomial time methods. Our motivation was not only to handle the LCP problems in applications e ciently, but it was also theoretical. Based on the modi ed interior point methods we gave constructive proofs for new EP theorems. The thesis can be divided into two parts. In the rst part we mainly collect well-known results according to the LCPs and interior point methods. At the end of the Introduction we collect some well known problems, which can be reformulated as an LCP to illustrate how important an e cient algorithm for handling LCPs with arbitrary matrices will be in practice. Then we deal with some matrix classes related to LCPs, which are important for our purposes. Finally, we give an overview of the theory of interior point methods. In the second part of the thesis rst the dual of the LCP is considered. We show that the dual LCP can be solved in polynomial time if the matrix is row su cient, and we give an EP type theorem based on this complexity result. We generalize the Mizuno Todd Ye predictor-corrector algorithm for LCPs with P ( )- matrices and show that the algorithm preserves its nice property, that is, if the two used neighbourhoods