Contents Previous Next Subchapters Current Chapters-> interp interp1 lagrange polyfit smospl cubespl cubeval interp2 mlmode_interp2 snewton brent linlsq linlsqb nlsq dnlsq nlsqbox dnlsqb conjdir neldermead conjgrad minline lemke Qpos Qbox Qpro sqp relative fordiff cendiff autodiff testder testgrad testhess Parent Chapters-> Omatrix6 fit lemke Search Tools-> contents reference index search

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 ```