Re: Programming simple Bellman Equation and tracking the controls
- To: mathgroup at smc.vnet.net
- Subject: [mg83641] Re: [mg83631] Programming simple Bellman Equation and tracking the controls
- From: DrMajorBob <drmajorbob at bigfoot.com>
- Date: Tue, 27 Nov 2007 06:07:53 -0500 (EST)
- References: <6437533.1196077716493.JavaMail.root@m35>
- Reply-to: drmajorbob at bigfoot.com
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 at 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 at bigfoot.com