Changeset 1103
- Timestamp:
- 06/13/10 23:56:07 (15 years ago)
- Location:
- applications/dual/SIDP/text
- Files:
-
- 4 modified
Legend:
- Unmodified
- Added
- Removed
-
applications/dual/SIDP/text/ch1.tex
r1090 r1103 1 DEFINICNI OBORY 2 \section{Formulace � stochastick� �� 3 �t�m pojmem v teorii ��e \emph{syst�. Syst�je �t sv�, kterou chceme poznat ��. Budeme-li p�kl�t diskr��ovahu �u, stav syst� v �ov�okam�iku $t$ pod��� horizontu d�y $N$ popisuje syst�rovnic 1 \section{Formulace z�adn�lohy stochastick� �� 2 3 \subsection{Syst�a jeho popis} 4 �t�m pojmem v teorii ��e syst� Syst�je �t sv�, kterou chceme poznat ��. Ovliv�n�yst�, a� u� za �m jeho lep�� pozn�, �za �m ��prov�me pomoc�stup�d�ch z�h� 5 Ve v�in�����lohy stochastick� ��rov�no numericky, je proto ��racovat s diskr���em. Budeme-li proto uva�ovat diskr��ovahu �u, stav syst� v �ov�okam�iku $t$ pod�kone�ho horizontu d�y $N$ popisuje soustava rovnic 4 6 \begin{equation} 5 7 \label{sys} 6 8 x_{t+1}=f_k(x_t,u_t,w_t), \qquad t=0,1,\ldots,N-1, 7 9 \end{equation} 8 kde $x_t$ je stav syst� v �e $t$, $u_t$ je vstup v �e $t$ a $w_t$ n�dn�eli�a reprezentuj� p�nost �umu. V t� kapitole budeme p�kl�t, �e m� stav syst�pozorovat. P�em ne�ho pozorov� se zab�sleduj� kapitola.10 kde $x_t$ je stav syst� v �e $t$, $u_t$ je ���h v �e $t$ a $w_t$ n�dn�eli�a reprezentuj� p�nost �umu. Zde p�kl�me, �e tvar rovnic $f_t$ je n�zn� nap�d z fyzik�� rozboru �, �ze znalosti konstrukce stroje, kter�sujeme. D� p�kl�me, �e stav syst� m� p�pozorovat. P�em ne�ho pozorov� se zab�sleduj� kapitola. 9 11 10 V � ��� v�dy p�sanou ztr�vou (resp. �vou) funkci 12 \subsection{Ztr�v�unkce a optim���n� 13 C�m je pro zadan��\eqref{sys} navrhnout ��kter�ude syst�udr�ovat co nejbl� po�adovaneho stavu. Pro tyto � m� v � �� dispozici p�sanou ztr�vou (resp. �vou) funkci 11 14 \begin{equation} 12 g(x_{1:N},u_{0:N-1}) .15 g(x_{1:N},u_{0:N-1}), 13 16 \end{equation} 17 kter�r�e nakolik jsme vyty��l��i. 14 18 15 Ozna� $U(x_t)$ mno�inu p�tn�d�ch z�h� syst�ve stavu $x_t$. P�tnou ��trategi�\pi=\mu_{0:N-1}$ budeme rozum�posloupnost zobrazen�\begin{equation}19 Ozna� $U(x_t)$ nepr�nou mno�inu p�tn�d�ch z�h� syst�nachazej� se ve stavu $x_t$. P�tnou ��trategi�\pi=\mu_{0:N-1}$ budeme rozum�posloupnost zobrazen�\begin{equation} 16 20 \label{con} 17 21 \mu_t(x_t)=u_t \, \qquad t=0,1,\ldots,N-1, 18 22 \end{equation} 19 kde $ u_t \in U(x_t)$ je p�tn�c��h.23 kde $\mu_t(x_t)=u_t \in U(x_t)$ je p�tn�c��h. Nepr�n�no�ina $\Pi$ pak bude zna� mno�inu v�ech p�tn�d�ch strategi� 20 24 21 25 Pro danou ��trategii ozna� o��nou ztr� jako … … 26 30 27 31 �ohou je potom naj�takovou $\pi^*$, pro kterou plat�\begin{equation} 28 J_{\pi^*}(x_0)=\min_{\pi \in \Pi}J_\pi(x_0) ,32 J_{\pi^*}(x_0)=\min_{\pi \in \Pi}J_\pi(x_0). 29 33 \end{equation} 30 kde $\Pi$ zna�mno�inu v�ech p�tn�d�ch strategi�31 34 32 35 Celkov�e tedy jedn� optimaliza� � nal� takovou posloupnost funkc�eqref{con}, kter�inimalizuje o��nou ztr�vu \eqref{los} za podm�k \eqref{sys}. 33 36 34 \section{Pou�it�ynamick� programov� p��en�lohy stochastick� �� aditivn�tr�u} 35 �ohu stochastick� ��ak, jak byla definov� v p�oz��i, nelze obecn�e�it. Je tedy pot�� n�k bl� specifikovat. V tomto sm� je mo�n�mezit se na n�k�i��var ztr�v�unkce \eqref{los}. Jako vhodn�e ukazuje uva�ovat tzv. aditivn�var ztr�v�unkce, tedy �e existuj�unkce $g_t$ takov��e m� ps� 37 \section{�oha stochastick� �� aditivn�tr�u} 38 �ohu stochastick� ��ak, jak byla definov� v p�oz��i, nelze obecn�e�it. Je tedy pot�� n�k bl� specifikovat. 39 \subsection{Aditivn�tr�v�unkce} 40 Jako vhodn�e ukazuje omezit se na n�k�i��var ztr�v�unkce \eqref{los}. Budeme proto d� uva�ovat tzv. aditivn�var ztr�v�unkce, tedy �e existuj�unkce $g_t$ takov��e m� ps� 36 41 \begin{equation} 37 42 \label{adi} … … 41 46 O��nou ztr� \eqref{los} potom m� p�t do tvaru 42 47 \begin{equation} 48 \label{ex} 43 49 J_\pi(x_0)=\E_{w_{0:N-1}}\left\{\sum_{t=0}^{N-1}g_t(x_{t+1},\mu_t(x_t))\right\}. 44 50 \end{equation} 45 51 46 Takto specifikovan�loha se d�e�it pou�it�dynamick� programov� \cite{bellman1957dynamic}. Dynamick�rogramov� je p�p k ��ptimaliza�ch � na kter�e m� d�t jako na posloupnost rozhodnut�pro kter�lat�zv. princip optimality. Ten � �e optim��osloupnost rozhodnut��u vlastnost, �e pro libovoln�te� stav a rozhudnut�us��chna n�eduj� rozhodnut�ptim��zhledem k v��zhodnut�rvn�. D� �e pro ztr� tvaru \eqref{adi} plat�rincip optimality je snadn�e ho nal� nap�d v \cite{bertsekas1995dynamic}. 52 \subsection{Dynamick�rogramov�} 53 Takto specifikovan�loha stochastick� ��e d�e�it pou�it�dynamick� programov� \cite{bellman1957dynamic}. Dynamick�rogramov� je p�p k ��ptimaliza�ch � na kter�e m� d�t jako na posloupnost rozhodnut�pro kter�lat�zv. princip optimality. Ten � �e optim��osloupnost rozhodnut��u vlastnost, �e pro libovoln�te� stav a rozhudnut�us��chna n�eduj� rozhodnut�ptim��zhledem k v��zhodnut�rvn�. 47 54 48 P��en�lohy stochastick� �� aditivn�tr�u je tedy mo�n�ostupovat, jak je u ���moc�ynamick� programov� zvykem. Minim��odnotu st� ztr� od okam�iku $t$ do $N$ v z�slosti na $x_t$ ozna�e $J_t(x_t)$. M� pro ni ps� 55 Platnost principu optimality pro o��nou ztr� tvaru \eqref{ex} je intuitivn�nadno pochopiteln�Pokud by toti� n�k� ��trategie nebyl optim��pak o��nou ztr� sn�me p�dem ke strategii, ve kter�nu neoptim��� nahrad� optim����podprobl� na dan��. P� d�platnosti principu optimality pro o��nou ztr� tvaru \eqref{ex} lze nal� nap�d v \cite{bertsekas1995dynamic}. 56 57 \subsection{Pou�it�ynamick� programov� p��en�lohy stochastick� �� aditivn�tr�u} 58 P��en�lohy stochastick� �� aditivn�tr�u je mo�n�ostupovat, jak je u ���moc�ynamick� programov� zvykem. Ze t�o �m ozna� $J_t(x_t)$ minim��odnotu st� ztr� od okam�iku $t$ do $N$ v z�slosti na $x_t$. Dle \eqref{ex} pro ni m� ps� 49 59 \begin{gather} 50 60 J_N(x_N)=0\\ … … 52 62 \end{gather} 53 63 54 P� �en�udeme postupovat od konce �� horizontu a postupn�ledat $J_t(x_t)$. Pro v� $x_{t+1}$ se pou�ije rovnice \eqref{sys}.55 Libovoln ou ��trategii$\pi=\{\mu_0,\ldots,\mu_{N-1}\}$, kter�pl� syst�rovnic64 P�nstrukci optim���c�trategie budeme postupovat od konce �� horizontu a postupn�ledat $J_t(x_t)$. Pro v� $x_{t+1}$ se pou�ije rovnice \eqref{sys}. 65 Libovoln��c�trategie $\pi=\{\mu_0,\ldots,\mu_{N-1}\}$, kter�pl� syst�rovnic 56 66 \begin{equation} 57 67 \label{impl} 58 68 J_t(x_t)=\E_{w_t}\left\{g_k(x_t,\mu_t(x_t),w_t)+J_{t+1}(f_t(x_t,\mu_t(x_t),w_t))\right\} \qquad t=0,\ldots,N-1 59 69 \end{equation} 60 pak nazveme optim��osloupnost�ozhodnut�70 pak bude optim��osloupnost�ozhodnut� -
applications/dual/SIDP/text/ch2.tex
r1090 r1103 1 1 P�likaci matematick� modelov� na ���k�onkr��lohy se obvykle pot�s probl�m, jak ur� konstanty, kter�an�l ur��Zkoum�-li nap�d n�k�k��yst� z rozboru fyzik�� z�nitost�bvykle zn� tvar rovnic, kter�r��eho v� �e, nicm� po�e� podm�y �parametry, kter� rovnic� vystupuj� jsou pro dan��charakteristick�m� z�at pouze nep� obvykle m�n�vhodn�li�. Tato kapitola se zab�difikac�lohy stochastick� ��ro p� p�nosti nezn�ch parametr� 2 2 \section{Formulace � stochastick� �� nep�mi daty} 3 \subsection{V�syst� a infoma� vektor} 3 4 Informace o stavu syst� $x_t$ v �e $t$ z��me pomoc�� $y_t$, kter��jako 4 5 \begin{equation} … … 8 9 kde $v_t$ je n�dn�eli�a charakterizuj� chybu m�n�Po�e� stav $x_0$ je d�rozd�n�pravd�dobnosti $P^{x_0}$ a dal���yst� ur�e soustava \eqref{sys}. 9 10 10 Informace, kter�sou v pr� �� dispozici je zvykem ps�ve form�zv. \emph{informa�ho vektoru}, kter�var11 Informace, kter�sou v pr� �� dispozici je zvykem ps�ve form�zv. informa�ho vektoru, kter�var 11 12 \begin{equation} 12 13 I_0=y_0,\qquad I_{t+1}=(y_{0:t+1},u_{0:t}), \qquad t=1,\ldots,N-1. 13 14 \end{equation} 14 15 15 �d� z�h nyn�em�xplicitn��set na stavu syst�, proto�e m� k dispozici pouze informa� vektor. Podobn�ako v p�l�apitole proto zav�me mno�inu $U(I_t)$ v�ech p�tn�d�ch z�h�informace $I_t$ a p�tnou ��trategi�ude $\pi=\mu_{0:N-1}$ 16 \subsection{Optim���n�ro � s nep�mi daty} 17 �d� z�h nyn�em�xplicitn��set na stavu syst�, proto�e m� k dispozici pouze informa� vektor. Podobn�ako v p�l�apitole proto zav�me nepr�nou mno�inu $U(I_t)$ v�ech p�tn�d�ch z�h�informace $I_t$. P�tnou ��trategi�\pi=\mu_{0:N-1}$ bude posloupnost 16 18 \begin{equation} 17 19 \label{icon} 18 20 \mu_t(I_t)=u_t \, \qquad t=0,1,\ldots,N-1, 19 21 \end{equation} 20 kde $ u_t \in U(I_t)$ je p�tn�c��h.22 kde $\mu_t(I_t)=u_t \in U(I_t)$ je p�tn�c��h. 21 23 22 24 �olem je naj�p�tnou strategii, kter�y minimalizovala o��nou ztr� 23 25 \begin{equation} 24 26 \label{ilos} 25 J_\pi=\E_{\substack{x_0,\ w_{0:N-1},\\ v_{0:N -1}}}\left\{\sum_{t=0}^{N-1}g_t(x_{t+1},\mu_t(x_t))\right\},27 J_\pi=\E_{\substack{x_0,\ w_{0:N-1},\\ v_{0:N}}}\left\{\sum_{t=0}^{N-1}g_t(x_{t+1},\mu_t(x_t))\right\}, 26 28 \end{equation} 27 29 za podm�k \eqref{sys} a \eqref{poz}. 28 30 29 \s ection{P� na � s �mi daty}31 \subsection{P� na � s �mi daty} 30 32 Proto�e v �e $t$ nem� k dispozici p�stav syst� $x_t$, ale pouze informa� vektor $I_t$, nem� pou��postup z p�oz�apitoly. P��je pot�� vhodn�ransformovat. Za t�o �m zap�me informa� vektor ve tvaru 31 33 \begin{equation} … … 33 35 I_0=y_0,\qquad I_{t+1}=(I_t,u_t,y_{t+1}), \qquad t=1,\ldots,N-1. 34 36 \end{equation} 35 36 37 Na tuto rovnost m� pohl�t jako na rovnice syst� \eqref{sys}. Stav v �e $t$ je nyn�I_t$, vstup $u_t$ a $y_{t+1}$ n�dn�eli�a podm�n�I_t$ a $u_t$ p�eqref{poz}. 37 38 38 39 D� p�me k nov�tr�v�unkci, kterou definujeme jako 39 40 \begin{equation} 40 41 \tilde{g}_t(I_{t+1},u_t)=\E_{x_{t+1}}\left\{g_t(x_{t+1},u_t)|I_t,u_t\right\}, \qquad t=1,\ldots,N-1, 41 42 \end{equation} 42 43 kde $x_{t+1}$ se po��le \eqref{sys} a $x_t$ se pova�uje za n�dnou veli�u podm�nou informa�m vektorem $I_t$. 43 44 44 O��nou ztr� nyn�� ps�ve tvaru45 O��nou ztr� podprobl� od �u $t$ do $N$ nyn�� ps�ve tvaru 45 46 \begin{gather} 46 47 J_N(I_N)=0\\ … … 53 54 Pokud chceme � syst� jeho� v�z�s�a n�k�nezn�m konstant�parametru $\theta$, m� vyu��znalosti ��robl� s ne�m pozorov�m. Parametr $\theta$ bude reprezentovat stav syst� $x_t$, kter�yn� �e nem�. 54 55 56 \subsection{Syst�s nezn�mi parametry, hyperstav} 55 57 V t� � m� v� syst� $y_t$ pops� jako 56 58 \begin{equation} … … 77 79 Rovnici \eqref{the} m� podobn�ako \eqref{nep} pova�ovat za rovnici syst� \eqref{sys} pro stav $H_t$ a vstup $u_t$ s �umem $y_{t+1}$. 78 80 81 \subsection{P� na � s nep�mi daty} 79 82 Ztr�v�unkce je nyn�\begin{equation} 80 83 \label{los2} … … 91 94 Rovnice \eqref{the}, \eqref{poz2} a \eqref{los2} potom p�avuj�lohu stochastick� �� nep�mi daty. 92 95 93 �ohu �e pomoc�ynamick� programov�, tedy postupnou minimalizac���n�tr� od konce �� horizontu96 �ohu op��e pomoc�ynamick� programov�, tedy postupnou minimalizac���n�tr� od konce �� horizontu 94 97 \begin{gather} 95 98 J_N(H_N)=0\\ -
applications/dual/SIDP/text/uvod.tex
r919 r1103 8 8 V �edes�ch letech 20. stolet�avrhl Alexander Aronovich Feldbaum ��ou�it�takzvan� du�� ��cite{feldbaum1965optimal}. Hlavn�y�lenkou tohoto p�pu bylo, �e ��us�ejen minimalizovat aktu��tr�, ale rovn�mus��at o syst� co nejv� informac�ro minimalizaci budouc� ztr� 9 9 10 Dal�� mo�n�roxima�ch metod je pou�it�tochastick�terativn�proximace ��To spo�� pou�it�terativn� dynamick� programov� a simula� metody Mante Carlo. Tento p�p byl pops�v �nku \cite{thompson2005stochastic}. Podstatou algoritmu je hled� ��lohy dynamick� programov� iterativn�za pou�it�etody Monte Carlo pro simulaci neur�osti v syst�. 11 10 12 Tato bakal�k�r� si klade n�eduj� c� 11 13 \begin{itemize} … … 13 15 \item Formulace � stochastick� �� ne�m pozorov�m a jej��en�a � s �mi znalostmi syst� 14 16 \item P�aven��er�boptim�� p�p�loze stochastick� ��\item Aplikace a porovn� zm�n�tod k nalezen�ptim��trategie na jednoduch�syst� 17 \item Na z�ad��an�sledk�kutovat v�a nev�algoritmu a jeho pou�itelnost p�likaci na dal��lohy. 15 18 \end{itemize} 19 20 C�m pr� je sezn�n�e s probl�, kter�proximativn�e�en�lohy stochastick� ����P�em je pak vytvo�konkr��mplementace algoritmu stochastick� iterativn� dynamick� programov� a jeho srovn� s jin�goritmy. To umo�� z�at p�d o kladn�z�rn�r�� jednotliv��up�osoudit jejich aplikovatelnost na re��lohy. O��n�ledkem srovn� algoritmu iterativn� dynamick� programov� s jin� literatu��n��, je v��asov���st v� a lep��obustnost a p�st v�� ��
