root/applications/dual/SIDP/text/ch3.tex @ 919

A�liv pou�it�ynamick� programov� p����ok v ��lohy stochastick� ��analytick�e�en�bvykle nen�o�n��at. V ka�d��ov�kroku se toti� pot�se dv� obecn�bt��obl�my: 1) v� st� hodnoty a 2) minimalizace vzhledem k $u_t$. Oba probl� obecn�emaj�nalytick�e�en� bez dal��pecifikace � je proto t�p� k aproxima�m metod�

V t� kapitole se p�� popis n�lika mo�n��up�proximativn� ��lohy du�� ��P�e� �e �u du�� ��je nalezen��c�trategie $\pi=\mu_{0:N-1}$, kter�y minimalizovala o��nou ztr�
\begin{equation}
\label{ilos2}
J_\pi=\E_{\theta_0,v_{0:N-1}}\left\{g_N(y_N)+\sum_{t=0}^{N-1}g_t(y_t,\mu_t(I_t,T_t),v_t)\right\},
\end{equation}
za apriorn�nformace $\theta_0$ a podm�k
\begin{gather}
\label{the2}
T_{t+1}=f_t(I_t,T_t,u_t,y_{t+1}),\\
\label{poz3}
y_0=h_0(\theta_0,v_0),\qquad y_{t+1}=h_t(I_t,\theta,u_t,v_{t+1}), \qquad t=0,\ldots,N-1.\\
v_{t+1}\sim N(0,Q_{t+1})\\
\theta_t\sim N(\hat{\theta}_t,P_t),\\
\cov(v_{t+1},\theta_t)=0,
\end{gather}
kde $T_t$ je dostate� statistika pro parametr $\theta$ v �e $t$.

�ohu �e pomoc�ynamick� programov�, tedy postupnou minimalizac���n�tr� od konce �� horizontu
\begin{gather}
J_N(I_N,T_N)=\E_{\theta_N,v_N}\left\{g_N(y_N)\right\},\\
\label{los3}
J_t(I_t,T_t)=\min_{u_t \in U_t}\E_{y_{t+1},v_t}\left\{g_t(y_t,u_t,v_t)+J_{t+1}((I_t, ,u_t,y_{t+1},T_{t+1}))|I_t,T_t,u_t\right\}, \\ \qquad t=0,\ldots,N-1,
\end{gather}
kde $T_{t+1}$ a $y_{t+1}$ se po��le \eqref{the2} a \eqref{poz3}.

\section{Certainty equivalent control}
P�u�it�etody Certainty equivalent control (CEC) se v rovnici pro o��nou ztr� nahrad��dn�eli�y sv��mi hodnotami. O��n�tr� tak p� v
\begin{gather}
\label{CE}
J_N(I_N, T_N)=g_N(y_N),\\
J_t(I_t, T_t)=\min_{u_t \in U_t}\left\{g_t(y_t,u_t,\hat{v}_t) +J_{t+1}(I_t,T_{t+1},u_t,\hat{y}_{t+1}))|I_t,T_t,u_t\right\}, \\ \qquad t=0,\ldots,N-1,
\end{gather}

Podrobn��ojedn� s diskuz�spekt��it�EC lze nal� v \cite{bertsekas1995dynamic}.

\section{Metoda separace}
P�u�it�etody separace je proces ��ozd�n do dvou f�: 1) indentifikace nezn�ho parametru a 2) ��a pou�it�dhadu $\hat{\theta}$ z prvn��.

Prvn�� slou�� nez�sl� sb� dat, kter�sou n�edn�ou�ita k odhadu nezn�ho parametru. K odhadu m� pou��nap�d rovnici \eqref{the2}. V druh�� pak po zbytek �� horizontu pou�ijeme  pro n�h ��trategie odhad $\hat{\theta}$ z prvn��.

%\section{Du���n�
%Hledan��n�y m� nejen minimalizovat aktu��tr�, ale rovn�z�at o syst� co nejv� informac�ro minimalizaci budouc� ztr� Tento postup se naz����n�ref].

\section{Metoda Monte Carlo}
Metoda Monte Carlo [ref] je statistick�imula� metoda. Jej�rincip spo��e vzorkov� n�k��dn�eli�y za �m odhadu jej�ledan�harakteristiky, nap�� hodnoty. V t� pr� je metoda Monte Carlo pou�ita k v� o��n�tr� \eqref{ilos2}. 

P��n�pou�it�ynamick� programov� m� p�po� $J_t(I_t,T_t)$ k dispozici p�s pro n�eduj� o��nou ztr� $J_{t+1}(I_{t+1},T_{t+1})$. Metoda monte Carlo n�v�ak d� dispozici pouze odhad o��n�tr� a pou�it��to aproximac� dal��v� by chybu v�  navy�ovalo. Nam�o toho se pro dal��� uchov�j�\mu_t(I_t,T_t)$ a o��n�tr� v �e $t$ se pak po��ako pr�p�n$ realizac��dn�eli�y $(\theta_{t:N-1},v_{t:N})$, tedy
\begin{equation}
\label{mon}
\frac{1}{n}\sum_{i=1}^n\left(g_N(y_N^i)+\sum_{j=t}^{N-1}g_j(y_j^i,\mu_j(I_j^i,T_j),v_j^i)\right),
\end{equation}
kde $y_{j+1}^i$ se po��odle \eqref{poz3} jako
\begin{equation}
y_{j+1}^i=h_j( I_j^i,\theta_j^i,\mu(I_j^i, T_j),v_{j+1}^i), \qquad j=t,\ldots,N-1, \qquad i=1\ldots,n,
\end{equation}
a index $i$ ozna�e $i$-tou realizaci dan�eli�y. Realizace $\theta_{t:N-1}$ se generuj�od�trajektorie \eqref{poz3}. To znamen��e dan�$\theta_{k+1}$ se generuje a� ve chv�, kdy je zn� $I_k$, $u_k$, posta�� statistika $T_k$ a $y_{k+1}$ a tedy p�eqref{the2} i hustota pravd�dobnosti $f(\theta_{k+1})$.

Tento jednoduch�up lze vylep�it v��ov�ovn�m kandid� na ��Jedn�z mo�n�lep�en� je dvou�ov�ritmus poposan�ite{nelson2001simple}. V prvn�� tohoto algoritmu se nejprve pro ka�d� kandid� vygeneruje $n_0$ realizac�Na jejich z�ad�e vyberou ti, na kter�abyto minima s pravd�dobnost���e� je dan�ez $\alpha_0$. Pro tyto se v druh�� vygeneruje dostate� po� realizac�ak, aby bylo mo�n�ejlep��ozhodnut�volit s pravd�dobnost�lespo�vn�adan�ezi $\alpha_1$. Takto upraven�ritmus metody Monte Carlo je robustn�� umo�� porovn� v�� mno�stv�andid�, nebo� po� realizac� prvn�� m������u��ouze k odfiltrov� zjevn�or�� kandid� na ��

\section{Iterativn�ynamick�rogramov�}
Iterativn�ynamick�rogramov� \cite{luus2000iterative} je jedn� p�p�alezen�ptim��trategie, kter�inimalizuje o��nou ztr� \eqref{ilos2}. Oproti dynamick� programov� se probl��iterativn�Na za�ku se zvol��k�priorn�trategie. V ka�d�teraci se potom vych� ze strategie spo�n� p�oz�kroku a prost�ctv�perturbac�ohoto (suboptim��) ��e hled�trategie, pro kterou bude o�van�tr� ni���Tato se pou�ije v n�eduj� iteraci.

\subsection{Diskretizace prostoru}
P�ed� optim��trategie $\mu_t(I_t,T_t)$ bychom pro p� vy�len���n�tr� \eqref{mon} na � �� horizontu $t:N$ pot�ali jej�nalytick�yj�en�To ale nen�bvykle mo�n�Je proto nutn�� k n�k�proximaci, nap�d 1) p�kl�t n�k� optim��trategie a p�po� ur� pouze konstanty, kter��ou strategii ur�jednozna�, nebo 2) diskretizovat prostor $(I_t,T_t)$ a po�at $\mu_t(I_t,T_t)$ jen v bodech diskretizace a jinde se uch� interpolaci (pop��xtrapolaci). 

Jak�sobem efektivn�iskretizovat prostor nez�sl�om��o aproximativn�� o��n�tr� \eqref{mon} je p�u�it�ynamick� programov� obt��t�a. Bude-li bod�iskretizaci p� m�, bude v� nespolehliv�pak pro p� jemnou diskretizaci bude �ov���st v� rychle stoupat (o �ov���sti SIDP viz d�). Zde se ukazuje v�st pou�it�terativn� dynamick� programov�, nebo� sta�diskretizovat jen tu �t prostoru kter�ude pot� v n�eduj� iteraci. Pomoc�trategie spo�n� p�oz�kroku a n�dn�alizac�umu $v_{0:N}$ a nezn�ho parametru $\theta_{0:N}$ vygenerujeme trajektorie v $(I,T)_{0:N}$. V ka�d�asov�rovni pak diskretizujeme jen tu �t prostoru, kter�yla zasa�ena. 

V t� pr� je volena jednoduch�etoda v kter�e spo� nejmen��yperkv� kolem zasa�en�ak, �e se vezme nejmen��yperkv� orientovan�m� sou�ch os, do kter� se vygenerovan�ody vejdou. Prostor se pot�iskretizuje pouze v t� oblasti. Metodu k ur��yperkv�u s obecnou orientac�ze naj�v \cite{bh-eamvb-01}. 

\section{SIDP}
Metoda stochastick� iterativn� dynamick� programov� (SIDP) \cite{thompson2005stochastic} spo�� sou�n�pou�it�metody Monte Carlo k z�� aproximace pro o��nou ztr�  a iterativn� dynamick� programov� k nalezen�ptim��trategie. Pro � t� posta�e z�adn�erze metody Monte Carlo a je proto v n�eduj� implementaci SIDP pou�ita. P�u�it�terativn� dynamick� programov� se uch�k diskretizovat prostoru hyperstav�udeme pou��t interpolaci (pop��xtrapolaci) napo�n�dnot. Poznamenejme, �e d� p�kladu gaussovsk� rozd�n�arametru ${\theta_t}$, diskretizace vzhledem k ${T_t}$ znamen�iskretizaci vzhledem k ${(\hat{\theta}_t,P_t)}$.

\subsection{Algoritmus SIDP}
V tomto od� je pops�algoritmus SIDP. Jeho parametry jsou

\begin{itemize}
\item $n_{pass}, \, n_{iter}$� po� opakov� a iterac�lgoritmu
\item $N$ -- ��orizont
\item $n_g$ -- po� bod�iskretizaci ka�d�imenzi $H_t$, tj. $|H_t|=n_g^{\dim H_t}$
\item $\pi^*=\mu_{0:N-1}(H_{0:N-1})$ -- apriorn��c�trategie
\item $m$ -- po� kadnid� na zm�  �� z�hu v jedn�teraci IDP
\item $\beta^{in}$ -- po�e� rozsah pro hled� optim�� �� z�hu
\item $\gamma,\, \lambda$ -- parametry pro redukci $\beta^{in}$
\item $n$ -- po� realizac�ro odhad metodou Monte Carlo
\end{itemize}

Jak plyne z n�eduj�ho popisu, �ov�lo�itost SIDP vzhledem k jeho parametr� $O(n_{pass}n_{iter}N^2mn_g^{\dim H_N})$ (�ov���st metody Monte Carlo je ��zd�nosti od konce horizontu).

\begin{algorithm}
\begin{algorithmic}
\FOR{$i = 1$ to $n_{pass}$} 
\FOR{$j = 1$ to $n_{iter}$} 
\STATE $\beta_{i,j} := \gamma^{j-1}\lambda^{i-1}\beta^{in}$
\FOR{$k = 1 $ to $|H_t|$}  
\STATE spo� trajektorii $H_{0,k}$, pou�ij aktu��\pi^*$, jej�nterpolace a extrapolace a realizace nezn�ho parametru $\theta_0,\ldots,\theta_{N-1}$ pod�t� trajektorie
\ENDFOR
\FOR{$t = N-1 $ to $0$} 
\STATE vytvo�ilde{H}_t$ jako�to rovnom�ou s�v oblasti bod�t$
\STATE interpoluj (extrapoluj) $\mu_t^*(H_t)$ na $\mu_t^*(\tilde{H}_t)$
\FOR{$k = 1 $ to $|H_t|$}  
\FOR{$m=-\left[\frac{m-1}{2}\right]$ to $\left[\frac{m}{2}\right]$}
\STATE pro $\tilde{H}_{t,k}$ vygeneruj kandid� na ��\mu_t(\tilde{H}_{t,k}) =  \mu_t^*(\tilde{H}_{t,k})+m\beta_{i,j}$ 
\STATE pomoc�etody Monte Carlo spo� o��nou ztr�
\ENDFOR
\STATE rozhodnut� nejni���o��nou ztr�u uchovej jako nov�ptim��ozhodnut�ro $\tilde{H}_{t,k}$.
\ENDFOR
\ENDFOR
\ENDFOR
\ENDFOR
\end{algorithmic}
\end{algorithm}