Nonlinear Programming: A Simple Case
So far this chapter has considered how to maximize or minimize a function subject to
equality constraints. The final two sections concern “nonlinear programming” problems
which involve inequality constraints. Some particularly simple inequality constraints are
those requiring certain variables to be nonnegative. These often have to be imposed for the
solution to make economic sense. In addition, bounds on resource availability are often
expressed as inequalities rather than equalities.
In this section we consider the simple nonlinear programming problem
max f (x, y) s.t. g(x, y) ≤ c (14.8.1)
with just one inequality constraint. Thus, we seek the largest value attained by f (x, y) in
the admissible or feasible set S of all pairs (x, y) satisfying g(x, y) ≤ c. Problems where
one wants to minimize f (x, y) subject to (x, y) ∈ S can be handled by instead studying the
problem of maximizing - f (x, y) subject to (x, y) ∈ S.
Problem (14.8.1) can be solved using the methods explained in Chapter 13. This
involves examining not only the critical points of f in the interior of the admissible set S,
but also the behaviour of f on the boundary of S. However, since the 1950s, economists
have generally tackled such problems by using an extension of the Lagrangian multiplier
method due originally to H.W. Kuhn and A.W. Tucker.
To apply their method, we begin by writing down a recipe giving all the points (x, y)
that can possibly solve problem (14.8.1), except in some bizarre cases. The recipe closely
resembles the one we used to solve problem (14.1.3).
T H E K U H N – T U C K E R M E T H O D
To find the only possible solutions to problem (14.8.1), proceed as follows:
(i) Associate a constant Lagrange multiplier λ with the constraint g(x, y) ≤ c,
and define the Lagrangian
L(x, y) = f (x, y) - λ[g(x, y) - c]
❦
❦ ❦
❦
564 C H A P T E R 1 4 / C O N S T R A I N E D O P T I M I Z A T I O N
(ii) Find the critical points of L(x, y), by equating its partial derivatives to
zero:
L′1(x, y) = f1′(x, y) - λg′1(x, y) = 0 (14.8.2a)
L′2(x, y) = f2′(x, y) - λg′2(x, y) = 0 (14.8.2b)
(iii) Introduce the complementary slackness condition:
λ ≥ 0, with λ = 0 if g(x, y) < c (14.8.3)
(iv) Require (x, y) to satisfy the constraint
g(x, y) ≤ c (14.8.4)
(v) Find all the points (x, y) that, together with associated values of λ, satisfy
all the conditions (14.8.2a) to (14.8.4). These are the solution candidates,
at least one of which solves the problem, if it has a solution.
If g = c and g′1 = g′2 = 0 at the maximum of the problem, this method may
fail.
Note that the conditions (14.8.2a) and (14.8.2b) are exactly the same as those used in
the Lagrange multiplier method of Section 14.1. Condition (14.8.4) obviously has to be
satisfied, so the only new feature is condition (14.8.3), which can be rather tricky. It requires
that λ be nonnegative, and moreover that λ = 0 if g(x, y) < c. Thus, if λ > 0, we must have
g(x, y) = c. An alternative formulation of this condition, then, is that
λ ≥ 0, with λ · [g(x, y) - c] = 0 (14.8.5)
Later we shall see that even in nonlinear programming, the Lagrange multiplier can be
interpreted as a “price” per unit associated with increasing the right-hand side c of the
“resource constraint” g(x, y) ≤ c. With this interpretation, prices are nonnegative, and if
the resource constraint is not binding, because g(x, y) < c at the optimum, this means that
the price associated with increasing c by one unit is 0.
The two inequalities λ ≥ 0 and g(x, y) ≤ c are complementary in the sense that at most
one can be “slack”—that is, at most one can hold with inequality. Equivalently, at least one
must be an equality. Failure to observe that it is possible to have both λ = 0 and g(x, y) = c
in the complementary slackness condition is probably the most common error when solving
nonlinear programming problems.
Parts (ii) and (iii) of the method above are together called the Kuhn–Tucker conditions.
Note that these are (essentially) necessary conditions for the solution of Problem (14.8.1).
In general, though, they are far from sufficient: indeed, suppose that one can find a point
(x0, y0) where f is critical and g(x0, y0) < c; then the Kuhn–Tucker conditions will automatically be satisfied by (x0, y0) together with the Lagrange multiplier λ = 0, yet then (x0, y0)
could be a local or global minimum or maximum, or a saddle point