Changeset 1105

Show
Ignore:
Timestamp:
06/14/10 22:34:41 (14 years ago)
Author:
zimamiro
Message:
 
Location:
applications/dual/SIDP
Files:
113 added
2 modified

Legend:

Unmodified
Added
Removed

  • applications/dual/SIDP/text/ch3.tex

    r1090 r1105  
    3939Hledan��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) 
    4040 
     41\section{Iterativn�ynamick�rogramov�} 
     42 
     43Iterativn�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} 
     44\item prostor prom��_t$ se diskretizuje do m�, 
     45\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, 
     46\item optim��trategie bude ta, na kter�ude nabyto minim����n�tr� z po�e�ho stavu na konec �� horizontu. 
     47\end{enumerate} 
     48Tento 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". 
     49 
     50Oproti 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 �. 
     51 
     52\subsection{Diskretizace prostoru} 
     53P�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  
     54\begin{enumerate} 
     55\item p�kl�t n�k� optim��trategie a p�po� ur� pouze konstanty, kter��ou strategii ur�jednozna�, 
     56\item diskretizovat prostor $(H_t)$ a po�at $\mu_t(H_t)$ jen v bodech diskretizace a jinde se uch� interpolaci (pop��xtrapolaci).  
     57\end{enumerate} 
     58 
     59Jak�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 �� 
     60 
     61Zde 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�. 
     62 
     63KONVERGENCE 
    4164\section{Metoda Monte Carlo} 
    4265Metoda 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}.  
    4366 
    44 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 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(H_t)$ a o��n�tr� v �e $t$ se pak po��ako pr�p�n$ realizac��dn�li�y p�ter�e prov�na st� hodnota $(\theta_{t:N-1},v_{t:N})$, tedy 
     67\subsection{Pou�it�etody Monte Carlo k v� o��n�tr�} 
     68P��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. 
     69 
     70Nam�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 
    4571\begin{equation} 
    4672\label{mon} 
    47 \frac{1}{n}\sum_{i=1}^n\left(\sum_{j=t}^{N-1}g_j(y_{j+1}^i,\mu_j(H_j^i)\right), 
     73\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), 
    4874\end{equation} 
    4975kde $y_{j+1}^i$ se po��odle \eqref{poz4} jako 
    … …  
    5177y_{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, 
    5278\end{equation} 
    53 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$, posta�� statistika $T_k$ a $y_{k+1}$ a tedy p�eqref{the2} i hustota pravd�dobnosti $f(\theta_{k+1})$. 
     79a 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$.  
    5480 
    55 Tento jednoduch�up lze vylep�it v��ov�ovn�m kandid� na optim���n�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 �� 
    56  
    57 \section{Iterativn�ynamick�rogramov�} 
    58 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. 
    59  
    60 \subsection{Diskretizace prostoru} 
    61 P�ed� optim��trategie $\mu_t(H_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 $(H_t)$ a po�at $\mu_t(H_t)$ jen v bodech diskretizace a jinde se uch� interpolaci (pop��xtrapolaci).  
    62  
    63 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 $(H)_{0:N}$. V ka�d�asov�rovni pak diskretizujeme jen tu �t prostoru, kter�yla zasa�ena.  
    64  
    65 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}.  
     81V� 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. 
    6682 
    6783\section{SIDP} 
    68 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)}$. 
     84Metoda 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)}$. 
    6985 
    7086\subsection{Algoritmus SIDP} 
    71 V tomto od� je sch�ticky pops�algoritmus SIDP. Jeho parametry jsou 
     87V tomto od� je pops�algoritmus SIDP, tak jak byl navr�en v \cite{thompson2005stochastic}. Parametry algoritmu jsou 
    7288 
    7389\begin{itemize} 
    7490\item $n_{pass}, \, n_{iter}$� po� opakov� a iterac�lgoritmu 
    7591\item $N$ -- ��orizont 
    76 \item $n_g$ -- po� bod�iskretizaci ka�d�imenzi $H_t$, tj. $|H_t|=n_g^{\dim H_t}$ 
     92\item $n_g$ -- po� bod�iskretizaci ka�d�imenzi $H_t$, po� bod�iskretizaci je tedy $|H_t|=n_g^{\dim H_t}$ 
    7793\item $\pi^*=\mu_{0:N-1}(H_{0:N-1})$ -- apriorn��c�trategie 
    7894\item $m$ -- po� kadnid� na zm�  �� z�hu v jedn�teraci IDP 
    … …  
    107123\end{algorithmic} 
    108124\end{algorithm} 
     125 
     126\subsection{Detaily implementace} 
     127�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} 
     128 
     129\begin{figure} 
     130\centering 
     131\includegraphics[width=0.5\textwidth]{tra} 
     132\caption{Trajektorie v hyperstavu -- jednotliv�ealizace trajektorie je napo��na pomoc�ealizac�umu a nezn�ho parametru} 
     133\label{tra} 
     134\end{figure} 
     135 
     136 
     137V 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} .  
     138 
     139\begin{figure} 
     140\centering 
     141\includegraphics[width=0.25\textwidth]{box} 
     142\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$} 
     143\label{box} 
     144\end{figure} 
     145 
     146M�-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� 
     147Pro 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. 
     148 
     149Kandid� 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�  
     150 
     151Nam�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.