Grunnstrukturen

Et dynamisk programmeringsproblem har:

Tilstandsvariabel $x_t$: oppsummerer relevant informasjon i periode $t$
Kontrollvariabel $c_t$ eller $a_t$: beslutningstakerens valg
Tilstandsovergang: $x_{t+1} = f(x_t, c_t)$
Belønning per periode: $R(x_t, c_t)$
Mål: maksimer (eller minimer) $\sum_{t=t_0}^T \beta^{t-t_0}R(x_t, c_t)$

Bellman-likningen

Bellman-likningen uttrykker optimalitetsprinsippet rekursivt:

$$V_t(x_t) = \max_{c_t}\left\{R(x_t,c_t) + \beta V_{t+1}(f(x_t,c_t))\right\}$$

der $\beta = 1/(1+d)$ er diskonteringsfaktoren og terminalbetingelsen $V_T(x_T)$ er gitt i oppgaven. Løsningsmetode: baklengs induksjon — start fra $T$, beregn $V_{T-1}$, $V_{T-2}$, osv.

H2024, Problem 4: minimeringsvariant

Minimer $v_{t_0}(x_{t_0}) = \sum_{t=t_0}^{T-1}(1/2)^{t-t_0}c_t^2 + H(1/2)^{T-t_0}x_T^2$ med $x_{t+1}=x_t-c_t$ og $H>0$. Bellman-likning: $v_t(x_t) = \min_{c_t}\{c_t^2 + \frac{1}{2}v_{t+1}(x_t-c_t)\}$. Terminalt: $v_T(x_T)=Hx_T^2$. Beregn $v_{T-1}$ ved FOB: $2c_{T-1}=\frac{1}{2}v_{T+1}'=H(x_{T-1}-c_{T-1})$, gir $c_{T-1}=\frac{H}{2+H}x_{T-1}$.

H2025, Problem 2: stoppeproblem

Bellman-likning: $V_t(x_t)=\max\{x_t,\frac{1}{1+d}V_{t+1}(x_t(1+r))\}$. Induktivt bevis at $V_t(x_t)=x_t$ for alle $t$ når \(r

Eksempel (baklengs induksjon med $T=2026, t_0=2024$)

$v_t(x) = \min\{c^2 + \frac{1}{2}v_{t+1}(x-c)\}$, $v_{2026}(x) = Hx^2$.

Periode 2025: FOB: $2c = \frac{H}{1}(x-c)\Rightarrow c_{2025}^*=\frac{H}{2+H}x$

$v_{2025}(x) = \left(\frac{H}{2+H}\right)^2 x^2 + \frac{H}{2}\left(\frac{2}{2+H}\right)^2 x^2 = \alpha_{2025}x^2$

Periode 2024: antag $v_{2025}(x)=\alpha_{2025}x^2$, FOB: $2c=\alpha_{2025}(x-c)\Rightarrow c_{2024}^*=\frac{\alpha_{2025}}{2+\alpha_{2025}}x$

Studieguide: Dynamic Programming and Bellman Equations

Studieguide: Dynamic Programming and Bellman Equations