- 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/2007Entry Accepted: 04/10/2007Entry Last Modified: 04/10/2007Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Programming Society and by the Optimization Technology Center.