Thread Subject: Backward recursion (real option investment analysis)

Hello MATLAB community,

I am trying to implement a backward recursion procedure in Matlab for a real option analysis of investments.

The user of the program is entitled a given budget and with that budget may invest in a combination of investment alternatives (4 unique alternatives amounting to 25 investment combinations given the budget and investment costs). He may do so now or during the next five years (hence 6 investment windows). He is looking for the optimal policy (i.e. optimal investment combination choices throughout year zero to five) that will maximize his gain from investing.

Using Bellman's equation, that optimal policy would be given by the following formula:
V = max ("immediate reward in time t" + "1-year discount rate"*"optimal subsequent investments")
The move from "investment in time t" and "investment in time t+1" is constrained by the budget (thus, there is a transition matrix). The backward recursion starts with the optimal choices in time "t=5" given any of the 25 budget levels and works backwards using the V function.
 
Hopefully the program would return both the total value of the investment undertaken as well as the investment combinations chosen at any of the 6 investment windows.

So far, I have generated:
- a "reward matrix" comprised of the net gain from investing in unique investment combination (25) at a given time (6) and given a remaining budget level (25). The reward matrix has 150 rows (25 budget levels from 0 to initial budget multiplied by 6 investment windows) and 25 columns (corresponding to the unique investment combinations).
- a "transition matrix" for the budget. That matrix has 625 rows (25 rows for budget in time "t" multiplied by 25 investment combinations undertaken in time "t") and 25 columns (corresponding to budget in time "t+1"). The matrix is comprised of "1" and "-inf".
- a 1-year discount rate.

I am getting really stuck at this point and cannot seem to move any forward so if any of you has an idea to solve this problem that would be great!

Many thanks in advance for your help.

Best regards,

Morgan

PS: I have been trying (unsuccessfully) to use the CompEcon toolbox from Miranda but could not apply it since rewards are changing depending on year investments are undertaken and because of the whole set of functions that are to be checked with it...

PS: Hereafter is a sample of this reward matrix:
Row one means that the budget is exhausted and no investment can be undertaken.
Row 25 means that the budget is complete and any of the 25 investment combination can be undertaken.
In columns, we consider gains from one the 25 investment alternatives (in column one - the user considers not investing and simply waits next turn; in column two - he gains

   1 2 3 4
1 0 -Inf -Inf -Inf
2 0 -Inf -Inf -Inf
...
24 0 -6,41940944404530 156,566315880108 1772,90166521525
25 0 -6,41940944404530 156,566315880108 1772,90166521525
That's it for the year zero (i.e. now).
Stacked below are similar reward for year 1 to 5.

I am having similar problems with the R2009 versions implementing dynamic programming algorithms for this type of problem, including with the CompEcon Toolbox that used to run.

The following might be the source of one or more problems:
--interaction with Optimization Toolbox or Robust Control commands
--RecursionLimit issues (see Solution ID: 1-18UZA)
--Value function iteration produces infinite or -inf results at one iteration
--incompletely designed and limited equations (very easy to do!)
--no theoretical closure required; hence any algorithm blows up

I discuss some of the theoretical and practical basis for valuation (including real options) using dynamic programming in my 2004 book Business Economics & Finance (CRC Press), which includes some Matlab code. You might want to look there, although it will not be enough to solve your programming issue. There also is a mention of the technique in the April 2009 issue of Business Economics in the article "value of private businesses in the US".

I will re-post if I discover a more robust method.

PLA

Patrick Anderson <panderson@andersoneconomicgroup.com> wrote:
> I am having similar problems with the R2009 versions implementing dynamic
programming algorithms for this type of problem, including with the
CompEcon Toolbox that used to run.
>

I am not sure why you would be attempting to solve a dynamic programming
problem using a toolbox. The difficulty with DP (aside from the curse of
dimensionality) is that you almost always need to program the solution from
scratch for each new problem. The beauty of DP is that the programming is
almost always a very simple recursion, and is done in jus a few lines of
code, especially with MATLAB.

If you are having difficulty implementing DP for your particular investment
timing problem, I suggest that you work on a simpler version first. In
particular, ignore discounting, and ignore any stochastic side to the
problem.

Also, if you can, work through an example or two by hand, just on paper.
See the method in action, see the intermediate calculations. Then try and
identify where your code doesn't match your paper solution.

The hardest part with DP is to formulate the problem, choosing correctly
what should be the stages, and what should be the state variables. Then,
identify the state transformation equations, and you are about finished.

--
Dr Tristram J. Scott
Energy Consultant