# How do I find KKT Conditions for the Quadratic Function?

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?

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.)
• 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/…) – Zac Mar 16 '18 at 20:43
• @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. – angryavian Mar 16 '18 at 20:54