Mathematical methods for economic theory

Martin J. Osborne

7.4 Optimization with inequality constraints: nonnegativity conditions

Many of the optimization problems in economic theory have nonnegativity constraints on the variables. For example, a consumer chooses a bundle x of goods to maximize her utility u(x) subject to her budget constraint p·x ≤ w and the condition x ≥ 0. The general form of such a problem is
maxxf(x) subject to gj(x) ≤ cj for j = 1, ..., m and xi ≥ 0 for i = 1, ..., n.

This problem is a special case of the general maximization problem with inequality constraints, studied previously: the nonnegativity constraint on each variable is simply an additional inequality constraint. Specifically, if we define the function gm+i for i = 1, ..., n by gm+i(x) = −xi and let cm+i = 0 for i = 1, ..., n, then we may write the problem as

maxxf(x) subject to gj(x) ≤ cj for j = 1, ..., m+n
and solve it using the Kuhn-Tucker conditions
Li'(x = 0 for i = 1 ,..., n
λj ≥ 0, gj(x) ≤ cj and λj[gj(x) − cj = 0 for j = 1, ..., m + n,
where L(x) = f(x) − ∑m+n
j=1
λj(gj(x) − cj).

Approaching the problem in this way involves working with n + m Lagrange multipliers, which can be difficult if n is large. It turns out that the simple form of the inequality constraints associated with the nonnegativity conditions allows us to simplify the calculations as follows.

First, we form the modified Lagrangean

M(x) = f(x) − ∑m
j=1
λj(gj(x) − cj).
Note that this Lagrangean does not include the nonnegativity constraints explictly. Then we work with the Kuhn-Tucker conditions for the modified Lagrangean:
Mi'(x) ≤ 0, xi ≥ 0, and xi·Mi'(x)  =  0 for i = 1, ..., n
gj(x) ≤ cj, λj ≥ 0, and λj·[gj(x) − cj]  =  0 for j = 1, ..., m.
In an exercise, you are asked to show that if (x, (λ1, ..., λm+n)) satisfies the original Kuhn-Tucker conditions then (x, (λ1, ..., λm)) satisfies the conditions for the modified Lagrangean, and if (x, (λ1, ..., λm)) satisfies the conditions for the modified Lagrangean then we can find numbers λm+1, ..., λm+n such that (x, (λ1, ..., λm+n)) satisfies the original set of conditions.

This result means that in any problem for which the original Kuhn-Tucker conditions may be used, we may alternatively use the conditions for the modified Lagrangean. For most problems in which the variables are constrained to be nonnegative, the Kuhn-Tucker conditions for the modified Lagrangean are easier to work with than the conditions for the original Lagrangean.

Example
Consider the problem

maxx,y xy subject to x + y ≤ 6, x ≥ 0, and y ≥ 0

studied in the previous section. The modified Lagrangean is

M(xy) = xy − λ(x + y − 6)

and the Kuhn-Tucker conditions for this Lagrangean are

y − λ ≤ 0, x ≥ 0, and x(y − λ)  =  0
x − λ ≤ 0, y ≥ 0, and y(x − λ)  =  0
λ ≥ 0, x + y ≤ 6, λ(x + y − 6)  =  0.

We can find a solution of these conditions as follows.

  • If x > 0 then from the first set of conditions we have y = λ. If y = 0 in this case then λ = 0, so that the second set of conditions implies x ≤ 0, contradicting x > 0. Hence y > 0, and thus x = λ, so that x = y = λ = 3.
  • If x = 0 then if y > 0 we have λ = 0 from the second set of conditions, so that the first condition contradicts y > 0. Thus y = 0 and hence λ = 0 from the third set of conditions.

We conclude (as before) that there are two solutions of the Kuhn-Tucker conditions, in this case (xy, λ) = (3, 3, 3) and (0, 0, 0). Since the value of the objective function at (3, 3) is greater than the value of the objective function at (0, 0), the solution of the problem is (3, 3).