Mathematica 9 is now available
Services & Resources / Wolfram Forums / MathGroup Archive
-----

MathGroup Archive 2007

[Date Index] [Thread Index] [Author Index]

Search the Archive

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


  • 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