1.  A minimization example

To see in the concrete how to solve a minimization problem, consider

min      8x1 + 3x2

s.t.         x1 + 6x2  $  18

4x1 + 2x2  $  5

x1  $ 0, x2  $ 0

Ifwe converted the above into a maximization problem then we would solve

max     !8x1 ! 3x2

s.t.         !x1  ! 6x2  # ! 18

!4x1 ! 2x2  # !5

x1  $ 0, x2  $ 0.

Letting p1 and p2 be the prices ofthe two # constraints, the first order conditions (FOC’s) are

!8 + p1 + 4p2  # 0      ( = if x1 > 0)

!3 + 6p1 + 2p2  # 0    ( = if x2 > 0).

Ifwe instead minimized the profits of the activities, (8 ! p1 ! 4p2)x1 and (3 ! 6p1 ! 2p2)x2 , subject to x1  $ 0 and x2  $ 0 then we would arrive at the same FOC’s though they would        normally be written as

8 ! p1 ! 4p2  $ 0        ( = if x1 > 0)

3 ! 6p1 ! 2p2  $ 0      ( = if x2 > 0).

Since the FOC’s are unchanged, these two ways of thinking how the FOC’s arise are equally legitimate.

All the other equilibrium conditions for minimization problems (that prices are             nonnegative, that the constraints are satisfied, and that the prices for slack constraints equal 0) coincide with the conditions that arise with maximization problems.

Since the example at hand has a linear objective function and constraints and there are two activity variables, we should consider pairs of binding constraints when hunting for a        solution.  Suppose that x1 + 6x2  $  18 and x1  $ 0 bind.  Then x1= 0 and x2= 3, which              satisfies all ofthe constraints ofthe problem.  Since 4x1 + 2x2  $  5 is not one of the binding    constraints we selected, we set p2= 0 (and indeed since the constraint is slack when x1 = 0      and x2 = 3 we must set p2 = 0).  Since we have not chosen x2  $ 0 as one of our binding           constraints, the FOC for x2 must hold with equality:

3 ! 6p1 = 0.

Sop1 = 1'2.  Since the remaining FOC, 8 ! p1 ! 4p2  $ 0 ( = if x1 > 0), is also satisfied at x1 = 0, x2= 3, p2= 0, p1 = 1'2, we have found the solution.

2.  More on nonnegativity constraints.

You may be slightly puzzled by the fact that our treatment of linear programming has treated nonnegativity constraints and resource constraints differently.  Consider for example

the linear programming problem

max      x1 + 6x2

s.t.         x1 + 3x2  # 60

x1 +   x2  # 30

x1 , x2  $ 0.

(N)

(K)

The FOC’s for this problem are

1 ! pN ! pK # 0          ( = if x1 > 0),

(1)

6 ! 3pN ! pK # 0       ( = if x2 > 0).

Given our treatment of minimization problems, it is clear that we can convert the nonnegativity constraints into # constraints.  That is, we could instead solve

max      x1 + 6x2

s.t.         x1 + 3x2  # 60          (N)

x1 +   x2  # 30           (K)

!x1  # 0

!x2  # 0

since this new formulation of the problem has the same constraint set as the original formulation.

Suppose we treat the last two constraints of the above problem just like ordinary           resource constraints.  That is, we introduce prices p1  $ 0 and p2  $ 0 for these constraints and  require complementary slackness to hold.  Suppose we also tell the activity managers that,       since the final two constraints are now treated as resource constraints, they are free to choose   negative activity levels if it is profit-maximizing to do so.  (They will not do so in equilibrium of course, just as activity managers will not in equilibrium violate standard resource                 constraints.)  Most of the equilibrium conditions for this problem will repeat the equilibrium   conditions ofthe original problem.  But the FOC’s now become

1 ! pN ! pK + p1 = 0

(2)

6 ! 3pN ! pK + p2= 0,

(with no additional parenthetical conditions since activity mangers are allowed to go negative), there will now be two additional complementary slackness conditions

if !x1 < 0 (equivalently, if x1 > 0) then p1 = 0

(3)

if !x2 < 0 (equivalently, if x2 > 0) then p2= 0,

and finally, as all prices must be nonnegative, we now require that

(4)                                          p1  $ 0 and p2  $ 0.

Conditions (2), (3), and (4) together imply condition (1): conditions (2) and (4) imply the inequalities in (1) while conditions (2) and (3) imply the parenthetical parts of (1).  We     can therefore treat nonnegativity constraints just like resource constraints, and still be sure     that the activity levels that rule in an equilibrium will solve the underlying programming        problem.

With this new approach, the algorithm for finding equilibria requires only a minor        adjustment.  As usual, we begin with a set of binding constraints where the number of             constraints equals the number of activity variables (in this case, two).  Then we solve the         binding constraints and see ifthose solutions satisfy the remaining constraints ofthe problem. Next, we set the prices of the remaining constraints equal to 0 (including the new prices we     have introduced for any of the nonnegativity constraints that are not among our set of binding constraints).  Here is the slight adjustment: since we must solve the FOC’s that hold with        equality, we must include one FOC for every activity variable.  Ifwe arrive at nonnegative      prices, we are done.  Since every FOC holds with equality, there is no final step where we       check the FOC’s that are allowed to hold with inequality.

To apply this new method, let us try the guess that the binding constraints are !x1  # 0 constraint and the N constraint.  This occurs at the point x1= 0, x2= 20, which satisfies the     remaining constraints ofthe problem.  Setting pK=p2= 0, the FOC’s for this problem are

1 ! pN + p1 = 0

6 ! 3pN  = 0,

which are solved at pN= 2, p1 = 1.  Since these prices are nonnegative, we have satisfied (2), (3), and (4) and the standard equilibrium conditions that remain unchanged from the original formulation of the problem (the nonnegativity of all prices and activity levels, that the            resource constraints are satisfied, and that complementary slackness holds).  So x1 = 0,

x2 = 20 is the solution.

I have used the fact that conditions (2), (3), and (4) imply condition (1) to conclude     that if we treat nonnegativity constraints like resource constraints then the equilibria that         result will solve the underlying linear programming problem.  We could alternatively directly show that any equilibrium that satisfies (2), (3), and (4) and the standard equilibrium               conditions will solve the underlying programming problem: it would require only minor         changes to the proof ofthe optimality theorem from week 1.  That’s useful to know.  You       may recall from week 2 that when we maximized a quadratic function subject to linear            constraints, Ijust declared that the profits earned by an activity are maximized when the first  derivative of profits is nonpositive and is exactly equal to 0 if the activity is used at a strictly

positive level.  For instance, I asserted that ifwe maximize

60x1 ! (x1)2 ! 3pNx1 ! pL x1 ! pK x1   s.t. x1  $ 0

with respect to x1 then we will reach a solution if the following FOC is satisfied:

60 ! 2x1 ! 3pN ! pL ! pK # 0   ( = if x1 > 0) .

You can now see why this claim is true: ifwe were to introduce a price for the nonnegativity constraint then the equilibrium conditions for this simple programming problem will be met  when the above FOC is satisfied.

3.  Concave functions

So far we have primarily considered linear objective functions, i.e., functions ofthe

But if x does consist of a single variable andf is twice differentiable then there is an    equivalent definition of concavity that you have seen before, that the second derivative off is

always less than or equal to 0, that is, if for all x ,

f NN(x) =  d2f (x)  # 0.

dx 2

To see why these definitions are equivalent whenf is a twice differentiable function of a      single variable, supposef NN(x) # 0 for all x and let x and y be two arbitrary points in the       domain off with y > x.  The point αx + (1 ! α)y then lies between x and y.  Sincef NN(x) # 0 for all x , the slope ofthe chord connecting

(x ,f (x)) and (αx + (1 ! α)y ,f (αx + (1 ! α)y ))

must be at least as great as the slope ofthe chord connecting

(αx + (1 ! α)y ,f (αx + (1 ! α)y)) and (y,f (y)).

That is,

f (αx % (1!α)y) &f (x)      f (y) &f (αx % (1!α)y)

αx % (1!α)y & x               y & αx & (1!α)y     ,

and therefore,

f (αx % (1!α)y) &f (x)      f (y) &f (αx % (1!α)y)

(1!α)(y & x)                          α (y & x)

Multiplying by the nonnegative number α (1 ! α)(y ! x),

αf (αx + (1 ! α)y) ! αf (x) $ (1 ! α)f (y) ! (1 !α)f (αx + (1 ! α)y), or

f (αx + (1 ! α)y) $ αf (x) + (1 ! α)f (y).

Thusf is concave.  One may argue in the reverse direction as well: iff is concave, then the

slopes of the chords connecting points on the graph off diminish in slope, from which it follows thatf NN(x) # 0 for all x .

For twice differentiable functions of one variable, it is therefore easy to figure out if a

function is concave: just check to see ifthe second derivative is everywhere nonpositive.

Familiar examples includef (x) = cx andf (x) =  = x 2 . Nondifferentiable functions of     one variable can be concave as well, e.g., consider the functionf (x) that equals the minimum of cx and a + bx, which is usually written as min [cx , a + bx ].  To confirm concavity for       nondifferentiable functions, you have to apply the chord definition.

For functions of more than one variable, the concavity off of course implies thatf remains concave when restricted to any line in its domain.  It follows that iff is twice       differentiable then it must display a nonpositive second derivative along any line in its      domain.  Fix an arbitrary line L in the domain off.  Since the concavity off implies

f (αx + (1 ! α)y) $ αf (x) + (1 ! α)f (y) for all x and y and all α such that 0 # α # 1, it remains true thatf (αx + (1 ! α)y) $ αf (x) + (1 ! α)f (y) if x and y happen both to sit on L .  It follows   that the second derivative off along any such line must be nonpositive.  Conversely if for         every line, the second derivative off along that line is nonpositive, thenf must be concave.1        Later in the course, we will see how to calculate the derivatives of a function along lines in its domain.

Showing that a twice differentiable functionf ofmore than one variable is concave would appear to be a daunting challenge: there are infinitely many lines in the domain off and it would be impossible to check separately thatf displays a negative second derivative 

1   Given two arbitrary points x and y in the domain off and an arbitrary αx + (1 ! α)y   between x and y, we could, as above, compare the slope of the chord off between x and αx +  (1 ! α)y and the slope of the chord off between αx + (1 ! α)y and y and thereby conclude that the inequalityf (αx + (1 ! α)y) $ αf (x) + (1 ! α)f (y) must hold.

along each one ofthem.  Later, when I introduce a precise definition ofthe second derivative of a function along a line in its domain, I will show you a shortcut.  But it definitely is not      sufficient to check that the own second partial derivatives off are negative.  For example, a   functionf (x1 , x2) oftwo variables need not be concave even when

and

are both negative.

Showing that a function is not concave can often be easier than showing that a      function is concave.  To conclude that a functionf is not concave, it is sufficient to find a

single pair of points in its domain, say x and y, and a number α between 0 and 1 such that

f (αx + (1 !α)y) < αf (x) + (1 ! α)f (y).

For example, with the function g(x) of a single variable that equals the maximum ofx and 2x, usually written g(x) = max [x , 2x], suppose we pick the points x = ! 1 and y = 1 in the domain

of g and α = 1'2.   Since g (! 1) = ! 1, g (1) = 2, and g (0) = 0, we have

g( 1 (! 1) +  1 (1)) = g(0) = 0

2             2

1 g(! 1) +  1 g (1) =  1 (! 1) +  1 2 =  1 .

2                2              2              2         2

Hence

g ( 1 (! 1) +  1 (1)) <  1 g(! 1) +  1 g (1).

2             2            2                2

and therefore g is not concave.  Even though g is a function of a single variable, it is not           differentiable and so we could not have concluded that g fails to be concave by just looking at the sign of its second derivatives.  In fact, at each point where g is twice differentiable – every point besides 0 – it would pass the second derivative test of concavity since its second              derivative at these points is 0.  Yet g is not concave.

One convenient fact about concave functions is that iff (x) and g(x) are both concave

then so is their sum h(x) =f (x) + g(x).  To see why, note that the concavity off and g imply that for all x, y and all α between 0 and 1,

f (αx + (1 ! α)y) $ αf (x) + (1 ! α)f (y),

g(αx + (1 ! α)y) $ αg(x) + (1 ! α)g(y).

Summing, we have

f (αx + (1 ! α)y) + g(αx + (1 ! α)y) $ αf (x) + (1 ! α)f (y) + αg(x) + (1 ! α)g(y),

h(αx + (1 ! α)y) $ α (f (x) + g(x)) + (1 ! α)(f (y) + g(y)) =  α h(x) + (1 ! α) h(y). Notice that I didn’t need to specify whether x consists of one or many variables: the same argument works in both cases.

This simple result for sums provides one way to show that the quadratic function we    considered earlier, c1x1 ! d1(x1)2 + c2x2 ! d2 (x2)2, where the di ’s are positive, is concave     when it is viewed as a function of both x1 and x2 .  Each ofthe four functions c1x1 , !d1(x1)2,  c2x2 , and !d2 (x2)2 is concave when seen as a function of one variable, which you can             confirm by calculating their second derivatives.  To show that their sum is concave, we need   only confirm that each ofthese functions or indeed any concave function of one variable, say   f (x1), remains concave when we view it as a function of an expanded domain that includes an additional variable x2 .  To that end, suppose thatf is concave and let g be the function of x1       and x2 defined by g(x1 , x2) =f (x1) for all (x1 , x2).  Let x = (x1 , x2) and y = (y1 , y2) be two      arbitrary points in the domain of g and let α be some number between 0 and 1.  Then

g(αx + (1 ! α)y) =f (αx1 + (1 ! α)y1) $ αf (x1) + (1 ! α)f (y1) = αg(x) + (1 ! α)g(y). So g is indeed concave.  Hence c1x1 ! d1(x1)2 + c2x2 ! d2 (x2)2 is concave as well.

4.  Further concave functions

[Problems and test questions for the material in this section will occur in Spring Week 4.]

Consider the function h(x) = min [g1(x), g2(x)] where both g1 and g2 are concave functions and where x is allowed to be a vector ofvariables.  Is h concave?

To answer this question, fix some x and y in the domain of h and some α between 0 and 1.  Then for some value of i (either 1 or 2),

h(αx + (1 ! α)y) = gi(αx + (1 ! α)y).

Since gi is concave,

gi(αx + (1 ! α)y) $ αgi(x) + (1 ! α)gi(y).

And since gi(x) $ h(x) and gi(y) $ h(y), we have

h(αx + (1 ! α)y) $ αgi(x) + (1 ! α)gi(y) $ αh(x) + (1 ! α)h(y). So h is concave.

Now suppose g is a concave function of n variables andf is a function of one variable and increasing, where the range in both cases is the real line, then the compositionf (g(x)) is  concave.  A functionf is increasing if zN > z impliesf (zN) >f (z).

To see why this concavity conclusion is correct, let x and y be arbitrary points in the     domain off (g( @ )) and let α be an arbitrary number between 0 and 1.  Due to the concavity of g,

g(αx + (1 ! α)y) $ αg(x) + (1 ! α)g(y).

Sincef is increasing,

f (g(αx + (1 ! α)y)) $f (αg(x) + (1 ! α)g(y)).

Notice that g(x) and g(y) are just two points in the domain off.  Consequently, sincef is concave,

f (αg(x) + (1 ! α)g(y)) $ αf (g(x)) + (1 ! α)f (g(y)). Combining the last two inequalities proves the result we are seeking.

To apply these results, consider the function h(x , y) = ln (min [ax , by]) defined on     pairs (x , y) of positive real numbers, where a and b are both positive.  Is it concave?  Well,    both ax and by are concave (check their second derivatives), they remain concave when seen as functions of both x and y, and hence min [ax , by] is concave too.  Finally since lnz is         concave and increasing (check its second derivative) and h is the composition of ln and