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
|Li'(x)||= 0 for i = 1 ,..., n|
|λj ≥ 0, gj(x) ≤ cj and λj[gj(x) − cj]||= 0 for j = 1, ..., 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
j=1λj(gj(x) − cj).
|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.|
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.
Consider the problem
maxx,y xy subject to x + y ≤ 6, x ≥ 0, and y ≥ 0
studied in the previous section. The modified Lagrangean isM(x, y) = 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 (x, y, λ) = (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).