Уравнение Беллмана , названное в честь Беллмана , является необходимым условием оптимальности , связанной с математической оптимизацией методой , известной как динамическое программирование . [1] Он записывает «ценность» проблемы решения в определенный момент времени в терминах выигрыша от некоторых начальных выборов и «ценности» оставшейся проблемы решения, которая является результатом этих первоначальных выборов. [ необходимая цитата ] Это разбивает задачу динамической оптимизации на последовательность более простых подзадач, как предписывает «принцип оптимальности» Беллмана . [2]
Уравнение Беллмана впервые было применено к инженерной теории управления и к другим темам прикладной математики, а впоследствии стало важным инструментом экономической теории ; хотя основные концепции динамического программирования прообразом в Джона фон Неймана и Оскара Моргенштерна «s Теория игр и экономическое поведение и Abraham Wald » s последовательного анализа . [ необходимая цитата ] Термин «уравнение Беллмана» обычно относится к уравнению динамического программирования, связанному с задачами оптимизации с дискретным временем . [3] В задачах оптимизации с непрерывным временем аналогичное уравнение является уравнением в частных производных , которое называется уравнением Гамильтона – Якоби – Беллмана . [4] [5]
В дискретном времени любая задача многоступенчатой оптимизации может быть решена путем анализа соответствующего уравнения Беллмана. Соответствующее уравнение Беллмана можно найти, введя новые переменные состояния (увеличение состояния). [6] Однако результирующая многоэтапная задача оптимизации с расширенным состоянием имеет пространство состояний более высокой размерности, чем исходная задача многоэтапной оптимизации - проблема, которая потенциально может сделать расширенную проблему неразрешимой из-за « проклятия размерности ». В качестве альтернативы было показано, что если функция стоимости многоступенчатой задачи оптимизации удовлетворяет «обратно разделяемой» структуре, то соответствующее уравнение Беллмана может быть найдено без увеличения состояния. [7]
Аналитические концепции в динамическом программировании
Чтобы понять уравнение Беллмана, необходимо понять несколько основных концепций. Во-первых, любая задача оптимизации имеет некоторую цель: минимизировать время в пути, минимизировать затраты, максимизировать прибыль, максимизировать полезность и т. Д. Математическая функция, описывающая эту цель, называется целевой функцией .
Динамическое программирование разбивает задачу многопериодного планирования на более простые шаги в разные моменты времени. Следовательно, это требует отслеживания того, как ситуация принятия решений меняется с течением времени. Информация о текущей ситуации, необходимая для принятия правильного решения, называется «состоянием». [8] [9] Например, чтобы решить, сколько потреблять и тратить в каждый момент времени, людям необходимо знать (среди прочего) свое первоначальное богатство. Следовательно, богатствобудет одной из их переменных состояния , но, вероятно, будут и другие.
Переменные, выбранные в любой данный момент времени, часто называют контрольными переменными . Например, с учетом своего текущего благосостояния люди могут решить, сколько потреблять сейчас. Выбор управляющих переменных сейчас может быть эквивалентен выбору следующего состояния; в более общем случае, на следующее состояние влияют другие факторы в дополнение к текущему элементу управления. Например, в простейшем случае сегодняшнее богатство (состояние) и потребление (контроль) могут точно определять завтрашнее богатство (новое состояние), хотя обычно другие факторы также будут влиять на завтрашнее богатство.
Подход динамического программирования описывает оптимальный план путем нахождения правила, которое сообщает, какими должны быть элементы управления при любом возможном значении состояния. Например, если потребление ( c ) зависит только от богатства ( W ), мы будем искать правилоэто дает потребление как функцию от богатства. Такое правило, определяющее элементы управления как функцию состояний, называется функцией политики (см. Bellman, 1957, Ch. III.2). [8]
Наконец, по определению, оптимальное правило принятия решений - это правило, которое позволяет достичь наилучшего возможного значения цели. Например, если кто-то выбирает потребление, учитывая богатство, чтобы максимизировать счастье (предполагая, что счастье H может быть представлено математической функцией, такой как функция полезности, и является чем-то определенным богатством), то каждый уровень богатства будет связан с какой-то наивысший возможный уровень счастья,. Наилучшее возможное значение цели, записанное как функция состояния, называется функцией значения .
Беллман показал, что задача динамической оптимизации в дискретном времени может быть сформулирована в рекурсивной , пошаговой форме, известной как обратная индукция, путем записи отношения между функцией ценности в один период и функцией ценности в следующем периоде. Связь между этими двумя функциями стоимости называется «уравнением Беллмана». В этом подходе оптимальная политика в последний период времени указывается заранее как функция значения переменной состояния в это время, и, таким образом, полученное оптимальное значение целевой функции выражается через это значение переменной состояния. Затем оптимизация предпоследнего периода включает в себя максимизацию суммы целевой функции конкретного периода и оптимального значения будущей целевой функции, что дает оптимальную политику для этого периода, зависящую от значения переменной состояния на следующий период. решение до последнего периода. [ требуется пояснение ] Эта логика продолжается рекурсивно назад во времени, пока не будет получено правило принятия решения для первого периода, как функция значения переменной начального состояния, путем оптимизации суммы целевой функции для первого периода и значения второй функция значения периода, которая дает значение для всех будущих периодов. Таким образом, решение для каждого периода принимается путем явного признания того, что все будущие решения будут приниматься оптимально.
Вывод
Проблема динамического решения
Пусть государство на время быть . Для решения, которое начинается в момент времени 0, мы принимаем начальное состояние. В любой момент набор возможных действий зависит от текущего состояния; мы можем написать это как, где действие представляет одну или несколько управляющих переменных. Мы также предполагаем, что состояние меняется с в новое состояние когда действие берется, и что текущий выигрыш от принятия мер в состоянии является . Наконец, мы предполагаем нетерпение, представленное дисконтным фактором. .
При этих предположениях проблема принятия решений с бесконечным горизонтом принимает следующий вид:
с учетом ограничений
Обратите внимание, что мы определили обозначение для обозначения оптимального значения, которое может быть получено путем максимизации этой целевой функции с учетом предполагаемых ограничений. Эта функция является функцией значения . Это функция переменной начального состояния, поскольку наилучшее возможное значение зависит от исходной ситуации.
Принцип оптимальности Беллмана
Метод динамического программирования разбивает эту проблему решения на более мелкие подзадачи. Принцип оптимальности Беллмана описывает, как это сделать:
Принцип оптимальности: Оптимальная политика обладает тем свойством, что независимо от начального состояния и первоначального решения, остальные решения должны составлять оптимальную политику в отношении состояния, вытекающего из первого решения. (См. Bellman, 1957, гл. III.3.) [8] [9] [10]
В информатике считается, что проблема, которую можно разбить на части, имеет оптимальную подструктуру . В контексте теории динамических игр этот принцип аналогичен концепции идеального равновесия в подиграх , хотя то, что составляет оптимальную политику в этом случае, зависит от того, что оппоненты лица, принимающего решения, выбирают одинаково оптимальную политику со своей точки зрения.
Согласно принципу оптимальности , мы рассмотрим первое решение отдельно, отложив в сторону все будущие решения (мы начнем заново с момента 1 с новым состоянием). Собирая будущие решения в скобки справа, вышеупомянутая проблема принятия решений с бесконечным горизонтом эквивалентна: [ требуется пояснение ]
с учетом ограничений
Здесь мы выбираем , зная, что наш выбор приведет к тому, что состояние времени 1 будет . Это новое состояние затем повлияет на проблему принятия решения с момента 1. Вся проблема будущего решения отображается в квадратных скобках справа. [ требуется разъяснение ] [ необходимо дополнительное объяснение ]
Уравнение Беллмана
Пока что кажется, что мы только усугубили проблему, отделив сегодняшнее решение от будущих решений. Но мы можем упростить, заметив, что то, что находится внутри квадратных скобок справа, - это значение задачи принятия решения за время 1, начиная с состояния.
Следовательно, мы можем переписать задачу как рекурсивное определение функции значения:
- , с учетом ограничений:
Это уравнение Беллмана. Его можно упростить еще больше, если мы отбросим временные индексы и подставим значение следующего состояния:
Уравнение Беллмана классифицируется как функциональное уравнение , поскольку его решение означает нахождение неизвестной функции, которая является функцией цены . Напомним, что функция ценности описывает наилучшее возможное значение цели как функцию состояния.. Вычисляя функцию цены, мы также найдем функциюкоторый описывает оптимальное действие как функцию состояния; это называется функцией политики .
В стохастической задаче
В детерминированной установке для решения указанной выше проблемы оптимального управления могут использоваться другие методы, помимо динамического программирования . Однако уравнение Беллмана часто является наиболее удобным методом решения задач стохастического оптимального управления.
В качестве конкретного примера из экономики рассмотрим бесконечно живущего потребителя с начальным богатством. в период . У них есть функция мгновенной полезности где обозначает потребление и дисконтирует полезность следующего периода по ставке . Предположим, что то, что не потребляется в период переносится на следующий период с процентной ставкой . Тогда задача максимизации полезности потребителя состоит в том, чтобы выбрать план потребления. это решает
при условии
а также
Первое ограничение - это закон накопления капитала / движения, определяемый проблемой, в то время как второе ограничение - это условие трансверсальности , при котором потребитель не несет долгов в конце своей жизни. Уравнение Беллмана имеет вид
В качестве альтернативы можно решить проблему последовательности напрямую, используя, например, гамильтоновы уравнения .
Теперь, если процентная ставка меняется от периода к периоду, потребитель сталкивается с проблемой стохастической оптимизации. Пусть интерес r следует марковскому процессу с вероятностной переходной функцией где обозначает вероятностную меру, регулирующую распределение процентной ставки в следующем периоде, если текущая процентная ставка. В этой модели потребитель принимает решение о потреблении в текущий период после объявления процентной ставки текущего периода.
Вместо того, чтобы просто выбирать одну последовательность , теперь потребитель должен выбрать последовательность для каждой возможной реализации таким образом, чтобы их ожидаемая полезность за весь срок службы была максимальной:
Ожидание берется относительно соответствующей вероятностной меры, заданной Q на последовательностях r . Поскольку r управляется марковским процессом, динамическое программирование значительно упрощает задачу. Тогда уравнение Беллмана просто:
При некотором разумном предположении результирующая функция оптимальной политики g ( a , r ) измерима .
Для общей стохастической последовательной задачи оптимизации с марковскими шоками и где агент сталкивается с их решением экс-постом , то уравнение Беллмана имеет очень сходную форму
Методы решения
- Метод неопределенных коэффициентов , также известные как «угадать и проверяйте», может быть использован для решения какого - то бесконечный горизонта, автономные уравнения Беллмана. [11]
- Уравнение Беллмана может быть решено обратной индукцией либо аналитически в некоторых частных случаях, либо численно на компьютере. Числовая обратная индукция применима к широкому кругу задач, но может оказаться невыполнимой при большом количестве переменных состояния из-за проклятия размерности . Приближенное динамическое программирование было введено Д. П. Бертсекасом и Ю. Н. Цициклисом с использованием искусственных нейронных сетей ( многослойных персептронов ) для аппроксимации функции Беллмана. [12] Это эффективная стратегия смягчения последствий для уменьшения влияния размерности путем замены запоминания полного отображения функций для всего пространственного домена запоминанием единственных параметров нейронной сети. В частности, для систем с непрерывным временем был представлен приближенный подход динамического программирования, сочетающий обе итерации политики с нейронными сетями. [13] В дискретном времени был представлен подход к решению уравнения HJB, объединяющий итерации значений и нейронные сети. [14]
- Вычисляя условия первого порядка, связанные с уравнением Беллмана, а затем используя теорему об огибающей для исключения производных функции цены, можно получить систему разностных уравнений или дифференциальных уравнений, называемую « уравнениями Эйлера ». [15] Стандартные методы решения разностных или дифференциальных уравнений могут затем использоваться для расчета динамики переменных состояния и управляющих переменных задачи оптимизации.
Приложения в экономике
Первое известное применение уравнения Беллмана в экономике принадлежит Мартину Бекманну и Ричарду Муту . [16] Мартин Бекманн также много писал о теории потребления, используя уравнение Беллмана в 1959 году. Его работа, в частности, оказала влияние на Эдмунда С. Фелпса .
Знаменитым экономическим применением уравнения Беллмана является основополагающая статья Роберта К. Мертона 1973 года о модели межвременного ценообразования капитальных активов . [17] (См. Также проблему портфеля Мертона ). Решение теоретической модели Мертона, в которой инвесторы выбирают между доходом сегодня и будущим доходом или приростом капитала, является формой уравнения Беллмана. Поскольку экономические приложения динамического программирования обычно приводят к уравнению Беллмана, которое является уравнением разностей , экономисты называют динамическое программирование «рекурсивным методом», и в настоящее время в экономической науке признается подполе рекурсивной экономики.
Нэнси Стоки , Роберт Э. Лукас и Эдвард Прескотт довольно подробно описывают стохастическое и нестохастическое динамическое программирование и развивают теоремы о существовании решений проблем, удовлетворяющих определенным условиям. Они также описывают множество примеров моделирования теоретических проблем экономики с использованием рекурсивных методов. [18] Эта книга привела к использованию динамического программирования для решения широкого круга теоретических проблем в экономике, включая оптимальный экономический рост , добычу ресурсов , проблемы принципала-агента , государственные финансы , инвестиции в бизнес , ценообразование на активы , предложение факторов производства и организацию производства. . Ларс Юнгквист и Томас Сарджент применяют динамическое программирование для изучения множества теоретических вопросов в области денежно-кредитной политики , налогово-бюджетной политики , налогообложения , экономического роста , теории поиска и экономики труда . [19] Авинаш Диксит и Роберт Пиндик показали ценность этого метода для размышления о капитальном бюджете . [20] Андерсон адаптировал эту технику для оценки бизнеса, в том числе частного. [21]
Использование динамического программирования для решения конкретных задач осложняется информационными трудностями, такими как выбор ненаблюдаемой ставки дисконтирования. Существуют также вычислительные проблемы, главная из которых - проклятие размерности, возникающее из-за огромного количества возможных действий и потенциальных переменных состояния, которые необходимо учитывать, прежде чем можно будет выбрать оптимальную стратегию. Подробное обсуждение вычислительных вопросов см. В Miranda and Fackler, [22] и Meyn 2007. [23]
Пример
В марковских процессах принятия решений уравнение Беллмана - это рекурсия для ожидаемых вознаграждений. Например, ожидается , вознаграждение за то , что в конкретном состоянии с и после некоторой фиксированной политики имеет уравнение Беллмана:
Это уравнение описывает ожидаемое вознаграждение за действие, предписанное некоторой политикой. .
Уравнение оптимальной политики называется уравнением оптимальности Беллмана :
где оптимальная политика и относится к функции ценности оптимальной политики. Приведенное выше уравнение описывает вознаграждение за действие, дающее наивысший ожидаемый доход.
Смотрите также
- Псевдоспектральный метод Беллмана
- Динамическое программирование - метод оптимизации задачи.
- Уравнение Гамильтона – Якоби – Беллмана.
- Марковский процесс принятия решений
- Теория оптимального управления
- Оптимальная подконструкция
- Рекурсивное конкурентное равновесие
- Стохастическое динамическое программирование
Рекомендации
- ^ Диксит, Авинаш К. (1990). Оптимизация в экономической теории (2-е изд.). Издательство Оксфордского университета. п. 164. ISBN 0-19-877211-4.
- ^ Кирк, Дональд Э. (1970). Теория оптимального управления: введение . Прентис-Холл. п. 55. ISBN 0-13-638098-0.
- ^ Кирк 1970 , стр. 70
- ^ Камиен, Мортон И .; Шварц, Нэнси Л. (1991). Динамическая оптимизация: исчисление вариаций и оптимальное управление в экономике и управлении (второе изд.). Амстердам: Эльзевир. п. 261. ISBN. 0-444-01609-0.
- ^ Кирк 1970 , стр. 88
- ^ Джонс, Морган; Пит, Мэтью М. (2020). «Расширения среды динамического программирования: планирование аккумуляторов, сборы по требованию и интеграция с возобновляемыми источниками энергии». Транзакции IEEE по автоматическому контролю : 1. arXiv : 1812.00792 . DOI : 10.1109 / TAC.2020.3002235 . S2CID 119622206 .
- ^ Джонс, Морган; Пит, Мэтью М. (2021). «Обобщение уравнения Беллмана с приложением к планированию пути, предотвращению препятствий и оценке инвариантного множества» . Automatica : 109510. arXiv : 2006.08175 . DOI : 10.1016 / j.automatica.2021.109510 .
- ^ а б в Беллман, Р. Э. (2003) [1957]. Динамическое программирование . Дувр. ISBN 0-486-42809-5.
- ^ а б Дрейфус, С. (2002). «Ричард Беллман о рождении динамического программирования» . Исследование операций . 50 (1): 48–51. DOI : 10.1287 / opre.50.1.48.17791 .
- ^ Беллман, Р. (август 1952 г.). «К теории динамического программирования» . Proc Natl Acad Sci USA . 38 (8): 716–9. Полномочный код : 1952PNAS ... 38..716B . DOI : 10.1073 / pnas.38.8.716 . PMC 1063639 . PMID 16589166 .
- ^ Юнгквист, Ларс; Сарджент, Томас Дж. (2004). Рекурсивная макроэкономическая теория (2-е изд.). MIT Press. стр. 88 -90. ISBN 0-262-12274-X.
- ^ Bertsekas, Dimitri P .; Цициклис, Джон Н. (1996). Нейродинамическое программирование . Афина Сайентифик. ISBN 978-1-886529-10-6.
- ^ Абу-Халаф, Мурад; Льюис, Фрэнк Л. (2005). «Почти оптимальные законы управления для нелинейных систем с насыщающими исполнительными механизмами с использованием подхода нейронной сети HJB». Automatica . 41 (5): 779–791. DOI : 10.1016 / j.automatica.2004.11.034 .
- ^ Аль-Тамими, Асма; Льюис, Фрэнк Л .; Абу-Халаф, Мурад (2008). «Решение нелинейного HJB с дискретным временем с использованием приближенного динамического программирования: доказательство сходимости». IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics) . 38 (4): 943–949. DOI : 10.1109 / TSMCB.2008.926614 . PMID 18632382 . S2CID 14202785 .
- ^ Мяо, Цзяньцзюнь (2014). Экономическая динамика в дискретном времени . MIT Press. п. 134. ISBN 978-0-262-32560-8.
- ^ Бекманн, Мартин; Мут, Ричард (1954). «О решении« фундаментального уравнения »теории запасов» (PDF) . Документ для обсуждения Комиссии Коулза 2116 .
- ^ Мертон, Роберт С. (1973). «Модель межвременного ценообразования капитальных активов». Econometrica . 41 (5): 867–887. DOI : 10.2307 / 1913811 . JSTOR 1913811 .
- ^ Стоки, Нэнси; Лукас, Роберт Э .; Прескотт, Эдвард (1989). Рекурсивные методы в экономической динамике . Издательство Гарвардского университета. ISBN 0-674-75096-9.
- ^ Юнгквист, Ларс; Сарджент, Томас (2012). Рекурсивная макроэкономическая теория (3-е изд.). MIT Press. ISBN 978-0-262-01874-6.
- ^ Диксит, Авинаш; Пиндик, Роберт (1994). Инвестиции в условиях неопределенности . Издательство Принстонского университета. ISBN 0-691-03410-9.
- ^ Андерсон, Патрик Л. (2004). «Глава 10». Бизнес-экономика и финансы . CRC Press. ISBN 1-58488-348-0.
- (2009). «Значение частного бизнеса в Соединенных Штатах». Экономика бизнеса . 44 (2): 87–108. DOI : 10.1057 / be.2009.4 . S2CID 154743445 .
- (2013). Экономика оценки бизнеса . Издательство Стэнфордского университета. ISBN 9780804758307. Стэнфорд Пресс архивации 2013-08-08 в Wayback Machine - ^ Миранда, Марио Дж .; Факлер, Пол Л. (2004). Прикладная вычислительная экономика и финансы . MIT Press. ISBN 978-0-262-29175-0.
- ^ Мейн, Шон (2008). Методы управления сложными сетями . Издательство Кембриджского университета. ISBN 978-0-521-88441-9.Приложение содержит сокращенную версию Meyn & Tweedie, заархивированную 12 октября 2007 г. на Wayback Machine .