Editing Bellman equation (section)

{{short description|Necessary condition for optimality associated with dynamic programming}}
{{More footnotes needed|date=April 2018}}
[[File:Bellman flow chart.png|thumb|Bellman flow chart.]]
A '''Bellman equation''', named after [[Richard E. Bellman]], is a [[necessary condition]] for optimality associated with the mathematical [[Optimization (mathematics)|optimization]] method known as [[dynamic programming]].<ref>{{cite book |first=Avinash K. |last=Dixit |title=Optimization in Economic Theory |publisher=Oxford University Press |edition=2nd |year=1990 |isbn=0-19-877211-4 |page=164 |url=https://books.google.com/books?id=dHrsHz0VocUC&pg=PA164 }}</ref> It writes the "value" of a decision problem at a certain point in time in terms of the payoff from some initial choices and the "value" of the remaining decision problem that results from those initial choices.<ref>{{Cite web |title=Bellman's principle of optimality. |url=https://www.ques10.com/p/8343/bellmans-principle-of-optimality/ |access-date=2023-08-17 |website=www.ques10.com}}</ref> This breaks a dynamic optimization problem into a [[sequence]] of simpler subproblems, as Bellman's “principle of optimality" prescribes.<ref>{{cite book |first=Donald E. |last=Kirk |title=Optimal Control Theory: An Introduction |publisher=Prentice-Hall |year=1970 |isbn=0-13-638098-0 |page=55 |url=https://books.google.com/books?id=fCh2SAtWIdwC&pg=PA55 }}</ref>  The equation applies to algebraic structures with a total ordering; for algebraic structures with a partial ordering, the generic Bellman's equation can be used.<ref name = "Generic Dijkstra correctness">{{citation | title = NOMS 2023-2023 IEEE/IFIP Network Operations and Management Symposium | last1 = Szcześniak | first1 = Ireneusz | last2 = Woźna-Szcześniak | first2 = Bożena | chapter = Generic Dijkstra: Correctness and tractability | year = 2023 | pages = 1–7 | doi = 10.1109/NOMS56928.2023.10154322 | arxiv = 2204.13547| isbn = 978-1-6654-7716-1 | s2cid = 248427020 }}</ref>

The Bellman equation was first applied to engineering [[control theory]] and to other topics in applied mathematics, and subsequently became an important tool in [[economic theory]]; though the basic concepts of dynamic programming are prefigured in [[John von Neumann]] and [[Oskar Morgenstern]]'s ''[[Theory of Games and Economic Behavior]]'' and [[Abraham Wald]]'s ''[[sequential analysis]]''.{{Citation needed|date=September 2017}} The term "Bellman equation" usually refers to the dynamic programming equation (DPE) associated with [[discrete-time]] optimization problems.<ref>{{harvnb|Kirk|1970|p=[https://books.google.com/books?id=fCh2SAtWIdwC&pg=PA70 70]}}</ref> In continuous-time optimization problems, the analogous equation is a [[partial differential equation]] that is called the [[Hamilton–Jacobi–Bellman equation]].<ref>{{cite book |first1=Morton I. |last1=Kamien |author-link=Morton Kamien |first2=Nancy L. |last2=Schwartz |title=Dynamic Optimization: The Calculus of Variations and Optimal Control in Economics and Management |location=Amsterdam |publisher=Elsevier |edition=Second |year=1991 |isbn=0-444-01609-0 |page=261 |url=https://books.google.com/books?id=liLCAgAAQBAJ&pg=PA261 }}</ref><ref>{{harvnb|Kirk|1970|p=[https://books.google.com/books?id=fCh2SAtWIdwC&pg=PA88 88]}}</ref>

In discrete time any multi-stage optimization problem can be solved by analyzing the appropriate Bellman equation. The appropriate Bellman equation can be found by introducing new state variables (state augmentation).<ref>{{cite journal |last1=Jones |first1=Morgan |last2=Peet |first2=Matthew M. |title=Extensions of the Dynamic Programming Framework: Battery Scheduling, Demand Charges, and Renewable Integration |journal=IEEE Transactions on Automatic Control |date=2020 |volume=66 |issue=4 |pages=1602–1617 |doi=10.1109/TAC.2020.3002235|arxiv=1812.00792 |s2cid=119622206 }}</ref> However, the resulting augmented-state multi-stage optimization problem has a higher dimensional state space than the original multi-stage optimization problem - an issue that can potentially render the augmented problem intractable due to the “[[curse of dimensionality]]”. Alternatively, it has been shown that if the cost function of the multi-stage optimization problem satisfies a "backward separable" structure, then the appropriate Bellman equation can be found without state augmentation.<ref>{{cite journal |last1=Jones |first1=Morgan |last2=Peet |first2=Matthew M. |title=A Generalization of Bellman's Equation with Application to Path Planning, Obstacle Avoidance and Invariant Set Estimation |journal=Automatica |date=2021 |volume=127 |pages=109510 |doi=10.1016/j.automatica.2021.109510 |url=https://www.sciencedirect.com/science/article/pii/S0005109821000303  |arxiv=2006.08175 |s2cid=222350370 }}</ref>