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: