Mathematical methods for economic theory

Martin J. Osborne

7.3 Optimization with inequality constraints: the sufficiency of the Kuhn-Tucker conditions

We saw previously that for both an unconstrained maximization problem and a maximization problem with an equality constraint the first-order conditions are sufficient for a global optimum when the objective and constraint functions satisfy appropriate concavity/convexity conditions. The same is true for an optimization problem with inequality constraints.

Concave objective function

Proposition (Sufficiency of Kuhn-Tucker conditions for concave objective function)  
Let f and gj for j = 1, ..., m be continuously differentiable functions of many variables and let cj for j = 1, ..., m be constants. Suppose that If there exists λ = (λ1, ..., λm) such that (x*, λ) satisfies the Kuhn-Tucker conditions then x* solves the problem
maxxf(x) subject to gj(x) ≤ cj for j = 1,...,m.
Proof  
The fact that (x*, λ) satisfies the Kuhn-Tucker conditions means that
f'i(x*) − ∑m
j=1
λjg'ji(x*) = 0 for i = 1, ..., n
λj ≥ 0, gj(x*) ≤ cj and λj[gj(x*) − cj] = 0 for j = 1, ..., m
(where g'ji(x*) is the derivative of gj with respect to its ith argument evaluated at x*).

Let x be such that gj(x) ≤ cj for all j. We need to show that f(x) ≤ f(x*).

Let j be an index such that gj(x*) = cj. (That is, the jth constraint is binding at x*.) Then gj(x) ≤ gj(x*), so that by a characterization of quasiconvex functions, ∑n
i=1
g'ji(x*)·(xi − x*i) ≤ 0. Thus given λj ≥ 0 we have λjn
i=1
g'ji(x*)·(xi − x*i) ≤ 0.

Now let j be an index such that gj(x*) < cj. Then by the complementary slackness condition for constraint j in the Kuhn-Tucker conditions, λj = 0.

Thus for every constraint j we have

λjn
i=1
g'ji(x*)·(xi − x*i) ≤ 0
and hence
m
j=1
λjn
i=1
g'ji(x*)·(xi − x*i) ≤ 0,
or, reversing the summations,
n
i=1
m
j=1
λjg'ji(x*)·(xi − x*i) ≤ 0.
Now, multiplying the ith first-order condition in the Kuhn-Tucker conditions by xi − x*i and summing over i we get
n
i=1
f'i(x*)·(xi − x*i) − ∑n
i=1
m
j=1
λjg'ji(x*)·(xi − x*i) = 0.
By the previous inequality, the second term is nonpositive, so
n
i=1
f'i(x*)·(xi − x*i) ≤ 0.
Thus from characterization of concave functions, f(x) ≤ f(x*), completing the proof.
This result together with the result giving conditions under which the Kuhn-Tucker conditions are necessary and the fact that a convex function (and hence a linear one) is quasiconvex yields the following useful corollary.
Corollary (Necessity and sufficiency of Kuhn-Tucker conditions for concave objective function)
Let f and gj for j = 1, ..., m be continuously differentiable functions of many variables and let cj for j = 1, ..., m be constants. Suppose that f is concave and
  • either each gj is linear
  • or each gj is convex and there exists x such that gj(x) < cj for j = 1, ..., m.
Then x* solves the problem
maxxf(x) subject to gj(x) ≤ cj for j = 1, ..., m
if and only if it satisfies the Kuhn-Tucker conditions.

Quasiconcave objective function

The condition that the objective function be concave is a bit too strong to be useful in some economic applications. For example, the assumption we would like to impose on a consumer's utility function is that it be quasiconcave. The next result is useful in this case.
Proposition (Sufficiency of Kuhn-Tucker conditions for quasiconcave objective function)  
Let f and gj for j = 1, ..., m be continuously differentiable functions of n variables and let cj for j = 1, ..., m be constants. Suppose that If there exists λ = (λ1, ..., λm) and x* such that (x*, λ) satisfies the Kuhn-Tucker conditions and it is not the case that f'i(x*) = 0 for i = 1, ..., n then x* solves the problem
maxxf(x) subject to gj(x) ≤ cj for j = 1,...,m.
Proof  
The proof of the previous result uses the concavity of f only in the last sentence. In particular, under the assumption that f is quasiconcave we can conclude that
n
i=1
f'i(x*)·(xi − x*i) ≤ 0,
as in that proof. Now suppose, contrary to the claim that x* solves the maximization problem, that f(x) > f(x*) for some x that satisfies the constraints.

Denote the vector of partial derivatives of f by ∇f. Given the continuity of f, the fact that f(x) > f(x*) means that there exists t > 0 (small enough) such that f(x − tf(x*)) > f(x*), and the conclusion from the proof of the previous result may be written

f(x*)·(x − x*) ≤ 0.
Thus
f(x*)·(x − tf(x*) − x*)  =  tf(x*)·∇f(x*) + ∇f(x*)(x − x*)
 ≤  tn
i=1
(f'i(x*))2 < 0,
given the assumption that ∇f(x*) ≠ (0, ..., 0). But now, by a characterization of quasiconcave functions, this inequality implies that f(x − tf(x*)) < f(x*), contradicting f(x − tf(x*)) > f(x*). Thus in fact f(x) ≤ f(x*).
The constraints in a standard consumer's optimization problem are linear, so the following implication of this result and the earlier result giving conditions under which the Kuhn-Tucker conditions are necessary is useful.
Corollary (Necessity and sufficiency of Kuhn-Tucker conditions for quasiconcave objective function)
Let f and gj for j = 1, ..., m be continuously differentiable functions of n variables and let cj for j = 1, ..., m be constants. Suppose that f is quasiconcave and each gj is linear. If x* solves the problem
maxxf(x) subject to gj(x) ≤ cj for j = 1, ..., m
then there exists a unique vector λ such that (x*, λ) satisfies the Kuhn-Tucker conditions, and if (x*, λ) satisfies the Kuhn-Tucker conditions and f'i(x*) ≠ 0 for i = 1, ..., n then x* solves the problem.
If you have a minimization problem, remember that you can transform it to a maximization problem by multiplying the objective function by −1. Thus for a minimization problem the condition on the objective function in the first result above is that it be convex, and the condition in the second result is that it be quasiconvex.

Examples

The next two very simple examples illustrate how to use the Kuhn-Tucker conditions.
Example
Consider the problem
maxx[−(x − 2)2] subject to x ≥ 1,
illustrated in the following figure.

x 0 1 2 3 4 0 −1 −2 −3 −4 x = 1 −(x − 2)2

Written in the standard format, this problem is

maxx[−(x − 2)2] subject to 1 − x ≤ 0.
The objective function is concave and the constraint is linear. Thus the Kuhn-Tucker conditions are both necessary and sufficient: the set of solutions of the problem is the same as the set of solutions of the Kuhn-Tucker conditions.

The Kuhn-Tucker conditions are

−2(x − 2) + λ  = 0
x−1 ≥ 0, λ ≥ 0, and λ(1 − x = 0.
From the last condition we have either λ = 0 or x = 1.
  • x = 1: 2 + λ = 0, or λ = −2, which violates λ ≥ 0.
  • λ = 0: −2(x − 2) = 0; the only solution is x = 2.
Thus the Kuhn-Tucker conditions have a unique solution, (x, λ) = (2, 0). Hence the problem has a unique solution x = 2.
Example
Consider the problem
maxx[−(x − 2)2] subject to x ≥ 3,
illustrated in the following figure.

x 0 1 2 3 4 0 −1 −2 −3 −4 x = 3 −(x − 2)2

Written in the standard format, this problem is

maxx[−(x − 2)2] subject to 3 − x ≤ 0.
As in the previous example, the objective function is concave and the constraint function is linear, so that the set of solutions of the problem is the set of solutions of the Kuhn-Tucker conditions.

The Kuhn-Tucker conditions are

−2(x−2) + λ  = 0
x−3 ≥ 0, λ ≥ 0, and λ(3 − x = 0.
From the last conditions we have either λ = 0 or x = 3.
  • x = 3: −2 + λ = 0, or λ = 2.
  • λ = 0: −2(x − 2) = 0; since x ≥ 3 this has no solution compatible with the other conditions.
Thus the Kuhn-Tucker conditions have a single solution, (x, λ) = (3, 2). Hence the problem has a unique solution, x = 3.
These two examples illustrate a procedure for finding solutions of the Kuhn-Tucker conditions that is useful in many problems. First, look at the complementary slackness conditions, which imply that either a Lagrange multiplier is zero or a constraint is binding. Then follow through the implications of each case, using the other equations. In the two examples, this procedure is very easy to follow. The following examples are more complicated.
Example
Consider the problem
maxx1x2 [−(x1 − 4)2 − (x2 − 4)2] subject to x1 + x2 ≤ 4 and x1 + 3x2 ≤ 9.
The objective function is concave and the constraints are both linear, so the solutions of the problem are the solutions of the Kuhn-Tucker conditions.

We previously found that the Kuhn-Tucker conditions for this problem 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.
What are the solutions of these conditions? Start by looking at the two conditions λ1(x1 + x2 − 4) = 0 and λ2(x1 + 3x2 − 9) = 0. These two conditions yield the following four cases.
  • x1 + x2 = 4 and x1 + 3x2 = 9: In this case we have x1 = 3/2 and x2 = 5/2. Then the first two equations are
    5 − λ1 − λ2  = 0
    3 − λ1 − 3λ2  = 0
    which imply that λ1 = 6 and λ2 = −1, which violates the condition λ2 ≥ 0.
  • x1 + x2 = 4 and x1 + 3x2 < 9, so that λ2 = 0: Then first two equations imply x1 = x2 = 2 and λ1 = 4. All the conditions are satisfied, so (x1x2, λ1, λ2) = (2, 2, 4, 0) is a solution.
  • x1 + x2 < 4 and x1 + 3x2 = 9, so that λ1 = 0: Then the first two equations imply x1 = 33/10 and x2 = 19/10, violating x1 + x2 < 4.
  • x1 + x2 < 4 and x1 + 3x2 < 9, so that λ1 = λ2 = 0: Then first two equations imply x1 = x2 = 4, violating x1 + x2 < 4.
So (x1x2, λ1, λ2) = (2, 2, 4, 0) is the single solution of the Kuhn-Tucker conditions. Hence the unique solution of problem is (x1x2) = (2, 2).
The next example involves a problem of the form
maxx u(x) subject to p·x ≤ w, x ≥ 0,
where u is quasiconcave, p is a vector, and w is a scalar. A standard consumer's maximization problem in economic theory takes this form; the technique used in the example may be used also in problems with other specifications of the function u.
Example
Consider the problem
maxx,y xy subject to x + y ≤ 6, x ≥ 0, and y ≥ 0.
The objective function is twice-differentiable and quasiconcave and the constraint functions are linear, so the Kuhn-Tucker conditions are necessary and if ((x*, y*), λ*) satisfies these conditions and no partial derivative of the objective function at (x*, y*) is zero then (x*, y*) solves the problem. Solutions of the Kuhn-Tucker conditions at which all derivatives of the objective function are zero may or may not be solutions of the problem—we need to check the values of the objective function at these solutions.

(Alternatively we can argue as follows. The constraint functions are linear, so the Kuhn-Tucker conditions are necessary. Further, the objective function is continuous and the constraint set is compact, so by the extreme value theorem the problem has a solution. Thus the solutions of the problem are the solutions of the first-order conditions that yield the highest values for the function.)

The Lagrangean is

L(xy) = xy − λ1(x + y − 6) + λ2x + λ3y.
The Kuhn-Tucker conditions are
y − λ1 + λ2 = 0
x − λ1 + λ3 = 0
λ1 ≥ 0, x + y ≤ 6, λ1(x + y − 6) = 0
λ2 ≥ 0, x ≥ 0, λ2x = 0
λ3 ≥ 0, y ≥ 0, λ3y = 0.
  • If x > 0 and y > 0 then λ2 = λ3 = 0, so that λ1 = x = y from the first two conditions. Hence x = y = λ1 = 3 from the third condition. These values satisfy all the conditions.
  • If x = 0 and y > 0 then λ3 = 0 from the last condition and hence λ1 = x = 0 from the second condition. But now from the first condition λ2 = −y < 0, contradicting λ2 ≥ 0.
  • If x > 0 and y = 0 then λ2 = 0, and a symmetric argument yields a contradiction.
  • If x = y = 0 then λ1 = 0 form the third set of conditions, so that λ2 = λ3 from the first and second conditions. These values satisfy all the conditions.
We conclude that there are two solutions of the Kuhn-Tucker conditions, (xy, λ1, λ2, λ3) = (3, 3, 3, 0, 0) and (0, 0, 0, 0, 0). The value of the objective function at (3, 3) is greater than the value of the objective function at (0, 0), so the solution of the problem is (3, 3).