0
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – copper.hat
    Commented May 5, 2017 at 3:33
  • $\begingroup$ @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? $\endgroup$
    – Nikitau
    Commented May 6, 2017 at 22:18
  • $\begingroup$ Where did you get the KKT conditions above? They don't look quite right to me. $\endgroup$
    – copper.hat
    Commented May 7, 2017 at 0:38

1 Answer 1

1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .