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 inequalityconstraints. 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.
S E C T I O N 1 4 . 8 / N O N L I N E A R P R O G R A M M I N G : A S I M P L E C A S E 527
In this section we consider the simplenonlinear programming problem
maxf (x, y) subject to g(x, y)≤c (1) with just one inequality constraint. Thus, we seek the largest value attained byf (x, y)in theadmissibleorfeasiblesetSof all pairs(x, y)satisfyingg(x, y)≤c.
Problems where one wants to minimizef (x, y)subject to(x, y)∈Scan be handled by instead studying the problem of maximizing−f (x, y)subject to(x, y)∈S.
Using the methods explained in Chapter 13, problem (1) can be solved by classical methods. It involves examining not only the stationary points off in the interior of the admissible setS, but also the behaviour offon the boundary ofS. 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 (1), except in some bizarre cases. The recipe closely resembles the one we used to solve the Lagrange problem maxf (x, y)subject tog(x, y)=c.
R E C I P E F O R S O L V I N G P R O B L E M ( 1 )
A. Associate a constant Lagrange multiplierλwith the constraintg(x, y)≤c, and define the Lagrangian
L(x, y)=f (x, y)−λ
g(x, y)−c
B. Find whereL(x, y)is stationary by equating its partial derivatives to zero:
L1(x, y)=f1(x, y)−λg1(x, y)=0
L2(x, y)=f2(x, y)−λg2(x, y)=0 (2) C. Introduce thecomplementary slackness condition
λ≥0, andλ=0 ifg(x, y) < c (3)
D. Require(x, y)to satisfy the constraint
g(x, y)≤c (4)
Find all the points(x, y)that, together with associated values ofλ, satisfy all the conditions B, C, and D. These are the solution candidates, at least one of which solves the problem (if it has a solution).
Note that the conditions (2) are exactly the same as those used in the Lagrange multiplier method of Section 14.1. Condition (4) obviously has to be satisfied, so the only new feature is condition (3). In fact, condition (3) is rather tricky. It requires that λis nonnegative, and moreover thatλ =0 ifg(x, y) < c. Thus, ifλ > 0, we must haveg(x, y)=c. An
alternative formulation of this condition is that
λ≥0, λã[g(x, y)−c]=0 (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 becauseg(x, y) < cat the optimum, this means that the price associated with increasingcby one unit is 0.
The two inequalitiesλ≥0 andg(x, y)≤carecomplementaryin 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.
WARNING:Failure to observe that itispossible to havebothλ=0andg(x, y)=cin (3), is probably the most common error that students make when answering questions in exam papers involving nonlinear programming problems.
Parts B and C of the above rule are together called theKuhn–Tucker conditions. Note that these are (essentially)necessaryconditions for the solution of problem (1). In general, they are far from sufficient. Indeed, suppose one can find a point(x0, y0)at which f is stationary 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.
NOTE 1 We say that conditions B and C are essentially necessary because the Kuhn–Tucker conditions may not hold for some rather rare constrained optimization problems that fail to satisfy a special technical condition called the “constraint qualification”. For details, see FMEA.
NOTE 2 With equality constraints, setting the partial derivative∂L/∂λequal to zero just recovers the constraintg(x, y)=c. (See Note 14.1.1.) With an inequality constraint, how- ever, one can have∂L/∂λ = −g(x, y)+c > 0 if the constraint is slack or inactive at an optimum. For this reason, we advise against differentiating the Lagrangian w.r.t. the multiplierλ, even though several other books advocate this procedure.
In Theorem 14.5.1 we proved that if the Lagrangian is concave, then the first-order conditions in the problem maxf (x, y)subject tog(x, y)=care sufficient for optimality.
The corresponding result is also valid for problem (1):
T H E O R E M 1 4 . 8 . 1 ( S U F F I C I E N T C O N D I T I O N S )
Consider problem (1) and suppose that(x0, y0)satisfies conditions (2)–(4).
If the LagrangianL(x, y)is concave, then(x0, y0)solves the problem.
S E C T I O N 1 4 . 8 / N O N L I N E A R P R O G R A M M I N G : A S I M P L E C A S E 529 Proof: Any pair(x0, y0)that satisfies conditions (2) must be a stationary point of the Lagrangian.
By Theorem 13.2.1, if the Lagrangian is concave, this(x0, y0)will give a maximum. So L(x0, y0)=f (x0, y0)−λ(g(x0, y0)−c)≥L(x, y)=f (x, y)−λ(g(x, y)−c) Rearranging the terms, we obtain
f (x0, y0)−f (x, y)≥λ[g(x0, y0)−g(x, y)] (∗) Ifg(x0, y0) < c, then by (3), we haveλ = 0, so(∗) implies thatf (x0, y0) ≥ f (x, y)for all (x, y). On the other hand, ifg(x0, y0) = c, thenλ[g(x0, y0)−g(x, y)]= λ[c−g(x, y)]. Here λ≥0, andc−g(x, y)≥0 for all(x, y)satisfying the inequality constraint. Hence,(x0, y0)solves problem (1).5
E X A M P L E 1 A firm has a total ofLunits of labour to allocate to the production of two goods. These can be sold at fixed positive pricesaandbrespectively. Producingxunits of the first good requiresαx2 units of labour, whereas producingy units of the second good requiresβy2 units of labour, whereαandβ are positive constants. Find what output levels of the two goods maximize the revenue that the firm can earn by using this fixed amount of labour.
Solution: The firm’s revenue maximization problem is
maxax+by subject to αx2+βy2≤L
The Lagrangian isL(x, y)=ax+by−λ(αx2+βy2−L), and the necessary conditions for(x∗, y∗)to solve the problem are
(i) Lx =a−2λαx∗=0, (ii) Ly =b−2λβy∗=0 (iii) λ≥0, and λ=0 if α(x∗)2+β(y∗)2< L
We see thatλ,x∗, andy∗are all positive, andλ=a/2αx∗=b/2βy∗. So
x∗=a/2αλ, y∗=b/2βλ (∗)
Becauseλ >0, condition (iii) implies thatα(x∗)2+β(y∗)2 =L. Inserting the expressions forx∗andy∗into the resource constraint yieldsa2/4αλ2+b2/4βλ2=L. It follows that
λ=12L−1/2
a2/α+b2/β (∗∗)
Our recipe has produced the solution candidate withx∗andy∗ given by(∗), andλas in (∗∗). The LagrangianLis obviously concave, so we have found the solution.
E X A M P L E 2 Solve the problem
maxf (x, y)=x2+y2+y−1 subject to g(x, y)=x2+y2 ≤1
5 In fact, as in the argument preceding Theorem 14.5.1, this proof shows that if the Lagrangian achieves a (global) maximum at a point(x0, y0)that satisfies conditions (3) and (4) (whether or not the Lagrangian is concave), then(x0, y0)solves the problem.
Solution: The Lagrangian is L(x, y) = x2+y2+y −1−λ(x2 +y2−1). Here the first-order conditions are:
(i) L1(x, y)=2x−2λx=0 (ii) L2(x, y)=2y+1−2λy=0 The complementary slackness condition is
λ≥0, and λ=0 if x2+y2<1 (iii) We want to find all pairs(x, y)that satisfy these conditions for some suitable value ofλ.
Conditions (i) and (ii) can be written as 2x(1−λ)=0 and 2y(1−λ)= −1, respectively.
The second of these implies thatλ=1, so the first implies thatx =0.
Supposex2+y2 =1 and soy= ±1 becausex =0. Tryy=1 first. Then (ii) implies λ=3/2 and so (iii) is satisfied. Thus,(0,1)withλ=3/2is a first candidate for optimality (because all the conditions (i)–(iii) are satisfied). Next, tryy = −1. Then condition (ii) yieldsλ=1/2 and (iii) is again satisfied. Thus,(0,−1)withλ=1/2is a second candidate for optimality.
Consider, finally, the case whenx=0 and alsox2+y2 =y2<1—that is,−1< y <1.
Then (iii) implies thatλ=0, and so (ii) yieldsy = −1/2. Hence,(0,−1/2)withλ=0is a third candidate for optimality.
We conclude that there are three candidates for optimality. Now
f (0,1)=1, f (0,−1)= −1, f (0,−1/2)= −5/4
Because we want to maximize a continuous function over a closed, bounded set, by the extreme value theorem there is a solution to the problem. Because the only possible solutions are the three points already found, we conclude that(x, y)=(0,1)solves the maximization problem. (The point(0,−1/2)solves the corresponding minimization problem. We solved both these problems in Example 13.5.1.)
Why Does the Recipe Work?
Suppose(x∗, y∗)solves problem (1). Then eitherg(x∗, y∗) < c, in which case the constraint g(x∗, y∗)≤cis said to beinactiveorslackat(x∗, y∗), or elseg(x∗, y∗)=c, in which case the same inequality constraint is said to beactiveorbindingat(x∗, y∗). The two different cases are illustrated for two different values ofcin Figs. 1 and 2, which both display the same four level curves of the objective functionf as well. This function is assumed to increase as the level curves shrink. In Fig. 1, the solution(x∗, y∗)to problem (1) is an interior point of the admissible set. On the other hand, in Fig. 2, the solution(x∗, y∗)is at the boundary of the admissible set.
In case the solution(x∗, y∗)satisfies g(x∗, y∗) < c, as in Fig. 1, the point (x∗, y∗) is usually an interior maximum of the function f. Then it is a stationary point at which f1(x∗, y∗)=f2(x∗, y∗)=0. In this case, if we setλ=0, then conditions (2) to (4) of the recipe are all satisfied.
S E C T I O N 1 4 . 8 / N O N L I N E A R P R O G R A M M I N G : A S I M P L E C A S E 531
f(x, y) ⫽ const.
g(x, y) ⫽ c g(x, y) ⱕ c
y
x P
f(x, y) ⫽ const.
y
x g(x, y) ⫽ c g(x, y) ⱕ c
P
Figure 1 The pointP =(x∗, y∗)is an interior point of the admissible set.
Figure 2 The constraintg(x, y) ≤ cis binding atP=(x∗, y∗).
On the other hand, in the case when the constraint is binding at(x∗, y∗), as in Fig. 2, the point(x∗, y∗)solves the Lagrange problem maxf (x, y)subject tog(x, y)=cwith an equality constraint. Provided that the conditions of Theorem 14.4.1 are all satisfied, there will exist a unique Lagrange multiplierλsuch that the Lagrangian satisfies the first-order conditions (2) at(x∗, y∗). It remains to be shown that this Lagrange multiplierλsatisfies λ≥0, thus ensuring that (3) is also satisfied at(x∗, y∗).
To prove thatλ≥0, consider the two value functions
v(b)=max{f (x, y):g(x, y)≤b} and f∗(b)=max{f (x, y):g(x, y)=b} (6) for the versions of problem (1) in which the constantchas been replaced by the variable parameter b, and wheref∗(b)arises from the problem where the inequality constraint has been replaced by the corresponding equality constraint. Recall from (14.2.2) thatλ=df∗(c)/dciff∗is differentiable atc. We shall now show thatf∗(b)≤f∗(c)whenb≤c, thus implying that
λ=lim
c→b
f (c)−f (b) c−b = lim
c→b−
f (c)−f (b) c−b ≥0
—at least whenf∗is differentiable.
Indeed, (6) implies thatf∗(b)≤v(b)for allb, because the equality constraintg(x, y)=bis more stringent thang(x, y)≤b, and imposing a more stringent constraint never allows a higher maximum value. But also, in caseb < c, the constraintg(x, y)≤bis more stringent thang(x, y)≤c, from which it follows thatv(b)≤v(c). Finally, because we are discussing the case when the constraint g(x∗, y∗)=cbinds at the solution to problem (1), we must havev(c)=f∗(c). Thus, the chain f∗(b)≤v(b)≤v(c)=f∗(c)is satisfied wheneverb < c(and also whenb=c). It follows that f∗(b)≤f∗(c)wheneverb≤c, as required.
P R O B L E M S F O R S E C T I O N 1 4 . 8
1. (a) Solve the problem max−x2−y2 subject to x−3y≤ −10.
(b) The pair (x∗, y∗) that solves the problem in (a) also solves the minimization problem min(x2+y2)subject tox−3y ≤ −10. Sketch the admissible setS and explain the solution geometrically.
2. (a) Solve the consumer demand problem max√
x+√y subject to px+qy≤m (b) Are the demand functions homogeneous of degree 0?
3. (a) Write down the Kuhn–Tucker conditions for the problem max 4−12x2−4y subject to 6x−4y≤a (b) Solve the problem.
(c) WithV (a)as the value function, verify thatV(a)=λ, whereλis the Lagrange multiplier in (b).
4. (a) Write down the Lagrangian and conditions (2)–(3) for the problem maxx2+2y2−x subject to x2+y2≤1
(b) Find all pairs(x, y)that satisfy all the necessary conditions. (There are five candidates.) Find the solution to the problem.
⊂SM⊃5. Consider the problem
maxf (x, y)=2−(x−1)2−ey2 subject to x2+y2≤a whereais a positive constant.
(a) Write down the Kuhn–Tucker conditions for the solution of the problem. Find the only solution candidate. (You will need to distinguish between the casesa∈(0,1)anda≥1.) Prove optimality by using Theorem 14.8.1.
(b) The optimal value off (x, y)will depend ona. The resulting functionf∗(a)is called the value functionfor the problem. Verify thatdf∗(a)/da=λin both cases.
6. Suppose a firm earns revenueR(Q) = aQ−bQ2and incurs costC(Q)= αQ+βQ2as functions of outputQ≥0, wherea,b,α, andβare positive parameters. The firm maximizes profitπ(Q)=R(Q)−C(Q)subject to the constraintQ≥0. Solve this one-variable problem by the Kuhn–Tucker method, and find conditions for the constraint to bind at the optimum.