Strathprints Home | Open Access | Browse | Search | User area | Copyright | Help | Library Home | SUPrimo

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

Csizmadia, Zsolt and Illes, T. (2006) New criss-cross type algorithms for linear complementarity problems with sufficient matrices. Optimization Methods and Software, 21 (2). pp. 247-266. ISSN 1055-6788

Full text not available in this repository. (Request a copy from the Strathclyde author)

Abstract

We generalize new criss-cross type algorithms for linear complementarity problems (LCPs) given with sufficient matrices. Most LCP solvers require a priori 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 Akkeles¸, Balogh and Ille´s's criss-cross type algorithm for LCP-QP problems. We modify our basic algorithm in such a way that it can start with any matrix M , without having any information about the properties of the matrix (sufficiency, bisymmetry, positive definiteness, etc.) in advance. Even in this case, our algorithm terminates with one of the following cases in a finite number of steps: it solves the LCP problem, it solves its dual problem or it gives a certificate that the input matrix is not sufficient, thus cycling can occur. Although our algorithm is more general than that of Akkeles¸, Balogh and Ille´s's, the finiteness proof has been simplified. Furthermore, the finiteness proof of our algorithm gives a new, constructive proof to Fukuda and Terlaky's LCP duality theorem as well.

Item type: Article
ID code: 28221
Keywords: linear complementarity problem, sufficient matrix, criss-cross algorithm, alternative and EP theorems, Management. Industrial Management
Subjects: Social Sciences > Industries. Land use. Labor > Management. Industrial Management
Department: Strathclyde Business School > Management Science
Related URLs:
    Depositing user: Mrs Caroline Sisi
    Date Deposited: 21 Oct 2010 17:42
    Last modified: 12 Mar 2012 11:20
    URI: http://strathprints.strath.ac.uk/id/eprint/28221

    Actions (login required)

    View Item