I am working on a project which need to solve a dynamic programming problem with dimension over 1000. In past literature, there exist several methods like Smolyak algorithm and Sparse grid method that can solve dynamic programming problem with dimension no more than 100. My question is that does there exist such a brute force method that can solve problem with high dimension efficiently. Or I need to apply some approximation or reduce dimension.
6
-
1$\begingroup$ I guess the big question is how accurate do you need your answers to be? $\endgroup$– Kitsune Cavalry ♦May 17, 2016 at 0:17
-
$\begingroup$ Yes, I need to control the error in my model maybe using error of Euler equation. Imagine we apply 10 points to each dimension and it will be 10^1000 grid points. It's horrible. $\endgroup$– sincostancotMay 17, 2016 at 13:42
-
$\begingroup$ I think that rather than asking how to solve a thousand state + control problem (or whatever you mean by dimension over 1,000) you should ask yourself (or others) how to reduce the dimensionality of the problem. Some heterogeneous agent problems are solved this way. $\endgroup$– MathUserMay 19, 2016 at 23:12
-
$\begingroup$ My general thoughts are that in macroeconomics, people don't expect accuracy up to any decimal places, because you'll generally have model specification problems anyway, and there simply exist no really good ways of doing high dimension problems without lots of error. So you shouldn't be too worried about efficiency to be honest. But I also don't know much about dynamic programming, so take that with a grain of salt. $\endgroup$– Kitsune Cavalry ♦Nov 15, 2016 at 4:01
-
$\begingroup$ @KitsuneCavalry I don't agree at all. The accuracy in numerical simulations is a very important issue in macroeconomics. The criteria for the deviation from steady-state in a simulation (when you use a shooting algorith let's say) is conventionnaly something 0.00000001. $\endgroup$– optimal controlDec 14, 2016 at 12:54
|
Show 1 more comment
1 Answer
$\begingroup$
$\endgroup$
Numerical Dynamic programming is always an approximation when any of the variables are continuous....
Depending on the structure of the problem, some people claim that you can apply linear programming techniques to approximate a solution. These guys MIT paper, claim that they have experiments that show that their linear reprogramming approximation is good enough.
