2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I guess the big question is how accurate do you need your answers to be? $\endgroup$ – Kitsune Cavalry May 17 '16 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$ – sincostancot May 17 '16 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$ – MathUser May 19 '16 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 '16 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 control Dec 14 '16 at 12:54
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.