stringtranslate.com

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

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

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

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

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

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

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

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

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

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

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

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

Вывод

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

при условии

и

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример

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

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

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

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

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

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

  1. ^ Диксит, Авинаш К. (1990). Оптимизация в экономической теории (2-е изд.). Издательство Оксфордского университета. п. 164. ИСБН 0-19-877211-4.
  2. ^ «Принцип оптимальности Беллмана». www.ques10.com . Проверено 17 августа 2023 г.
  3. ^ Кирк, Дональд Э. (1970). Теория оптимального управления: Введение. Прентис-Холл. п. 55. ИСБН 0-13-638098-0.
  4. ^ Щесняк, Иренеуш; Возна-Щесняк, Божена (2023), «Общая Дейкстра: корректность и управляемость», NOMS 2023-2023 Симпозиум по сетевым операциям и управлению IEEE/IFIP , стр. 1–7, arXiv : 2204.13547 , doi : 10.1109/NOMS56928.2023.10154 322, ISBN 978-1-6654-7716-1, S2CID  248427020
  5. ^ Кирк 1970, с. 70
  6. ^ Камен, Мортон И .; Шварц, Нэнси Л. (1991). Динамическая оптимизация: вариационное исчисление и оптимальное управление в экономике и менеджменте (второе изд.). Амстердам: Эльзевир. п. 261. ИСБН 0-444-01609-0.
  7. ^ Кирк 1970, с. 88
  8. ^ Джонс, Морган; Пит, Мэтью М. (2020). «Расширения структуры динамического программирования: планирование использования батарей, плата за спрос и интеграция возобновляемых источников энергии». Транзакции IEEE при автоматическом управлении . 66 (4): 1602–1617. arXiv : 1812.00792 . дои : 10.1109/TAC.2020.3002235. S2CID  119622206.
  9. ^ Джонс, Морган; Пит, Мэтью М. (2021). «Обобщение уравнения Беллмана с применением к планированию пути, предотвращению препятствий и оценке инвариантного набора». Автоматика . 127 : 109510. arXiv : 2006.08175 . doi : 10.1016/j.automatica.2021.109510. S2CID  222350370.
  10. ^ abc Bellman, RE (2003) [1957]. Динамическое программирование . Дувр. ISBN 0-486-42809-5.
  11. ^ аб Дрейфус, С. (2002). «Ричард Беллман о рождении динамического программирования». Исследование операций . 50 (1): 48–51. дои : 10.1287/opre.50.1.48.17791.
  12. ^ Беллман, 1957, гл. III.2.
  13. ^ Беллман, Р. (август 1952 г.). «К теории динамического программирования». Proc Natl Acad Sci США . 38 (8): 716–9. Бибкод : 1952PNAS...38..716B. дои : 10.1073/pnas.38.8.716 . ПМЦ 1063639 . ПМИД  16589166. 
  14. ^ Юнгквист, Ларс; Сарджент, Томас Дж. (2004). Рекурсивная макроэкономическая теория (2-е изд.). МТИ Пресс. стр. 88–90. ISBN 0-262-12274-Х.
  15. ^ Берцекас, Дмитрий П.; Цициклис, Джон Н. (1996). Нейродинамическое программирование . Афина Сайентифик. ISBN 978-1-886529-10-6.
  16. ^ Абу-Халаф, Мурад; Льюис, Фрэнк Л. (2005). «Почти оптимальные законы управления для нелинейных систем с насыщающими приводами с использованием подхода нейронной сети HJB». Автоматика . 41 (5): 779–791. doi :10.1016/j.automatica.2004.11.034. S2CID  14757582.
  17. ^ Аль-Тамими, Асма; Льюис, Фрэнк Л.; Абу-Халаф, Мурад (2008). «Нелинейное решение HJB с дискретным временем с использованием приближенного динамического программирования: доказательство сходимости». Транзакции IEEE о системах, человеке и кибернетике. Часть B: Кибернетика . 38 (4): 943–949. дои : 10.1109/TSMCB.2008.926614. PMID  18632382. S2CID  14202785.
  18. ^ Мяо, Цзяньцзюнь (2014). Экономическая динамика в дискретном времени. МТИ Пресс. п. 134. ИСБН 978-0-262-32560-8.
  19. ^ Бекманн, Мартин; Мут, Ричард (1954). «О решении «фундаментального уравнения» теории запасов» (PDF) . Документ для обсуждения Комиссии Коулза 2116 .
  20. ^ Мертон, Роберт С. (1973). «Межвременная модель ценообразования капитальных активов». Эконометрика . 41 (5): 867–887. дои : 10.2307/1913811. JSTOR  1913811.
  21. ^ Стоки, Нэнси; Лукас, Роберт Э.; Прескотт, Эдвард (1989). Рекурсивные методы в экономической динамике . Издательство Гарвардского университета. ISBN 0-674-75096-9.
  22. ^ Юнгквист, Ларс; Сарджент, Томас (2012). Рекурсивная макроэкономическая теория (3-е изд.). МТИ Пресс. ISBN 978-0-262-01874-6.
  23. ^ Диксит, Авинаш; Пиндик, Роберт (1994). Инвестиции в условиях неопределенности . Издательство Принстонского университета. ISBN 0-691-03410-9.
  24. ^ Андерсон, Патрик Л. (2004). «Гл. 10». Экономика бизнеса и финансы . ЦРК Пресс. ISBN 1-58488-348-0.
    - (2009). «Ценность частного бизнеса в Соединенных Штатах». Экономика бизнеса . 44 (2): 87–108. дои :10.1057/be.2009.4. S2CID  154743445.
    - (2013). Экономика оценки бизнеса . Издательство Стэнфордского университета. ISBN 9780804758307.Stanford Press. Архивировано 8 августа 2013 г. в Wayback Machine.
  25. ^ Миранда, Марио Дж.; Факлер, Пол Л. (2004). Прикладная вычислительная экономика и финансы . МТИ Пресс. ISBN 978-0-262-29175-0.
  26. ^ Мейн, Шон (2008). Методы управления сложными сетями. Издательство Кембриджского университета. ISBN 978-0-521-88441-9. Приложение содержит сокращенные версии Meyn & Tweedie, заархивированные 12 октября 2007 г. в Wayback Machine .