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

Блок-схема Беллмана.

Уравнение Беллмана , названное в честь Ричарда Э. Беллмана , является необходимым условием оптимальности, связанной с методом математической оптимизации, известным как динамическое программирование . Он описывает «ценность» проблемы принятия решения в определенный момент времени с точки зрения выигрыша от некоторых первоначальных выборов и «ценности» оставшейся проблемы принятия решений, возникающей в результате этих первоначальных выборов. Это разбивает задачу динамической оптимизации на последовательность более простых подзадач, как предписывает «принцип оптимальности» Беллмана. Уравнение применимо к алгебраическим структурам с полным упорядочением; для алгебраических структур с частичным упорядочением можно использовать общее уравнение Беллмана.

Уравнение Беллмана было впервые применено к инженерной теории управления и к другим темам прикладной математики и впоследствии стало важным инструментом экономической теории ; хотя основные концепции динамического программирования заложены в Джона фон Неймана и Оскара Моргенштерна, » «Теории игр и экономического поведения а также Абрахама Вальда в последовательном анализе . Термин «уравнение Беллмана» обычно относится к уравнению динамического программирования (DPE), связанному с задачами оптимизации дискретного времени . В задачах оптимизации с непрерывным временем аналогичное уравнение представляет собой уравнение в частных производных , которое называется уравнением Гамильтона – Якоби – Беллмана .

Любую задачу многоэтапной оптимизации можно решить в дискретное время путем анализа соответствующего уравнения Беллмана. Соответствующее уравнение Беллмана можно найти, вводя новые переменные состояния (приращение состояния). Однако результирующая задача многоэтапной оптимизации с дополненным состоянием имеет пространство состояний более высокой размерности, чем исходная задача многоэтапной оптимизации — проблема, которая потенциально может сделать расширенную задачу неразрешимой из-за « проклятия размерности ». В качестве альтернативы было показано, что если функция стоимости задачи многоэтапной оптимизации удовлетворяет структуре «обратного разделения», то подходящее уравнение Беллмана может быть найдено без увеличения состояния.

Аналитические концепции в динамическом программировании

Чтобы понять уравнение Беллмана, необходимо понять несколько основных концепций. Во-первых, любая задача оптимизации имеет некоторую цель: минимизировать время в пути, минимизировать затраты, максимизировать прибыль, максимизировать полезность и т. д. Математическая функция, описывающая эту цель, называется целевой функцией .

Динамическое программирование разбивает задачу многопериодного планирования на более простые этапы в разные моменты времени. Поэтому необходимо отслеживать, как ситуация принятия решения развивается с течением времени. Информация о текущей ситуации, необходимая для принятия правильного решения, называется «состоянием». Например, чтобы решить, сколько потреблять и тратить в каждый момент времени, людям необходимо знать (помимо прочего) свое первоначальное богатство. Следовательно, богатство $(W)$ будет одной из их переменных состояния , но, вероятно, будут и другие.

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

Подход динамического программирования описывает оптимальный план путем нахождения правила, определяющего, какими должны быть элементы управления при любом возможном значении состояния. Например, если потребление ( c ) зависит только от богатства ( W ), мы бы искали правило $c(W)$ что дает потребление как функцию богатства. Такое правило, определяющее средства контроля как функцию государств, называется функцией политики .

Наконец, по определению, оптимальное правило принятия решения — это то, которое достигает наилучшего возможного значения цели. Например, если кто-то выбирает потребление при наличии богатства, чтобы максимизировать счастье (при условии, что счастье H может быть представлено математической функцией, такой как функция полезности , и определяется богатством), тогда каждый уровень богатства будет связан с какой-то максимально возможный уровень счастья, $H(W)$. Наилучшее возможное значение цели, записанное как функция состояния, называется функцией ценности .

Беллман показал, что задачу динамической оптимизации в дискретное время можно сформулировать в рекурсивной , пошаговой форме, известной как обратная индукция, путем записи взаимосвязи между функцией ценности в один период и функцией ценности в следующий период. Связь между этими двумя функциями ценности называется «уравнением Беллмана». В этом подходе оптимальная политика в последний период времени определяется заранее как функция значения переменной состояния в этот момент, и результирующее оптимальное значение целевой функции, таким образом, выражается через это значение переменной состояния. Далее, оптимизация предпоследнего периода включает в себя максимизацию суммы целевой функции, специфичной для этого периода, и оптимального значения будущей целевой функции, придавая оптимальную политику этого периода в зависимости от значения переменной состояния на следующий период. решение о последнем периоде. Эта логика продолжается рекурсивно назад во времени, пока не будет получено решающее правило первого периода как функция значения переменной начального состояния путем оптимизации суммы целевой функции, специфичной для первого периода, и значения функции значения второго периода. который дает значение для всех будущих периодов. Таким образом, решение каждого периода принимается путем явного признания того, что все будущие решения будут приняты оптимально.

Вывод

Проблема динамического решения

Позволять $x_{t}$ быть государством в свое время $t$. Для решения, которое начинается в момент времени 0, примем за заданное начальное состояние $x_{0}$. В любой момент набор возможных действий зависит от текущего состояния; мы выражаем это как $a_{t}\in \Gamma (x_{t})$, где конкретное действие $a_{t}$ представляет конкретные значения для одной или нескольких управляющих переменных, и $\Gamma (x_{t})$ набор действий, доступных для выполнения в состоянии $x_{t}$. Предполагается также, что состояние меняется с $x$ в новое состояние $T(x,a)$ когда действие $a$ предпринимается, и что текущий выигрыш от совершения действия $a$ в штате $x$ является $F(x,a)$. Наконец, мы предполагаем нетерпение, представленное коэффициентом дисконтирования. $0<\beta <1$.

При этих предположениях задача принятия решения на бесконечном горизонте принимает следующую форму:

$V(x_{0})\;=\;\max _{\left\{a_{t}\right\}_{t=0}^{\infty }}\sum _{t=0}^{\infty }\beta ^{t}F(x_{t},a_{t}),$

с учетом ограничений

$a_{t}\in \Gamma (x_{t}),\;x_{t+1}=T(x_{t},a_{t}),\;\forall t=0,1,2,\dots$

Обратите внимание, что мы определили обозначение $V(x_{0})$ для обозначения оптимального значения, которое может быть получено путем максимизации этой целевой функции с учетом предполагаемых ограничений. Эта функция является функцией значения . Это функция переменной начального состояния $x_{0}$, поскольку наилучшее достижимое значение зависит от начальной ситуации.

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

Метод динамического программирования разбивает эту проблему решения на более мелкие подзадачи. Беллмана Принцип оптимальности описывает, как это сделать:

Принцип оптимальности: Оптимальная политика обладает тем свойством, что какими бы ни были начальное состояние и начальное решение, остальные решения должны составлять оптимальную политику относительно состояния, возникшего в результате первого решения. (См. Bellman, 1957, гл. III.3.)

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

Как предполагает принцип оптимальности , мы будем рассматривать первое решение отдельно, отложив в сторону все будущие решения (начнем заново с момента 1 с новым состоянием $x_{1}$). Если собрать будущие решения в скобках справа, описанная выше проблема принятия решений на бесконечном горизонте эквивалентна:

$\max _{a_{0}}\left\{F(x_{0},a_{0})+\beta \left[\max _{\left\{a_{t}\right\}_{t=1}^{\infty }}\sum _{t=1}^{\infty }\beta ^{t-1}F(x_{t},a_{t}):a_{t}\in \Gamma (x_{t}),\;x_{t+1}=T(x_{t},a_{t}),\;\forall t\geq 1\right]\right\}$

с учетом ограничений

$a_{0}\in \Gamma (x_{0}),\;x_{1}=T(x_{0},a_{0}).$

Вот мы выбираем $a_{0}$, зная, что наш выбор приведет к тому, что состояние времени 1 будет $x_{1}=T(x_{0},a_{0})$. Это новое состояние затем повлияет на проблему решения с момента 1. Вся проблема будущего решения отображается внутри квадратных скобок справа.

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

До сих пор кажется, что мы только усугубили проблему, отделив сегодняшнее решение от будущих решений. Но мы можем упростить, заметив, что внутри квадратных скобок справа находится значение задачи решения за время 1, начиная с состояния $x_{1}=T(x_{0},a_{0})$.

Следовательно, задачу можно переписать как рекурсивное определение функции ценности:

$V(x_{0})=\max _{a_{0}}\{F(x_{0},a_{0})+\beta V(x_{1})\}$, с учетом ограничений: $a_{0}\in \Gamma (x_{0}),\;x_{1}=T(x_{0},a_{0}).$

Это уравнение Беллмана. Это можно упростить еще больше, если отбросить индексы времени и подключить значение следующего состояния:

$V(x)=\max _{a\in \Gamma (x)}\{F(x,a)+\beta V(T(x,a))\}.$

Уравнение Беллмана классифицируется как функциональное уравнение , поскольку его решение означает нахождение неизвестной функции. $V$, что является функцией значения . Напомним, что функция ценности описывает наилучшую возможную ценность цели как функцию состояния. $x$. Вычислив функцию цены, мы также найдем функцию $a(x)$ который описывает оптимальное действие как функцию состояния; это называется функцией политики .

В стохастической задаче

См. Также: Марковский процесс принятия решений

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

В качестве конкретного примера из экономики рассмотрим бесконечно живущего потребителя с начальным запасом богатства. ${\color {Red}a_{0}}$ в период $0$. Они имеют мгновенную функцию полезности. $u(c)$ где $c$ обозначает потребление и дисконтирует полезность следующего периода по ставке $0<\beta <1$. Предположим, что то, что не потреблено за период $t$ переносится на следующий период с процентной ставкой $r$. Тогда задача максимизации полезности потребителя состоит в выборе плана потребления. $\{{\color {OliveGreen}c_{t}}\}$ это решает

$\max \sum _{t=0}^{\infty }\beta ^{t}u({\color {OliveGreen}c_{t}})$

при условии

${\color {Red}a_{t+1}}=(1+r)({\color {Red}a_{t}}-{\color {OliveGreen}c_{t}}),\;{\color {OliveGreen}c_{t}}\geq 0,$

и

$\lim _{t\rightarrow \infty }{\color {Red}a_{t}}\geq 0.$

Первое ограничение — это накопление капитала/закон движения, заданный задачей, а второе ограничение — это условие трансверсальности , согласно которому потребитель не несет долгов в конце своей жизни. Уравнение Беллмана

$V(a)=\max _{0\leq c\leq a}\{u(c)+\beta V((1+r)(a-c))\},$

В качестве альтернативы можно решить проблему последовательности напрямую, используя, например, уравнения Гамильтона .

Теперь, если процентная ставка меняется от периода к периоду, потребитель сталкивается с проблемой стохастической оптимизации. Пусть проценты r следуют марковскому процессу с вероятностной функцией перехода $Q(r,d\mu _{r})$ где $d\mu _{r}$ обозначает вероятностную меру, определяющую распределение процентной ставки в следующем периоде, если текущая процентная ставка равна $r$. В этой модели потребитель принимает решение о своем потреблении в текущем периоде после объявления процентной ставки текущего периода.

Вместо того, чтобы просто выбирать одну последовательность $\{{\color {OliveGreen}c_{t}}\}$, потребитель теперь должен выбрать последовательность $\{{\color {OliveGreen}c_{t}}\}$ для каждой возможной реализации $\{r_{t}\}$ таким образом, чтобы их ожидаемая полезность в течение всего срока службы была максимальной:

$\max _{\left\{c_{t}\right\}_{t=0}^{\infty }}\mathbb {E} {\bigg (}\sum _{t=0}^{\infty }\beta ^{t}u({\color {OliveGreen}c_{t}}){\bigg )}.$

Ожидание $\mathbb {E}$ берется относительно соответствующей вероятностной меры, заданной Q на последовательностях r ' s. Поскольку r управляется марковским процессом, динамическое программирование значительно упрощает задачу. Тогда уравнение Беллмана выглядит просто:

$V(a,r)=\max _{0\leq c\leq a}\{u(c)+\beta \int V((1+r)(a-c),r')Q(r,d\mu _{r})\}.$

При некоторых разумных предположениях результирующая оптимальная политическая функция g ( a , r ) измерима .

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

$V(x,z)=\max _{c\in \Gamma (x,z)}\{F(x,c,z)+\beta \int V(T(x,c),z')d\mu _{z}(z')\}.$

Методы решения

• Метод неопределенных коэффициентов , также известный как «угадай и проверь», можно использовать для решения некоторых автономных уравнений Беллмана с бесконечным интервалом времени.
• Уравнение Беллмана можно решить методом обратной индукции либо аналитически в некоторых особых случаях, либо численно на компьютере. Численная обратная индукция применима к широкому кругу задач, но может оказаться неосуществимой при наличии большого количества переменных состояния из-за проклятия размерности . Приближенное динамическое программирование было введено Д. П. Берцекасом и Ю. Н. Цициклисом с использованием искусственных нейронных сетей ( многослойных персептронов ) для аппроксимации функции Беллмана. Это эффективная стратегия смягчения воздействия размерности путем замены запоминания полного отображения функций для всей пространственной области запоминанием отдельных параметров нейронной сети. В частности, для систем с непрерывным временем был представлен подход приближенного динамического программирования, сочетающий обе итерации политики с нейронными сетями. В дискретном времени был представлен подход к решению уравнения HJB, сочетающий итерации значений и нейронные сети.
• Вычислив условия первого порядка, связанные с уравнением Беллмана, а затем используя теорему о конверте для исключения производных функции цены, можно получить систему разностных уравнений или дифференциальных уравнений, называемую « уравнениями Эйлера ». Затем можно использовать стандартные методы решения разностных или дифференциальных уравнений для расчета динамики переменных состояния и управляющих переменных задачи оптимизации.

Приложения в экономике

Первое известное применение уравнения Беллмана в экономике принадлежит Мартину Бекману и Ричарду Мут . Мартин Бекманн также много писал по теории потребления, используя уравнение Беллмана в 1959 году. Его работа, среди прочего, повлияла на Эдмунда С. Фелпса .

Знаменитым экономическим применением уравнения Беллмана является плодотворная статья Роберта К. Мертона 1973 года о межвременной модели ценообразования капитальных активов . (См. также проблему портфеля Мертона ). Решение теоретической модели Мертона, в которой инвесторы выбирают между сегодняшним доходом и будущим доходом или приростом капитала, представляет собой форму уравнения Беллмана. Поскольку экономические применения динамического программирования обычно приводят к уравнению Беллмана, которое является разностным уравнением , экономисты называют динамическое программирование «рекурсивным методом», и подобласть рекурсивной экономики теперь в экономической науке признается .

Нэнси Стоки , Роберт Э. Лукас и Эдвард Прескотт довольно подробно описывают стохастическое и нестохастическое динамическое программирование и разрабатывают теоремы существования решений проблем, удовлетворяющих определенным условиям. Они также описывают множество примеров моделирования теоретических проблем экономики с использованием рекурсивных методов. Эта книга привела к использованию динамического программирования для решения широкого спектра теоретических проблем в экономике, включая оптимальный экономический рост , добычу ресурсов , проблемы принципала и агента , государственные финансы , бизнес- инвестиции , ценообразование на активы , предложение факторов и промышленную организацию . Ларс Юнгквист и Томас Сарджент применяют динамическое программирование для изучения множества теоретических вопросов денежно-кредитной политики , налогово-бюджетной политики , налогообложения , экономического роста , теории поиска и экономики труда . Авинаш Диксит и Роберт Пиндик продемонстрировали ценность этого метода при планировании капитальных затрат . Андерсон адаптировал эту методику для оценки бизнеса, в том числе частного бизнеса.

Использование динамического программирования для решения конкретных задач осложняется информационными трудностями, такими как выбор ненаблюдаемой ставки дисконтирования. Существуют также вычислительные проблемы, главная из которых — это проклятие размерности, возникающее из-за огромного количества возможных действий и потенциальных переменных состояния, которые необходимо учитывать, прежде чем можно будет выбрать оптимальную стратегию. Подробное обсуждение вычислительных проблем см. в Miranda and Fackler, и Мейн 2007.

Пример

В марковских процессах принятия решений уравнение Беллмана представляет собой рекурсию для ожидаемых вознаграждений. Например, ожидаемое вознаграждение за пребывание в определенном состоянии и соблюдение некоторой фиксированной политики. $\pi$ имеет уравнение Беллмана:

$V^{\pi }(s)=R(s,\pi (s))+\gamma \sum _{s'}P(s'|s,\pi (s))V^{\pi }(s').\$

Это уравнение описывает ожидаемое вознаграждение за выполнение действия, предписанного некоторой политикой. $\pi$.

Уравнение оптимальной политики называется уравнением оптимальности Беллмана :

$V^{\pi *}(s)=\max _{a}\left\{{R(s,a)+\gamma \sum _{s'}P(s'|s,a)V^{\pi *}(s')}\right\}.\$

где ${\pi *}$ является оптимальной политикой и $V^{\pi *}$ относится к функции ценности оптимальной политики. Приведенное выше уравнение описывает вознаграждение за действие, дающее наибольшую ожидаемую прибыль.

См. также

• Псевдоспектральный метод Беллмана
• Динамическое программирование - метод оптимизации задачи
• Уравнение Гамильтона – Якоби – Беллмана - условие оптимальности в теории оптимального управления.
• Марковский процесс принятия решений – Математическая модель
• Теория оптимального управления - математический способ достижения желаемого результата динамической системы.
• Оптимальная подструктура - свойство вычислительной задачи.
• Рекурсивное конкурентное равновесие - концепция экономического равновесия, связанная с динамической программой. Страницы, отображающие описания викиданных в качестве запасного варианта.
• Стохастическое динамическое программирование - метод 1957 года для моделирования проблем принятия решений в условиях неопределенности.