Week 3: KKT and Sensitivity

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

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:

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#

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)$.

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.")

Key takeaways#

• The KKT system is four conditions: stationarity, primal feasibility, dual feasibility, and complementary slackness.
• Complementary slackness $\lambda_j h_j(x) = 0$ says an inactive constraint does not participate in stationarity; a positive multiplier means the constraint binds.
• For a convex problem with a constraint qualification, KKT is necessary and sufficient for global optimality.
• The optimal multiplier is a shadow price: $\partial p^* / \partial u_j = \lambda_j^*$, the marginal value of relaxing that constraint.
• A zero multiplier means the constraint has no first-order effect; the largest multiplier marks the bottleneck where resources should go.
• KKT has sharp edges — a failing CQ, nonconvex KKT points, multiple solutions, and degeneracy all break naive use.

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.