Уравнение Гамильтона – Якоби – Беллмана

Уравнение Беллмана ( HJB ) нелинейное представляет собой уравнение в частных производных , которое обеспечивает необходимые и достаточные условия управления оптимальности относительно Гамильтона-Якоби - функции потерь . ^{[ 1 ]} Его решением является функция цены задачи оптимального управления, которую, если она известна, можно использовать для получения оптимального управления, взяв максимизатор (или минимизатор) гамильтониана, включенного в уравнение HJB. ^{[ 2 ]}^{[ 3 ]}

Уравнение является результатом теории динамического программирования , впервые разработанной в 1950-х годах Ричардом Беллманом и его коллегами. ^{[ 4 ]}^{[ 5 ]}^{[ 6 ]} Связь с уравнением Гамильтона-Якоби из классической физики была впервые установлена Рудольфом Кальманом . ^{[ 7 ]} В задачах с дискретным временем аналогичное разностное уравнение обычно называют уравнением Беллмана .

Хотя классические вариационные задачи , такие как проблема брахистохроны , могут быть решены с использованием уравнения Гамильтона – Якоби – Беллмана, ^{[ 8 ]} метод может быть применен к более широкому спектру задач. В дальнейшем его можно обобщить на стохастические системы, и в этом случае уравнение HJB представляет собой эллиптическое уравнение в частных производных второго порядка . ^{[ 9 ]} Однако основным недостатком является то, что уравнение HJB допускает классические решения только для достаточно гладкой функции цены, что не гарантируется в большинстве ситуаций. Вместо этого требуется понятие вязкостного решения , в котором обычные производные заменяются субпроизводными (с заданными значениями) . ^{[ 10 ]}

Задачи оптимального управления

Рассмотрим следующую задачу детерминированного оптимального управления за период времени $[0,T]$ :

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

где $C[\cdot ]$ скалярная функция ставки стоимости и $D[\cdot ]$ это функция, которая дает значение наследства в конечном состоянии, $x(t)$ вектор состояния системы, $x(0)$ предполагается заданным, и $u(t)$ для $0\leq t\leq T$ — вектор управления, который мы пытаемся найти. Таким образом, $V(x,t)$ – это функция ценности .

Система также должна подчиняться

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

где $F[\cdot ]$ дает вектор, определяющий физическую эволюцию вектора состояния во времени.

Уравнение в частных производных

Для этой простой системы уравнение в частных производных Гамильтона – Якоби – Беллмана имеет вид

{\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

при условии терминального состояния

V(x,T)=D(x),\,

Как и раньше, неизвестная скалярная функция $V(x,t)$ в приведенном выше уравнении в частных производных является функцией стоимости Беллмана , которая представляет затраты, понесенные с момента запуска в состоянии $x$ во время $t$ и оптимально управлять системой с тех пор и до момента $T$ .

Вывод уравнения

Интуитивно уравнение HJB можно вывести следующим образом. Если $V(x(t),t)$ — это оптимальная функция себестоимости (также называемая «функцией стоимости»), то в соответствии с принципом оптимальности Ричарда Беллмана , переходя от времени t к t + dt , мы имеем

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

Обратите внимание, что разложение Тейлора первого члена в правой части имеет вид

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),

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

Решение уравнения

Уравнение HJB обычно решается в обратном направлении во времени , начиная с $t=T$ и заканчивая $t=0$ . ^{[ 11 ]}

При решении во всем пространстве состояний и $V(x)$ непрерывно дифференцируемо, уравнение HJB является необходимым и достаточным условием оптимума, когда терминальное состояние не имеет ограничений. ^{[ 12 ]} Если мы сможем решить $V$ то мы сможем найти из него управление $u$ что обеспечивает минимальные затраты.

В общем случае уравнение ГЯБ не имеет классического (гладкого) решения. Для охвата таких ситуаций было разработано несколько понятий обобщенных решений, включая решение вязкости ( Пьер-Луи Лионс и Майкл Крэндалл ), ^{[ 13 ]} минимаксное решение ( Андрей Измайлович Субботин [ ru ] ) и другие.

Приближенное динамическое программирование было введено Д. П. Берцекасом и Ю. Н. Цициклисом с использованием искусственных нейронных сетей ( многослойных персептронов ) для аппроксимации функции Беллмана в целом. ^{[ 14 ]} Это эффективная стратегия смягчения воздействия размерности путем замены запоминания полного отображения функций для всей пространственной области запоминанием отдельных параметров нейронной сети. В частности, для систем с непрерывным временем был представлен приближенный подход динамического программирования, сочетающий обе итерации политики с нейронными сетями. ^{[ 15 ]} В дискретном времени был представлен подход к решению уравнения HJB, сочетающий итерации значений и нейронные сети. ^{[ 16 ]}

В качестве альтернативы было показано, что оптимизация суммы квадратов может дать приближенное полиномиальное решение уравнения Гамильтона – Якоби – Беллмана сколь угодно хорошо относительно $L^{1}$ норма. ^{[ 17 ]}

Расширение стохастических задач

Идея решения задачи управления путем применения принципа оптимальности Беллмана с последующей разработкой стратегии оптимизации в обратном направлении во времени может быть обобщена на задачи стохастического управления. Рассмотрим аналогичный вариант выше

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

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

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

где ${\mathcal {A}}$ представляет оператор стохастического дифференцирования и подчиняется терминальному условию

V(x,T)=D(x)\,\!.

Обратите внимание, что случайность исчезла. В этом случае решение $V\,\!$ Последнее не обязательно решает основную проблему, это всего лишь кандидат, и требуется дальнейший подтверждающий аргумент. Этот метод широко используется в финансовой математике для определения оптимальных инвестиционных стратегий на рынке (см., например, задачу портфеля Мертона ).

Приложение к LQG-Control

В качестве примера мы можем рассмотреть систему с линейной стохастической динамикой и квадратичной стоимостью. Если динамика системы определяется выражением

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

и стоимость накапливается со скоростью $C(x_{t},u_{t})=r(t)u_{t}^{2}/2+q(t)x_{t}^{2}/2$ уравнение HJB имеет вид

-{\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}}}.

с оптимальным действием, заданным

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

Принимая квадратичную форму функции цены, мы получаем обычное уравнение Риккати для гессиана функции цены, как обычно для линейно-квадратично-гауссовского управления .

См. также

Уравнение Беллмана , аналог уравнения Гамильтона – Якоби – Беллмана в дискретном времени.
Принцип максимума Понтрягина , необходимое, но не достаточное условие оптимума, путем максимизации гамильтониана , но он имеет преимущество перед HJB, поскольку его необходимо соблюдать только для одной рассматриваемой траектории.

Ссылки

^ Кирк, Дональд Э. (1970). Теория оптимального управления: Введение . Энглвуд Клиффс, Нью-Джерси: Прентис-Холл. стр. 86–90. ISBN 0-13-638098-0 .
^ Ён, Джионгмин; Чжоу, Сюнь Юй (1999). «Динамическое программирование и уравнения HJB» . Стохастические управления: гамильтоновы системы и уравнения HJB . Спрингер. стр. 157–215 [с. 163]. ISBN 0-387-98723-1 .
^ Найду, Десинени С. (2003). «Уравнение Гамильтона – Якоби – Беллмана» . Оптимальные системы управления . Бока-Ратон: CRC Press. стр. 277–283 [с. 280]. ISBN 0-8493-0892-5 .
^ Беллман, Р.Э. (1954). «Динамическое программирование и новый формализм в вариационном исчислении» . Учеб. Натл. акад. наук. 40 (4): 231–235. Бибкод : 1954PNAS...40..231B . дои : 10.1073/pnas.40.4.231 . ПМК 527981 . ПМИД 16589462 .
^ Беллман, Р.Э. (1957). Динамическое программирование . Принстон, Нью-Джерси: Издательство Принстонского университета.
^ Беллман, Р.; Дрейфус, С. (1959). «Применение динамического программирования для определения оптимальных траекторий спутников». Дж. Бр. Интерпланета. Соц . 17 : 78–83.
^ Кальман, Рудольф Э. (1963). «Теория оптимального управления и вариационное исчисление». В Беллмане, Ричарде (ред.). Методы математической оптимизации . Беркли: Издательство Калифорнийского университета. стр. 309–331. ОСЛК 1033974 .
^ Кемажу-Браун, Изабель (2016). «Краткая история теории оптимального управления и некоторые недавние разработки». В Будбане, Григорий; Хьюз, Гарри Рэндольф; Шурц, Анри (ред.). Вероятность в алгебраических и геометрических структурах . Современная математика. Том. 668. стр. 119–130. дои : 10.1090/conm/668/13400 . ISBN 9781470419455 .
^ Чанг, Фву-Ранк (2004). Стохастическая оптимизация в непрерывном времени . Кембридж, Великобритания: Издательство Кембриджского университета. стр. 113–168. ISBN 0-521-83406-6 .
^ Барди, Мартино; Капуццо-Дольчетта, Итало (1997). Оптимальное управление и вязкостные решения уравнений Гамильтона–Якоби–Беллмана . Бостон: Биркхойзер. ISBN 0-8176-3640-4 .
^ Льюис, Фрэнк Л.; Врабие, Драгуна; Сирмос, Василис Л. (2012). Оптимальное управление (3-е изд.). Уайли. п. 278. ИСБН 978-0-470-63349-6 .
^ Берцекас, Дмитрий П. (2005). Динамическое программирование и оптимальное управление . Афина Сайентифик.
^ Барди, Мартино; Капуццо-Дольчетта, Итало (1997). Оптимальное управление и вязкостные решения уравнений Гамильтона-Якоби-Беллмана . Бостон: Биркхойзер. ISBN 0-8176-3640-4 .
^ Берцекас, Дмитрий П.; Цициклис, Джон Н. (1996). Нейродинамическое программирование . Афина Сайентифик. ISBN 978-1-886529-10-6 .
^ Абу-Халаф, Мурад; Льюис, Фрэнк Л. (2005). «Почти оптимальные законы управления для нелинейных систем с насыщающими приводами с использованием подхода нейронной сети HJB». Автоматика . 41 (5): 779–791. дои : 10.1016/j.automatica.2004.11.034 . S2CID 14757582 .
^ Аль-Тамими, Асма; Льюис, Фрэнк Л.; Абу-Халаф, Мурад (2008). «Нелинейное решение HJB с дискретным временем с использованием приближенного динамического программирования: доказательство сходимости». Транзакции IEEE о системах, человеке и кибернетике. Часть B: Кибернетика . 38 (4): 943–949. дои : 10.1109/TSMCB.2008.926614 . ПМИД 18632382 . S2CID 14202785 .
^ Джонс, Морган; Пит, Мэтью (2020). «Полиномиальная аппроксимация функций значения и проектирование нелинейных контроллеров с оценками производительности». arXiv : 2010.06828 [ math.OC ].

Дальнейшее чтение

Берцекас, Дмитрий П. (2005). Динамическое программирование и оптимальное управление . Афина Сайентифик.
Фам, Хуен (2009). «Классический подход PDE к динамическому программированию» . Стохастический контроль и оптимизация в непрерывном времени с помощью финансовых приложений . Спрингер. стр. 37–60. ISBN 978-3-540-89499-5 .
Стенгель, Роберт Ф. (1994). «Условия оптимальности» . Оптимальное управление и оценка . Нью-Йорк: Дувр. стр. 201–222. ISBN 0-486-68200-5 .

[1] Кирк, Дональд Э. (1970). Теория оптимального управления: Введение . Энглвуд Клиффс, Нью-Джерси: Прентис-Холл. стр. 86–90. ISBN 0-13-638098-0 .

[2] Ён, Джионгмин; Чжоу, Сюнь Юй (1999). «Динамическое программирование и уравнения HJB» . Стохастические управления: гамильтоновы системы и уравнения HJB . Спрингер. стр. 157–215 [с. 163]. ISBN 0-387-98723-1 .

[3] Найду, Десинени С. (2003). «Уравнение Гамильтона – Якоби – Беллмана» . Оптимальные системы управления . Бока-Ратон: CRC Press. стр. 277–283 [с. 280]. ISBN 0-8493-0892-5 .

[4] Беллман, Р.Э. (1954). «Динамическое программирование и новый формализм в вариационном исчислении» . Учеб. Натл. акад. наук. 40 (4): 231–235. Бибкод : 1954PNAS...40..231B . дои : 10.1073/pnas.40.4.231 . ПМК 527981 . ПМИД 16589462 .

[5] Беллман, Р.Э. (1957). Динамическое программирование . Принстон, Нью-Джерси: Издательство Принстонского университета.

[6] Беллман, Р.; Дрейфус, С. (1959). «Применение динамического программирования для определения оптимальных траекторий спутников». Дж. Бр. Интерпланета. Соц . 17 : 78–83.

[7] Кальман, Рудольф Э. (1963). «Теория оптимального управления и вариационное исчисление». В Беллмане, Ричарде (ред.). Методы математической оптимизации . Беркли: Издательство Калифорнийского университета. стр. 309–331. ОСЛК 1033974 .

[8] Кемажу-Браун, Изабель (2016). «Краткая история теории оптимального управления и некоторые недавние разработки». В Будбане, Григорий; Хьюз, Гарри Рэндольф; Шурц, Анри (ред.). Вероятность в алгебраических и геометрических структурах . Современная математика. Том. 668. стр. 119–130. дои : 10.1090/conm/668/13400 . ISBN 9781470419455 .

[9] Чанг, Фву-Ранк (2004). Стохастическая оптимизация в непрерывном времени . Кембридж, Великобритания: Издательство Кембриджского университета. стр. 113–168. ISBN 0-521-83406-6 .

[10] Барди, Мартино; Капуццо-Дольчетта, Итало (1997). Оптимальное управление и вязкостные решения уравнений Гамильтона–Якоби–Беллмана . Бостон: Биркхойзер. ISBN 0-8176-3640-4 .

[11] Льюис, Фрэнк Л.; Врабие, Драгуна; Сирмос, Василис Л. (2012). Оптимальное управление (3-е изд.). Уайли. п. 278. ИСБН 978-0-470-63349-6 .

[12] Берцекас, Дмитрий П. (2005). Динамическое программирование и оптимальное управление . Афина Сайентифик.

[13] Барди, Мартино; Капуццо-Дольчетта, Итало (1997). Оптимальное управление и вязкостные решения уравнений Гамильтона-Якоби-Беллмана . Бостон: Биркхойзер. ISBN 0-8176-3640-4 .

[NeuroDynProg-14] Берцекас, Дмитрий П.; Цициклис, Джон Н. (1996). Нейродинамическое программирование . Афина Сайентифик. ISBN 978-1-886529-10-6 .

[CTHJB-15] Абу-Халаф, Мурад; Льюис, Фрэнк Л. (2005). «Почти оптимальные законы управления для нелинейных систем с насыщающими приводами с использованием подхода нейронной сети HJB». Автоматика . 41 (5): 779–791. дои : 10.1016/j.automatica.2004.11.034 . S2CID 14757582 .

[DTHJB-16] Аль-Тамими, Асма; Льюис, Фрэнк Л.; Абу-Халаф, Мурад (2008). «Нелинейное решение HJB с дискретным временем с использованием приближенного динамического программирования: доказательство сходимости». Транзакции IEEE о системах, человеке и кибернетике. Часть B: Кибернетика . 38 (4): 943–949. дои : 10.1109/TSMCB.2008.926614 . ПМИД 18632382 . S2CID 14202785 .

[17] Джонс, Морган; Пит, Мэтью (2020). «Полиномиальная аппроксимация функций значения и проектирование нелинейных контроллеров с оценками производительности». arXiv : 2010.06828 [ math.OC ].

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]