Mathematica - Programming simple Bellman Equation and tracking the controls

Author

Programming simple Bellman Equation and tracking the controls

martin_schleicher@yahoo.com

2007-11-26, 4:36 am

Hi everybody,

I am pretty new to Mathematica and I guess the problem I am
encountering is not difficult to solve. I am trying to solve a simple
dynamic programing problem for finite horizon - finite states
(t=0,1,2,3), where:

1) control / decision is u(t)
2) state x(t+1)=[x(t)+u(t)]^2 (the state next period depends on the
current state and the control chosen)
3) cost at each period: x(t)-u(t)
4) Objective: Minimize sum of costs across periods starting at period
t=0 and state x(0)=0.

The following function computes the total cost properly (I think!) in
recursive fashion.

J[t_, w_] := J[t, w] =
If[t >= 3, 0,
Extract[
Minimize[{(-u + w) + J[t + 1, (w + u)^2], -1 <= u <= 1 && u \
[Element] Integers}, u]
, 1]
];

J[0, 0] = -1

However, I don't know how to track the controls u[t] to use at each
period that solve the minimization. For this basic problem they should
be: u[0]=0;u[1]=0;u[2]=1. Whatever I try I just get one control u =1.

I hope someone can help me out.

Best,
Slater

DrMajorBob

2007-11-27, 8:20 am

If I've understood you properly...

solve[k_Integer?Positive] := Block[{u, x, cost, uvec},
x[0] = -1;
cost[0] = u[0] = 0;
x[t_] := x[t] = (x[t - 1] + u[t - 1])^2;
cost[t_] := cost[t] = cost[t - 1] + x[t] - u[t];
uvec = Array[u, k];
goal = Expand@cost[k];
Minimize[{goal, Thread[-1 <= uvec <= 1], uvec \[Element] Integers} //
Flatten, uvec]
]

solve[4]

{1, {u[1] -> -1, u[2] -> 0, u[3] -> 0, u[4] -> 1}}

solve[5]

{1, {u[1] -> -1, u[2] -> 0, u[3] -> 0, u[4] -> 0, u[5] -> 1}}

solve[6]

{1, {u[1] -> -1, u[2] -> 0, u[3] -> 0, u[4] -> 0, u[5] -> 0,
u[6] -> 1}}

That doesn't minimize cost at each stage, obviously -- it maximizes cost
at t==1, for instance -- but the greedy optimum (u[t_] = 1 for all t) is
horrible in the long run, as it pumps up the value of x geometrically:

Clear[u, x, cost]
x[0] = -1;
cost[0] = u[0] = 0;
x[t_] := x[t] = (x[t - 1] + u[t - 1])^2
cost[t_] := cost[t] = cost[t - 1] + x[t] - u[t]
u[t_] := 1

cost[4]

702

cost[5]

459030

"solve" is slow, but that's to be expected when cost[k] is a polynomial of
degree 2^(k-1) in k unknown integers.

Bobby

On Mon, 26 Nov 2007 02:48:21 -0600, <martin_schleicher@yahoo.com> wrote:

> Hi everybody,
>
> I am pretty new to Mathematica and I guess the problem I am
> encountering is not difficult to solve. I am trying to solve a simple
> dynamic programing problem for finite horizon - finite states
> (t=0,1,2,3), where:
>
> 1) control / decision is u(t)
> 2) state x(t+1)=[x(t)+u(t)]^2 (the state next period depends on the
> current state and the control chosen)
> 3) cost at each period: x(t)-u(t)
> 4) Objective: Minimize sum of costs across periods starting at period
> t=0 and state x(0)=0.
>
> The following function computes the total cost properly (I think!) in
> recursive fashion.
>
> J[t_, w_] := J[t, w] =
> If[t >= 3, 0,
> Extract[
> Minimize[{(-u + w) + J[t + 1, (w + u)^2], -1 <= u <= 1 && u \
> [Element] Integers}, u]
> , 1]
> ];
>
> J[0, 0] = -1
>
> However, I don't know how to track the controls u[t] to use at each
> period that solve the minimization. For this basic problem they should
> be: u[0]=0;u[1]=0;u[2]=1. Whatever I try I just get one control u =1.
>
> I hope someone can help me out.
>
> Best,
> Slater
>
>

--

DrMajorBob@bigfoot.com

Sponsored Links