Polynomial Path-following Interior Point Algorithim for General Linear Complimentarity Problems

Authors: Illés Tibor, Nagy Marianna, Terlaky Tamas

Keywords: Linear Complementarity Problem, Sufficient Matrix, Interior Point Method

Management Science Working Paper No. 7 (2007)

Abstract

Email abstract to a colleague

Linear Complementarity Problems (LCP) belong to the class of NP-complete problems. Therefore we cannot expect a polynomial time solution method for LCPs without requiring some special property of the coefficient matrix. Our aim is to construct interior point algorithm which, according to the duality theorem in EP (existentially polynomial-time) form, gives a solution of the original problem or detects the lack of property P*(?) (with arbitrary large, but a priori fixed ? and gives a polynomial size certificate of it in polynomial time (depending on the given value of parameter ?, the initial interior point and the dimension of the LCP). We give the general idea of a modification of interior point algorithms and illustrate on the long-step path-following interior point algorithm.