ISSN:
1573-2878
Keywords:
Linear complementarity problem
;
Murty's algorithm
;
digraphs
;
P-matrices
;
Q-matrices
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Notes:
Abstract The linear complementarity problem (M|q) is to findw andz inR n such thatw−Mz=q,w≥0,z≥0,w t z=0, givenM inR n×n andq in . Murty's Bard-type algorithm for solving LCP is modeled as a digraph. Murty's original convergence proof considered allq inR n andM inR n×n , aP-matrix. We show how to solve more LCP's by restricting the set ofq vectors and enlarging the class ofM matrices beyondP-matrices. The effect is that the graph contains an embedded graph of the type considered by Stickney and Watson wheneverM is a matrix containing a principal submatrix which is aP-matrix. Examples are presented which show what can happen when the hypotheses are further weakened.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF00940447
Permalink