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

Zsolt Csizmadia, T. Illes

Research output: Contribution to journalArticle

7 Citations (Scopus)

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.
LanguageEnglish
Pages247-266
Number of pages19
JournalOptimization Methods and Software
Volume21
Issue number2
DOIs
Publication statusPublished - Apr 2006

Fingerprint

Linear Complementarity Problem
Sufficient
Sufficiency
Finiteness
Positive Definiteness
Duality Theorems
Cycling
M-matrix
Dual Problem
Certificate
Terminate
Linear programming
Polynomial time
Polynomials
Generalise

Keywords

  • linear complementarity problem
  • sufficient matrix
  • criss-cross algorithm
  • alternative and EP theorems

Cite this

@article{c6016b1b5fbf4ad79ada7a5e2068308c,
title = "New criss-cross type algorithms for linear complementarity problems with sufficient matrices",
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.",
keywords = "linear complementarity problem, sufficient matrix, criss-cross algorithm, alternative and EP theorems",
author = "Zsolt Csizmadia and T. Illes",
year = "2006",
month = "4",
doi = "10.1080/10556780500095009",
language = "English",
volume = "21",
pages = "247--266",
journal = "Optimization Methods and Software",
issn = "1055-6788",
number = "2",

}

New criss-cross type algorithms for linear complementarity problems with sufficient matrices. / Csizmadia, Zsolt; Illes, T.

In: Optimization Methods and Software, Vol. 21, No. 2, 04.2006, p. 247-266.

Research output: Contribution to journalArticle

TY - JOUR

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

AU - Csizmadia, Zsolt

AU - Illes, T.

PY - 2006/4

Y1 - 2006/4

N2 - 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.

AB - 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.

KW - linear complementarity problem

KW - sufficient matrix

KW - criss-cross algorithm

KW - alternative and EP theorems

UR - http://dx.doi.org/10.1080/10556780500095009

U2 - 10.1080/10556780500095009

DO - 10.1080/10556780500095009

M3 - Article

VL - 21

SP - 247

EP - 266

JO - Optimization Methods and Software

T2 - Optimization Methods and Software

JF - Optimization Methods and Software

SN - 1055-6788

IS - 2

ER -