       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>

```If I've understood you properly...

solve[k_Integer?Positive] := Block[{u, x, cost, uvec},
x = -1;
cost = u = 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

{1, {u -> -1, u -> 0, u -> 0, u -> 1}}

solve

{1, {u -> -1, u -> 0, u -> 0, u -> 0, u -> 1}}

solve

{1, {u -> -1, u -> 0, u -> 0, u -> 0, u -> 0,
u -> 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 = -1;
cost = u = 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

702

cost

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;u=0;u=1. Whatever I try I just get one control u =1.
>
> I hope someone can help me out.
>
> Best,
> Slater
>
>

--

DrMajorBob at bigfoot.com

```

• Prev by Date: Re: FindInstance puzzler
• Next by Date: time series of count data...
• Previous by thread: Programming simple Bellman Equation and tracking the controls
• Next by thread: solving large sparse system in Mathematica