# KKT conditions for QP $\min x_1^2 - 2x_1 x_2 + 4x_2^2 + 2x_1$?

I'm trying to solve for KKT conditions for the following QP

$\min x_1^2 - 2x_1 x_2 + 4x_2^2 + 2x_1$ subject to

$2x_1 x_2 \geq 4$

$x_1, x_2$ both free.

So first, I know that quadratic KKT conditions are of the form

$0 \leq \bar{x} \perp Q\bar{x} - A'\bar{x} + p \geq 0$

$0 \leq \bar{u} \perp A \bar{x} -b \geq 0$

In other words, our complimentary condition is $\bar{x} (Q\bar{x} - A'\bar{x} + p) = 0$ and our feasibility condition is $\bar{x} \geq 0$.

And so, first I find that $Q = \begin{bmatrix}2&2\\2&8\end{bmatrix}$, $p = \begin{bmatrix}2\\0\end{bmatrix}$.

And in my solution sheet, the KKT condition for the probem is listed as:

$2x_1 - 2x_2 - 2u_1 + 2 = 0$

$2x_1 + 8 x_2 - u_1 = 0$

$0 \leq 2x_1 + 2x_2 - 4 \perp u_1 \geq 0$

My questions are as follows:

1. When dealing with the $x_1x_2$ term in Q, do we just throw on a negative sign in front of it when putting it in the KKT conditions?

2. Why do we get equal signs in the first two conditions? Why isn't it like the last condition?

• I think you are missing some minus signs in your Hessian. Also, you should check for a global minimum that might satisfy the constraint in which case the complementarity conditions are irrelevant. Commented May 5, 2017 at 3:33
• @copper.hat Thanks! I'm realizing now that the diagonals in my Hessian should be negative because it's $-2x_1x_2$. Ah, I see. So would a global minimum like $\bar{x} = 0, 0$ satisfy the constraints? And so this renders our complementary conditions irrelevant? Commented May 6, 2017 at 22:18
• Where did you get the KKT conditions above? They don't look quite right to me. Commented May 7, 2017 at 0:38

It is straightforward to check that the unconstrained $\min$ $(-{4 \over 3}, -{1 \over 3})$ does not satisfy the constraint, hence the constraint is active.
The KKT conditions would then be \begin{eqnarray} 2 x_1 - 2 x_2 + 2 + 2 \lambda x_2 &=& 0 \\ -2 x_1 + 8 x_2 + 2 \lambda x_1 &=& 0 \\ 2 x_1 x_2 &=& 4 \end{eqnarray} We can solve these, however it is easier in this case to notice that $x_2 = {2 \over x_1}$ and then the problem reduces to finding the minimisers of $x_1^2+ 2 x_1 + {4 \over x_1^2} - 4$. A little work shows that there is a global minimiser $x_1^* \in [-3,-1]$ (at $x_1^*\approx -2.306$, $x_2^* \approx -0.867$ with corresponding multiplier $\lambda^* \approx -0.505$).