Bellmanova rovnice

Z Wikipedie, otevřené encyklopedie
Skočit na navigaci Skočit na vyhledávání
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í.[1] 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“.[2]

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[3]. 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[4][5].

Analytické koncepty v dynamickém programování[editovat | editovat zdroj]

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. Matematické funkce, která popisuje tento cíl, se nazývá účelová funkce (anglicky objective function).

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. Informace o aktuální situaci, které jsou nutné pro optimální rozhodnutí, se nazývají „stav“[6][7]. 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 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. 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 , které dává spotřebu jako funkci majetku. Takové pravidlo, které určuje hodnotu řídicí proměnné jako funkce stavů, se nazývá řídicí funkce (anglicky policy function, viz Bellman, 1957, Ch. III.2)[6].

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, . Nejlepší možná hodnota účelové funkce, zapsaná jako funkce stavu, se nazývá hodnotová funkce (anglicky value function).

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“. 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í[editovat | editovat zdroj]

Dynamický rozhodovací problém[editovat | editovat zdroj]

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

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

při platnosti omezení

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

Bellmanův princip optimality[editovat | editovat zdroj]

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í. (Viz Bellman, 1957, Chap. III.3.)[6][7][8]

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 ). Budoucí rozhodnutí jsou shrnuta v hranatých závorkách. Předchozí problém je ekvivalentní s:

při platnosti omezení

Zde volíme , protože víme, že naše rozhodnutí povede do stavu 1, tj. . 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[editovat | editovat zdroj]

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 , můžeme rovnici přepsat jako rekurzivní definici hodnotové funkce:

, při platnosti omezení

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:

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. 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[editovat | editovat zdroj]

Související informace naleznete také v článku Markovův rozhodovací proces.

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 v čase . Spotřebitel má okamžitou užitkovou funkci , kde označuje spotřebu a diskontování užitku v další periodě má velikost . Předpokládejme, že to, co není spotřebováno v čase , se přenáší do další etapy s úrokovou sazbou . Pak problém maximalizace užitku spotřebitele znamená vybrat takový plán spotřeby , který maximalizuje

za následujících omezení:

a

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

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 , kde označuje pravděpodobnostní míru řídící výši úrokové sazby v další etapě, je-li současná úroková sazba je . 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 musí spotřebitel nyní zvolit posloupnost pro každou možnou realizaci takovým způsobem, aby maximalizoval očekávaný užitek pro dobu svého života:

Očekávání 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. Bellmanova rovnice pak má jednoduchý tvar

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

Metody řešení[editovat | editovat zdroj]

  • 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.[9]
  • 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. 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.[10] 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.[11] 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ě.[12]
  • 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.[13] 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[editovat | editovat zdroj]

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

Dobře známou ekonomickou aplikací Bellmanovy rovnice je podnětný článek Roberta C. Mertona z roku 1973 o intertemporálním modelu oceňování kapitálových aktiv.[16] (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. 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.[17] 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.[18] Avinash Dixit a Robert Pindyck ukázali význam metody pro rozvahy v oblasti kapitálového rozpočtování.[19] Anderson upravil tuto techniku pro ohodnocování firem, včetně soukromých.[20]

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. Výpočetní problémy podrobně diskutuje Miranda a Fackler,[21] a Meyn 2007.[22]

Příklad[editovat | editovat zdroj]

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 ve stavu s má Bellmanova rovnice tvar:

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

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

kde je optimální strategie a 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[editovat | editovat zdroj]

Související články[editovat | editovat zdroj]

Reference[editovat | editovat zdroj]

V tomto článku byl použit překlad textu z článku Bellman equation na anglické Wikipedii.

  1. DIXIT, Avinash K. Optimization in Economic Theory. 2. vyd. Oxford: Oxford University Press, 1990. Dostupné online. ISBN 0-19-877211-4. 
  2. KIRK, Donald E. Optimal Control Theory: An Introduction. Englewood Cliffs, NJ: Prentice-Hall, 1970. Dostupné online. ISBN 0-13-638098-0. 
  3. KIRK, Donald E. Optimal Control Theory: An Introduction. Englewood Cliffs, NJ: Prentice-Hall, 1970. Dostupné online. ISBN 0-13-638098-0. 
  4. KAMIEN, Morton I.; SCHWARTZ, Nancy L. Dynamic Optimization: The Calculus of Variations and Optimal Control in Economics and Management. 2. vyd. Amsterdam: Elsevier, 1991. Dostupné online. ISBN 0-444-01609-0. 
  5. KIRK, Donald E. Optimal Control Theory: An Introduction. Englewood Cliffs, NJ: Prentice-Hall, 1970. Dostupné online. ISBN 0-13-638098-0. 
  6. a b c BELLMAN, R. E. Dynamic Programming. Princeton, NJ; Dover: Princeton University Press, 1957 (1957 tisk). ISBN 0-486-42809-5. .
  7. a b DREYFUS, S. Richard Bellman on the birth of dynamic programmin. Operation Research. 2005-01-10, roč. 50, čís. 1. Dostupné v archivu pořízeném z originálu.  Archivováno 10. 1. 2005 na Wayback Machine
  8. R Bellman, On the Theory of Dynamic Programming, Proceedings of the National Academy of Sciences, 1952
  9. LJUNGQVIST, Lars; SARGENT, Thomas J. Recursive Macroeconomic Theory. 2. vyd. [s.l.]: MIT Press, 2004. Dostupné online. ISBN 0-262-12274-X. 
  10. BERTSEKAS, D. P.; TSITSIKLIS, J. N. Neuro-Dynamic Programming. [s.l.]: Athena Scientific, 1996. 
  11. ABU-KHALAF, Murad; LEWIS, Frank L., 2005. Nearly optimal control laws for nonlinear systems with saturating actuators using a neural network HJB approach. Automatica. Roč. 41, čís. 5, s. 779–791. DOI 10.1016/j.automatica.2004.11.034. 
  12. AL-TAMIMI, Asma; LEWIS, Frank L.; ABU-KHALAF, Murad, 2008. Discrete-Time Nonlinear HJB Solution Using Approximate Dynamic Programming: Convergence Proof. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics). Roč. 38, čís. 4, s. 943–949. DOI 10.1109/TSMCB.2008.926614. PMID 18632382. S2CID 14202785. 
  13. MIAO, Jianjun. Economic Dynamics in Discrete Time. [s.l.]: MIT Press, 2014. Dostupné online. ISBN 978-0-262-32560-8. 
  14. BECKMANN, Martin; MUTH, Richard. On the Solution to the ‘Fundamental Equation’ of inventory theory. cowles.yale.edu. 1954. Dostupné online. 
  15. BECKMANN, Martin, 1959. A Dynamic Programming Model of the Consumption Function. [s.l.]: [s.n.]. Dostupné online. 
  16. MERTON, Robert C. An Intertemporal Capital Asset Pricing Model. Econometrica. 1973, roč. 41, čís. 5. DOI 10.2307/1913811. JSTOR 1913811. 
  17. STOKEY, Nancy; LUCAS, Robert E.; PRESCOTT, Edward. Recursive Methods in Economic Dynamics. [s.l.]: Harvard Univ. Press., 1989. ISBN 0-674-75096-9. 
  18. LJUNGQVIST, Lars; SARGENT, Thomas, 2012. Recursive Macroeconomic Theory. 2. vyd. [s.l.]: MIT Press. ISBN 978-0-262-01874-6. 
  19. DIXIT, Avinash; PINDYCK, Robert, 1994. Investment Under Uncertainty. [s.l.]: Princeton University Press. Dostupné online. ISBN 0-691-03410-9. 
  20. ANDERSON, Patrick L., 2004. Business Economics & Finance. [s.l.]: CRC Press. ISBN 1-58488-348-0. Kapitola Ch. 10. 
    ANDERSON, Patrick L., 2009. The Value of Private Businesses in the United States. Business Economics. Roč. 44, čís. 2, s. 87–108. DOI 10.1057/be.2009.4. S2CID 154743445. 
    ANDERSON, Patrick L., 2013. Economics of Business Valuation. [s.l.]: Stanford University Press. ISBN 9780804758307.  Stanford Press Archivováno 2. 7. 2014 na Wayback Machine
  21. MIRANDA, Mario J.; FACKLER, Paul L. Applied Computational Economics and Finance. [s.l.]: MIT Press, 2004. Dostupné online. ISBN 978-0-262-29175-0. 
  22. MEYN, Sean, 2008. Control Techniques for Complex Networks. [s.l.]: Cambridge University Press. Dostupné online. ISBN 978-0-521-88441-9.  Appendix obsahuje zkrácená Meyn & Tweedie Archivováno 10. 8. 2009 na Wayback Machine.