Уравнение Беллмана

Уравнение Беллмана (также уравнение динамического программирования) — достаточное условие оптимальности в методах оптимизации динамического программирования, названное в честь Ричарда Эрнста Беллмана и основывающееся на принципе оптимальности Беллмана.

Описание

Уравнение Беллмана представляет собой дифференциальное уравнение в частных производных с начальными условиями, заданными для последнего момента времени (то есть справа), для функции Беллмана, которая выражает минимальное значение критерия оптимизации, которое может быть достигнуто, при условии эволюции системы из текущего состояния в некоторое конечное. А это в свою очередь позволяет перейти от решения исходной многошаговой задачи оптимизации к последовательному решению нескольких одношаговых задач оптимизации.

Понятие уравнения Беллмана и функции Беллмана обычно применяется для непрерывных систем. Для дискретных систем аналогом выступает рекуррентное соотношение Беллмана. Принцип оптимальности (см. ниже) позволяет в этом случае оптимальное планирование от конца к началуШаблон:Sfn.

Формальные соотношения, выражающие достаточное условия оптимальности как для дискретных, так и для непрерывных систем могут быть записаны как для случая детерминированных, так и для случая стохастических динамических систем общего вида. Отличие заключается лишь в том, что для случая стохастических систем в правых частях этих выражений возникает условное математическое ожидание.

В контексте решения задачи оптимального управления можно выделить два подхода: численный и аналитический. Численный подход основан на использовании вычислительных процедур динамического программирования, в то время как аналитический подход связан с решением уравнения Беллмана. То есть, нелинейного уравнения в частных производных, которое имеет аналитическое решение лишь в простейших случаяхШаблон:Sfn.

Принцип оптимальности

Принцип оптимальности, подходящий как для непрерывных, так и дискретных систем является основополагающим в теории управления. Две формулировкиШаблон:Sfn:

Шаблон:Цитата

Указанное свойство можно сравнить с соответствующим свойством марковского процесса Шаблон:Sfn.

Шаблон:Цитата

Как следствие этого, оптимальное управление зависит только от текущего состояния системы. Последствия неоптимального управления в прошлом не могут быть исправлены в будущемШаблон:Sfn.

Согласно принципу оптимальности, оптимальная стратегия гарантирует, что после первого решения последующие решения будут оптимальными относительно нового состояния, полученного в результате первоначального решения, независимо от начального состояния и начального решенияШаблон:Sfn.

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

Модель системы и управления

Рассмотрим уравнение состояния управляемой динамической системы Шаблон:Sfn:

\dot{x} (t) = f (t, x (t), u (t))

,

где:

t

— время из интервала времени функционирования системы

t \in T = [t_{0}, t_{1}]

,

x

— вектор-функция состояния системы из пространства состояний (n-мерного евклидова пространства,

ℝ^{n}

),

u

— вектор-функция управления со значениями из пространства управлений

U \subseteq ℝ^{n}

,

f

— вектор-функция системы

T \times ℝ^{n} \times U \to ℝ^{n}

.

Для упрощения изложения требования к гладкости функций и другие нюансы здесь и далее опущены.

Вектор начальных условий:

x (t_{0}) = x_{0} \in ℝ^{n}

,

где $x_{0}$ не считается произвольным.

Определим функционал качества управления для минимизации:

I (x, u) = \int_{t_{0}}^{t_{1}} g (x (t), u (t), t) d t + F (x (t)),

где:

F

и

g

— заданные непрерывно дифференцируемые функции.

Для получения управления используется текущее время $t$ и состояние системы $x$ :

u (t) = u (t, x (t))

Задача оптимального управления состоит в том, чтобы найти такую функцию $u^{*} (t, x)$ , которая минимизирует $I (x, u)$ :

\forall x_{0} I (x^{*}, u^{*}) = \min_{D} I (x, u),

где:

(x^{*} (\cdot), u^{*} (\cdot)) = u^{*} (\cdot, x (\cdot))

,

D — множество допустимых управлений с учетом

t_{0}

и

x_{0}

, то есть, ограничение на возможные

(x (\cdot), u (\cdot))

.

Функция оптимального управления $u^{*} (t, x)$ для любого начального $x_{0}$ дает оптимальный процесс: оптимальное управление $u^{*} (\cdot)$ и оптимальную траекторию $x^{*} (\cdot)$ .