Polynomial interior point algorithms for general LCPs

Tibor Illés(illesmath.elte.hu)
Marianna Nagy(nmarianncs.elte.hu)
Tamás Terlaky(terlakymcmaster.hu)

Abstract: Linear Complementarity Problems ($LCP$s) belong to the class of $\mathbb{NP}$-complete problems. Therefore we can not expect a polynomial time solution method for $LCP$s without requiring some special property of the matrix coefficient matrix. Our aim is to construct some interior point algorithms which, according to the duality theorem in EP form, gives a solution of the original problem or detects the lack of property $\mathcal{P}_*(\tilde\kappa)$ (with arbitrary large, but apriori fixed $\tilde\kappa$) and gives a polynomial size certificate of it in polynomial time (depending on parameter $\tilde{\kappa}$, the initial interior point and the dimension of the $LCP$). We give the general idea of a modification of interior point algorithms and present three concrete methods: affine scaling, long-step path-following and predictor-corrector interior point algorithm.

Keywords: LCP, interior point method, sufficient matrix, EP theorem

Category 1: Linear, Cone and Semidefinite Programming

Citation: unpublished: ORR 2007-3 Eötvös Loránd University of Sciences, Department of Operations Research, Budapest, Hungary 02/2007

Download: [PDF]

Entry Submitted: 04/10/2007
Entry Accepted: 04/10/2007
Entry Last Modified: 04/10/2007

Modify/Update this entry