  


New crisscross type algorithms for linear complementarity problems with sufficient matrices
Zsolt Csizmadia (csiszacs.elte.hu) Abstract: We generalize new crisscross type algorithms for linear complementarity problems (LCPs) given with sufficient matrices. Most LCP solvers require apriori information about the input matrix. The sufficiency of a matrix is hard to be checked (no polynomial time method is known). Our algorithm is similar to Zhang's linear programming, and AkkeleºBaloghIllés's crisscross type algorithm for LCPQP problems. We modify our basic algorithm in such a way that can start with any matrix M, without having information about the property of the matrix (sufficiency, bisymmetricity, positive definitness, etc) in advance. Even in this case our algorithm terminates with one of the following cases in finite number of steps: it solves the LCP problem, solves its dual problem, or gives a certificate that the input matrix is not sufficient, so cycling can occur. Although our algorithm is more general than that of Akkeleº and Illés's, the finiteness proof has benn simplified. Furhermore, the finiteness proof of our algorithm gives a new, constructive proof to Fukuda and Terlaky`s LCP duality theorem as well. Keywords: linear complementarity problem, sufficient matrix,crisscross algorithm, alternative and EP theorems. Category 1: Applications  OR and Management Sciences Citation: Accepted for publication Download: Entry Submitted: 10/16/2003 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  