Linear Complementarity Problem (LCP)
Let $M\in\mathbf{R}^{n\times n}$ and $q\in\mathbf{R}^n$ be a matrix and a vector of real numbers, this application uses Lemke's algorithm to find the vectors $z\in\mathbf{R}^n$ and $w\in\mathbf{R}^n$ that satisfy the condition \[ z\geqslant 0,w=Mz+q\geqslant 0\quad\text{and}\;\; z^Tw=0 \]
Input Data
See Input Data for how to enter data to a matrix and a vector of real numbers.
NOTE: There are some problems that cannot be solved using Lemke's algorithm as implemented in this calculator. For example, \[ M = \left(\begin{array}{rrrr} 0 & 0 & 10 & 20 \\ 0 & 0 & 30 & 15 \\ 10 & 20 & 0 & 0 \\ 30 & 15 & 0 & 0 \end{array}\right)\quad\text{and}\;\; q = \left(\begin{array}{c} -1 \\ -1 \\ -1 \\ -1 \end{array}\right) \] To solve this problem, NCP Solver is recommended, with $F(x)=Mx+q$: \[ \begin{align} 10x_3+20x_4-1 & \\ 30x_3+15x_4-1 & \\ 10x_1+20x_2-1 & \\ 30x_1+15x_2-1 & \end{align} \]