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:
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?
Why do we get equal signs in the first two conditions? Why isn't it like the last condition?
Since the cost is a positive definite quadratic we see that there are solutions and the solution set is compact.
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$).