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


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


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


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.


  cash advance online . But it is worth noting that these tests were carried out on the blood cells. Therefore, it's too early to say about scientific evidence of Viagra influence on blood clots.