Dynamic Programming with 2 state variables

In summary, the Euler Equation of the dynamic programming problem is derived by maximizing the value function and using the first-order condition at the optimal z*. This results in three equations, which can be manipulated to obtain the Euler Equation. However, the exact steps to derive the equation may vary and may require further manipulation.
  • #1
physicsguy142
3
0

Homework Statement



Derive the Euler Equation of the dynamic programming problem:

[itex]\[max_{\{ z_t \}^\infty_{t=0}}
\sum_{t=0}^{\infty} \delta^t f(x_t, y_t, z_t)
\] [/itex]

subject to:

[itex] x_{t+1} = g_1(x_t, y_t, z_t),

\

y_{t+1} = g_2(x_t, y_t, z_t),

\
x_0 = x^0,
y_0 = y^0 [/itex]

and where [itex] \delta <1 [/itex]

Homework Equations



We can write the value function as:

[itex]V(x,y) = max_z [f(x, y, z) + \delta V(g_1(x, y, z), g_2(x, y, z))][/itex]

The Attempt at a Solution



The solution is characterized by 3 equations:

The first-order-condition at the optimal z* is:

[itex] \frac{\partial f(x, y, z^*)}{\partial z} + \delta[\frac{\partial V (g_1(x, y, z^*), g_2(x, y, z^*))}{\partial g_1(x, y, z^*)}\frac{\partial g_1(x, y, z^*)}{\partial z} + \frac{\partial V (g_1(x, y, z^*), g_2(x, y, z^*))}{\partial g_2(x, y, z^*)}\frac{\partial g_2(x, y, z^*)}{\partial z}] = 0[/itex]

Differentiating the value function with respect to each state gives us:

[itex]

\frac{\partial V (x, y)}{\partial x} = \frac{\partial f(x, y, z^*)}{\partial x} + \delta[\frac{\partial V (g_1(x, y, z^*), g_2(x, y, z^*))}{\partial g_1(x, y, z^*)}\frac{\partial g_1(x, y, z^*)}{\partial x} + \frac{\partial V (g_1(x, y, z^*), g_2(x, y, z^*))}{\partial g_2(x, y, z^*)}\frac{\partial g_2(x, y, z^*)}{\partial x}]

[/itex]

and

[itex]

\frac{\partial V (x, y)}{\partial y} = \frac{\partial f(x, y, z^*)}{\partial y} + \delta[\frac{\partial V (g_1(x, y, z^*), g_2(x, y, z^*))}{\partial g_1(x, y, z^*)}\frac{\partial g_1(x, y, z^*)}{\partial y} + \frac{\partial V (g_1(x, y, z^*), g_2(x, y, z^*))}{\partial g_2(x, y, z^*)}\frac{g_2(x, y, z^*)}{\partial y}]

[/itex]

I think I should be able to derive an Euler Equation with the above 3 equations, but I'm not sure how to manipulate the equations to get a meaningful answer.
 
Last edited:
Physics news on Phys.org
  • #2
bump. any help would be greatly appreciated!
 
  • #3
bumping this on the off-chance somebody will be able to help out.
 

1. What is Dynamic Programming with 2 state variables?

Dynamic Programming with 2 state variables is a method used to solve complex problems by breaking them down into smaller subproblems and finding optimal solutions for each subproblem. It involves using two variables to keep track of the current state of the problem and using the solutions of previous subproblems to find the optimal solution for the current state.

2. How is Dynamic Programming with 2 state variables different from other methods?

Dynamic Programming with 2 state variables differs from other methods, such as greedy algorithms or divide and conquer, in that it takes into account the solutions of previous subproblems and uses them to find the optimal solution for the current state. This allows for a more efficient and optimal solution to be found for complex problems.

3. What are some common applications of Dynamic Programming with 2 state variables?

Dynamic Programming with 2 state variables has many practical applications, such as in the fields of computer science, economics, and engineering. It can be used for tasks such as optimizing resource allocation, scheduling, and network routing.

4. What are the key components of Dynamic Programming with 2 state variables?

The key components of Dynamic Programming with 2 state variables include defining the two state variables, identifying the optimal substructure of the problem, and determining the recurrence relation that relates the solutions of the subproblems to the optimal solution of the current state.

5. What are some tips for implementing Dynamic Programming with 2 state variables?

When implementing Dynamic Programming with 2 state variables, it is important to carefully define the state variables and the subproblems. It is also helpful to use memoization, which stores the solutions of subproblems in a table for quicker access. Additionally, understanding the problem and its optimal substructure is crucial for finding an efficient solution.

Similar threads

Replies
4
Views
648
  • Calculus and Beyond Homework Help
Replies
8
Views
470
  • Calculus and Beyond Homework Help
Replies
2
Views
462
  • Calculus and Beyond Homework Help
Replies
6
Views
853
  • Calculus and Beyond Homework Help
Replies
18
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
544
  • Calculus and Beyond Homework Help
Replies
6
Views
760
  • Calculus and Beyond Homework Help
Replies
8
Views
1K
  • Calculus and Beyond Homework Help
Replies
7
Views
688
  • Calculus and Beyond Homework Help
Replies
1
Views
964
Back
Top