The Salty Economist

Things I Should Have Learned in High School
posts - 56, comments - 0, trackbacks - 0

F# Calc IRR with Newton's Method

Today's problem is:

Given an investment stream how to I calculate the internal rate of return (IRR)?  For all of you home gamers out there, the internal rate of return is the discount rate that when applied to the investment stream yields a zero present value.

Take for example the following:

You have to pay $1,000 for an investment that returns the following cash flow over its life:

End of Year  1:  $100.00
End of Year  2:  $120.00
End of Year  3:  $125.00
End of Year  4:  $150.00
End of Year  5:  $180.00
End of Year  6:  $200.00
End of Year  7:  $220.00
End of Year  8:  $250.00
End of Year  9:  $290.00
End of Year 10:  $300.00

The question to be solved is what discount rate makes the present value of the stream zero?

In general, this problem is solved iteratively, meaning that you start with some interest rate and then move it up or down in increments until the present value converges to zero.  Obviously, this can be a computationally intense job, so we'd like to make as few interations as possible until we reach convergence.

Hence Newton's Method.

Newton's Method is way cool.  What can I say.

The logic behind Newton's method id this:

Let's say we have a function:

f(x) - y = ?

and we want to select x, such that the function evaluates to zero.  How do we find x?

Let's start with an initial value of x, say x0.  We plug x0 into the function and evaluate it:

f(x0) - y = k

It returns a value of k, meaning we have missed the mark by k.

Newton's method says:  take the first derivative f'(x0), which is the amount that f(x) will change for an incremental change in x.  The logic here is that if we are off by k units and the derivative is f'(X0), our next guess should k multiplied by the derivative plus the initial value of x0:

xNew = x0 + (k * f''(x0))

We then plug this new value into the expression and evaluate its result.  If the result still differs from zero by a certain tolerance, try again.  We then iterate until the result falls within our tolerance level.

So, now let's program this puppy in F#

 In my last post, I showed how to calculate a present value:

let vals = [-1000.0; 100.0; 120.0; 125.0; 150.0; 180.0; 200.0; 220.0; 250.0; 290.0; 300.0]

let pv (i : float) (n : float) =
     1.0 / Math.Pow( (1.0 + i ), n)

let npv x i n =
    x * (pv i n)

let rec valList aList (ir : float) (n : float) =
    match aList with
    | [] -> []
    | h::t -> npv h ir n :: valList t ir (n+1.0)

let presentValue vals (ir : float) =
    List.fold(+)0.0 <| valList vals ir 0.0

let ret1 = presentValue vals 0.12

In the code above, I have a function  presentValue that takes a value list as input and a fixed interest rate (0.12) and returns the present value of the investment stream.  In order to calculate the internal rate of return, I want my interest rate to be variable and solve for the rate that makes the present value equal to zero.  The brute force method, would just iterate over a series of interest rates until the present value reached a certain small number (say epsilon).

But, that is not only ugly, but an uninteresting problem.  So, let's solve it using Newton's method:

First, we need a function that we calculate (numerically) the derivative to a function:

let calcDerivative (afunc: float -> float) x delta k =
    let xNeg = (afunc (x - delta)) - k
    let xPos = (afunc (x + delta)) - k
    let derivative = (xPos - xNeg)/2.0
    printfn "derivative: %10.7f" derivative
    derivative

This function takes as inputs a function (afunc), a value of 'x0' which is the current value of x (the latest guess), a value 'delta' which represents an incremental step, and 'k' which is the value of the function evaluated at x0.

Note the syntax: 

(afunc: float -> float)

This tells F# that we are passing in a function (afunc) that accepts one floating point value as an input and returns one floating point value.  This is really cool because it means we can basically pass the calcDerivative any function to get its derivative -- we don't need to code up specifically for every problem we work on.  Sweet.

What is xNeg?  XNeg is the function evaluated at the current guess (x), less some incremental change (=delta), less the value of the function evaluated at x (=k).  In other words, it is the change in the function from a small decrease in the value of x.

XPos is the same, except that it is the change in the function from a small increase in the value of x.

So, XNeg and XPos are the changes the function if x is first changed down and then up.

We do not pick either one or the other as the derivative, we just settle on the average:

let derivative = (xPos - xNeg)/2.0

Ok, so now we have a derivative.  Our next chore is to create a function to employ Newton's method:

let eps = 0.0001  // Near zero

let Newton (afunc: float -> float) x delta =

    let mutable k = afunc x  //x is the initial guess
    let mutable xNew = x     //initialize xNew = initial guess
    let mutable n = 0        //iteration counter

    while Math.Abs( (float) k ) > eps && n < 25 do
        let derivative = calcDerivative afunc xNew delta k
        xNew <- xNew - ((k / derivative) * delta)
        k <- afunc xNew
        n <- n + 1
        ()
    xNew

Okay, let's go through this line by line.

We first set epsilon (eps) to a value that we consider near zero.

Next, we declare a function Newton:

let Newton afunc x delta =

that takes a function (afunc) as one argument, x which is our initial guess at the solution value and delta which is our increment value used to calculate the derivative

In the function we initialize three mutable (changeable) variables.  These need to be mutable because their values will change within the function.

    let mutable k = afunc x  //x is the initial guess
    let mutable xNew = x     //initialize xNew = initial guess
    let mutable n = 0        //iteration counter

k: is the result of the function evaluated at x
xNew:  will hold our current guess for x
n : is just a counter.  We need this to avoid the possibility of an infinite loop.

We then set up an iteration loop:

    while Math.Abs( (float) k ) > eps && n < 25 do

Which says: Keep iterating until the value of the expression reaches near zero or we have reached 25 iterations.  Because k can approach zero from above or below we need to take its absolute value, hence the Math.Abs function.

Note that:  Math.Abs( k ) will Not work.  I have learned that there is a difference between a regular (immutable) float in F# versus a mutable float.  You need to cast the mutable float into a regular float, using the (float) operator, to get the compiler to behave.

So, in our loop we calculate the derivative:

let derivative = calcDerivative afunc xNew delta k

using our calcDerivative function from above.  It is evaluated at the current value for k for the current guess xNew.

Based on the derivative, we compute our new guess:

xNew <- xNew - ((k / derivative) * delta)

Our new guess xNew equals the old guess less (k / derivative) units of delta.  We need to use the '<-' to set the new value of a mutable variable.

We finish off with:

k <- afunc xNew
n <- n + 1

That reevaluates our function using our new guess.  We then increment our counter.  That's all there is to it.

Now, we have our Newton's method function created, let's apply it to our internal rate of return problem:

let delta = 0.01

let afunc irr =
    presentValue vals irr

let x = Newton afunc 0.1 delta

printfn "IRR: %10.7f" x

We set delta to be 0.01 (1 percentage point).  We create function afunc that takes one floating point value (irr) and returns the present value of the vals List:

let afunc irr =
    presentValue vals irr

We're now ready to rock 'n roll.

We next call Newton's function, using inputs of afunc (our present value function), 0.1 (10%) as our initial guess and our delta as our value to calculate derivatives.

So let's run it:

Starting Newton: xNew:  0.1000000, k: 79.2825644
Derivative: -56.4605965
Iteration 1: New vals xNew:  0.1140421, k:  4.0405266
Derivative: -50.9365534
Iteration 2: New vals xNew:  0.1148354, k:  0.0158683
Derivative: -50.6444916
Iteration 3: New vals xNew:  0.1148385, k:  0.0000170
IRR:  0.1148385

I've thrown in a couple of print statements, so we can see the progress to the solution.  You can see that at our first guess of 10%, k had a value of 79.28.

We next compute our next guess to be 11.404%, which yield a value for k of 4.0405.

From there, it only takes two more guesses to reach a value for k of 0.0000170.

The solution is 11.48385 percent.

I should note, that the speed to convergence greatly depends on your starting guess.  Suppose I had started at zero, we get this:

Starting Newton: xNew:  0.0000000, k: 935.0000000
Derivative: -125.8347959
Iteration 1: New vals xNew:  0.0743038, k: 239.1306183
Derivative: -68.5674031
Iteration 2: New vals xNew:  0.1091790, k: 29.2275793
Derivative: -52.7723509
Iteration 3: New vals xNew:  0.1147175, k:  0.6125441
Derivative: -50.6877687
Iteration 4: New vals xNew:  0.1148383, k:  0.0009165
Derivative: -50.6434072
Iteration 5: New vals xNew:  0.1148385, k:  0.0000010
IRR:  0.1148385

It takes 5 iterations to hit zero.  If I had started at 20 percent it would take 5 iterations.  If we started at 50 percent, it would take a full 18 iterations.  The moral is that a good starting guess will always make it run faster.

So, we now have a function that applies Newton's method to any function single parameter function.  It can be anything, it does not have to be an IRR calculation.  It can be any function that can be characterized as as a single input / single output.  Of course, if we had two equations and two unknowns, we could solve that too, but for that we would employ the Newton-Raphson method instead.  This we will save for a rainy day.

Key Caution:

In this example, we are solving an nth order polynomial equation, in this case 10th order.  We know from high school algebra that polynomial equations have as many solutions as their degree, hence we really have 10 answers to IRR question.  We only found one.  The other 9, however, are irrelevant because they are imaginary numbers.

What we have here is a special case that is characterized by an initial investment outlay in period 0 and positive cash flows in every period thereafter.  This investment profile will always have exactly one real number result.  If the investment stream switches signs in future periods, this statement does not hold -- you will have multiple real answers.  Newton's method above only returns one answer, but which one will it be if there are more than one?  I suspect, it will return the one that is closest to your initial guess, but this is only my supposition.

 

Print | posted on Friday, July 10, 2009 9:24 AM |

Powered by:
Powered By Subtext Powered By ASP.NET