Derive LCP from KKT conditions of a QP

Question

I'm working through this tutorial on LCPs and interior point methods. In it, the authors claim that the following quadratic program $$ \begin{aligned} \min \quad& \frac{1}{2}u^TQu - c^Tu\\ \text{subject to} \quad& Au\leq b, 0 \leq u \end{aligned} $$ has the following KKT conditions $$ \begin{align} y &= Mx+q,\; x^Ty = 0, \; 0 \leq x, \; 0 \leq y \end{align} $$ where $$ \begin{align} x &= \begin{bmatrix}u\\v\end{bmatrix}\\ M &= \begin{bmatrix}Q & A^T\\-A & 0\end{bmatrix}\\ q &= \begin{bmatrix}-c\\b\end{bmatrix}. \end{align} $$ (Note, I already corrected $q$ to have $-c$.) The authors claim the KKT conditions are equivalent to a linear complementarity problem.

I am trying to derive the above LCP from the KKT conditions as I know them. I can write the KKT conditions down as

$$ \begin{align} 0&\leq u\\ 0&\leq Au-b\\ 0&\leq v\\ 0&\leq \lambda\\ 0&=v^T(Au-b)\\ 0&=\lambda^Tu\\ 0&=Qu-c+A^Tv+\lambda \end{align} $$ where $v$ and $\lambda$ are Lagrange multipliers. I believe the source of my confusion is understanding which relation ($=,\subset,\supset,\cap\neq\emptyset$) should go in the middle of $$ SOL(QP) \quad?\quad SOL(LCP) $$ This is confusion from a number of directions. First, if $\lambda = 0$ and the LCP is feasible, then I can argue that $(u,v) \in \text{SOL(QP)}$ $\Rightarrow$ $(u,v) \in \text{SOL(LCP)}$. However, what if $\lambda \neq 0$? Second, the complimentarity constraint in the LCP evaluates to $$ x^Ty = u^T(Qu -c + A^Tv) -v^T(Au-b) = 0 $$ which isn't the same as requiring the equality constraints in the KKT conditions because $u^T(Qu -c + A^Tv) = v^T(Au-b)$ might happen.

I noticed similar issues also show up in Cotte's book, Lemma 3.1.1. Again, the Lagrange multipliers on the inequality constraint $x\geq0$ are ignored.

Answer 1

I came across this post in searching something related, and although it's old I'll try to offer an answer in case it helps anyone else that comes across it.

I think there are a few difficulties here:

1. First, because $u$ is non-negative, the Lagrangian function should be $$L(u,v,\lambda) = \frac{1}{2}u^T Q u - c^T u + v^T(Au - b) - \lambda^T u.$$ Note here the minus sign before the $\lambda^T u$ term. Hence, when we take the partial derivative with respect to $u$ and set it to zero, we should get $$0 = Qu - c + A^T v - \lambda.$$ Again, note the sign discrepancy in the original post.
2. Clearly, $0 \leq Au - b$ in the original KKT conditions should be $0 \geq Au - b$.
3. The OP did not specify how $y$ in the LCP relates to the original QP. I would propose that $y$ be defined as $$y = \left[\begin{array}{c} \lambda\\ s\\ \end{array}\right]$$ where $s \geq 0$ is a vector of slack variables on the $Au \leq b$ inequalities. Note, however, that there is no need to add the slack variable before writing down the KKT conditions. We can just do it after. So, this results in the following additional changes to the OP's KKT conditions $$ 0 \geq Au - b \quad \longrightarrow \quad 0 = Au + s - b $$ and, by substitution, $$0 = v^T(Au - b) \quad \longrightarrow \quad 0 = v^T s.$$

After this, we can see that the LCP conditions exactly match the KKT conditions with the exception that in the LCP conditions $x^T y = 0$ implies that $\lambda^T u + v^T s = 0$, whereas in the KKT conditions we have $\lambda^T u = 0$ and $v^T s = 0$ separately. However, note that these are equivalent due to the fact that $\lambda, v, u, s \geq 0$.

To answer some of the other questions raised, we have that KKT conditions are always necessary, but not always sufficient. We gain sufficiency whenever the KKT conditions are applied to a convex problem. So, in the context of QP, we have equivalence between QP and LCP whenever the QP is convex, i.e., the $Q$ matrix is PSD.