The KKT System#
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, optimum is interior to both inequality constraints (both slack). The unconstrained optimum is feasible, so it is the constrained optimum — no constraint is binding. ## 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. The dual variables $\lambda_1^* \approx 1.33$ (labour), $\lambda_2^* \approx 0.33$ (materials). Interpretation: one extra unit of labour would increase profit by about $\$1.33$; one extra unit of materials by about $\$0.33$. The labour 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." <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, 2, 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, 2.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 = (2, 0)") true_res = kkt_residual(1, 1, 2, 0) print(f"Total KKT residual at true optimum: {true_res['total']:.2e}") ```