# Linear complementarity problem - Classification

For Linear complementarity problems (LCP) like

• $\mathbf{Mz}+\mathbf{q} \ge \mathbf{0}$
• $\mathbf{z} \ge \mathbf{0}$
• $\mathbf{z}^{\mathrm{T}}(\mathbf{Mz}+\mathbf{q}) = 0$

• $\mathbf{Mz}+\mathbf{q} \ge \mathbf{0}$
• $\mathbf{Az} +\mathbf{b}\ge \mathbf{0}$
• $(\mathbf{Az} +\mathbf{b})^{\mathrm{T}}(\mathbf{Mz}+\mathbf{q}) = 0$

Is it also called LCP? Can it be transformed into the form above?

The real question is, how to solve it without the need to invert one of the matrices explicitly.

-

To answer your last question, you can formulate your problem as a quadratic program and then solve it using one of the standard methods for solving quadratic programs. (And, yes, your problem can be transformed into a linear complementarity problem. See the end of my answer.)

Rewrite the equality constraint as $$0 = {\bf z}^T {\bf A}^T {\bf Mz} + {\bf z}^T {\bf A}^T {\bf q} + {\bf b}^T {\bf Mz} + {\bf b}^T {\bf q} = {\bf z}^T {\bf A}^T {\bf Mz} + {\bf z}^T ({\bf A}^T {\bf q} + {\bf M}^T {\bf b}) + {\bf b}^T {\bf q}.$$ The second equality is valid because ${\bf b}^T {\bf Mz}$ is a scalar.

Now, ${\bf A}^T {\bf M}$ is not necessarily symmetric, but by doing the matrix multiplication you can find some symmetric matrix ${\bf Q}$ so that ${\bf z}^T {\bf A}^T {\bf Mz} = \frac{1}{2} {\bf z}^T {\bf Qz}$. Then your problem is equivalent to solving the quadratic program

$$\min \frac{1}{2}{\bf z}^T {\bf Q z} + {\bf z}^T {\bf c} + {\bf b}^T {\bf q}$$ subject to $${\bf Mz} + {\bf q} \geq {\bf 0},$$ $${\bf Az} + {\bf b} \geq {\bf 0},$$ where ${\bf c} = {\bf A}^T {\bf q} + {\bf M}^T {\bf b}$.

Why is this equivalent to your problem? Let ${\bf z}^*$ be the optimal solution to the quadratic program. The value of ${\bf z}^*$ cannot be smaller than $0$ because the problem constraints force $({\bf Az} + {\bf b})^T({\bf Mz} + {\bf q}) \geq 0$. If the value of ${\bf z}^*$ is $0$, then ${\bf z}^*$ is a solution to your second problem. If the value of ${\bf z}^*$ is strictly greater than $0$, then you cannot force $({\bf Az} + {\bf b})^T({\bf Mz} + {\bf q})$ to $0$ while satisfying the first two constraints, and so there is no solution to your second problem.

If you want, you could also transform the quadratic program into a linear complementarity problem. The Wikipedia page on linear complementarity problems explains how to do that, so I'll leave it to you to work that out if you want. You will have to introduce a nonnegativity constraint on the variables in the quadratic program first, though. The standard way to do that is to replace ${\bf z}$ with ${\bf z}^+ - {\bf z}^-$ throughout the quadratic program and add the nonnegativity constraints ${\bf z}^+ \geq 0, {\bf z}^- \geq 0$.

-