On the complexity of computing the handicap of a sufficient matrix

E. de Klerk, M. Nagy

Research output: Contribution to journalArticleScientificpeer-review

Abstract

The class of sufficient matrices is important in the study of the linear complementarity problem (LCP)—some interior point methods (IPM’s) for LCP’s with sufficient data matrices have complexity polynomial in the bit size of the matrix and its handicap.In this paper we show that the handicap of a sufficient matrix may be exponential in its bit size, implying that the known complexity bounds of interior point methods are not polynomial in the input size of the LCP problem. We also introduce a semidefinite programming based heuristic, that provides a finite upper bond on the handicap, for the sub-class of Ρ-matrices (where all principal minors are positive).
Original languageEnglish
Pages (from-to)383-402
JournalMathematical Programming
Volume129
Issue number2
Publication statusPublished - 2011

Fingerprint

Sufficient
Computing
Linear Complementarity Problem
Interior Point Method
Polynomials
Polynomial Complexity
Semidefinite Programming
Minor
Heuristics
Polynomial
Class

Cite this

@article{90d8fd123461472bb9bc3ce0e75bf394,
title = "On the complexity of computing the handicap of a sufficient matrix",
abstract = "The class of sufficient matrices is important in the study of the linear complementarity problem (LCP)—some interior point methods (IPM’s) for LCP’s with sufficient data matrices have complexity polynomial in the bit size of the matrix and its handicap.In this paper we show that the handicap of a sufficient matrix may be exponential in its bit size, implying that the known complexity bounds of interior point methods are not polynomial in the input size of the LCP problem. We also introduce a semidefinite programming based heuristic, that provides a finite upper bond on the handicap, for the sub-class of Ρ-matrices (where all principal minors are positive).",
author = "{de Klerk}, E. and M. Nagy",
year = "2011",
language = "English",
volume = "129",
pages = "383--402",
journal = "Mathematical Programming",
issn = "0025-5610",
publisher = "Springer",
number = "2",

}

On the complexity of computing the handicap of a sufficient matrix. / de Klerk, E.; Nagy, M.

In: Mathematical Programming, Vol. 129, No. 2, 2011, p. 383-402.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

T1 - On the complexity of computing the handicap of a sufficient matrix

AU - de Klerk, E.

AU - Nagy, M.

PY - 2011

Y1 - 2011

N2 - The class of sufficient matrices is important in the study of the linear complementarity problem (LCP)—some interior point methods (IPM’s) for LCP’s with sufficient data matrices have complexity polynomial in the bit size of the matrix and its handicap.In this paper we show that the handicap of a sufficient matrix may be exponential in its bit size, implying that the known complexity bounds of interior point methods are not polynomial in the input size of the LCP problem. We also introduce a semidefinite programming based heuristic, that provides a finite upper bond on the handicap, for the sub-class of Ρ-matrices (where all principal minors are positive).

AB - The class of sufficient matrices is important in the study of the linear complementarity problem (LCP)—some interior point methods (IPM’s) for LCP’s with sufficient data matrices have complexity polynomial in the bit size of the matrix and its handicap.In this paper we show that the handicap of a sufficient matrix may be exponential in its bit size, implying that the known complexity bounds of interior point methods are not polynomial in the input size of the LCP problem. We also introduce a semidefinite programming based heuristic, that provides a finite upper bond on the handicap, for the sub-class of Ρ-matrices (where all principal minors are positive).

M3 - Article

VL - 129

SP - 383

EP - 402

JO - Mathematical Programming

JF - Mathematical Programming

SN - 0025-5610

IS - 2

ER -