## Invited Session Tue.1.MA 313

#### Tuesday, 10:30 - 12:00 h, Room: MA 313

**Cluster 3: Complementarity & variational inequalities** [...]

### Matrix classes for linear complementarity problems

**Chair: Todd Munson**

**Tuesday, 10:30 - 10:55 h, Room: MA 313, Talk 1**

**Todd Munson**

Preprocessing with composite matrices

**Abstract:**

In this talk, I present a class of matrices called composite matrices that include nonnegative matrices with positive diagonals and P-matrices, and form a subset of the strictly semi-monotone matrices. These matrices have interesting properties that are useful when preprocessing linear complementarity problems to improve the model formulation. In particular, we can easily include implied bounds on the variables for subproblems identified by finding diagonal composite matrix blocks.

**Tuesday, 11:00 - 11:25 h, Room: MA 313, Talk 2**

**Richard Warren Cottle**

Lemke's algorithms and matrix classes for the linear complementarity problem

**Coauthor: Ilan Adler**

**Abstract:**

This survey paper deals with the algorithms of Carleton

E. Lemke for the linear complementarity problem. Special attention is paid to the matrix classes for which these algorithms are known to be applicable. The algorithms were not designed to obtain more than one solution, although in some cases, repeated application of a variant of the algorithm will yield several solutions. Nevertheless, there are instances where some solutions are "elusive'' or "inaccessible'' by the algorithm in question. We review efforts that have been made to overcome this limitation. We also examine other equilibrium problems and investigate a different (possibly novel) algorithm for exposing "elusive'' equilibrium points.

**Tuesday, 11:30 - 11:55 h, Room: MA 313, Talk 3**

**Gabriele E. Uchida**

Think co(mpletely)positive! Algebraic properties of matrices belonging to the copositive or related cones

**Coauthors: Immanuel M. Bomze, Werner Schachinger**

**Abstract:**

In the context of conic programming (optimizing a linear functional over a convex cone subject to linear constraints) properties of, and relations between, corresponding matrix classes play an important role. A well known subclass of this problem family is semi-definite programming and, to a quickly expanding extent, copositive programming. Therefore the cones of copositive matrices and the dual cone, all completely positive matrices, are studied and structural algebraic properties provided. Several (counter-)examples demonstrate that many relations familiar from semidefinite optimization may fail in the copositive context, illustrating the transition from polynomial-time to NP-hard worst-case behaviour.