Index: applications/dual/SIDP/text/ch3.tex
===================================================================
--- applications/dual/SIDP/text/ch3.tex (revision 891)
+++ applications/dual/SIDP/text/ch3.tex (revision 917)
@@ -1,18 +1,106 @@
 A�liv pou�it�ynamick� programov� p����ok v ��lohy du�� ��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 p��me 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�
+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{ilos}
-J_\pi=\E_{y_0,w_{0:N-1}}\left\{g_N(y_N)+\sum_{t=0}^{N-1}g_t(y_t,\mu_t(I_t),w_t)\right\},
+\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,\theta_t),v_t)\right\},
 \end{equation}
-za podm�k
+za apriorn�nformace $\theta_0$ a podm�k
 \begin{gather}
 \label{the2}
-\theta_{t+1}=h_t(\theta_t,I_t,y_{t+1},u_t),\\
-\label{poz3}
-y_0=h_0(\theta_0,v_0),\qquad y_{t+1}=h_t(\theta_t, I_t,u_t,v_{t+1}), \qquad t=0,\ldots,N-1,
+\theta_{t+1}=f_t(I_t,\theta_t,u_t,y_{t+1}),\\
+\label{poz4}
+y_0=h_0(\theta_0,v_0),\qquad y_{t+1}=h_t(I_t,\theta_t,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},P_t),\\
+\cov(v_{t+1},\theta)=0.
 \end{gather}
 
-\section{Certainty equivalecnce control}
+�ohu �e pomoc�ynamick� programov�, tedy postupnou minimalizac���n�tr� od konce �� horizontu
+\begin{gather}
+J_N(I_N,\theta_N)=\E_{\theta_N,v_N}\left\{g_N(y_N)\right\},\\
+\label{los3}
+J_t(I_t,\theta_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},\theta_{t+1}))|I_t,\theta_t,u_t\right\}, \\ \qquad t=0,\ldots,N-1,
+\end{gather}
+kde $\theta_{t+1}$ a $y_{t+1}$ se po��le \eqref{the2} a \eqref{poz4}.
+
+\section{Certainty equivalent control}
+P�u�it�etody Certainty equivalent control (CEC) [ref] se v rovnici pro o��nou ztr� nahrad��dn�eli�y sv��mi hodnotami. O��n�tr� tak p� v
+\begin{gather}
+J_N(I_N, \theta_N)=g_N(y_N),\\
+J_t(I_t, \theta_t)=\min_{u_t \in U_t}\left\{g_t(y_t,u_t,\hat{v}_t) +J_{t+1}(I_t,\theta_{t+1},u_t,\hat{y}_{t+1}))|I_t,\theta_t,u_t\right\}, \\ \qquad t=0,\ldots,N-1,
+\end{gather}
+
 \section{Metoda separace}
-\section{SIDP} 
+P�u�it�etody separace [ref] 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{SIDP}
+Metoda stochastick� iterativn� dynamick� programov� (SIDP) [ref] spo�� sou�n�pou�it�metody Monte Carlo k z�� aproximace pro o��nou ztr� a iterativn� dynamick� programov� k nalezen�ptim��trategie.
+
+\subsection{Metoda Monte Carlo}
+Metoda Monte Carlo je statistick�imula� metoda, kterou navrhl ... [ref]. 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,\theta_t)$ k dispozici p�s pro n�eduj� o��nou ztr� $J_{t+1}(I_{t+1},\theta_{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,\theta_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,\theta_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, \theta_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{poz4}. To znamen��e dan�$\theta_{k+1}$ se generuje a� ve chv�, kdy je zn� $I_k$, $u_k$, rozd�n�\theta_k$ a $y_{k+1}$ a tedy p�eqref{the2} i rozd�n�\theta_{k+1}$.
+
+Tento jednoduch�up lze vylep�it v��ov�ovn�m. Jedn�z mo�n�lep�en� je dvou�ov�ritmus poposan�f]. V tomto algoritmu se nejprve pro ka�d� kandid� vygeneruje $n_0$ realizac�Na z�ad�ealizac�e vyberou ti kandid�, 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 upraveny algoritmus metody Monte Carlo je robustn�� umo�� porovn� v�� mno�stv�andid�, nebo� po� realizac� prvn�� m������u��ouze k odfiltrov� zjevn�or�� kandid� na ��Pro � t� pr� nicm� posta�e z�adn�erze metody Monte Carlo a je proto v n�eduj� implementaci SIDP pou�ita. 
+
+\subsection{Iterativn�ynamick�rogramov�}
+Iterativn�ynamick�rogramov� [ref] 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,\theta_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,\theta_t)$ a po�at $\mu_t(I_t,\theta_t)$ jen v bodech diskretizace a jinde se uch� interpolaci (pop��xtrapolaci). V t� pr� vol� druhou zm�nou metodu. Poznamenejme, �e d� p�kladu gaussovsk� rozd�n�arametru ${\theta_t}$, diskretizace vyhledem k ${\theta_t}$ znamen�iskretizaci vzhledem k ${(\hat{\theta}_t,P_t)}$.
+
+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,\theta)_{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 [ref]. 
+
+\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}
