### Tibor Illés (Management Science, University of Strathclyde)

#### Linear complementarity problems: matrix classes, alternative theorems, algorithms

*Wednesday 3 October 2007 at 15.30, JCMB 5327*

##### Abstract

Linear complementarity problems (LCP) are widely used for instance in
industrial engineering, management science, economics, game theory and has
a long history. In the late eighties, for solving several classes of LCP,
mainly pivot algorithms were used. In early nineties, started by the work of
Kojima and his co-authors, interior point algorithms with polynomial complexity
have been developed for a wide class of LCP.

In this talk we would like to discuss the effect of the properties of
matrix on the efficient solvability of LCP problems. Recently,
Potra and his co-author developed an algorithm that solves any
sufficient LCP in polynomial time without knowing the ? value of
the matrix in advance. Following the ideas of Potra, taking into
consideration the alternative theorem of LCP proved by Fukuda
and Terlaky and its EP-theorem form introduced by Fukuda and his
co-authors we were able to obtain some nice and general
results. We showed that general linear complementarity problems
can be solved in the following (EP-theorem) sense: interior
point methods with a given nonnegative real parameter k, either
solves (in polynomial time, depending on the size of the problem
and k) the primal linear complementarity problem, or solves - in
the same manner - the dual linear complementarity problem, or
gives a polynomial size certificate that the matrix of the
problem is not in the class of P*(k)-matrices.

### Seminars by year

*Current*
*2016*
*2015*
*2014*
*2013*
*2012*
*2011*
*2010*
*2009*
*2008*
*2007*
*2006*
*2005*
*2004*
*2003*
*2002*
*2001*
*2000*
*1999*
*1998*
*1997*
*1996*