Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$

there exists a vast amount of material and algorithms. But what about this kind of problem:

  • $\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.

share|improve this question
add comment

1 Answer

up vote 1 down vote accepted

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$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.