  


Polynomial interior point algorithms for general LCPs
Tibor Illés(illesmath.elte.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, longstep pathfollowing and predictorcorrector interior point algorithm. Keywords: LCP, interior point method, sufficient matrix, EP theorem Category 1: Linear, Cone and Semidefinite Programming Citation: unpublished: ORR 20073 Eötvös Loránd University of Sciences, Department of Operations Research, Budapest, Hungary 02/2007 Download: [PDF] Entry Submitted: 04/10/2007 Modify/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  