KKT Conditions — Hyunjoo Park

KKT = the conditions a point must satisfy to be optimal. It extends Lagrange multipliers to inequality constraints.

Lagrange intuition

Optimum on a constraint: the contour of $f$ touches the constraint (crossing → you could still improve) → gradients parallel: $\nabla f = \lambda \nabla g \qquad \lambda = \frac{df^*}{db}$

$x$ = decision variables: the optimizer chooses them
$b$ = RHS of the constraint: the limit given from outside (e.g. demand = 300)
$f^*$ = the best achievable value → $\lambda$ = how much the best result changes when the limit changes by 1 = Shadow Price

What

\mu_j

means (min,

g_j(x) \le 0

\mu_j \ge 0

)

$\mu_j$ = how much the minimum cost drops when constraint $j$ is relaxed by 1 → always ≥ 0. Mini dispatch: demand $\mu$ = 30 · A capacity $\mu$ = 10 · B capacity $\mu$ = 0 (non-binding)

Recipe

Standard form: min; every constraint $g_j(x) \le 0$ (move constants left, RHS = 0); name the multiplier next to it $(\mu_j)$ ; equalities $h_i(x) = 0$ $(\lambda_i)$
Lagrangian: $L = f(x) + \sum_i \lambda_i h_i(x) + \sum_j \mu_j g_j(x)$
Conditions:

Condition	Form	How many
Stationarity	$\partial L/\partial x_k = 0$	one per variable
Primal feasibility	$h_i(x) = 0$ , $g_j(x) \le 0$	one per constraint
Complementary Slackness	$\mu_j\, g_j(x) = 0$	one per inequality
Dual feasibility	$\mu_j \ge 0$	one per inequality

Why learn it

Not to solve big LPs (that’s the solver; $2^n$ active-set guesses by hand)
Shows why dual = price (Market Clearing)
Several players can’t share one LP → write each player’s KKT and stack them = Mixed Complementarity Problem (W7)

Typical traps

Bounds are constraints too: $x_1 \ge 0$ → $-x_1 \le 0$ → $\mu_n$
Write " $= 0$ " after each $\partial L/\partial x$
Inequalities can be added, never subtracted
Write constraints as given, don’t simplify (÷2 → its $\mu$ ×2 and loses its unit, e.g. €/MWh)

Links: Duality, Shadow Price, Complementary Slackness, Mixed Complementarity Problem