The KKT System#
KKT says that at a constrained optimum the objective gradient is a non-negative combination of the active constraint gradients. Inactive constraints carry zero multiplier — that is complementary slackness, and it is what makes the system solvable.
The Karush–Kuhn–Tucker (KKTKarush–Kuhn–Tucker (optimality conditions)) conditions are the generalisation of "set the derivative to zero" to constrained problems. For the primal
\min_x &\quad f(x) \\ \text{s.t.} &\quad g_i(x) = 0, \quad i = 1, \ldots, m \\ &\quad h_j(x) \leq 0, \quad j = 1, \ldots, p \end{aligned}$$ with differentiable $f, g_i, h_j$, the KKT conditions are: 1. **Stationarity:** $\nabla_x \mathcal{L}(x, \lambda, \nu) = 0$, i.e., $$\nabla f(x) + \sum_{i=1}^m \nu_i \nabla g_i(x) + \sum_{j=1}^p \lambda_j \nabla h_j(x) = 0$$ 2. **Primal feasibility:** $g_i(x) = 0 \;\forall i$, $h_j(x) \leq 0 \;\forall j$ 3. **Dual feasibility:** $\lambda_j \geq 0 \;\forall j$ (inequality multipliers nonnegative; equality multipliers $\nu_i$ unrestricted) 4. **Complementary slackness:** $\lambda_j \, h_j(x) = 0 \;\forall j$ Together, these four conditions are **necessary** for a local minimum when a constraint qualification holds, and **sufficient** under convexity (if $f$ and $h_j$ are convex, $g_i$ affine, then any KKT point is a global minimum). **Why four parts?** Each plays a distinct role: - Stationarity says the gradient of the objective is balanced by a linear combination of constraint gradients — constraints "push back" against the objective. - Primal feasibility says the point must actually satisfy the constraints. - Dual feasibility locks the sign of inequality multipliers (penalties can only push *inward* from the boundary). - Complementary slackness says at most one of $\lambda_j$ and $h_j(x)$ can be nonzero: if a constraint is slack ($h_j(x) < 0$), its multiplier must be zero; if the multiplier is positive, the constraint must be active ($h_j(x) = 0$). ## Complementary Slackness The product $\lambda_j h_j(x) = 0$ encodes the logic: **an inactive constraint does not participate in stationarity**. If $h_j(x) < 0$, then $\lambda_j = 0$ and $\lambda_j \nabla h_j(x)$ vanishes from the stationarity equation. The constraint is invisible to optimality — which makes intuitive sense: if you are inside the feasible region away from the boundary, the wall does not affect where you stand. Conversely, if $\lambda_j > 0$, then $h_j(x) = 0$ — the constraint is binding. The positive multiplier indicates the constraint is "pushing back" against the objective: relaxing it would allow the objective to decrease. **Worked numeric example.** Consider $$\min_x \; x_1^2 + x_2^2 \quad \text{s.t.} \quad x_1 + x_2 \geq 2, \; x_1 \geq 0$$ Rewrite in standard form: $$h_1(x) = 2 - x_1 - x_2 \leq 0, \quad h_2(x) = -x_1 \leq 0$$ Lagrangian: $\mathcal{L} = x_1^2 + x_2^2 + \lambda_1(2 - x_1 - x_2) + \lambda_2(-x_1)$. Stationarity: $$\frac{\partial \mathcal{L}}{\partial x_1} = 2x_1 - \lambda_1 - \lambda_2 = 0$$ $$\frac{\partial \mathcal{L}}{\partial x_2} = 2x_2 - \lambda_1 = 0 \;\Rightarrow\; x_2 = \lambda_1/2$$ From the geometry (smallest circle touching the line $x_1 + x_2 = 2$ in the right half-plane), the solution is $(1, 1)$. At this point: - $h_1(1,1) = 0$ (active), so $\lambda_1 \geq 0$ - $h_2(1,1) = -1 < 0$ (inactive), so complementary slackness forces $\lambda_2 = 0$ With $\lambda_2 = 0$, stationarity gives $2x_1 = \lambda_1$, so $\lambda_1 = 2$. The multiplier $\lambda_1 = 2$ is positive, confirming $h_1$ is binding. All KKT conditions satisfied. ## Worked QP A quadratic program (QP) exposes all four KKT parts cleanly: $$\begin{aligned} \min_x &\quad \tfrac{1}{2}x^T Q x + c^T x \\ \text{s.t.} &\quad Ax \leq b \end{aligned}$$ with $Q \succeq 0$ (convex QP). The Lagrangian: $$\mathcal{L}(x, \lambda) = \tfrac{1}{2}x^T Q x + c^T x + \lambda^T(Ax - b)$$ Stationarity: $Qx + c + A^T\lambda = 0 \;\Rightarrow\; x = -Q^{-1}(c + A^T\lambda)$ (if $Q \succ 0$). The KKT conditions reduce to solving for $(x, \lambda)$: $$Qx + A^T\lambda = -c, \quad Ax \leq b, \quad \lambda \geq 0, \quad \lambda_j(a_j^T x - b_j) = 0 \;\forall j$$ This is a **linear complementarity problem (LCP)** — a mixed system of equations and inequalities. IPM solvers (Week 6) solve essentially this system for successively relaxed complementarity. **Worked 2D QP:** $$\min_{x,y} \; \tfrac{1}{2}(x^2 + y^2) \quad \text{s.t.} \quad x + y \leq 3,\; x \geq 0$$ In standard form: $h_1 = x + y - 3 \leq 0$, $h_2 = -x \leq 0$ (inequality only, no equalities). $Q = I$, $c = 0$. At the unconstrained optimum $(0,0)$, the constraint $x \geq 0$ is active, $x + y \leq 3$ is slack ($0 + 0 - 3 = -3 < 0$). Complementary slackness: $\lambda_2 > 0$ possible, $\lambda_1 = 0$ since $h_1(x,y) < 0$. Stationarity: $x + \lambda_1\frac{\partial h_1}{\partial x} + \lambda_2\frac{\partial h_2}{\partial x} = x + \lambda_1 - \lambda_2 = 0$, and similarly $y + \lambda_1 = 0$. With $\lambda_1 = 0$: $x - \lambda_2 = 0$, $y = 0$. At $(0,0)$, $\lambda_2 = 0$ — all multipliers zero. The constraint $h_2 = -x$ is *active* at $(0,0)$ (that is exactly $x = 0$) but has a degenerate zero multiplier: the objective's gradient already points away from the boundary, so the constraint does not participate in stationarity. The unconstrained optimum is feasible, so it is the constrained optimum — complementary slackness is satisfied, but this is degeneracy ($\lambda_2 = 0$ with $h_2 = 0$), not a slack constraint. ## Sensitivity / Shadow Prices **Interpretation.** The optimal dual variable $\lambda_j^*$ equals the rate of change of the optimal value when the $j$-th constraint bound is perturbed: $$\frac{\partial p^*}{\partial b_j} \approx -\lambda_j^* \quad \text{(for $Ax \leq b$, standard form $a_j^T x - b_j \leq 0$)}$$ More precisely, for the perturbed problem $\min \{ f(x) \mid h_j(x) \leq u_j \}$, under suitable conditions: $$\frac{\partial p^*(u)}{\partial u_j}\bigg|_{u=0} = \lambda_j^*$$ The sign convention matters: for $h_j(x) \leq 0$ in the standard form, tightening the constraint (making $u_j$ more negative) increases the optimal value, so the derivative is positive and equals $\lambda_j^*$. **Shadow price intuition.** If $\lambda_j^* = 0$, the $j$-th constraint is not binding — relaxing or tightening it by a small amount has no first-order effect on the optimum. If $\lambda_j^*$ is large, the constraint is expensive: the optimal value is highly sensitive to that constraint's location. In engineering design, shadow prices tell you where to spend resources: relax the constraint with the largest multiplier for the biggest payoff. **Worked example — Factory production.** A simplified production problem: $\min \; -3x_1 - 2x_2$ (maximise profit) subject to $x_1 + 2x_2 \leq 8$ (labour), $2x_1 + x_2 \leq 6$ (materials), $x_1, x_2 \geq 0$. Solving: the optimum is at $x_1 = 4/3 \approx 1.33$, $x_2 = 10/3 \approx 3.33$. Both labour and materials constraints are active. Solving the KKT system gives the dual variables $\lambda_1^* = 1/3 \approx 0.33$ (labour), $\lambda_2^* = 4/3 \approx 1.33$ (materials). Interpretation: one extra unit of labour would increase profit by about $\$0.33$; one extra unit of materials by about $\$1.33$. The materials constraint is the bottleneck. ## What Can Go Wrong KKT is a powerful tool but has sharp edges: 1. **CQ failure.** Without a constraint qualification, KKT may not hold at a local minimum. The $x^2 \leq 0$ example from Week 1 illustrates this: the minimum exists but no finite multiplier satisfies stationarity because $\nabla h(x^*) = 0$. 2. **Nonconvex KKT points.** KKT conditions are necessary but not sufficient for nonconvex problems. A point can satisfy all four KKT conditions and still be a saddle or a local maximum. Always check second-order conditions or problem structure. 3. **Multiple KKT solutions.** Nonconvex problems can have many KKT points — each corresponds to a local minimum, maximum, or saddle. Numerical solvers find *a* KKT point; which one depends on initialisation. 4. **Degeneracy.** When active constraint gradients are nearly linearly dependent, the LICQ is barely satisfied, and the KKT system becomes ill-conditioned. Solvers report this as "numerical difficulties" or "near-degeneracy." ## Knowledge check <Exercise type="fill-blank" question="Complementary slackness requires that for each inequality constraint $j$, the product $\lambda_j \cdot h_j(x^*)$ equals ____." correctAnswer="0" explanation="$\lambda_j \, h_j(x^*) = 0$ — at least one of the multiplier or the constraint slack must be zero. A binding constraint has $h_j = 0$; an inactive constraint forces $\lambda_j = 0$." /> <Quiz questions={[ { type: "multiple-choice", question: "Which KKT condition is violated if $\lambda_j = -2$ for an inequality constraint $h_j(x) \leq 0$?", options: ["Stationarity", "Primal feasibility", "Dual feasibility", "Complementary slackness"], correctIndex: 2, explanation: "Inequality multipliers must be $\lambda_j \geq 0$ — this is dual feasibility. A negative multiplier would mean the constraint is pushing in the wrong direction." }, { type: "multiple-choice", question: "A shadow price of $\lambda^* = 0$ for a constraint means:", options: ["The constraint is binding and expensive", "The constraint is inactive or has no marginal effect", "The problem is infeasible", "Strong duality fails"], correctIndex: 1, explanation: "A zero multiplier means small perturbations of that constraint bound do not affect the optimal value — the constraint is not binding at the optimum." }, { type: "fill-blank", question: "For a convex problem where Slater's condition holds, any point satisfying the KKT conditions is a ____ optimum.", correctAnswer: "global", explanation: "Under convexity and a constraint qualification, KKT is both necessary and sufficient for global optimality." } ]} /> ## Browser lab Consider the small QP: $\min_{x,y} \; \tfrac{1}{2}(x^2 + y^2)$ subject to $x + y \geq 2$, $x \geq 0$. Compute the KKT residual at candidate points $(x, y, \lambda_1, \lambda_2)$ and verify the true KKT point $(1, 1, 1, 0)$. ```python import numpy as np def kkt_residual(x, y, lam1, lam2): """Compute violations of the four KKT conditions for: min 0.5*(x^2 + y^2) s.t. 2 - x - y <= 0, -x <= 0 Lagrangian: L = 0.5*(x^2 + y^2) + lam1*(2 - x - y) + lam2*(-x) """ # Stationarity stat_x = x - lam1 - lam2 stat_y = y - lam1 stat = np.sqrt(stat_x**2 + stat_y**2) # Primal feasibility (negative means satisfied for <= 0) h1 = 2 - x - y h2 = -x primal_viol = max(0, h1) + max(0, h2) # Dual feasibility dual_viol = max(0, -lam1) + max(0, -lam2) # Complementary slackness comp_viol = abs(lam1 * h1) + abs(lam2 * h2) return { "stationarity": stat, "primal_violation": primal_viol, "dual_violation": dual_viol, "complementarity_violation": comp_viol, "total": stat + primal_viol + dual_viol + comp_viol } # Test candidate points candidates = [ ("(0, 0) [infeasible]", 0.0, 0.0, 0.0, 0.0), ("(1, 1) [KKT]", 1.0, 1.0, 1.0, 0.0), ("(2, 0) [feasible, non-optimal]", 2.0, 0.0, 1.0, 0.0), ("(1, 1) [wrong lam]", 1.0, 1.0, 0.0, 0.0), ("(0.5, 1.5) [feasible]", 0.5, 1.5, 0.5, 0.0), ] print(f"{'Point':<28s} {'stat':>8s} {'primal':>8s} {'dual':>8s} {'comp':>8s} {'total':>8s}") print("-" * 70) for name, x, y, l1, l2 in candidates: res = kkt_residual(x, y, l1, l2) print(f"{name:<28s} {res['stationarity']:8.4f} {res['primal_violation']:8.4f} " f"{res['dual_violation']:8.4f} {res['complementarity_violation']:8.4f} " f"{res['total']:8.4f}") # Verify KKT point print(f"\nTrue KKT point: (1, 1) with lam = (1, 0)") true_res = kkt_residual(1, 1, 1, 0) print(f"Total KKT residual at true optimum: {true_res['total']:.2e}") print("Notice: the total KKT residual is exactly 0.00e+00 at (1,1) with λ = (1,0), and ≥ 1.0 at every other test point.") ``` --- ## Further Reading - **Stephen Boyd & Lieven Vandenberghe**, *Convex Optimization* (Cambridge University Press, 2004) — the KKT conditions and the sensitivity/shadow-price interpretation. - **Jorge Nocedal & Stephen Wright**, *Numerical Optimization* (2nd ed., Springer, 2006) — the theory of constrained optimisation, including degeneracy. - **Dimitri P. Bertsekas**, *Nonlinear Programming* (3rd ed., Athena Scientific, 2016) — the fullest treatment of constraint qualifications.