Mathematical methods for economic theory

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:

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.

     

We consider a problem of the form

where f and g_j for j = 1, ..., m are functions of n variables, x = (x₁, ..., x_n), and c_j 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

max_x f(x) subject to h(x) = 0

may be written as

max_x f(x) subject to h(x) ≤ 0 and −h(x) ≤ 0.

Nonnegativity constraints

For a problem with a constraint x_k ≥ 0 we let g_j(x) = −x_k and c_j = 0 for some j.

Minimization problems

For a minimization problem we multiply the objective function by −1:

min_x h(x) subject to g_j(x) ≤ c_j for j = 1, ..., m

is the same as

max_x f(x) subject to g_j(x) ≤ c_j 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 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.

  

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

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 f_i'(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

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 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.

Like many other writers, I name these conditions for Harold W. Kuhn (1925–2014) and Albert W. Tucker (1905–1995; obituary), who in 1950 presented results connecting solutions of the conditions with solutions of an optimization problem with inequality constraints. However, such results had been established previously, in 1939, by William Karush (1917–1997). See Kjeldsen (2000) for a detailed discussion of the history of the results.

On the following pages I discuss the results. The following example illustrates the conditions for a specific problem.