Kuhn–Tucker (KKT) theorem: explanation and worked examples
The Kuhn–Tucker theorem is the standard tool for constrained optimisation with inequality constraints. In economics, it is what turns “corner solutions” into a clean algorithm: write the Lagrangian, add sign restrictions on multipliers, and use complementary slackness to decide which constraints bind.
We start from the general problem: $$ \min_{x\in\mathbb{R}^n} f(x) \quad \text{subject to} $$ $$ \quad g_i(x)\le 0 \ (i=1,\dots,m), $$ $$ \qquad h_j(x)=0 \ (j=1,\dots,k). $$
The Lagrangian is $$ \mathcal{L}(x,\lambda,\mu)=f(x)+\sum_{i=1}^m \lambda_i g_i(x)+\sum_{j=1}^k \mu_j h_j(x), $$ where inequality multipliers satisfy \( \lambda_i\ge 0 \), while equality multipliers \( \mu_j \) are unrestricted.
At a solution \((x^\*,\lambda^\*,\mu^\*)\) the KKT conditions are: $$ \nabla_x \mathcal{L}(x^\*,\lambda^\*,\mu^\*)=0, $$ $$ g_i(x^\*)\le 0,\quad h_j(x^\*)=0, $$ $$ \lambda_i^\*\ge 0, $$ and the key link between geometry and economics: $$ \lambda_i^\*\,g_i(x^\*)=0 \quad \text{for each } i. $$
Complementary slackness means: either the constraint is binding (\(g_i(x^\*)=0\)) and then its multiplier can be positive, or the constraint is slack (\(g_i(x^\*)<0\)) and then its multiplier must be zero. Economically, a binding constraint has a shadow price; a slack constraint has none.
Example 1: inequality constraint plus nonnegativity (a clean “active set” case)
Consider the problem: $$ \min_{x_1,x_2}\; f(x_1,x_2)=\frac{1}{2}x_1^2-2x_2 $$ subject to $$ x_1^2+x_2^2\le 4,\qquad x_1\ge 0,\qquad x_2\ge 0. $$
The feasible set is the quarter-disk of radius 2 in the first quadrant. The objective decreases when \(x_2\) increases, but the circle constraint prevents us from “pushing” \(x_2\) to infinity. This is the typical situation where the optimum ends up on the boundary \(x_1^2+x_2^2=4\), unless nonnegativity forces a corner.
Lagrangian (one inequality constraint \(g(x)=x_1^2+x_2^2-4\le 0\)): $$ \mathcal{L}(x_1,x_2,\lambda)=\frac{1}{2}x_1^2-2x_2+\lambda\,(x_1^2+x_2^2-4), \qquad \lambda\ge 0. $$
Insert image file for the geometry/contours: figure_1.jpg. Use it to show the quarter-disk feasible set and the direction in which the objective “wants” to move.
Insert image file for the candidate table / feasibility check: figure_2.jpg. Use it to show which KKT candidates survive feasibility and which one minimises \(f\).
Maxima code (as-is):
kill(all)$
/* Objective and constraint */
f : (1/2)*x1^2 - 2*x2$
g : x1^2 + x2^2 - 4$ /* g <= 0 */
/* Lagrangian */
L : f + lambda*g$
/* Stationarity */
eq1 : diff(L,x1,1) = 0$
eq2 : diff(L,x2,1) = 0$
/* Complementary slackness */
eq3 : lambda*g = 0$
/* Solve the system, then filter by:
x1>=0, x2>=0, g<=0, lambda>=0 */
sol : solve([eq1,eq2,eq3],[x1,x2,lambda])$Example 2: two linear inequalities and one nonnegativity (geometry first, KKT second)
Now maximise $$ f(x_1,x_2)=(x_1-1)^2+x_2^2 $$ subject to $$ x_1+3x_2\le 6,\qquad 4x_1-3x_2\le 9,\qquad x_1\ge 0, $$ with \(x_2\) unrestricted.
Level sets of \(f\) are circles centred at \((1,0)\). Maximising \(f\) means looking for the feasible point that is farthest from \((1,0)\). With linear constraints the feasible set is a polygonal region (here: two half-planes plus \(x_1\ge 0\)), so the optimum typically appears on an edge or at a corner where at least one constraint binds.
Insert image file for feasible region + level sets: figure_3.jpg. The plot should make it visually obvious which corner/edge is the farthest from \((1,0)\).
To apply KKT, convert maximisation into minimisation of \(-f\). Let $$ g_1(x)=x_1+3x_2-6\le 0,\qquad g_2(x)=4x_1-3x_2-9\le 0. $$ The Lagrangian for minimising \(-f\) is $$ \mathcal{L}(x_1,x_2,\lambda_1,\lambda_2)=-(x_1-1)^2-x_2^2+\lambda_1 g_1(x)+\lambda_2 g_2(x), \qquad \lambda_1,\lambda_2\ge 0. $$
Because \(x_1\ge 0\) we allow a corner solution at \(x_1=0\). Because \(x_2\) is free, the stationarity condition for \(x_2\) is the usual equality \(\partial \mathcal{L}/\partial x_2=0\).
Insert image file for candidate table / active-set cases: figure_4.jpg. This should list the cases “which constraints bind” and which candidates pass feasibility and multiplier sign restrictions.
Maxima code (as-is):
kill(all)$
/* Objective (max), rewritten as minimisation of -f */
f : (x1-1)^2 + x2^2$
g1 : x1 + 3*x2 - 6$ /* g1 <= 0 */
g2 : 4*x1 - 3*x2 - 9$ /* g2 <= 0 */
L : -f + lambda1*g1 + lambda2*g2$
/* Stationarity */
eq1 : diff(L,x1,1) = 0$
eq2 : diff(L,x2,1) = 0$
/* Complementary slackness */
eq3 : lambda1*g1 = 0$
eq4 : lambda2*g2 = 0$
/* Solve, then filter by:
x1>=0, g1<=0, g2<=0, lambda1>=0, lambda2>=0 */
sol : solve([eq1,eq2,eq3,eq4],[x1,x2,lambda1,lambda2])$Economic application 1: cost minimisation with an equality constraint (energy allocation)
A firm must allocate a fixed total amount of energy \(16\) between two channels \(x_1\) and \(x_2\). The cost function is $$ C(x_1,x_2)=5x_1^2-8x_1x_2+7x_2^2-12x_1-4x_2+81, $$ and the hard constraint is $$ x_1+x_2=16,\qquad x_1\ge 0,\qquad x_2\ge 0. $$
The Lagrangian is $$ \mathcal{L}(x_1,x_2,\mu)=C(x_1,x_2)+\mu\,(x_1+x_2-16), $$ where \(\mu\) is unrestricted because this is an equality constraint.
Insert image file for the cost surface/contours and the constraint line: figure_5.jpg. The picture should show that the minimum occurs where the line \(x_1+x_2=16\) touches the lowest reachable contour.
Maxima code (as-is):
kill(all)$
C : 5*x1^2 - 8*x1*x2 + 7*x2^2 - 12*x1 - 4*x2 + 81$
w : x1 + x2 - 16$ /* equality constraint */
L : C + mu*w$
eq1 : diff(L,x1,1) = 0$
eq2 : diff(L,x2,1) = 0$
eq3 : w = 0$
sol : solve([eq1,eq2,eq3],[x1,x2,mu])$Economic application 2: minimum-variance portfolio with a target return
Two assets \(A\) and \(B\) have expected returns \(R_A, R_B\), standard deviations \(\sigma_A, \sigma_B\), and correlation \(\rho\). With weights \(x_A, x_B\) (and full investment \(x_A+x_B=1\)), portfolio variance is $$ \sigma_p^2 = x_A^2\sigma_A^2+x_B^2\sigma_B^2+2x_Ax_B\sigma_A\sigma_B\rho. $$
We minimise \(\sigma_p^2\) subject to a target expected return and the budget constraint: $$ x_A R_A + x_B R_B \ge \bar R,\qquad x_A+x_B=1, $$ often with \(x_A\ge 0, x_B\ge 0\) in the no-short-selling version.
Insert image file for the variance surface and the feasible set: figure_6.jpg. The plot should illustrate how the return constraint shifts the feasible set away from the global minimum-variance point.
Maxima code (as-is):
kill(all)$
RA : 0.0209$ RB : 0.0095$
SA : 0.0547$ SB : 0.0361$
rho: 0.5$
/* variance */
V : xA^2*SA^2 + xB^2*SB^2 + 2*xA*SA*xB*SB*rho$
/* constraints */
ret : xA*RA + xB*RB - 0.02$ /* ret >= 0 */
bud : xA + xB - 1$ /* bud = 0 */
L : V - lambda*ret + mu*bud$
eq1 : diff(L,xA,1) = 0$
eq2 : diff(L,xB,1) = 0$
eq3 : bud = 0$
eq4 : lambda*ret = 0$
sol : solve([eq1,eq2,eq3,eq4],[xA,xB,lambda,mu])$