Рівняння Гамільтона — Якобі — Беллмана

У теорії оптимального управління рівняння Гамільтона — Якобі — Беллмана (HJB) дає необхідну та достатню умову оптимальності керування щодо функції втрат.^[1] Загалом це нелінійне диференціальне рівняння з частинними похідними у функції значення, що означає, що його розв'язком є сама функція значення. Як тільки цей розв'язок знайдено, його можна використовувати для отримання оптимального управління, взявши максимізер (або мінімізатор) гамільтоніан, що бере участь у рівнянні HJB.^[2][3]

Рівняння є результатом теорії динамічного програмування, яка була започаткована в 1950-х роках Річардом Беллманом та його колегами.^[4][5][6] Зв'язок із рівнянням Гамільтона–Якобі з класичної фізики вперше встановив Рудольф Кальман.^[7] У задачах з дискретним часом^[en] відповідне рекурентне співвідношення зазвичай називають рівнянням Беллмана.

Хоча класичні варіаційні задачі, такі як проблема брахістохрони, можна розв'язати за допомогою рівняння Гамільтона–Якобі–Беллмана,^[8] цей метод можна застосувати до більш широкого спектру задач. Далі його можна узагальнити на стохастичні системи, у цьому випадку рівняння HJB є еліптичним диференціальним рівнянням у частинних похідних другого порядку.^[9] Головним недоліком, однак, є те, що рівняння HJB допускає класичні рішення лише для достатньо гладкої функції значення, що не гарантується в більшості ситуацій. Натомість потрібне поняття в'язкісного рішення^[en], в якому звичайні похідні замінюються (з заданим значенням) підпохідними.^[10]

Проблеми оптимального управління

Розглянемо наступну задачу детермінованого оптимального управління за період часу ${\displaystyle [0,T]}$ :

${\displaystyle V_{T}(x(0),0)=\min _{u}\left\{\int _{0}^{T}C[x(t),u(t)]\,dt+D[x(T)]\right\}}$

де ${\displaystyle C[\cdot ]}$ — скалярна функція норми втрат і ${\displaystyle D[\cdot ]}$ є функцією, яка дає успадковану цінність^[en] у кінцевому стані, ${\displaystyle x(t)}$ — вектор стану системи, ${\displaystyle x(0)}$ передбачається даним, і ${\displaystyle u(t)}$ для ${\displaystyle 0\leq t\leq T}$ — це вектор управління, який ми намагаємося знайти.

Система також повинна підпорядковуватися

${\displaystyle {\dot {x}}(t)=F[x(t),u(t)]\,}$

де ${\displaystyle F[\cdot ]}$ дає вектор, що визначає фізичну зміну вектора стану з часом.

Диференціальне рівняння з частинними похідними

Для цієї простої системи (нехай ${\displaystyle V=V_{T}}$), диференціальне рівняння з частинними похідними Гамільтона–Якобі–Беллмана представляє собою

${\displaystyle {\frac {\partial V(x,t)}{\partial t}}+\min _{u}\left\{{\frac {\partial V(x,t)}{\partial x}}\cdot F(x,u)+C(x,u)\right\}=0}$

залежно від термінальної умови

${\displaystyle V(x,T)=D(x),\,}$

Невідомий скаляр ${\displaystyle V(x,t)}$ у наведеному вище диференціальному рівнянні з частинними похідними є функцієї цінності Беллмана, яка представляє втрати, понесені від початку роботи в стані ${\displaystyle x}$ під час ${\displaystyle t}$ і оптимальне управління системою з тих пір і до часу ${\displaystyle T}$.

Виведення рівняння

Інтуїтивно рівняння HJB можна вивести наступним чином. Якщо ${\displaystyle V(x(t),t)}$ є оптимальною функцією втрат на доставку (також званою «функцією цінності»), то відповідно до принципу оптимальності Річарда Беллмана, переходячи від часу t до t + dt, маємо

${\displaystyle V(x(t),t)=\min _{u}\left\{V(x(t+dt),t+dt)+\int _{t}^{t+dt}C(x(s),u(s))\,ds\right\}.}$

Зауважте, що розкладання Тейлора першого члена в правій частині є

${\displaystyle V(x(t+dt),t+dt)=V(x(t),t)+{\frac {\partial V(x,t)}{\partial t}}\,dt+{\frac {\partial V(x,t)}{\partial x}}\cdot {\dot {x}}(t)\,dt+{\mathcal {o}}(dt),}$

де ${\displaystyle {\mathcal {o}}(dt)}$ позначає елементи в розкладанні Тейлора вищого порядку за одиницю у нотації з маленьким о. Тоді, якщо відняти ${\displaystyle V(x(t),t)}$ з обох сторін, поділити на dt і знайти границю, коли dt наближається до нуля, то ми отримуємо рівняння HJB, визначене вище.

Розв'язування рівняння

Рівняння HJB зазвичай розв'язується у зворотному напрямку в часі, починаючи з ${\displaystyle t=T}$ і закінчується на ${\displaystyle t=0}$.

При розв'язанні на всьому просторі станів ${\displaystyle V(x)}$ є безперервно диференційованою, рівняння HJB є необхідною та достатньою умовою оптимуму, коли кінцевий стан є необмеженим.^[11] Якщо ми зможемо вирішити ${\displaystyle V}$, то матимемо змогу знайти з нього елемент управління ${\displaystyle u}$, що забезпечує мінімальну вартість (цінність).

У загальному випадку рівняння HJB не має класичного (гладкого) розв'язку. Для охоплення таких ситуацій було розроблено кілька понять про узагальнені рішення, включаюч в'язкісне рішення (П'єр-Луї Лайонс і Майкл Крендалл^[en]),^[12] мінімаксне рішення (Андрій Ізмаїлович Субботін^[ru]), та інші.

Наближене динамічне програмування було введено Д. П. Берцекасом^[en] та Дж. Цициклісом^[en] із використанням штучних нейронних мереж (багатошарових персептронів) для апроксимації функції Беллмана в цілому.^[13] Це ефективна стратегія пом'якшення для зменшення впливу розмірності шляхом заміни запам'ятовування повного відображення функцій для всієї просторової області запам'ятовуванням окремих параметрів нейронної мережі. Зокрема, для систем безперервного часу введено наближений підхід динамічного програмування, який поєднує обидва ітераційних підходи з нейронними мережами.^[14] У дискретному часі було введено підхід до вирішення рівняння HJB, що поєднує ітерації значень і нейронні мережі.^[15]

Крім того, було показано, що оптимізація суми квадратів^[en] може дати наближений поліноміальний розв'язок рівняння Гамільтона-Якобі-Беллмана довільно добре по відношенню до ${\displaystyle L^{1}}$ норми.^[16]

Ідею вирішення задачі управління шляхом застосування з подальшою розробкою стратегії оптимізації назад у часі можна узагальнити на стохастичні задачі управління. Розглянемо

${\displaystyle \min _{u}\mathbb {E} \left\{\int _{0}^{T}C(t,X_{t},u_{t})\,dt+D(X_{T})\right\}}$

де ${\displaystyle (X_{t})_{t\in [0,T]}\,\!}$ є стохастичним процесом для оптимізації та ${\displaystyle (u_{t})_{t\in [0,T]}\,\!}$ є управлінням. Спочатку використавши принцип оптимальності Беллмана, а потім розширивши ${\displaystyle V(X_{t},t)}$ за правилом Іто, можна знайти стохастичне рівняння HJB

${\displaystyle \min _{u}\left\{{\mathcal {A}}V(x,t)+C(t,x,u)\right\}=0,}$

де ${\displaystyle {\mathcal {A}}}$ представляє стохастичний оператор диференціювання^[en], і підлягає термінальній умові

${\displaystyle V(x,T)=D(x)\,\!.}$

Зауважте, що випадковість зникла. В даному випадку останнє рішення ${\displaystyle V\,\!}$не обов'язково вирішує основну задачу, воно є лише кандидатом і потрібен додатковий перевіряючий аргумент. Цей метод широко використовується у фінансовій математиці для визначення оптимальних інвестиційних стратегій на ринку (див., наприклад, проблему портфеля Мертона^[en]).

Застосування до LQG Control

Як приклад можна розглянути систему з лінійною стохастичною динамікою та квадратичною вартістю. Якщо динаміка системи задана

${\displaystyle dx_{t}=(ax_{t}+bu_{t})dt+\sigma dw_{t},}$

і вартість накопичується зі швидкістю ${\displaystyle C(x_{t},u_{t})=r(t)u_{t}^{2}/2+q(t)x_{t}^{2}/2}$, рівняння HJB задається як

${\displaystyle -{\frac {\partial V(x,t)}{\partial t}}={\frac {1}{2}}q(t)x^{2}+{\frac {\partial V(x,t)}{\partial x}}ax-{\frac {b^{2}}{2r(t)}}\left({\frac {\partial V(x,t)}{\partial x}}\right)^{2}+{\frac {\sigma ^{2}}{2}}{\frac {\partial ^{2}V(x,t)}{\partial x^{2}}}.}$

з оптимальною дією, заданою

${\displaystyle u_{t}=-{\frac {b}{r(t)}}{\frac {\partial V(x,t)}{\partial x}}}$

Прийнявши квадратичну форму для функції значення, ми отримуємо звичайне рівняння Ріккаті для гесіана функції значення, як це зазвичай відбувається для лінійно-квадратично-гауссового управління^[en].

Див. також

• Рівняння Беллмана, аналог рівняння Гамільтона–Якобі–Беллмана з дискретним часом.
• Принцип максимуму Понтрягіна, необхідна, але не достатня умова для оптимуму, шляхом максимізації гамільтоніана, але він має перевагу над HJB, оскільки його необхідно задовольнити лише на одній розглянутій траєкторії.

Посилання

1. Kirk, Donald E. (1970). Optimal Control Theory: An Introduction. Englewood Cliffs, NJ: Prentice-Hall. с. 86—90. ISBN 0-13-638098-0.
2. Yong, Jiongmin; Zhou, Xun Yu (1999). Dynamic Programming and HJB Equations. Stochastic Controls : Hamiltonian Systems and HJB Equations. Springer. с. 157–215 [p. 163]. ISBN 0-387-98723-1.
3. Naidu, Desineni S. (2003). The Hamilton–Jacobi–Bellman Equation. Optimal Control Systems. Boca Raton: CRC Press. с. 277–283 [p. 280]. ISBN 0-8493-0892-5.
4. Bellman, R. E. (1954). Dynamic Programming and a new formalism in the calculus of variations. Proc. Natl. Acad. Sci. 40 (4): 231—235. Bibcode:1954PNAS...40..231B. doi:10.1073/pnas.40.4.231. PMC 527981. PMID 16589462.
5. Bellman, R. E. (1957). Dynamic Programming. Princeton, NJ.
6. Bellman, R.; Dreyfus, S. (1959). An Application of Dynamic Programming to the Determination of Optimal Satellite Trajectories. J. Br. Interplanet. Soc. 17: 78—83.
7. Kálmán, Rudolf E. (1963). The Theory of Optimal Control and the Calculus of Variations. У Bellman, Richard (ред.). Mathematical Optimization Techniques. Berkeley: University of California Press. с. 309—331. OCLC 1033974.
8. Kemajou-Brown, Isabelle (2016). Brief History of Optimal Control Theory and Some Recent Developments. У Budzban, Gregory; Hughes, Harry Randolph; Schurz, Henri (ред.). Probability on Algebraic and Geometric Structures. Contemporary Mathematics. Т. 668. с. 119—130. doi:10.1090/conm/668/13400. ISBN 9781470419455.
9. Chang, Fwu-Ranq (2004). Stochastic Optimization in Continuous Time. Cambridge, UK: Cambridge University Press. с. 113—168. ISBN 0-521-83406-6.
10. Bardi, Martino; Capuzzo-Dolcetta, Italo (1997). Optimal Control and Viscosity Solutions of Hamilton–Jacobi–Bellman Equations. Boston: Birkhäuser. ISBN 0-8176-3640-4.
11. Bertsekas, Dimitri P. (2005). Dynamic Programming and Optimal Control. Athena Scientific.
12. Bardi, Martino; Capuzzo-Dolcetta, Italo (1997). Optimal Control and Viscosity Solutions of Hamilton-Jacobi-Bellman Equations. Boston: Birkhäuser. ISBN 0-8176-3640-4.
13. Bertsekas, Dimitri P.; Tsitsiklis, John N. (1996). Neuro-dynamic Programming. Athena Scientific. ISBN 978-1-886529-10-6.
14. Abu-Khalaf, Murad; Lewis, Frank L. (2005). Nearly optimal control laws for nonlinear systems with saturating actuators using a neural network HJB approach. Automatica. 41 (5): 779—791. doi:10.1016/j.automatica.2004.11.034.
15. 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). 38 (4): 943—949. doi:10.1109/TSMCB.2008.926614. PMID 18632382.
16. Jones, Morgan; Peet, Matthew (2020). Polynomial Approximation of Value Functions and Nonlinear Controller Design with Performance Bounds. arXiv:2010.06828.

Бібліографія

• Bertsekas, Dimitri P. (2005). Dynamic Programming and Optimal Control. Athena Scientific.
• Pham, Huyên (2009). The Classical PDE Approach to Dynamic Programming. Continuous-time Stochastic Control and Optimization with Financial Applications. Springer. с. 37–60. ISBN 978-3-540-89499-5.
• Stengel, Robert F. (1994). Conditions for Optimality. Optimal Control and Estimation. New York: Dover. с. 201—222. ISBN 0-486-68200-5.