Optimization Online


On the complexity of computing the handicap of a sufficient matrix

Etienne De Klerk (e.deklerk***at***uvt.nl)
Marianna Nagy (m.nagy***at***uvt.nl)

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 P-matrices (where all principal minors are positive).

Keywords: sufficient matrix, semidefinite programming, handicap of a matrix

Category 1: Complementarity and Variational Inequalities

Category 2: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Citation: Preprint Tilburg University, The Netherlands, February 2010.

Download: [PDF]

Entry Submitted: 02/15/2010
Entry Accepted: 03/01/2010
Entry Last Modified: 11/19/2010

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