Contents Previous Next Subchapters

Solving Linear Complementarity Problems
Syntax lemke(level, maxitr, M, q, wout, zout)
See Also Qpos

Description
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 Practical Methods of Optimization by R. Fletcher. The return value of lemke is true, if it succeeds, and false otherwise.

The integer scalar maxitr specifies the maximum number of iterations to try before aborting. It is possible for Lemke's algorithm to cycle in a manner similar to the simplex method. The real or double-precision square matrix M specifies the linear term in the complementarity problem. The column vector q specifies the constant term in the complementarity problem. It has the same number of rows as the matrix M

The input values of the parameters wout and zout do not matter. The output values constitute the solution of the problem provided that the return value of lemke is true. These output values have the same type and dimensions as q.

The integer scalar level specifies the level of tracing during the execution of the algorithm. If level > 1, the text "Begin lemke" and the value of M, and q are printed at the beginning of the algorithm. The output values of wout and zout are printed at the end of the algorithm. In addition, the final 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, index values less than m + 1 correspond to the elements of w, the index value m + 1 corresponds to z0, index values greater than m + 1 correspond to the elements of z.

If level > 3, the Tableaux is printed at each iteration (see Table 10.6.3 of Practical Methods of Optimization for a description of the Tableaux).

Example
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