<p>Numerical Dynamic programming is <em>always</em> an approximation when any of the variables are continuous....</p>

<p>Depending on the structure of the problem, some people claim that you can apply linear programming techniques to approximate a solution. These guys <a href="http://www.mit.edu/~pucci/discountedLP.pdf" rel="nofollow">MIT paper</a>, claim that they have experiments that show that their linear reprogramming approximation is good enough.</p>

CC BY-SA 3.0
2016-05-18T03:18:52.730Z
2016-05-18T03:18:52.730Z
Fix.B.
<p>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. </p>

CC BY-SA 3.0
2016-11-15T04:01:40.063Z
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.
Kitsune Cavalry
CC BY-SA 3.0
2016-12-14T12:54:37.140Z
@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.
optimal control
CC BY-SA 3.0
2016-12-14T18:25:24.977Z
@optimalcontrol That's about the opposite impression I've gotten. How odd. Perhaps we are thinking of different types of problems then.
Kitsune Cavalry
CC BY-SA 3.0
2016-05-17T00:17:11.667Z
I guess the big question is how accurate do you need your answers to be?
Kitsune Cavalry
CC BY-SA 3.0
2016-05-17T13:42:10.260Z
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.
sincostancot
CC BY-SA 3.0
2016-05-19T23:12:40.847Z
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.
MathUser
<competitive-equilibrium><dynamic-programming>
Dynamic programming problem with dimension over 1000
sincostancot
# Dynamic programming problem with dimension over 1000

(Asked by: username_0 on 2016-05-17)

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.

**Tags:** competitive-equilibrium, dynamic-programming

> **Comments:**
> **username_1**: I guess the big question is how accurate do you need your answers to be?  
> **username_0**: 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.  
> **username_3**: 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.  
> **username_1**: 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.  
> **username_2**: @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.  
> **username_1**: @optimalcontrol That's about the opposite impression I've gotten. How odd. Perhaps we are thinking of different types of problems then.  

---

## 1 answers

### Answer by username_4 on 2016-05-18. Score: 1

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](http://www.mit.edu/~pucci/discountedLP.pdf), claim that they have experiments that show that their linear reprogramming approximation is good enough.


---

