kkt2.dvi
A Karush-Kuhn-Tucker Example
It’s only for very simple problems that we can use the Karush-Kuhn-Tucker conditions
to solve a nonlinear programming problem. Consider the following problem:
maximize f(x, y) = xy
subject to x + y2 ≤ 2
x, y ≥ 0
Note that the feasible region is bounded, so a global maximum must exist: a continuous
function on a closed and bounded set has a maximum there.
We write the constraints as g1(x, y) = x + y
2 ≤ 2, g2(x, y) = −x ≤ 0, g3(x, y) = −y ≤
0. Thus the KKT conditions can be written as
y − λ1 + λ2 = 0
x − 2yλ1 + λ3 = 0
λ1(2 − x − y2) = 0
λ2x = 0
λ3y = 0
x + y2 ≤ 2
x, y, λ1, λ2, λ3 ≥ 0
In each of the “complementary slackness” equations λi(bi − gi(x1, . . . , xn)) = 0, at
least one of the two factors must be 0. With n such conditions, there would potentially
be 2n possible cases to consider. However, with some thought we might be able to reduce
that considerably.
Case 1: Suppose λ1 = 0. Then the first KKT condition says y + λ2 = 0 and the second
says x + λ3 = 0. Since each term is nonnegative, the only way that can happen is if
x = y = λ2 = λ3 = 0. Indeed, the KKT conditions are satisfied when x = y = λ1 =
λ2 = λ3 = 0 (although clearly this is not a local maximum since f(0, 0) = 0 while
f(x, y) > 0 at points in the interior of the feasible region).
Case 2: Suppose x + y2 = 2. Now at least one of x = 2 − y2 and y must be positive.
Case 2a: Suppose x > 0. Then λ2 = 0. The first KKT condition says λ1 = y. The second
KKT condition then says x− 2yλ1 + λ3 = 2− 3y2 + λ3 = 0, so 3y2 = 2 + λ3 > 0,
and λ3 = 0. Thus y =
√
2/3, and x = 2 − 2/3 = 4/3. Again all the KKT
conditions are satisfied.
Case 2b: Suppose x = 0, i.e. y =
√
2. Since y > 0 we have λ3 = 0. From the second KKT
condition we must have λ1 = 0. But that takes us back to Case 1.
We conclude there are only two candidates for a local max: (0, 0) and (4/3,
√
2/3).
The global maximum is at (4/3,
√
2/3).