2
$\begingroup$

I am trying to understand how to find the KKT conditions for the general Quadratic Programming problem, in vector form. Following Cornujoels & Tütüncü (7.1), this is written:

$$\min_x \frac{1}{2}\, \underline{x}^T Q\, \underline{x} + c^T \underline{x}$$ $$s.t. \;A \underline{x} = \underline{b}$$ $$\qquad \underline{x} \geq 0$$

I believe the first optimality condition is that the gradient of the Lagrangian $ (\mathcal{\nabla L})$ will be equal to zero, where:

$$ \mathcal{L}(\underline{x},\lambda) = \frac{1}{2} \underline{x}^T Q \,\underline{x} + c^T \underline{x} - \lambda \,(\underline{b}-A \underline{x} )$$

but I am not entirely sure how to actually perform the differentiation given that the Lagrangian appears to be a matrix; are we looking for the Jacobian?

In the textbook, equation 7.3 gives the first KKT condition to be: $$ A^T \underline{y} - Q \underline{x} + \underline{s} = \underline{c} $$ which I simply can't follow. It seems to be using the variables $y, s$ from the dual problem (7.2), but I'm not sure why, or why there appears to be a slack variable $s$.

Am I wrong to think I should be differentiating the Lagrangian of the primal problem, and if so, why?

$\endgroup$
0
$\begingroup$

The Lagrangian is $$L(x, y, s) = \frac{1}{2} x^\top Q x + c^\top x + y^\top (b-Ax) - s^\top x$$ with $s \succeq 0$.

Taking the gradient yields $$Qx + c - A^\top y - s.$$ (Note that you copied down the KKT condition incorrectly.)

$\endgroup$
  • $\begingroup$ Thanks - I've corrected the equation. I see how you took the gradient, which visually looks like treating the vectors like scalars but I realise now (of course) that $x^T Q x$ is in fact a sum of scalars, as are the other terms. However, I don't see how you have calculated the Lagrangian? (Note: I was following (12.16) from Nocedal & Wright xn--vjq503akpco3w.top/literature/…) $\endgroup$ – Zac Mar 16 '18 at 20:43
  • $\begingroup$ @Zac Maybe look at this section of a Wikipedia page. Basically the constraints $Ax=b$ and $x \ge 0$ are a sequence of one-dimensional constraints $a_i^\top x = b$ and $x_j \ge 0$, so if you get a Lagrange multiplier for each constraint. The sums on the Wikipedia page can be condensed using matrix notation, so the vectors $y$ and $s$ are vectors of Lagrange multipliers. $\endgroup$ – angryavian Mar 16 '18 at 20:54
  • $\begingroup$ Ah excellent. The vector notation had me confused but that makes sense! And I guess I had missed that the non-negativity constraints needed to be included in the Lagrangian too. Putting those together and I get the same answer, thank you. $\endgroup$ – Zac Mar 16 '18 at 21:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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