KKT Conditions

Formula

\[ \nabla_x \mathcal{L}(x,\lambda,\nu)=0,\quad g(x)\le 0,\quad h(x)=0,\quad \lambda\ge 0,\quad \lambda \odot g(x)=0 \]

Parameters

• \(\mathcal{L}\): Lagrangian
• \(g(x)\le 0\): inequality constraints
• \(h(x)=0\): equality constraints
• \(\lambda\): inequality multipliers
• \(\nu\): equality multipliers

What it means

First-order optimality conditions for constrained problems; for convex problems, they are also sufficient.

What it's used for

• Checking optimality in constrained optimization.
• Deriving solutions with inequality constraints.

Key properties

• Complementary slackness: each \(\lambda_i g_i(x)=0\)
• Feasibility + stationarity + dual feasibility

Common gotchas

• KKT are necessary only under constraint qualification.
• For nonconvex problems, KKT points need not be global optima.

Example

For \(\min x^2\) s.t. \(x\ge 1\): \(x^*=1\), \(\lambda^*=2\) satisfy KKT.

How to Compute (Pseudocode)

Input: candidate point x and multipliers lambda, nu for a constrained problem
Output: KKT condition check (satisfied / violated)

check primal feasibility: g(x) <= 0 and h(x) = 0
check dual feasibility: lambda >= 0
compute stationarity residual: grad_x L(x, lambda, nu)
check complementary slackness: lambda_i * g_i(x) = 0 for all i
report whether all checks pass (within tolerance)

Complexity

• Time: Depends on the costs of evaluating constraints and computing the Lagrangian gradient/Jacobians (often dominated by derivative evaluations)
• Space: Depends on the number of variables/constraints and stored residuals/Jacobians
• Assumptions: Numerical KKT verification with tolerances is shown; sufficiency depends on convexity and constraint qualifications

See also

• Lagrangian