KKT Conditions for Quadratic Programs

Worked Solution

How to Think About It: KKT conditions are the first-order necessary conditions for optimality in a constrained optimization -- the analog of "set the derivative to zero" for the unconstrained case. For a convex problem (PSD $Q$), they are also sufficient: any KKT point is a global minimizer. Before writing the conditions, sketch the structure: equality constraints generate sign-free multipliers (shadow prices that can be positive or negative), while inequality constraints generate nonnegative multipliers that "turn off" when the constraint is slack. Complementary slackness is the condition that formalizes this on/off behavior. The one subtlety to get right is the SIGN of the shadow price, which is dictated by the sign convention you chose in the Lagrangian.

Quick Estimate: In a convex QP the KKT system is a linear system in $(x, \lambda, \mu)$ coupled with the complementarity pairing $\mu_i x_i = 0$ -- you can often solve it directly or reduce it to a linear complementarity problem (LCP). Strict curvature pins down $x$; flat directions of $Q$ are exactly what can create a continuum of optima.

Approach: Form the Lagrangian with $-\lambda^{\top}(Ax-b)$ on the equality block, take $\nabla_x L = 0$ for stationarity, append primal feasibility, dual feasibility on the inequality multipliers, and complementary slackness. For the economic reading, use the envelope theorem on the value function $f^{*}(b)$; the sign of $\partial f^{*}/\partial b_i$ follows mechanically from how $b$ enters $L$. For uniqueness, separate curvature of the objective along feasible directions from the geometry of the feasible polyhedron.

Formal Solution:

*Part 1 -- The KKT conditions.* Form the Lagrangian $L(x, \lambda, \mu) = \frac{1}{2} x^{\top} Q x + c^{\top} x - \lambda^{\top}(Ax - b) - \mu^{\top} x,$ where $\lambda \in \mathbb{R}^m$ are the equality multipliers and $\mu \in \mathbb{R}^n$ the inequality multipliers. The four KKT conditions are:

1. Stationarity ($\nabla_x L = 0$): $\;Qx + c - A^{\top} \lambda - \mu = 0.$
2. Primal feasibility: $\;Ax = b, \quad x \ge 0.$
3. Dual feasibility: $\;\mu \ge 0$ (the equality multipliers $\lambda$ are unrestricted in sign).
4. Complementary slackness: $\;\mu_i x_i = 0$ for each $i$ -- so for every coordinate either $x_i = 0$ (the bound is active) or $\mu_i = 0$ (the bound is slack), or both.

Because $Q \succeq 0$ the problem is convex, so these conditions are not only necessary but also sufficient for global optimality.

*Part 2 -- Economic interpretation (shadow prices).* Let $f^{*}(b)$ be the optimal value as a function of the equality right-hand side $b$. At a KKT point $f^{*}(b) = L(x^{*}, \lambda^{*}, \mu^{*}; b)$ because $Ax^{*} = b$ and $\mu^{*\top} x^{*} = 0$. The only explicit dependence of $L$ on $b$ is the term $+\lambda^{\top} b$, so the envelope theorem gives $\frac{\partial f^{*}}{\partial b_i} = \frac{\partial L}{\partial b_i} = \lambda_i.$ Hence, with this Lagrangian sign convention, $\lambda_i = +\,\partial f^{*}/\partial b_i$: it is the (sign-free) shadow price of equality constraint $i$, telling you how the optimal value moves per unit change in $b_i$. In a portfolio context where the equality is a budget constraint, $\lambda$ is the marginal value of an additional dollar of capital. (Had we used $+\lambda^{\top}(Ax-b)$ instead, the same envelope step would give $\lambda_i = -\,\partial f^{*}/\partial b_i$ -- the sign is purely a convention.)

The multiplier $\mu_i \ge 0$ on $x_i \ge 0$ is the marginal cost of imposing nonnegativity on coordinate $i$. If $\mu_i > 0$ the bound is active ($x_i = 0$) and the optimizer would prefer $x_i < 0$, so you "pay" $\mu_i$ per unit for the restriction; if $\mu_i = 0$ the bound is slack and costless at the margin. By complementary slackness $\mu_i$ is strictly positive only when $x_i = 0$. Note that multipliers are marginal sensitivities (derivatives of $f^{*}$), not the optimal value or the optimal coordinates themselves.

*Part 3 -- Uniqueness and the solution set.*

• Sufficient condition for a unique minimizer. If $Q \succ 0$ (strictly positive definite) the objective is strictly convex everywhere and the minimizer is unique. More sharply, since only feasible directions matter, uniqueness holds whenever $Q$ is strictly convex on the feasible directions, i.e. $d^{\top} Q d > 0$ for every nonzero $d$ with $Ad = 0$ -- this can hold even when $Q$ is only PSD globally.

- Non-unique case and the shape of the optimal set. When $Q$ is only positive semidefinite the objective is flat along $\ker Q$, and there can be a continuum of optimal primal solutions even when the dual solution $\lambda$ is unique. The optimal set is a closed convex set, but it is *not* in general a face of the feasible polyhedron $P = \{x : Ax = b,\ x \ge 0\}$. Concretely, from any single optimizer $x^{*}$ a feasible $x$ is also optimal iff both pieces of $f(x) - f(x^{*}) = \tfrac{1}{2}(x - x^{*})^{\top} Q (x - x^{*}) + (Qx^{*} + c)^{\top}(x - x^{*})$ vanish (each is $\ge 0$ at the optimum: the first by $Q \succeq 0$, the second by the optimality variational inequality). Thus $X^{*} = \{\, x \in P : Q(x - x^{*}) = 0,\ (Qx^{*} + c)^{\top}(x - x^{*}) = 0 \,\},$ an intersection of the polyhedron with affine conditions, which need not be a face.

*Counterexample to the "face" claim.* Take $n = 2$, $c = 0$, the equality $x_1 + x_2 = 1$, and $x \ge 0$, with $Q = \begin{pmatrix} 1 & -1 \\ -1 & 1 \end{pmatrix} \succeq 0$. The feasible set is the segment $\{(t, 1-t) : 0 \le t \le 1\}$ and the objective is $\tfrac{1}{2}(x_1 - x_2)^2$, uniquely minimized at $x^{*} = (\tfrac{1}{2}, \tfrac{1}{2})$. That single interior point of the segment is not a face of the segment, confirming the optimal set is a convex set but not necessarily a face.

Answer: The KKT system is $Qx + c - A^{\top}\lambda - \mu = 0,\quad Ax = b,\quad x \ge 0,\quad \mu \ge 0,\quad \mu_i x_i = 0\ \forall i,$ and for the convex QP ($Q \succeq 0$) it is necessary and sufficient for a global optimum. With the Lagrangian $L = f - \lambda^{\top}(Ax - b) - \mu^{\top} x$, the equality shadow price is $\lambda_i = +\,\partial f^{*}/\partial b_i$ (sign-free), while $\mu_i \ge 0$ is the marginal cost of the bound $x_i \ge 0$, positive only when $x_i = 0$. The minimizer is unique when the objective is strictly convex on feasible directions (e.g. $Q \succ 0$, or $d^{\top} Q d > 0$ for all nonzero $d$ with $Ad = 0$); otherwise the optimal set is the closed convex set $X^{*} = \{x \in P : Q(x - x^{*}) = 0,\ (Qx^{*} + c)^{\top}(x - x^{*}) = 0\}$ -- a convex set that need NOT be a face of the feasible polyhedron, as the $Q = \bigl(\begin{smallmatrix} 1 & -1 \\ -1 & 1 \end{smallmatrix}\bigr)$ example with unique interior optimum $(\tfrac12,\tfrac12)$ shows.