Chapter 14, Constrained Optimisation



Multivariate Optimization

In applied economics, we often need to optimize a function of several variables. A firm may want to maximize profits by choosing the optimal levels of capital and labor. A consumer allocates his wealth and income between saving and consumption. In chapter 3 it was shown how you could use Excel and the Solver to maximize or minimize functions of one variable. Here, we show how to maximize and minimize functions that have two or more. The chapter is divided into two parts. The first part examines the case where the variables may be chosen freely. The second part considers the case where constraints restrict the values the variables are allowed to take.

In chapter three, you saw that you could use Newton’s method to solve the equation f’(x) = 0 and find stationary points. You could then examine second order conditions to see whether the stationary point gave rise to a maximum or a minimum. When computers solve optimization problems with more than one variable they do this by using computer programs that (often) are generalizations of Newton’s method. These methods are beyond the scope of this booklet, so we will only use the Solver to find solutions to our problems. You should ,however, be aware that all the problems that may occur when we optimize with respect to one variable are even more likely to occur in the multivariate case.

Unconstrained Multivariate Optimization

An unconstrained optimization problem in n variables takes the form

[pic]

In EMEA, you find analytical techniques that may be used to solve this problem. Here, we go directly to the Solver in order to solve it.

Example 1

Consider the problem:

[pic]

Solve this problem analytically and also by using the Solver. You may assume that the problem has a maximum.

Solution.

Using analytical methods we find [pic] and [pic]. It is straightforward to see that setting the derivatives equal to zero implies that x = 1 and y = 1, and f(1, 1) = –1. Enter initial guesses x = 0 into cell A2 and y = 0 into cell B2. Then enter the formula =-(A2^2)-(B2^2)+2*A2+2*B2-3 into cell D2 . Now activate the Solver application. Set the Solver to maximize the content of D2 by changing the cells in A2:B2. Excel should look like Figure 1 at this point.

[pic]

Figure 1 Maximizing – x2 – y2 +2x + 2y – 3

Now click Solve. The Solver then returns the solution x = 1 and y = 1, f(1, 1) = –1.

Example 2

A firm seeks to maximize profits. Using the inputs K and L (capital and labor), it produces X units of product, based on the production sheme given by the function [pic]. The firm sells its product on the market for a price of 100 (monetary units) per unit product ανδ buys K and L for prices of 2 and 2 (monetary units) respectively. The firm’s problem is then

[pic]

Solution.

Setting up the problem as in Example 1 above and solving gives K = 156.25 and L = 156.25 so that [pic] and profits equal 625

Constrained Multivariate Optimization

Constrained optimization is probably one of the most common uses of numerical methods in Economics. This is not surprising, since economics to a large extent is concerned with the optimal allocation of scarce resources and constrained optimization does exactly this: it makes a function take its optimal value, subject to constraints that say what values the variables may take.

Special care should be taken when solving constrained optimization problems with Excel. Sometimes there are several local maxima and/or minima. However when solving constrained optimization problems, the Solver cannot always be trusted to get it right: sometimes a maximum is reported where a minimum occurs and the other way around! Therefore, you should always check, by entering other feasible values (values that obey the constraint) and compare. If an answer is reported as a maximum and you can find other feasible values of the variables that give the objective function a larger value, then the Solver reports an error or the maximum is local. Below, an alternative method is presented. Again, this does not make the Solver (or numerical methods in general) useless. But it remains the responsibility of the user to verify the answers produced by the computational aids he or she employs. Good advise is to try and solve the problem from many different starting points until he or she is reasonably certain that the true optimum has been found.

The Lagrange Multiplier Method

The Solver uses numerical methods to obtain solutions. Example 3 illustrates how the Solver can be made to do that.

Example 3

A consumer makes use of the utility function U(x, y) = xy and faces the budget constraint 2x + y = 100. Solve this problem using the Solver.

Solution.

This example is further explored below, so you may want to save your work. Let x be the content of cell B1 and y that of cell C1. First enter the initial value 0 for both x and y into their respective cells. Then enter the formula =B1*C1 into cell A1. This is the objective function. Enter the formula =2*B1+C1 into cell A2. This gives the constraint. Now set up the Solver to solve the problem. How to do this is illustrated in Figure 2.

[pic]

Figure 2 Solver Dialog Box for Example 3

When examining Figure 2, you see that there is a constraint added in the list box Subject to the Constraints. The constraint information is that the content of cell A2 is equal to 100. This constraint is entered by pressing Add. A dialog box then appears that looks like the one in Figure 3.

[pic]

Figure 3 The Add Constraint Dialog Box

There are three lists in the dialog box in Figure 3. In the leftmost list you enter A2. In the middle list you can choose different relational symbols, giving different types of equation or inequality constraints. In this chapter, we will mostly use equality constraints. The value of the constraint is entered in the rightmost list. Press OK and the Solver Dialog Box will show that the constraint has been added. When the Solver Dialog Box looks like the one in Figure 2, press Solve and the optimal utility value of 1250 appears in cell A1. This maximum is attained at (x,y)=(25,50), which is shown in cells B1 and C1.

Example 4

Solve the problem

[pic]

Solution.

Enter =B1^2+C1^2 into cell A1. This is the objective function. Enter the formula =B1^2+B1*C1+C1^2 into cell A2, giving the constraint. Let x be the content of cell B1 and y that of cell C1 . Let both cells have the value 0. Now set up the Solver to solve the problem. First we solve the maximization problem. The Solver Dialog Box should look like that of Figure 4. Pressing Solve gives us the answer 6 with x = –1.731942 – in cell B1 and y = 1.732159 in cell C1. But we know from the main text that there are two solutions to the maximization problem and Solver has found only one! Indeed, it may very well be the case that solving this problem with different versions of Excel gives different solutions. If you are unlucky you may even get (x, y) = (1, 1) or (–1, –1), which are solutions to the minimization problem. Most likely, starting from x = 0.9 and y = 0.9 gives the solution (1, 1).

[pic]

Figure 4. Solver Dialog Box for Example 4

To understand this, we must have an idea of how the Solver works. It seems that the Solver homes in on the nearest stationary point as seen from the starting point. So, in order to find other optimal values one must try out different starting values for x and y . Entering 2 into B1 and –2 into C1 before pressing Solve should work .

In order to solve the minimization problem, repeat the process above with the option min in the Solver Dialog Box.

Example 5

Consider the problem

[pic].

Let A = 1, a = 0.6, b = 0.4, p = 10 and m = 100. Make a graph of an approximate curve for the optimal y as a function of the parameter q.

Let q = 10. What is the effect of changing A to 2? What is the effect of simultaneously changing a to 1.5 and b to 1? Explain.

Solution.

We ask Excel to solve the problem

[pic]

for several values of q. Let q take the values 2.5, 5, 7.5, 10, 15 and 20. Figure 5 shows the optimal y as a function of q.

[pic]

Figure 5 Optimal y as a function of q

From theorem 13.5.3, on page 493 in EMEA you know that in the unconstrained multivariate case, and under certain conditions, the maximization (minimization) of a function F(f(x,y)) immediately follows from that of the function f(x,y), because the optimum values of both functions are attained at the same point. This example illustrates that this also holds for constrained optimization problems. Changing A to 2 has no effect on the values of x and y corresponding to the solution. Increasing A to 2 is the same as multiplying the objective funtion by 2. In this case F(f(x,y)) is simply 2f(x,y) and [pic] is a strictly increasing function. The simultaneous changes in a and b have no effect on the solution either. Changing a to 1.5 and b to 1 is equivalent to raising the objective function to the power of 5/2, and [pic] means that [pic], which is also a strictly increasing function for [pic] .

Example 6

Solve

[pic]

Solution.

Solving this problem with the Solver produces the message: The Set Cell values do not Converge. This is the Solver's standard response to problems whithout solution as is the case here . To see this, try to solve the problem graphically.

Exercises

Exercises 1 to 5 in section 14.1 of EMEA may all be solved with Excel.

Economic Interpretations of The Lagrange Multiplier.

In the previous examples of this chapter, we did not ask the Solver for the multiplier value at (x*,y*) corresponding to the solution. However, the Solver does in fact calculate the multiplier. It mentions the multiplier value in the Sensitivity Analysis report that may be created after Solver has found a solution.

Example 7

With reference to Example 1 in 14.1, find the value of the Lagange multiplier. Then solve the problem with the new constraint 2x + y = 101. Explain the increased value of the objective function by means of the Lagrange multiplier.

Solution.

After pressing Solve, click on Sensitivity in the Reports list. This is illustrated in Figure 6 .

[pic]

Figure 6. Getting the Lagrange multiplier

A new sheet is created where the Lagrange multiplier is reported to be = 25. We already know that maximizing xy with respect to 2x + y = 100 gives the result x = 25, y = 50. Observe that xy = 1250 when x = 25 and y = 50 . We do not need to set up the problem from schratch when solving the slightly adjusted problem with constraint 2x + y = 101. Call the Solver application in the same sheet you used to solve Example 1 of section 14.1. Then press the Change button. In the dialog box that appears, change the constraint constant from 100 to 101. Now press Solve in the Solver dialog box. The answer should be x = 25.25 and y = 50.5, with corresponding value of the objective function 25.25×50.5 = 1275.125. Since 1275.125 – 1250 = 25.125, the Lagange multiplier is a good indicator of the effect of a small change in the constraint constant. In fact, if 2x + y = c is the constraint and M is the optimal value of the objective function viewed as a function of c, then the Lagrange multiplier is [pic].

Exercises

1. A consumer has an income m that must be allocated between the purchase of goods x and y. The unit price of x is € 8 and that of y is € 6. The utility of the consumer is given by U(x, y) = [pic] . Solve the problem:

[pic] (1)

for m = 10, 15, 20 and 25. For each value of m find the Lagrange multiplier λ. Sketch the graph of λ as a function of m. Interpret the graph.

Sufficiency Conditions

Since numerical algorithms may result in wrong answers, it is important to find conditions that enable us to ascertain whether we have found a correct solution. Local optima may be discovered by finding the stationary points of the Lagrangian function. There is, however, no way of deciding whether a given optimum is global other than comparing its value with that of all possible candidates (the local optima). Here, we implement the sufficiency conditions from the main text in Excel for the problem max(min) f(x, y) subject to g(x, y) = c, and use them to check if solutions obtained by the Solver satisfy the conditions for a local maximum or minimum .

Local Second-Order Conditions

The main text reports the following condition for a local maximum (minimum). Define

[pic] (2)

Let (x0, y0) satisfy the first-order conditions for a maximum (minimum). Then (x0, y0) solves the local maximization problem if D(x0, y0) < 0 and the local minimization problem if D(x0, y0) > 0 (page 517 of the main text).

Example 8

Consider the problem

[pic] (3)

In order to make the Excel formulae legible we define f, g and the second order derivatives in Excel's macro language. You are encouraged to activate the Visual Basic Editor, insert a new module, name it Functions and copy the function coding below into this module. Having done this once, you can use the same sheet as a template anytime you want to solve a problem of the form max(min) f(x, y), subject to g(x, y) = c. You just have to change the functional definitions in the code. The function names should indicate which derivative or second order derivative is being evaluated.

Function f(x, y)

f = x ^ 2 + y ^ 2

End Function

Function g(x, y)

g = x ^ 2 + x * y + y ^ 2

End Function

Function dfdx(x, y)

dfdx = 2 * x

End Function

Function dfdy(x, y)

dfdx = 2 * y

End Function

Function dgdx(x, y)

dgdx = 2 * x + y

End Function

Function dgdy(x, y)

dgdy = 2 * y + x

End Function

Function dfdxdy(x, y)

dfdxdy = 0

End Function

Function dfdydy(x, y)

dfdydy = 2

End Function

Function dfdxdx(x, y)

dfdxdx = 2

End Function

Function dgdxdx(x, y)

dgdxdx = 2

End Function

Function dgdydy(x, y)

dgdydy = 2

End Function

Function dgdydx(x, y)

dgdydx = 1

End Function

After coding the functions, their derivatives and second order derivatives, we can code D(x, y). The Lagrange multiplier λ is also an argument; it is included in the list of arguments that the function takes under the name L.

Function D(x, y, L)

p1 = (dfdxdx(x, y) - L * dgdxdx(x, y)) * (dgdx(x, y)) ^ 2

p2 = 2 * (dfdxdy(x, y) - L * dgdydx(x, y)) * dgdx(x, y) * dgdy(x, y)

p3 = (dfdydy(x, y) - L * dgdydy(x, y)) * (dgdy(x, y)) ^ 2

D = p1 - p2 + p3

End Function

After defining these functions we can code the spreadsheet. This is done as in Figure 7.

[pic]

Figure 7 Checking Sufficiency Conditions

In Figure 7 , the objective function is entered into cell A2. The constraint function is entered into cell A3. Instead of using the Solver option to get the value of the multiplier λ in a separate worksheet, we calculate it in this sheet. Since λ = [pic], (it could also be given by [pic]) we calculate λ by entering this formula in cell B7. D(x0, y0) is calculated in cell B8. After entering the problem into the Solver Dialog Box, the dialog box should look like the one in Figure 8. Note that we have asked the Solver to solve the minimization problem.

[pic]

Figure 8 Solver Dialog Box for the problem in Example 8

After pressing Solve, the answer x = 0.9999 ≈ 1, y = 1 and λ = 0.666667 ≈ 2/3 is reported. Further, D(1, 1) is reported to be 23.9999 > 0. We have therefore confirmed that at (1,1) the objective function attains a local minimum.

Exercises

1. Solve exercise 1 in Section 14.4 of EMEA.

2. First solve exercise 3 in Section 14.4 of EMEA algebraically. Verify that the solution exists for all positive values of q. Further, let a = 0.5, p = 5, q = 5 and m = 75. Now use the Solver to solve this problem. Solve the problem again with q = 10. And again with q = 20. Does the Solver run into problems? If so, try to work around them. Verify numerically that you have found a local maximum. (In fact you found a global maximum.)

More Variables and More Constraints

Up to a point, it is straightforward to increase the number of variables and constraints in the Solver. There is a built-in limitation of 100 variables and 100 constraints. If you ever need to solve larger problems, you will probably want to use other programs. Also, the larger the problem, the more complicated it is to establish that sufficiency conditions are fulfilled.Also, you are well advised never to enter more constraints than there are variables. Example 9 below is about a problem with three variables, and Example 10 has three variables and two constraints.

Example 9

Solve the problem max [pic], subject to x + y + z = m. Solve the problem for m = 12, 24 and 36.

Solution.

Setting up the problem in Excel and solving leads to (x, y, z) = (4,6,2) when m = 12, (x, y, z) = (8,12,4) when m = 24, and (x, y, z) = (12,18,6) for m = 36.

NB. The x,y, and z values are given approximately, depending on the version and the setting of the Excel software in use.

Example 10

Solve the problem min x2 + y2 + z2, subject to [pic].

Solution.

Enter =C2^2+D2^2+E2^2 into the cell B2, enter =C2+2*D2+E2 into the cell B3 and enter =2*C2-D2-3*E2 into the cell B3. Then set the Solver up as in Figure 9 . To enter multiple constraints, use the Add button twice. The optimal value of the objective function is 200, and the minimum is attained at (x,y,z) = (10,10,0).

[pic]

Figure 9 Solver Dialog Box for the problem in Example 10

Exercises

1. Solve exercise 1 (a) in section 14.5 of EMEA.

2. Solve exercise 2 in section 14.5 of EMEA for b = 1.

3. By using the solver:

(a) Solve the problem max x2 + y2, subject to [pic].

(b) Solve the problem max [pic], subject to [pic].

(c) Explain why you get the same solution under (a) and (b).

Comparative Statics

Also for problems with more than one constraint the Solver computes the Lagange multipliers for every constraint. When the Solver tells you it has found a solution, click on Sensitivity in the Reports window and a sensitivity report sheet is added to the current workbook.

Example 11.

Solve the problem max [pic], subject to [pic].

Let λ1 and λ2 be the multipliers associated with the constraints x + y = 2 and y – x2 = 0, repectively. The problem has two solutions. It can be shown that both are local maxima. Depending on the starting value, the Solver returns the answer x = 1, y = 1 and z = 1, or x = -2, y = 4 and z = 10. Asking for a sensitivity report in the two different cases gives two different sets of Lagrange multipliers. For the solution x = 1, y = 1 and z = 1, the Solver gives λ1 = 2 and λ2 = 0, and for the solution x = –2, y = 4 and z = 10, the Solver comes up with λ1 = 120 and λ2 = –40. Comparing the two solutions one verifyies that x = -2, y = 4 and z = 10 gives the global maximum.

Example 12.

Confirm that the marginal utility of money is equal to λ and confirm Roy's identity for the model max x0.5y0.5 subject to px + qy = m, when p = 2, q = 4 and m = 4.

Solution.

Solving the problem with Excel gives the answer: [pic] for x = 1, y = 0.5 and λ = 0.1767766.

Solving the problem again with the constraint 2x + 4y = 5 gives the solution x = 1.25, y = 0.625, and [pic]≈ 0.8838. Subtracting maximal utility when m = 5 from maximal utility when m = 4 gives [pic] – [pic] = 0.17677 = λ, which shows that here marginal utility of money is given by λ. Checking Roy’s identity is a bit more tricky. We now vary p. Solving the problem again with the constraint 3x + 4y = 4 gives the solution x = 25/3, y = 0.625, and [pic]≈ 0.7216. Subtracting maximal utility when p = 2 from maximal utility when p = 3 gives [pic] – [pic] ≈ –0.1297. Calculating –λx from the original solution gives –λx = –0.17677. Although the values –0.17677 and –0.1297 are not so far apart, they are not close enough to give a satisfactory result. Let us try again, but with a much smaller increase in price. We solve the problem for p = 2.1. The solution is x = 0.953 and y = 0.5, and [pic] – [pic] = –0.01704. Multiplying this number with 10, since we only added 0.1 to the price, gives –0.1704 which is considerably closer to [pic].

Why did we have to use a trick when confirming Roy's identity but not when we found the marginal utility of money? This is best seen by finding an analytical solution to the problem. Solving the problem analytically gives x* = m/2p and y* = m/2q, and [pic]. From this solution, we see that maximal utility is a linear function of m, but highly non-linear in p and q. Because of this non-linearity, the partial derivatives of U* with respect to p and q are also highly non-linear functions, whereas the derivative of maximal utility U* with respect to m is constant.

Exercises

1. Solve problem 1 (a) in section 14.6 of EMEA for b = 1, 2, 3, , 10. In each case find the value of the multiplier. Draw a graph of the multiplier as a function of b.

2. Solve problem 2 (b) in section 14.6 of EMEA with the Solver.

3. Solve Problem 3 in section 14.6 of EMEA with the Solver.

Nonlinear Programming: A Simple Case

In this section we look at problems of the form max f(x, y), subject to g(x, y) c. Compared to solving constrained problems with constraint g(x, y) = c, only a small change must be made setting up the Solver in order to solve constrained problems with an inequality constraint. When adding the constraint, simply specify the constraint as an inequality.

Example 13.

Solve max f(x, y) = x2 + y2 + y – 1, subject to g(x, y) = x2 + y2 1.

Solution.

Enter the objective function and the constraint in just the same way as you would in case of an equality constraint. When adding the constraint take care to check that the constraint takes the form of a constraint. This is illustrated in Figure 10. Figure 10 assumes that the constraint takes a value contained in the cell L30.

[pic]

Figure 10 Entering a “less than” constraint

Solving the problem with the Solver from the starting point (x,y) = (0,0) gives x = 0.00094 and y = 1, which corresponds with the (global) maximum 1. The multiplier value is given as 1.5. Observe that [pic] for any (x,y) that satisfies the constraint, so that indeed the global maximum is 1, attained at (x,y) = (0,1).

Exercises

1. Solve Problem 1 (b) in section 14.7 of EMEA. Since there are 5 candidates for solutions, experiment with different starting points and see how many candidates you can get Solver to report as optimal.

More on Nonlinear Programming

How to go from problems with two variables and one constraint to problems with more variables and more constraints is not hard to guess. Example 13 shows how to solve a problem with two variables and two constraints.

Example 13

Solve max y – e-x subject to ex + ey 6 and y – x 0.

Solution.

:Let be the multiplier associated with the constraint ex + ey 6 and let be the multiplier associated with the constraint y – x 0. Enter =E4-EXP(-D4) into cell C4. Thus, x is the content of D4 and y that of E4. Now enter =EXP(D4)+EXP(E4) into cell C6 and =E4-D4 into cell C7. Then activate the Solver. After setting up the Solver and adding the constraints, the Solver Dialog Box should look as in Figure 11.

[pic]

Figure 11 The Solver Dialog Box for Example 13

Note that the second constraint takes the form of a constraint. You can of course rewrite the constraint to –y + x 0 and enter the constraint in the Solver as a constraint. Pressing Solve gives x = 0.6932 ln2 and y = 1.3862 ln4, with maximum [pic]. The sensitivity report gives the Lagrange multiplier values = 0.25 and = 0. This agrees with the fact that Excel reports ex + ey = 6 and y – x > 0 for these values of x and y.

Exercises

1. Solve Problem 1 (b), section 14.8 in EMEA.

2. Solve Problem 2 (b), section 14.8 in EMEA.

3. Solve problem 5. Do this in two ways. First solve the problem entering the non-negativity constraints explicitly in the constraints box. Next remove the non-negativity constraints and instead check Assume Non-Negative in the Solver Options Dialog Box. Verify that the answer fits the Kuhn Tucker conditions by checking the sign of the derivatives of the Lagrangian.

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download