Single Variable Optimization



Single Variable Optimization

Numerical Optimization - Why and how.

Single optimisation is the basis for many results in economics. However, many optimisation problems can only be solved with numerical methods. To illustrate, consider the building of a dam where the choice variable, x, is dam capacity. The dam produces a constant stream of benefits equal to A. The cost of the dam is a quadratic function of capacity, namely cx2 for a suitable positive constant c. There is also a probability that the dam may overflow causing damage worth K, and the probability of this happening is a decreasing function of capacity, given by e-x. The benefits is thus g(x) = A – e-xK –cx2. This leads to the following optimisation problem:

[pic] (*)

where all constants are positive. Note that g’(x) = (e-(xK – 2cx and g’’(x) = –(2e-(xK –2c < 0. Since g’(0) > 0, g’(x) ( ( as x ( ( and g’(x) is strictly decreasing, g’(0) =0 has a unique solution, x0 on (0, (). Since x0 is an interior stationary point and g(x) is concave, x0 a global maximum point. However, the equation [pic] can not be solved explicitly for x0. Let A = K = c = 1 and = 2 for simplicity. The graph of g is shown in Figure 1. It seems to have a maximum at x0 ( 0.4.

[pic]

Figure 1, The benefits of building a dam

The maximum point satisfies

[pic] (**)

Let us now solve the problem [pic] with Excel. The easiest way is to use the Solver and maximise the function directly. This can be done as follows. First enter a formula into a cell. E.g. enter the formula =1-EXP(-2*D4)-D4^2 into cell C4. Thus we have entered the objective function into cell C4 and the argument x is entered into cell D4. Next, load the Solver application. Press + + . This makes the Solver Dialog box appear. Enter a reference to cell C4 in the box Set Target Cell: and enter a reference to cell D4 in the text box By Changing Cells:. The Solver Dialog box should look like Figure 2.

[pic]

Figure 2, Solver Dialog Box for the problem: max 1 - e-2x - x2

Pressing Solve solves the problem. A new dialog box appears and one is asked if one wants to keep the solution found by Solver or keep the initial value entered in the D4 cell.[1] Pressing Ok and accepting the Solver solution gives the correct answer x = 0.426303 in the cell D4.

The benefits of using the Solver in this case are obvious. We have solved a problem that we would not have been able to solve with pen and paper, unless we went through a numerical solution method as Newton's method discussed in chapter 7 in EMEA or chapter 2 in this booklet. In fact, many methods for finding optimal solutions with a computer are based on Newton's method. Let us show how this method could be used to solve equation (**). g’(x) = [pic] = 0. Here g’’(x) is given by 1 + e-2x. The sequence [pic] defined by Newton's formula is here:

[pic]

To solve the problem using Newton's method, first define the following functions in VBA. (See chapter 1 for instructions on writing functions in VBA.)

Function dg(x)

'This is the derivative of g(x)

g = x - Exp(-2 * x)

End Function

Function d2g(x)

'This is the double derivative of g(x)

dg = 1 + 2 * Exp(-2 * x)

End Function

We then use these functions to look for the value x that solves g’(x) =0. Let 0 be the initial guess for x0. Enter 0 into D11. Then enter the formula =D11-dg(D11)/d2g(D11) into D12. This is the first iteration. Then copy the content of cell D12 into the range D13:D19. The results should look like Figure 3.

[pic]

Figure 3, Optimisation with Newton's method

From Figure 3 we can see that Newton's method seems to converge to an approximate solution very quickly and that this solution is the same as the one found with the Solver above.

Examples

Example 1

Consider Example 1 page 276 in EMEA. Solve the parameterised examples (a) and (b) using the Solver.

(a)

Max (N) = Max([pic])

Solution:

Enter the formula =10*sqrt(B2)-0.5*B2 into cell B3. Thus we want to maximize the content of the cell B3 by changing the content of cell B2. Load the Solver and enter the relevant cell names. The Solver Dialog Box should look similar to the one in Figure 4.

[pic]

Figure 4, Maximising [pic] with the Solver.

Clicking the Solve button solves the problem and gives us the answer x = 100 and [pic] = 50.

(b)

Max (N) = Max([pic])

Solution:

Use the same spreadsheet as above but simply change the formula in cell B3 to =1.4*(-13.62+0.984*B2 - 0.05*B2^1.5) - 0.18*B2. Then load the Solver and click Solve. The Solver then reports the correct answer 32.86406 for x = 130.0903, so that (130.0903) = 32.86406.

Example 2

Consider Example 3 page 279, EMEA. Solve the problem

[pic]

where c2 = y2 - (1+r)(c1 - y1) . Assume that y1 = y2 = 100 and r = = 0.5.

Solution: Since these expressions are somewhat involved we prefer to define them as VBA functions. Define:

Function U(c_1, c_2)

d=0.05

U = Log(c_1) + (1 / (1 + d)) * Log(c_2)

End Function

and:

Function K(c_1)

r=0.05

K = 100 - (1 + r) * (c_1 - 100)

End Function

The U function is the utility function. The K function gives consumption in period 2, c2, as a function of consumption in period 1, c1. Now enter a number, say 50, into cell B2, enter =K(B2) into C2 and =U(B2;C2) into D2. Then load the Solver. Set the Solver up to maximise the content of D2 by changing cell B2. The Solver Dialog Box and the content of the cells should be as in Figure 5. Clicking the Solve button gives us the solution c1 = 99.99998 100, c2 = 100 and U 9. The exact solution is c1 = 100 and c2 = 100. The reason the Solver reports c1 = 99.99998 is that the difference between U(99.99998, 100) and U(100, 100), (≈ 10−14 ) , is so small that the Solver, using Newton’s method, decides it cannot improve the result any further by varying c1. Another method however (the so-called Conjugate Gradient method, which can be selected under Solver/Options) gives the optimal value attained at exactly c1=100.

[pic]

Figure 5, Solving the two-period consumption problem.

Exercises

a)

Experiment with different values of y1 and y2. Verify for yourself that for all possible positive values of y1 and y2, c1* = c2* as long as = r. (This can be seen by using the formula for c1* in the example, with c2* = y2 – (1 + r)(c1* – y1).)

b)

Plot U as a function of c1 and verify that the solution above is in fact a maximum.

c)

y1 + (1 + )-1y2 is the Net Present Value of the consumer's income. What solution does the problem yield if y1 and y2 are chosen so that y1 + (1 + )-1y2 < 0. Comment.

Example 3

Consider Example 2 on page 287 EMEA. The firm has revenue R(Q) = 121Q and cost function C(Q) = 0.02Q3 -3Q2 + 175Q + 500. The firm can produce at most [pic] = 110 units.

(a)

Make a table of the values of the functions R(Q) = 121Q, C(Q) and (Q) = R(Q) - C(Q) for Q = 0, 10, 30, 70, 90 and 110. Draw the graphs of R(Q) and C(Q) in the same co-ordinate system.

(b) Use the Solver to answer the following questions:

(i) How many units must be produced in order to make a profit?

(ii) How many units must be produce for the profit to be 2000 dollars?

(iii) Which production level maximizes profits?

(c)

What is the smallest price per unit the firm must charge in order not to lose money if capacity is fully utilized (Q = [pic]= 110)?

Solution:

(a) It is convenient to define C(Q) as a function in VBA. Unfortunately VBA does not accept the letter C as a function name so we rename the cost function K(Q). The VBA code for the cost function should look like this:

Function K(Q)

K = 0.02 * Q ^ 3 - 3 * Q ^ 2 + 175 * Q + 500

End Function

After defining the cost function in VBA, enter the formulas into a worksheet as shown in Figure 6.

[pic]

Figure 6

The figure shows the formulas. The corresponding values are those in Table 1, p 288 in EMEA. Making graphs of R(Q) and C(Q) in Excel is easy once the numbers have been tabulated. This is done in Figure 7

[pic]

Figure 7. Revenue and Cost funtions

(b)

(i) This can be answered by solving the equation (Q) = 0. Enter = 121*B1 -K(B1) into the B2. Then in the Solver Dialog Box, set the content of B2 equal to zero by changing B1. Take care to enter the constraint Q 110 into the constraints box. (What can happen if you forget this and start with too large a value in B1?) The Solver Dialog Box should look like the one in Figure 8.

[pic]

Figure 8, The Solver Dialog Box set up to solve π(Q)=0.

Clicking the Solve button gives the solution Q = 29.43915 and indeed (29.43915) 0. From the graph we can see that for larger values of Q, profit is positive.

(ii) To solve this problem, we only need to change the Dialog Box by changing Value of: from 0 to 2000. Doing this and pressing the Solve button returns Q = 52.08522. A check shows that [pic] is equal to 2000.

(iii) To solve the profit maximization problem, set the Solver to maximise by clicking Max. The Solver returns Q = 90 and (90) = 4360.

(c)

For the profit function we now have [pic] P[pic] - C([pic]) = 110P - C(110) = 0. To find P, just enter the formula =K(110)/110 into a cell and the answer 91.54545 will appear.

Things that may go wrong

When looking for maxima and minima, it is often useful to make a graph of the function we want to optimize. The following example illustrates that Excel and similar programs may go wrong. Consider the problem max –ln(x – [pic])2. Figure 9 shows a graph of y = –ln(x – [pic])2. It appears that there is a maximum between x = 0.2 and x = 0.4.

[pic]

Figure 9, Approximate graph of y = –ln(x - 1/3)2

There is, however, no maximum. We can make -ln(x - [pic])2 as large as we want by letting x get closer and closer to 1/3. At x = 1/3, -ln(x - [pic])2 is not defined.

The problem with this example, is that when we draw a graph, Excel uses a sample of points and joins successive dots by small line segments. The resulting plot misses the discontinuity at x = 1/3. This should not be seen as a shortcoming of Excel, but merely as a consequence of the technique of joining points into a fluent line, which is used by most software packages. It may help to have a at the graph of the derivative y’ = –6/(3x – 1). This graph is shown in Figure 10. Observe that in the plot, the sample points are shown as individual dots, rather than joined into a continuous line. It is quite clear from this figure that there is no point at which the derivative vanishes. When x tends to 1/3 from below, the derivative is positive and grows larger and larger. For values of x larger than 1/3 the derivative is negative. It therefore seems plausible that there is no value of x for which [pic], which is in fact the case.

[pic]

Figure 10, [pic]

Another example in which curve-plotting and numerical solution can lead to wrong results is illustrated in the following problem.

Example 4

Find [pic] and [pic] when

[pic]

This graph of this function is drawn in Figure 11.

Figure 11 tells us that f(x) probably has a maximum at x = 5. We also get the impression that is close to 0 to the left of x = 4. This turns out to be an illusion created by the scale of the y-axis. Since f(x) explodes so rapidly to the right of x = 4, all detail disappears from the graph in the interval [-1,4]. We solve the problem by asking the Solver to minimise f.

[pic]

Figure 11

Enter an arbitrary number, say 0, into cell B2. Then enter =B2^26-32*B2^23-11*B2^5-2*B2^3-B2+28 into cell B3. Then load the Solver. Take care to enter the constraints x -1 and x 5. The Solver dialog box should be as in Figure 12,. Clicking the Solve button gives us the solution x = 3.047671274 and f(x) = -4.99534E+11. A pretty big minimum to miss! Now let us look for maxima. The problem is already set up, we just need to change the Min to a Max option. If your initial guess is x = 2 or thereabouts, there is quite a good chance that the Solver will report the maximum as 75 attained at x = -1. From Figure 11 we know that this can not be right. But starting from x = 4 we get the correct answer x = 5 and f(5) = 1.10865E+18.

The problem is that the algorithms used in the Solver, as almost all numerical algorithms for finding roots of equations, are “local” (as opposd to “global”) algorithms. This means that they work as follows: Guess an approximate value for the root, and substitute it into some formula derived from your equation to obtain another, hopefully better approximation to the root. Now iterate this until no real improvement occurs. However, if you happen to misjudge the general location of the root, making your initial guess too far removed from it, then things may go terribly wrong. In other words, starting “locally” finds the actual root to the precision required, but starting anywhere often does not.

[pic]

[pic]

Figure 12, Solver options for the problem min f(x)

Returning to our example, these algorithms use the shape of the function to find solutions that either satisfy f'(x) = 0, or find endpoint solutions corresponding to (are) local optima attained at the endpoints of the given interval. What they can not do is tell if there are other optima around.[2] Although this is not at all obvious, our polynomial function has no other local stationary points than those attained at x = –1, x = 3.047671274 and x = 5. We were just lucky to find them all.

[pic]

Figure 13

Guarantees for finding a global optimum from any starting point can only be given for a very restricted class of functions, in particular strictly convex and concave functions. An extreme example is given by the following function

[pic]

The graph of this function is illustrated in Figure 13. This function can be seen to have at least seven values of x for which h'(x) = 0. If a numerical algorithm comes sufficiently close to any such value, it will report that point as corresponding to a minimum or maximum and chances are that it will be wrong. The moral is that numerical optimization methods must be used with care. They are important tools that help us cope with difficult problems, but they must be used with caution and the results must be carefully interpreted. If not they may produce serious mistakes. Since economists use these methods to solve important practical problems, where the cost of errors to society can be severe, it is the practicing economist’s responsibility to aquaint herself with these methods and their problems so that costly mistakes can be avoided. In later chapters, we shall see that as we move from single to multi-variable optimization, the complexity involved increases, and hence the potential for errors also increases, and the problem of detecting such errors gets necessarily worse.

Exercises

1. Use Excel to solve excercises 2 and 3 (a), in Review Problems for chapter 8 in EMEA.

2. Use Excel to solve excercise 6, in Review Problems for chapter 8 in EMEA. Use Newton's method to Solve (b). Did you find extremal points?

-----------------------

[1]If no value was entered, the Solver returns the value 0 to the cell.

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

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

Google Online Preview   Download