Mathematical methods for economic theory

Martin J. Osborne

7.1 Optimization with inequality constraints: the Kuhn-Tucker conditions

Many models in economics are naturally formulated as optimization problems with inequality constraints.

Consider, for example, a consumer's choice problem. There is no reason to insist that a consumer spend all her wealth. To allow her not to spend it all, we can formulate her optimization problem with inequality constraints:

maxx u(x) subject to p·x ≤ w and x ≥ 0.
Depending on the character of the function u and the values of p and w, we may have p·x < w or p·x = w at a solution of this problem.

One approach to solving this problem starts by determining which of these two conditions holds at a solution. In more complex problems, with more than one constraint, this approach does not work well. Consider, for example, a consumer who faces two constraints (perhaps money and time). Three examples are shown in the following figure, which should convince you that we cannot deduce from simple properties of u alone which of the constraints, if any, are satisfied with equality at a solution.

x1 x2 Level curve of u Red constraint binds; green constraint slack    x1 x2 Level curve of u Both constraints bind    x1 x2 Level curve of u Green constraint binds; red constraint slack

We consider a problem of the form

maxx f(x) subject to gj(x) ≤ cj for j = 1, ..., m,
where f and gj for j = 1, ..., m are functions of n variables, x = (x1, ..., xn), and cj for j = 1, ..., m are constants.

All the problems we have studied so far may be put into this form.

Equality constraints
We introduce two inequality constraints for every equality constraint. For example, the problem
maxx f(x) subject to h(x) = 0
may be written as
maxx f(x) subject to h(x) ≤ 0 and −h(x) ≤ 0.
Nonnegativity constraints
For a problem with a constraint xk ≥ 0 we let gj(x) = −xk and cj = 0 for some j.
Minimization problems
For a minimization problem we multiply the objective function by −1:
minx h(x) subject to gj(x) ≤ cj for j = 1, ..., m
is the same as
maxx f(x) subject to gj(x) ≤ cj for j = 1, ..., m,
where f(x) = −h(x).
To start thinking about how to solve the general problem, first consider a case with a single constraint (m = 1). We can write such a problem as
maxx f(x) subject to g(x) ≤ c.
There are two possibilities for the solution of this problem. In the following figures, the black closed curves are contours of f; values of the function increase in the direction shown by the blue arrows. The downward-sloping red line is the set of points x satisfying g(x) = c. The set of points x satisfying g(x) ≤ c is the shaded set below and to the left of the line.

g(x) > c g(x) < c g(x) = c x*    g(x) > c g(x) < c g(x) = c x*

In each figure the solution of the problem is the point x*. In the first figure the constraint binds at the solution: a change in c changes the solution. In the second figure, the constraint is slack at the solution: small changes in c have no effect on the solution.

As before, define the Lagrangean function L by

L(x) = f(x) − λ(g(x) − c).
Then from our previous analysis of problems with equality constraints and with no constraints,
  • if g(x*) = c (as in the left-hand panel) and the constraint satisfies a regularity condition, then L'i(x*) = 0 for all i
  • if g(x*) < c (as in the right-hand panel), then fi'(x*) = 0 for all i.
Now, I claim that in the first case (that is, if g(x*) = c) we have λ ≥ 0. Suppose, to the contrary, that λ < 0. Then we know that a small decrease in c raises the maximal value of f. That is, moving x* inside the constraint raises the value of f, contradicting the fact that x* is the solution of the problem.

In the second case, the value of λ does not enter the conditions, so we can choose any value for it. Given the interpretation of λ, setting λ = 0 makes sense. Under this assumption we have f'i(x) = L'i(x) for all x, so that L'i(x*) = 0 for all i. Thus in both cases we have L'i(x*) = 0 for all i, λ ≥ 0, and g(x*) ≤ c. In the first case we have g(x*) = c and in the second case λ = 0.

We may combine the two cases by writing the conditions as

L'i(x*)  =  0 for j = 1, ..., n
λ ≥ 0, g(x*)  ≤  c, and either λ = 0 or g(x*) − c = 0.
Now, the product of two numbers is zero if and only if at least one of them is zero, so we can alternatively write these conditions as
L'i(x*)  =  0 for j = 1, ..., n
λ ≥ 0, g(x*)  ≤  c, and λ[g(x*) − c] = 0.
The argument I have given suggests that if x* solves the problem and the constraint satisfies a regularity condition, then x* must satisfy these conditions.

Note that the conditions do not rule out the possibility that both λ = 0 and g(x*) = c.

The condition that either (i) λ = 0 and g(x*) ≤ c or (ii) λ ≥ 0 and g(x*) = c is called a complementary slackness condition.

For a problem with many constraints, then as before we introduce one multiplier for each constraint and obtain the Kuhn-Tucker conditions, defined as follows.

Definition
Let f and gj for j = 1, ..., m be differentiable functions of n variables and let cj for j = 1, ..., m be numbers. Define the function L of n variables by
L(x)  =  f(x) − ∑m
j=1
λj(gj(x) − cj) for all x.
The Kuhn-Tucker conditions for the problem
maxx f(x) subject to gj(x) ≤ cj for j = 1, ..., m
are
L'i(x) = 0 for i = 1, ..., n
λj ≥ 0, gj(x) ≤ cj and λj[gj(x) − cj] = 0 for j = 1, ..., m.
These conditions are named in honor of Harold W. Kuhn (1925–2014) and Albert W. Tucker (1905–1995; obituary), who first formulated and studied them.

On the following pages I discuss results that specify the precise relationship between the solutions of the Kuhn-Tucker conditions and the solutions of the problem. The following example illustrates the conditions for a specific problem.

Example
Consider the problem
maxx1x2 [−(x1 − 4)2 − (x2 − 4)2] subject to x1 + x2 ≤ 4 and x1 + 3x2 ≤ 9,
illustrated in the following figure.

x1 x2 4 9 0 x1 + 3x2 = 9 x1 + x2 = 4 Level curves of −(x1 − 4)2 − (x2 − 4)2

We have

L(x1x2)  =  −(x1 − 4)2 − (x2 − 4)2 − λ1(x1 + x2 − 4) − λ2(x1 + 3x2 − 9).
The Kuhn-Tucker conditions are
−2(x1 − 4) − λ1 − λ2 = 0
−2(x2 − 4) − λ1 − 3λ2 = 0
x1 + x2 ≤ 4, λ1 ≥ 0, and λ1(x1 + x2 − 4) = 0
x1 + 3x2 ≤ 9, λ2 ≥ 0, and λ2(x1 + 3x2 − 9) = 0.