Optimization Online


New criss-cross type algorithms for linear complementarity problems with sufficient matrices

Zsolt Csizmadia (csisza***at***cs.elte.hu)
Tibor Illes (illes***at***cs.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
Entry Accepted: 10/21/2003
Entry Last Modified: 05/29/2007

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society