Русская Википедия:Уравнение Беллмана

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

Описание

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

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

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

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

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

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

«	Если управление оптимально, то, каковы бы ни были первоначальное состояние системы и управление системой в начальный момент времени, последующее управление оптимально относительно состояния, которое система примет в результате начального управления.	»
— Анонимус

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

«	Оптимальное управление в любой момент времени не зависит от предыстории системы и определяется только состоянием системы в этот момент и целью управления.	»
— Анонимус

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

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

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

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

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

<math>\dot{x}(t) = f(t, x(t), u(t))</math>,

где:

<math>t</math> — время из интервала времени функционирования системы <math>t \in T = [t_0, t_1]</math>,

<math>x</math> — вектор-функция состояния системы из пространства состояний (n-мерного евклидова пространства, <math>\mathbb R^n</math>),

<math>u</math> — вектор-функция управления со значениями из пространства управлений <math>U \subseteq \mathbb R^n</math>,

<math>f</math> — вектор-функция системы <math>T \times \mathbb R^n \times U \to \mathbb R^n</math>.

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

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

<math>x(t_0) = x_0 \in \mathbb R^n</math>,

где <math>x_0</math> не считается произвольным.

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

<math>I(x, u) = \int_{t_0}^{t_1}g(x(t), u(t), t) dt + F(x(t)),</math>

где:

<math>F</math> и <math>g</math> — заданные непрерывно дифференцируемые функции.

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

<math>u(t) = u(t, x(t))</math>

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

<math>\forall x_0\quad I(x^*, u^*) = \min_D I(x, u),</math>

где:

<math>(x^*(\cdot), u^*(\cdot)) = u^*(\cdot, x(\cdot))</math>,

D — множество допустимых управлений с учетом <math>t_0</math> и <math>x_0</math>, то есть, ограничение на возможные <math>(x(\cdot), u(\cdot))</math>.

Функция оптимального управления <math>u^*(t, x)</math> для любого начального <math>x_0</math> дает оптимальный процесс: оптимальное управление <math>u^*(\cdot)</math> и оптимальную траекторию <math>x^*(\cdot)</math>.

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

Если существует функция <math>\omega(t, x)</math>, непрерывно дифференцируемая по <math>t</math> и <math>x</math> на <math>(t_0, t_1) \times \mathbb R^n</math>, удовлетворяющая уравнению БеллманаШаблон:Sfn:

<math>\max\limits_{u \in U}\left[ \frac{\partial \omega(t, x)}{\partial t} + \frac{\partial \omega(t, x)}{\partial x} \cdot f(t, x, u) - g(t, x, u) \right] = 0</math>

и граничному условию

<math>\forall x \in \mathbb R^n\quad\omega(t_1, x) = -F(x)</math>,

то управление

<math>u^*(t, x) = \arg\max\limits_{u \in U}\left[ \frac{\partial \omega(t, x)}{\partial x} \cdot f(t, x, u) - g(t, x, u)\right]</math>,

является оптимальным управлением с полной обратной связью.

См. также

• Принцип максимума Понтрягина

Литература

• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга