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

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{ilos3}
J_\pi=\E_{\theta_0,v_{0:N-1}}\left\{\sum_{t=0}^{N-1}g_t(y_{t+1},\mu_t(H_t))\right\},
\end{equation}
za apriorn�nformace $\theta_0$ a podm�k
\begin{gather}
\label{the2}
H_{t+1}=f_t(H_t,u_t,y_{t+1}),\\
\label{poz4}
y_0=h_0(\theta,v_0),\qquad y_{t+1}=h_t(I_t^{(d)},\theta,u_t,v_{t+1}), \qquad t=0,\ldots,N-1,
\end{gather}
kde $H_t=(I_t^{(d)},T_t)$ je hyperstav syst� a $T_t$ dostate� statistika pro nezn� parametr $\theta$ v �e $t$.

�ohu �e pomoc�ynamick� programov�, tedy postupnou minimalizac���n�tr� od konce �� horizontu
\begin{equation}
\label{los3}
J_t(H_t)=\min_{u_t \in U_t}\E_{y_{t+1}}\left\{g_t(y_{t+1},u_t)+J_{t+1}(H_{t+1})|H_t,u_t\right\}, \qquad t=0,\ldots,N-1,
\end{equation}
kde $T_{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) se v rovnici pro o��nou ztr� nahrad��dn�eli�a $y_{t+1}$ st� hodnotou $\hat{y}_{t+1}$. Ta se vypo�� \eqref{poz4} pomoc�n�ch rozd�n�a $v_t$ a posta�� statistiky $T_t$. O��n�tr� \eqref{los} tak p� v
\begin{gather}
\label{CE}
J_t(H_t)=\min_{u_t \in U_t}\left\{g_t(\hat{y}_t,u_t)+J_{t+1}(\hat{H}_{t+1})|H_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]. ODKAZ NA FILDEBAUMA, POPIS PRINCIPU... (napr JEDNOKROKOVA OPTIMALIZACE S BUZENIM - FILATOV)

\section{Iterativn�ynamick�rogramov�}

Iterativn�ynamick�rogramov� \cite{luus2000iterative} je jednou z variant klasick� p�pu k  nalezen�ptim��trategie, kter�inimalizuje o��nou ztr� \eqref{ilos2}. Standardn�umerick�tup k dynamick� progamov� lze shrnout n�edovn�\begin{enumerate}
\item prostor prom��_t$ se diskretizuje do m�,
\item postupn�e od konce horizontu napo�� minim����n�tr� $J_t(H_t)$ pro ka�d�diskretizace $H_t$. K v� se pou��j�i� napo�n�inim����n�tr� v n�eduj�ch �ech,
\item optim��trategie bude ta, na kter�ude nabyto minim����n�tr� z po�e�ho stavu na konec �� horizontu.
\end{enumerate}
Tento postup je p�arou aplikac�rincipu dynamick� programov�. Bohu�el je velmi citliv�imenzi stavov� prostoru $H_t$, kter�ot�diskretizovat, nebo� po� bod��ch k disretizaci roste exponenci�� dimenz�rostoru. Tato skute�st se v anglick�iteratu�na�e jako "curse of dimenzionality".

Oproti klasick� dynamick� programov� iterativn�ynamick�rogramov� probl��v s�i iterac�V ka�d�teraci se vych� ze strategie spo�n� p�oz�b� a prost�ctv�perturbac�ohoto (suboptim��) ��e hled�trategie, pro kterou bude o��n�tr� ni���Tato se pou�ije v n�eduj� iteraci. V�st iterativn� p�pu spo��e sn�n�itlivosti na dimenzi �.

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

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�iskretizace p� m�, bude v� nespolehliv�pak pro p� jemnou diskretizaci bude po� bod�iskretizaci hyperstavu rychle stoupat a �ov���st v� pak prakticky znemo�n�eho ��

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�erturbac�trategie spo�n� p�oz�kroku se ur��t prostoru, kter�e pro bezprost� v� podstatn�D� tomu sta�k dostate� jemn�iskretizaci podstatn�� bod�nkr��mplementace bude probr� d�.

KONVERGENCE
\section{Metoda Monte Carlo}
Metoda Monte Carlo \cite{hammersley1964monte} 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{los3}. 

\subsection{Pou�it�etody Monte Carlo k v� o��n�tr�}
P��n�pou�it�ynamick� programov� m� p�po� $J_t(H_t)$ k dispozici p�s pro n�eduj� o��nou ztr� $J_{t+1}(H_{t+1})$. Metoda monte Carlo by n�v�ak dala k dispozici pouze odhad o��n�tr�. Pou�it��to aproximac� dal��v� by chybu v�  navy�ovalo.

Nam�o $J_t(H_t)$ je proto vhodn�ro dal��� uchov�t $\mu_t(H_t)$. O��nou ztr� v �e $t$ pak lze po�at jako pr�$n$ realizac��dn�li� p�ter�e prov�na st� hodnota $(\theta_{t:N-1},v_{t:N})$, tedy
\begin{equation}
\label{mon}
\frac{1}{n}\sum_{i=1}^n\left(g_j(y_{j+1}^i,\mu_j(H_j)+\sum_{j=t+1}^{N-1}g_j(y_{j+1}^i,\mu_j(H_j^i)\right),
\end{equation}
kde $y_{j+1}^i$ se po��odle \eqref{poz4} jako
\begin{equation}
y_{j+1}^i=h_j( I_j^i,\theta_j^i,\mu(H_j^i),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 $\theta_{j+1}^i$ se generuje a� ve chv�, kdy je zn� $I_j^i$, $u_j^i$, posta�� statistika $T_j^i$ a $y_{j+1}^i$ a tedy p�eqref{the2} i posta�� statistika $T_{j+1}^i$. 

V� je p�hov�n�\mu_t(H_t)$ nam�o $J_t(H_t)$ �ov���j��Nam�o p�n�J_t(H_t)$ je toti� nutn��t hodnotu $\mu_t(H_t)$ a n�edn�ygenerovat trajektorii od �u $t$ do konce horizontu. To obn� vygenerovat generovat n�dnou realizace �umu $v_t$ a nezn�ho parametru $\theta$ (pomoc�T_t$), aplikovat ���h, tedy dle \eqref{poz4} vypo�at $y_{t+1}$ a n�edn�eqref{the2} dle vypo�at $T_{t+1}$. T�bude ur� bod v $H_{t+1}$. Zde pak pomoc�nterpolace (a extrapolace) ur�e optim���h, kter�kujeme. Podobn�ako prve tak ur�e n�eduj� bod v $H_{t+2}$, a� nakonec se dostaneme na konec �� horizontu. P�po� postupn�apo��me hodnotu ztr�v�unkce.

\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. P�u�it�terativn� dynamick� programov� se uch�k diskretizaci prostoru hyperstav�udeme pou��t interpolaci (pop��xtrapolaci) napo�n�dnot. Poznamenejme, �e d� p�kladu gaussovsk� rozd�n�dhadu nezn�ho parametru $\theta$, diskretizace vzhledem k ${T_t}$ znamen�iskretizaci vzhledem k ${(\hat{\theta}_t,P_t)}$.

\subsection{Algoritmus SIDP}
V tomto od� je pops�algoritmus SIDP, tak jak byl navr�en v \cite{thompson2005stochastic}. Parametry algoritmu 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$, po� bod�iskretizaci je tedy $|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^2mnn_g^{\dim H_N})$ (�ov���st metody Monte Carlo je ��zd�nosti od konce horizontu, proto je �ov�lo�itost ��ruh�ocnin�N$).

\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}

\subsection{Detaily implementace}
�st prosotoru, kter�e bude v n�eduj� iteraci algoritmu diskretizovat se ur�pomoc�ktu�� suboptim�� �� n�dn�alizac�umu $v_{0:N}$ a nezn�ho parametru $\theta_{0:N}$. Pomoc��to realizac�ygenerujeme trajektorie v $H_{0:N}$. V ka�d�asov�rovni pak diskretizujeme jen tu �t prostoru, kterou takto vygenerovan�rajektorie proch�. Sch�ticky je situace zn�rn� v \ref{tra}

\begin{figure}
\centering
\includegraphics[width=0.5\textwidth]{tra}
\caption{Trajektorie v hyperstavu -- jednotliv�ealizace trajektorie je napo��na pomoc�ealizac�umu a nezn�ho parametru}
\label{tra}
\end{figure}


V t� pr� se pro diskretizaci zasa�en��i prostoru vol�ednoduch�etoda, ve kter�e ve sm� sou�ch os spo� nejmen��yperkv� obahuj� vygenerovan�ody. Prostor se pot�iskretizuje pouze v t� oblasti. V pr� \cite{thompson2005stochastic}, kde je metoda SIDP navr�ena, je pro diskretizaci prostoru pou�it hyperkv� s obecnou orientac�Metodu k jeho ur���li auto� \cite{bh-eamvb-01}. Tento postup by m�v� k je�t�fektivn��iskretizaci prostoru. Nicm� metoda, kter�e v na��r� pou�ita se uk�la jako posta��. Nav�je implementa� podstatn�ednodu��� vyhled�n� tabulce s orientac�e sm� sou�ch je rychlej��V� je i to, �e m� snadno zaru� po�adavek na kladn�tyl $P_t$ nezn�ho parametru $\theta$, viz \ref{box} . 

\begin{figure}
\centering
\includegraphics[width=0.25\textwidth]{box}
\caption{Oblast ur�� diskretizaci $H_t$ -- a�liv je objem obecn�rientovan� hyperkv�u men��body v n�nespl� po�adavek na kladn�tyl $P$}
\label{box}
\end{figure}

M�-li diskretizovanou po�adovanou �t prostoru, je nutn�a ni namapovat dosavadn�apo�n�ptim���n�K tomu se pou�ije interpolace, pop��xtrapolace napo�n� ��V t� pr� je interpolace/extrapolace realizov� jednodu�e pomoc�ejbli��� ji� napo�n� bodu. Mo�n�ep�en�by byla nap�d line��rojekce �v�n��nejbli��� napo�n�d�
Pro ka�d�d�jprve pro ty na konci �� horizontu) se optim���c��h hled�omoc�erturbace st�j�ho suboptim�� ��Pro dan�se proto vygeneruje $m$ kandid� na optim���h, rovnom��olem optim�� z�hu z p��j� iterace. Jako jeden z kandid� na optim���n�e v�dy ponech�t�j� suboptim��e�en� minul�terace.

Kandid� na ��e nyn�orovnaj�omoc�etody Monte Carlo. Jak ji� bylo pops� v�ro ka�d� kandid� se vygeneruje $n$ realizac�tr�, p�ter�e dle \eqref{mon} spo� pr� 

Nam�o jednoduch� porovn� pomoc�r� lze kandid� na optim���c��h porovnat n�k�istikovan��v��ov�oritmem. Jedno z mo�n�lep�en�e pou�ito i v \cite{thompson2005stochastic}. Konkr��e jedn� dvou�ov�ritmus poposan�ite{nelson2001simple}. V prvn�rovni tohoto algoritmu se nejprve pro ka�d� kandid� $u_t$ 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��Nav�umo�� efektivn�orovn� v�� mno�stv�andid�, nebo� po� realizac� prvn�� m������u��ouze k odfiltrov� zjevn�or�� kandid� na ��Pro � t� pr� posta�e z�adn�erze metody Monte Carlo a proto je v n�eduj� implementaci SIDP pou�ita.