New criss-cross type algorithms for linear complementarity problems with sufficient matrices
Zsolt Csizmadia (csiszacs.elte.hu)
Abstract: We generalize new criss-cross 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º-Balogh-Illés's criss-cross type algorithm for LCP-QP 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,criss-cross algorithm, alternative and EP theorems.
Category 1: Applications -- OR and Management Sciences
Citation: Accepted for publication
Entry Submitted: 10/16/2003
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|