Karush-Kuhn-Tucker Conditions

Derive first-order optimality conditions for constrained problems and interpret multipliers geometrically.

The Karush–Kuhn–Tucker (KKT) system characterizes optimal solutions to nonlinear programs of the form

min⁡xf(x) s.t.gi(x)≤0,;i=1,…,m, hj(x)=0,;j=1,…,p.\begin{aligned} \min_{\mathbf{x}} \quad & f(\mathbf{x}) \ \text{s.t.} \quad & g_i(\mathbf{x}) \le 0,; i = 1,\dots,m, \ & h_j(\mathbf{x}) = 0,; j = 1,\dots,p . \end{aligned}

Feasible points satisfy primal constraints; optimal points additionally obey stationarity, complementary slackness, and dual feasibility. The Lagrangian

L(x,λ,ν)=f(x)+∑iλigi(x)∗∑jνjhj(x)\mathcal{L}(\mathbf{x}, \boldsymbol{\lambda}, \boldsymbol{\nu}) = f(\mathbf{x}) + \sum_i \lambda_i g_i(\mathbf{x}) * \sum_j \nu_j h_j(\mathbf{x})

reveals sensitivities: multipliers λi\lambda_i quantify how much the objective would change if we relaxed a constraint, a concept central to Constraints and Softening in MPC.

Under constraint qualifications (e.g., Slater's condition for convex problems), KKT conditions are both necessary and sufficient for optimality. For nonconvex problems, they remain necessary for local optima and ground iterative algorithms such as sequential quadratic programming, which we implement in Line Search Methods and embed inside Direct Transcription. Complementary slackness, λigi(x∗)=0\lambda_i g_i(\mathbf{x}^*) = 0, ensures that only active constraints influence the gradient, providing intuition for active-set methods used in NMPC Overview.

import sympy as sp

x1, x2, lmbd = sp.symbols('x1 x2 lambda', real=True)
objective = x1**2 + x2**2
constraint = x1 + x2 - 1
lagrangian = objective + lmbd * constraint
stationarity = [sp.diff(lagrangian, x1), sp.diff(lagrangian, x2)]
solution = sp.solve(stationarity + [constraint], (x1, x2, lmbd))
print(solution)

Geometric interpretations of multipliers as supporting hyperplanes connect directly to dual problems, where the dual objective lower bounds the primal. Duality gaps flag infeasibility or nonconvex structure, guiding algorithm choice when orchestrating policy updates in Actor-Critic Architectures or designing estimators in EKF and UKF Overview.

See also