Уравнение беллмана - Bellman equation - Wikipedia

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

Уравнение Беллмана впервые было применено в технике. теория управления и другим темам прикладной математики, и впоследствии стал важным инструментом в экономическая теория; хотя основные концепции динамического программирования предустановлены в Джон фон Нейман и Оскар Моргенштерн с Теория игр и экономического поведения и Авраам Вальд с последовательный анализ.[нужна цитата ]

Практически любая проблема, которую можно решить с помощью теория оптимального управления также может быть решена путем анализа соответствующего уравнения Беллмана.[Почему? ][требуется дальнейшее объяснение ] Однако термин «уравнение Беллмана» обычно относится к уравнению динамического программирования, связанному с дискретное время проблемы оптимизации.[3] В задачах оптимизации с непрерывным временем аналогичным уравнением является уравнение в частных производных это называется Уравнение Гамильтона – Якоби – Беллмана..[4][5]

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

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

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

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

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

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

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

Вывод

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

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

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

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

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

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

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

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

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

Как было предложено принцип оптимальности, мы рассмотрим первое решение отдельно, отложив в сторону все будущие решения (мы начнем заново с момента 1 с новым состоянием ). Собирая будущие решения в скобки справа, указанная выше задача принятия решений с бесконечным горизонтом эквивалентна:[требуется разъяснение ]

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

Здесь мы выбираем , зная, что наш выбор приведет к тому, что состояние времени 1 станет . Это новое состояние затем повлияет на проблему принятия решения с момента 1. Вся проблема будущего решения отображается в квадратных скобках справа.[требуется разъяснение ][требуется дальнейшее объяснение ]

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

Пока что кажется, что мы только усугубили проблему, отделив сегодняшнее решение от будущих решений. Но мы можем упростить, заметив, что внутри квадратных скобок справа находится Значение времени 1 проблема решения, начиная с состояния .

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

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

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

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

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

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

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

при условии

и

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

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

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

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

Ожидание берется относительно соответствующей вероятностной меры, заданной Q на последовательности р с. Потому что р управляется марковским процессом, динамическое программирование значительно упрощает задачу. Тогда уравнение Беллмана просто:

При некотором разумном предположении результирующая оптимальная функция политики грамм(а,р) является измеримый.

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

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

  • В метод неопределенных коэффициентов, также известный как «угадай и проверь», можно использовать для решения некоторого бесконечного горизонта, автономный Уравнения Беллмана.[9]
  • Уравнение Беллмана может быть решено с помощью обратная индукция, либо аналитически в некоторых особых случаях или численно на компьютере. Числовая обратная индукция применима к широкому кругу задач, но может оказаться невыполнимой, когда есть много переменных состояния из-за проклятие размерности. Приближенное динамическое программирование было введено Д. П. Бертсекас и Я. Н. Цициклис с использованием искусственные нейронные сети (многослойные персептроны ) для аппроксимации функции Беллмана.[10] Это эффективная стратегия смягчения последствий для уменьшения влияния размерности за счет замены запоминания полного отображения функций для всего пространственного домена запоминанием отдельных параметров нейронной сети. В частности, для систем с непрерывным временем был представлен приближенный подход динамического программирования, сочетающий обе итерации политики с нейронными сетями.[11] В дискретном времени был представлен подход к решению уравнения HJB, объединяющий итерации значений и нейронные сети.[12]
  • Вычислив условия первого порядка, связанные с уравнением Беллмана, а затем используя теорема о конверте чтобы исключить производные функции цены, можно получить систему разностные уравнения или же дифференциальные уравнения называется 'Уравнения Эйлера '.[13] Стандартные методы решения разностных или дифференциальных уравнений затем могут использоваться для расчета динамики переменных состояния и управляющих переменных задачи оптимизации.

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

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

Известное экономическое приложение уравнения Беллмана: Роберт С. Мертон основополагающая статья 1973 г. модель межвременного ценообразования капитальных активов.[15] (Смотрите также Проблема портфеля Мертона Решение теоретической модели Мертона, в которой инвесторы выбирают между доходом сегодня и будущим доходом или приростом капитала, является формой уравнения Беллмана. Поскольку экономические приложения динамического программирования обычно приводят к уравнению Беллмана, которое является разностное уравнение, экономисты называют динамическое программирование "рекурсивным методом" и подполе рекурсивная экономика теперь признано в экономической науке.

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

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

Пример

В Марковские процессы принятия решений, уравнение Беллмана - это рекурсия за ожидаемые награды. Например, ожидаемая награда за нахождение в определенном состоянии. s и следуя некоторой фиксированной политике имеет уравнение Беллмана:

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

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

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

Смотрите также

Рекомендации

  1. ^ Диксит, Авинаш К. (1990). Оптимизация в экономической теории (2-е изд.). Издательство Оксфордского университета. п. 164. ISBN  0-19-877211-4.
  2. ^ Кирк, Дональд Э. (1970). Теория оптимального управления: введение. Прентис-Холл. п. 55. ISBN  0-13-638098-0.
  3. ^ Кирк 1970, п.70
  4. ^ Камиен, Мортон И.; Шварц, Нэнси Л. (1991). Динамическая оптимизация: вариационный расчет и оптимальное управление в экономике и менеджменте (Второе изд.). Амстердам: Эльзевир. п. 261. ISBN  0-444-01609-0.
  5. ^ Кирк 1970, п.88
  6. ^ а б c Беллман, Р. (2003) [1957]. Динамическое программирование. Дувр. ISBN  0-486-42809-5.
  7. ^ а б Дрейфус, С. (2002). «Ричард Беллман о рождении динамического программирования». Исследование операций. 50 (1): 48–51. Дои:10.1287 / opre.50.1.48.17791.
  8. ^ Беллман, Р. (август 1952 г.). «К теории динамического программирования». Proc Natl Acad Sci U S A. 38 (8): 716–9. Дои:10.1073 / pnas.38.8.716. ЧВК  1063639. PMID  16589166.
  9. ^ Юнгквист, Ларс; Сарджент, Томас Дж. (2004). Рекурсивная макроэкономическая теория (2-е изд.). MIT Press. стр.88 –90. ISBN  0-262-12274-X.
  10. ^ Bertsekas, Dimitri P .; Цициклис, Джон Н. (1996). Нейродинамическое программирование. Athena Scientific. ISBN  978-1-886529-10-6.
  11. ^ Абу-Халаф, Мурад; Льюис, Фрэнк Л. (2005). «Почти оптимальные законы управления для нелинейных систем с насыщающими исполнительными механизмами с использованием подхода нейронной сети HJB». Automatica. 41 (5): 779–791. Дои:10.1016 / j.automatica.2004.11.034.
  12. ^ Аль-Тамими, Асма; Льюис, Фрэнк Л .; Абу-Халаф, Мурад (2008). «Решение нелинейного HJB с дискретным временем с использованием приближенного динамического программирования: доказательство сходимости». IEEE Transactions по системам, человеку и кибернетике, часть B (кибернетика). 38 (4): 943–949. Дои:10.1109 / TSMCB.2008.926614.
  13. ^ Мяо, Цзяньцзюнь (2014). Экономическая динамика в дискретном времени. MIT Press. п. 134. ISBN  978-0-262-32560-8.
  14. ^ Бекманн, Мартин; Мут, Ричард (1954). «О решении« фундаментального уравнения »теории запасов» (PDF). Документ для обсуждения комиссии Коулза 2116.
  15. ^ Мертон, Роберт С. (1973). «Модель межвременного ценообразования капитальных активов». Econometrica. 41 (5): 867–887. Дои:10.2307/1913811. JSTOR  1913811.
  16. ^ Стоки, Нэнси; Лукас, Роберт Э .; Прескотт, Эдвард (1989). Рекурсивные методы в экономической динамике. Издательство Гарвардского университета. ISBN  0-674-75096-9.
  17. ^ Юнгквист, Ларс; Сарджент, Томас (2012). Рекурсивная макроэкономическая теория (3-е изд.). MIT Press. ISBN  978-0-262-01874-6.
  18. ^ Диксит, Авинаш; Пиндик, Роберт (1994). Инвестиции в условиях неопределенности. Издательство Принстонского университета. ISBN  0-691-03410-9.
  19. ^ Андерсон, Патрик Л. (2004). «Глава 10». Бизнес-экономика и финансы. CRC Press. ISBN  1-58488-348-0.
    - (2009). «Значение частного бизнеса в Соединенных Штатах». Экономика бизнеса. 44 (2): 87–108. Дои:10.1057 / be.2009.4. S2CID  154743445.
    — (2013). Экономика оценки бизнеса. Stanford University Press. ISBN  9780804758307. Стэнфорд Пресс В архиве 2013-08-08 в Wayback Machine
  20. ^ Миранда, Марио Дж .; Факлер, Пол Л. (2004). Прикладная вычислительная экономика и финансы. MIT Press. ISBN  978-0-262-29175-0.
  21. ^ Мейн, Шон (2008). Методы управления сложными сетями. Издательство Кембриджского университета. ISBN  978-0-521-88441-9. Приложение содержит сокращенный Мейн и Твиди В архиве 2007-10-12 на Wayback Machine.