Contents | Previous | Next | Subchapters |

Syntax |
`lemke(` level`, ` maxitr`, ` M`, ` q`, ` wout`, ` zout`)` |

See Also | Qpos |

Uses Lemke's algorithm to solve the linear complementarity problem; i.e., determine column vectors

*z* __>__ 0

and *w* __>__ 0

such that

*w* - *M* * *z* = *q*

*w*(*i*) * *z*(*i*) = 0 for all *i*

This problem and algorithm are discussed in Section 10.6 of
the second edition of
`lemke`

is true, if it succeeds,
and false otherwise.

The integer scalar

The input values of the parameters `lemke`

is true.
These output values have the same
type and dimensions as

The integer scalar *level* __>__ 1

, the text "Begin lemke" and
the value of `z0`

and the residual in the
complementarity equation are printed. These should both be zero.
If the algorithm fails for some reason, a message is printed
to this effect.
The message "Lemke returns true" is printed if the algorithm succeeds.

If *level* __>__ 2

, the value of `z0`

and its current
numerical error, `e0`

, are printed at each iteration.
In addition, the index and value of the current pivot element
and the corresponding right hand side of the equation is
printed at each iteration. The indices corresponding to the
basic variables (nonzero variables) are printed at each iteration
as well as at the end of the algorithm.
Lemke's algorithm completes when it finds a combination of basic variables
that results in a numerically zero value for `z0`

.
If *m*

is the number of rows in *m* + 1

correspond to the elements of *m* + 1

corresponds to `z0`

,
index values greater than *m* + 1

correspond to the elements of

If *level* __>__ 3

, the Tableaux is printed at each iteration
(see Table 10.6.3 of The following problem

minimize *x*(1)^2 + *x*(2)^2 + *x*(1) - *x*(2)

subject to *x* __>__ 0

has corresponding Lagrangian

*L*(*x*, *w*) = *x*(1)^2 + *x*(2)^2 + *x*(1) - *x*(2) - *w*(1) *x*(1) - *w*(2) *x*(2)

Setting the partial derivative of the Lagrangian
with respect to *x*

equal to zero we have

*w*(1) - 2 *x*(1) = +1

*w*(2) - 2 *x*(2) = -1

This corresponds to the following linear complementarity problem:
```
```

clear

#

M = {[2., 0.], [0., 2.]}

q = {+1., -1.}

#

level = 1

maxitr = 10

wout = novalue

zout = novalue

format real "g5.2"

flag = lemke(level, maxitr, M, q, wout, zout)

print "flag =", flag