Bellmanova rovnice

Bellmanův vývojový diagram Bellmanova rovnice pojmenovaná podle svého autora Richarda Bellmana, je nutná podmínka optimality matematických optimalizačních metod známých jako dynamické programování. Určuje „hodnotu“ rozhodovacího problému v určitém časovém okamžiku podle výplaty závislé na nějakých počátečních rozhodnutích a „hodnoty“ zbývajícího rozhodovacího problému, který vyplývá z těchto počátečních rozhodnutí. Tím se dynamický optimalizační problém rozloží na posloupnost jednodušších podproblémů, jak popisuje #Bellmanův princip optimality|„Bellmanův princip optimality“.

Bellmanova rovnice byla nejdříve aplikována na inženýrskou teorii řízení a různé obory užité matematiky, poté se stala důležitým nástrojem v ekonomické teorii; základní koncepty dynamického programování jsou však popsány již v pracích Theory of Games and Economic Behavior Johna von Neumanna a Oskara Morgensterna a Sequential analysis Abrahama Walda.

Téměř jakýkoli problém, který lze vyřešit pomocí teorie optimálního řízení může také být vyřešený analýzou určité Bellmanovy rovnice. Termín 'Bellmanova rovnice' se obvykle používá pro rovnici dynamického programování popisující optimalizační problém v diskrétním čase. +more Analogickou roli pro optimalizační problémy ve spojitém čase hraje parciální diferenciální rovnice, která se obvykle nazývá Hamiltonova-Jacobiho-Bellmanova rovnice.

Analytické koncepty v dynamickém programování

Pro pochopení Bellmanovy rovnice je třeba znát několik základních pojmů. Prvním z nich je, že každý optimalizační problém má určitý cíl, jímž může být minimalizace doby trvání cesty, minimalizace ceny, maximalizace zisku, maximalizace užitku, atd. +more Matematické funkce, která popisuje tento cíl, se nazývá účelová funkce .

Dynamické programování rozkládá několikaetapové rozhodovací procesy na řadu postupných rozhodnutí. Proto je třeba sledovat, jak rozhodnutí učiněné v určitém okamžiku ovlivní další situaci. +more Informace o aktuální situaci, které jsou nutné pro optimální rozhodnutí, se nazývají „stav“. Například pro rozhodnutí, jaké množství určitého statku (prostředku, majetku) spotřebovat a jaké vynaložit v dané časové etapě, je potřeba znát (mimo jiné) i počáteční množství majetku. Proto majetek (W) bude jedna ze stavových proměnných, ale pravděpodobně budou existovat i další stavové proměnné.

Proměnné, které popisují, jaké rozhodnutí bylo učiněno v určité časové etapě, se obvykle nazývají řídicí proměnné. Je-li například dán výchozí majetek určité osoby, může se tato osoba rozhodovat, jak velkou jeho část v aktuální etapě spotřebovat. +more Volba hodnoty řídicí proměnné ovlivňuje budoucí stav; obecně však může být další stav ovlivněn i jinými faktory než aktuální hodnotou řídicí proměnné. Například v nejjednodušším případě dnešní majetek (stav) a spotřeba (hodnota řídicí proměnné) může jednoznačně určovat zítřejší majetek (nový stav), i když typicky budou zítřejší majetek ovlivňovat i jiné faktory (např. neočekávané bonusy nebo přírodní katastrofy).

Dynamické programování popisuje optimální plán hledáním pravidla, které říká, jaké mají být hodnoty řídicích proměnných v každé etapě pro libovolnou hodnotu stavu. Pokud například spotřeba (c) závisí pouze na majetku (W), hledáme pravidlo c(W), které dává spotřebu jako funkci majetku. +more Takové pravidlo, které určuje hodnotu řídicí proměnné jako funkce stavů, se nazývá řídicí funkce ( viz Bellman, 1957, Ch. III. 2).

Podle definice je optimální rozhodovací pravidlo takové, které zajišťuje nejlepší možnou hodnotu účelové funkce. Pokud například někdo zvolí jako cíl maximalizaci spotřeby při daném majetku, aby maximalizoval spokojenost (za předpokladu, že spokojenost H lze reprezentovat matematickou funkcí, jako je užitková funkce, a že spokojenost je něco definované majetkem), pak každá úroveň majetku bude spojena s nějakou nejvyšší možnou úrovní spokojenosti, H(W). +more Nejlepší možná hodnota účelové funkce, zapsaná jako funkce stavu, se nazývá hodnotová funkce .

Richard Bellman ukázal, že dynamický optimalizační problém v diskrétním čase lze vyjádřit v rekurzivním tvaru známém jako zpětná indukce, který vyjadřuje vztah mezi hodnotou optimálního řešení úlohy v jedné etapě a její hodnotou v následující etapě. Vztah mezi těmito dvěma hodnotami hodnotové funkce se nazývá „Bellmanova rovnice“. +more Optimální strategie v poslední časové etapě je u tohoto přístupu zadaná předem jako funkce hodnoty stavové proměnné v této etapě; výsledná optimální hodnota účelové funkce je tedy vyjádřena pomocí této hodnoty stavové proměnné. Optimalizace pro následující etapu znamená maximalizaci součtu aktuální hodnoty účelové funkce a optimální hodnoty budoucí účelové funkce, což dává kontingenci optimální strategie pro tuto etapu v závislosti na hodnotě stavové proměnné jakožto rozhodnutí v následujících etapách. S touto logikou pokračujeme rekurzivně zpět v čase až k odvození rozhodovacího pravidla pro první etapu jako funkce počáteční hodnoty stavové proměnné optimalizací sumy účelové funkce pro první etapu a hodnoty hodnotové funkce pro druhou etapu, která určuje hodnotu pro všechny budoucí etapy. Rozhodnutí pro každou etapu se tedy provádí na základě předpokladu, že také všechna budoucí rozhodnutí budou optimální.

Odvození

Dynamický rozhodovací problém

Stav v čase t budeme značit x_t. Počáteční stav pro rozhodnutí učiněné v čase 0 je tedy x_0. +more Množina akcí možných v libovolném čase závisí na okamžitém stavu; což můžeme psát jako a_{t} \in \Gamma (x_t), kde akce a_t reprezentuje jednu nebo více řídicích proměnných. Také předpokládáme, že se provedením akce a stav změní z x do nového stavu T(x,a), a že současná výplata z provedení akce a ve stavu x je F(x,a). Míra netrpělivosti je reprezentována diskontním faktorem 0.

Rozhodovací problém s nekonečným časovým horizontem má za těchto předpokladů následující tvar:

: V(x_0) \; = \; \max_{ \left \{ a_{t} \right \}_{t=0}^{\infty} } \sum_{t=0}^{\infty} \beta^t F(x_t,a_{t}),

při platnosti omezení

: a_{t} \in \Gamma (x_t), \; x_{t+1}=T(x_t,a_t), \; \forall t = 0, 1, 2, \dots

V(x_0) označuje optimální hodnotu, kterou lze získat maximalizací účelové funkce F(x,a) při platnosti uvedených omezení. Tato funkce je hodnotová funkce. +more Je funkcí počáteční stavové proměnné x_0, protože nejlepší hodnota, kterou lze získat, závisí na počáteční situaci.

Bellmanův princip optimality

Metoda dynamického programování rozkládá rozhodovací problém na menší podproblémy. Richard Bellman zformuloval princip optimality, který popisuje, jak rozklad provést:Princip optimality: Optimální strategie má tu vlastnost, že ať je počáteční stav a počáteční rozhodnutí jakékoli, zbývající rozhodnutí musí tvořit optimální strategii pro stav, který je výsledkem prvního rozhodnutí. +more (Viz Bellman, 1957, Chap. III. 3. ).

O problému, který lze takto rozdělit na podproblémy, říkáme v matematické informatice, že má optimální podstrukturu. V kontextu dynamické teorie her je tento princip obdobou konceptu dokonalé rovnováhy podhry, i když to, z čeho se skládá optimální strategie, je v tomto případě podmíněné výběrem optimální (z pohledu protivníků) strategie protivníků.

V souladu s principem optimality budeme uvažovat první rozhodnutí odděleně, bez uvažování všech budoucích rozhodnutí (která začínají etapou 1 ve výchozím stavu x_1 ). Budoucí rozhodnutí jsou shrnuta v hranatých závorkách. +more Předchozí problém je ekvivalentní s:.

: \max_{ a_0 } \left \{ F(x_0,a_0) + \beta \left[ \max_{ \left \{ a_{t} \right \}_{t=1}^{\infty} } \sum_{t=1}^{\infty} \beta^{t-1} F(x_t,a_{t}): a_{t} \in \Gamma (x_t), \; x_{t+1}=T(x_t,a_t), \; \forall t \geq 1 \right] \right \}

při platnosti omezení

: a_0 \in \Gamma (x_0), \; x_1=T(x_0,a_0).

Zde volíme a_0, protože víme, že naše rozhodnutí povede do stavu 1, tj. x_1=T(x_0,a_0). +more Tento nový stav pak bude ovlivňovat rozhodovací problém od času 1 dále. Celý budoucí rozhodovací problém se objevuje v hranatých závorkách vpravo.

Bellmanova rovnice

Zdá se, že oddělením aktuálního rozhodnutí od budoucích rozhodnutí jsme problém pouze zkomplikovali. Pokud si však všimneme, že výraz v hranatých závorkách vpravo je hodnota rozhodovacího problému v čase 1, začínající ze stavu x_1=T(x_0,a_0), můžeme rovnici přepsat jako rekurzivní definici hodnotové funkce:

:V(x_0) = \max_{ a_0 } \{ F(x_0,a_0) + \beta V(x_1) \} , při platnosti omezení a_0 \in \Gamma (x_0), \; x_1=T(x_0,a_0).

Tento tvar nazýváme Bellmanova rovnice. Rovnici můžeme dále zjednodušit vypuštěním časových indexů a použitím hodnoty dalšího stavu:

:V(x) = \max_{a \in \Gamma (x) } \{ F(x,a) + \beta V(T(x,a)) \}.

Je zřejmé, že Bellmanova rovnice je funkcionální rovnicí, protože jejím řešením je funkce V, která je hodnotová funkce. Hodnotová funkce tedy popisuje nejlepší možnou hodnotu účelové funkce jako funkci stavu x. +more Při výpočtu hodnotové funkce zjistíme také funkci a(x), která popisuje optimální akci jako funkci stavu; tato funkce se nazývá řídicí funkce.

Stochastické problémy

V deterministickém prostředí lze pro řešení výše uvedeného problému optimálního řízení použít i jiné techniky než dynamické programování. V případě stochastických problémů optimálního řízení je však Bellmanova rovnice obvykle nejpohodlnější metodou jejich řešení.

Pro konkrétní příklad z ekonomie uvažujme spotřebitele žijícího nekonečnou dobu s počátečním majetkem {\color{Red}a_0} v čase 0. Spotřebitel má okamžitou užitkovou funkci u(c), kde c označuje spotřebu a diskontování užitku v další periodě má velikost 0. +more Předpokládejme, že to, co není spotřebováno v čase t, se přenáší do další etapy s úrokovou sazbou r. Pak problém maximalizace užitku spotřebitele znamená vybrat takový plán spotřeby \{{\color{OliveGreen}c_t}\}, který maximalizuje.

:\sum_{t=0} ^{\infty} \beta^t u ({\color{OliveGreen}c_t})

za následujících omezení:

:{\color{Red}a_{t+1}} = (1 + r) ({\color{Red}a_t} - {\color{OliveGreen}c_t}), \; {\color{OliveGreen}c_t} \geq 0,

a

:\lim_{t \rightarrow \infty} {\color{Red}a_t} \geq 0.

První omezení vyjadřuje akumulaci kapitálu popsanou v zadání problému, druhým omezením je podmínka transverzality, která říká, že spotřebitel nesmí mít na konci svého života dluh. Bellmanova rovnice této úlohy je

:V(a) = \max_{ 0 \leq c \leq a} \{ u(c) + \beta V((1+r) (a - c)) \},

Problém posloupnosti můžeme řešit také přímo, například pomocí Hamiltonových rovnic.

Jestliže se úrokové sazby v jednotlivých etapách mění, musí spotřebitel řešit stochastický optimalizační problém. Pokud budeme změny sazby r považovat za Markovův proces s funkcí přechodu pravděpodobnosti Q(r, d\mu_r), kde d\mu_r označuje pravděpodobnostní míru řídící výši úrokové sazby v další etapě, je-li současná úroková sazba je r. +more V tomto modelu spotřebitel rozhoduje o své spotřebě v příští etapě po ohlášení úrokové sazby pro tuto etapu.

Místo výběru jediné posloupnosti \{{\color{OliveGreen}c_t}\} musí spotřebitel nyní zvolit posloupnost \{{\color{OliveGreen}c_t}\} pro každou možnou realizaci \{r_t\} takovým způsobem, aby maximalizoval očekávaný užitek pro dobu svého života:

:\max_{ \left \{ c_{t} \right \}_{t=0}^{\infty} } \mathbb{E}\bigg( \sum_{t=0} ^{\infty} \beta^t u ({\color{OliveGreen}c_t}) \bigg).

Očekávání \mathbb{E} se bere vzhledem k vhodné pravděpodobnostní míře dané Q na posloupnosti r. Protože r je řízeno Markovovým procesem, dynamické programování problém výrazně zjednodušuje. +more Bellmanova rovnice pak má jednoduchý tvar.

:V(a, r) = \max_{ 0 \leq c \leq a } \left\{ u(c) + \beta \int V((1+r) (a - c), r') Q(r, d\mu_r) \right\} .

Za určitého rozumného předpokladu je výsledná optimální řídicí funkce g(a,r) měřitelná.

Pro obecný stochastický sekvenční optimalizační problém s Markovskými změnami, v němž je agent konfrontován se svými rozhodnutími ex-post, přejde Bellmanova rovnice na velmi podobný tvar

:V(x, z) = \max_{c \in \Gamma(x,z)} \left\{F(x, c, z) + \beta \int V( T(x,c), z') d\mu_z(z')\right\}.

Metody řešení

Metodu neurčitých koeficientů známou také jako 'odhadni a ověř' lze použít pro řešení některých autonomních Bellmanových rovnic s nekonečným horizontem. * Bellmanovu rovnici lze vyřešit zpětnou indukcí; v několika speciálních případech analyticky, v ostatních numericky na počítači. +more Numerickou zpětnou indukci lze použít ve velkém množství problémů, ale pokud je stavových proměnných příliš mnoho, může být nepoužitelná kvůli prokletí dimenzionality. D. P. Bertsekas a J. N. Tsitsiklis ukázali způsob přibližného řešení problémů dynamického programování s použitím neuronové sítě (vícevrstvých perceptronů) pro aproximaci Bellmanovy funkce. Jde o efektivní strategii omezující vliv dimenzionality tak, že místo uchovávání kompletního zobrazení na celém definičním oboru uchovává pouze parametry jedné neuronové sítě. Pro systémy pracující se spojitým časem byl popsán přístup, který kombinuje obě strategie iterace s neuronovými sítěmi. Pro systémy s diskrétním časem byl popsán přístup, jak řešit HJB rovnici kombinací hodnot získaných iteračně a pomocí neuronové sítě. * Výpočtem podmínek prvního řádu přiřazených k Bellmanově rovnici a použitím obálkové věty pro odstranění derivací hodnotové funkce je možné získat soustavu diferenčních nebo diferenciálních rovnic zvanou Eulerova-Lagrangeova rovnice. Pro výpočet dynamiky stavových proměnných a řídicích proměnných optimalizačního problému lze pak použít standardní techniky pro řešení diferenčních nebo diferenciálních rovnic.

Aplikace v ekonomii

První známá aplikace Bellmanovy rovnice v ekonomii se přičítá Martinu Beckmannovi a Richardu Muthovi. Martin Beckmann ve svém článku z roku 1959 podrobně popsal teorii spotřeby pomocí Bellmanovy rovnice. +more Jeho dílo mimo jiné ovlivnilo Edmunda S. Phelpse.

Dobře známou ekonomickou aplikací Bellmanovy rovnice je podnětný článek Roberta C. +more Mertona z roku 1973 o intertemporálním modelu oceňování kapitálových aktiv. (Viz také Mertonův problém portfolia). Řešení Mertonova teoretického modelu, kdy investoři volí mezi příjmem současným a budoucím a kapitálovými zisky, má tvar Bellmanovy rovnice. Protože při aplikaci dynamického programování na ekonomii má Bellmanova rovnice tvar diferenční rovnice, používají ekonomové pro dynamické programování obvykle název „rekurzivní metoda“ a příslušný podobor ekonomie se nazývá rekurzivní ekonomie.

Nancy Stokey, Robert E. +more Lucas a Edward C. Prescott popsali velmi detailně stochastické a nestochastické dynamické programování a zformulovali věty pro existenci řešení problémů, které splňují určité podmínky. Popsali také mnoho příkladů modelování teoretických problémů v ekonomii pomocí rekurzivních metod. Díky jejich knize se dynamické programování používá pro řešení nejrůznějších teoretických problémů v ekonomii, včetně optimálního ekonomického růstu, získávání prostředků, problému ředitel-agent, veřejných financí, obchodních investic, oceňování majetku, faktorů zásob a průmyslové organizace. Lars Ljungqvist a Thomas Sargent aplikovali dynamické programování na studium mnoha teoretických otázek v monetární politice, fiskální politice, zdaňování, hospodářském růstu, teorii vyhledávání a v ekonomii práce. Avinash Dixit a Robert Pindyck ukázali význam metody pro rozvahy v oblasti kapitálového rozpočtování. Anderson upravil tuto techniku pro ohodnocování firem, včetně soukromých.

[url=http://www.sup.org/book.cgi?id=11400]Stanford Press[/url]

Používání dynamického programování pro řešení konkrétních problémů komplikují informační potíže, jako například problém nezjistitelnosti diskontního faktoru. Existují také výpočetní problémy, z nichž hlavní je prokletí dimenzionality způsobené obrovským množstvím možných akcí a hodnot stavových proměnných, které musí být uvažovány pro výběr optimální strategie. +more Výpočetní problémy podrobně diskutuje Miranda a Fackler, a Meyn 2007.

Příklad

V Markovových rozhodovacích procesech je Bellmanova rovnice rekurzivním vztahem pro očekávaný výnos. Například pro očekávaný výnos při použití nějaké pevné strategie \pi ve stavu s má Bellmanova rovnice tvar:

: V^\pi(s)= R(s,\pi(s)) + \gamma \sum_{s'} P(s'|s,\pi(s)) V^\pi(s').\

a popisuje očekávaný výnos provedení akce předepsané nějakou strategií \pi.

Rovnice pro optimální strategii se nazývá Bellmanova rovnice optimality:

: V^{\pi*}(s)= \max_a \left\{ {R(s,a) + \gamma \sum_{s'} P(s'|s,a) V^{\pi*}(s')} \right\}.\

kde {\pi*} je optimální strategie a V^{\pi*} znamená hodnotovou funkci optimální strategie. Výše uvedená rovnice popisuje výnos z provedení akce, která dává nejvyšší očekávaný výnos.

Odkazy

Související články

Bellmanova pseudospektrální metoda * Dynamické programování * Hamiltonova-Jacobiho-Bellmanova rovnice * Markovův rozhodovací proces * Teorie optimálního řízení * Optimální podstruktura * Rekurzivní kompetitivní rovnováha * Stochastické dynamické programování

Reference

Kategorie:Optimalizace (matematika) Kategorie:Rovnice Kategorie:Dynamické programování Kategorie:Teorie řízení