贝尔曼方程(Bellman Equation)也被称作
动态规划方程(Dynamic Programming Equation),由理查·贝尔曼(Richard Bellman)发现。
来源
贝尔曼方程最早应用在工程领域的
控制理论和其他应用数学领域,而后成为经济学上的重要工具。
几乎所有的可以用最佳控制理论(Optimal Control Theory)解决的问题也可以通过分析合适的贝尔曼方程得到解决。然而,贝尔曼方程通常指离散时间(discrete-time)最佳化问题的
动态规划方程。
处理连续时间(continuous-time)最佳化问题上,也有类似那些
偏微分方程,称作汉密尔顿-雅克比-贝尔曼方程(Hamilton–Jacobi–Bellman Equation,HJB Equation)。
简介
贝尔曼方程是关于未知函数(
目标函数)的函数方程组。应用
最优化原理和嵌入原理建立函数方程组的方法称为
函数方程法。在实际运用中要按照具体问题寻求特殊解法。
动态规划理论开拓了函数方程理论中许多新的领域。
特点和应用范围 :
若多阶段决策过程为连续型,则动态规划与变分法处理的问题有共同之处。动态规划原理可用来将变分法问题归结为多阶段决策过程,用动态规划的贝尔曼方程求解。在
最优控制理论中动态规划方法比
极大值原理更为适用,但动态规划还缺少严格的逻辑基础。
60年代,В.Г.沃尔昌斯基对动态规划方法作了数学论证。
动态规划方法的五个特点:
②在给定的
定义域或限制条件下很难用微分方法求极值的函数,可用动态规划方法求极值;
③对于不能用解析形式表达的函数,可给出
递推关系求
数值解;
④动态规划方法可以解决古典方法不能处理的问题,如两点
边值问题和隐变分问题等;
⑤许多数学规划问题均可用
动态规划方法来解决,例如,含有随时间或空间变化的因素的经济问题。
投资问题、库存问题、生产计划、资源分配、
设备更新、最优搜索、
马尔可夫决策过程,以及
最优控制和自适应控制等问题,均可用动态规划方法来处理。
解析概念
想了解贝尔曼方程,先要了解许多相关概念。首先,任何最佳化问题都有目标:旅行时间最小化、成本最小化、利润最大化、效用最大化等。用来描述目标的数学函数就称为
目标函数。
动态规划是把一个规划问题转化为抽象状态之间的转移,因此,它需要追踪决策背景情况随时间的变化。作正确决策所需要当前情况的信息被称作是状态(State)(贝尔曼,1957,Ch. III.2)。例如,为了决定每一个时间要花一些钱,人们必须要知道他们初始财富的量,此例中财富就是一种状态变数(State Variables),或简称状态(State),当然也可能还有其他的种类。
控制变数(Control Variables)是控制理论中描述输入的变量,简称控制(Control)。例如给还是当前所具有的财富(状态),人们便可以用以取决还是当下的消费(控制变数)。靠选当下的控制变数能被视为挑选下状态,广义而语言,下状态受到当下控制变数比其他因数的影响。
举一个简单的例子:当前的财富(状态)比消费(控制变数)会决定未来的财富(新的状态),虽然通常也还有其他的因素可以影响未来的财富(例如获得意外之财)。
动态规划方法中最佳化的步骤可以被描述为“找某种规则告诉我们各可能状态下的(最佳)控制为何。例如:假如消费(c)的与财富(W)相关,我们想要找到一套规则c(W)来以财富描述消费。
这些“把控制(Controls)表示成状态(States)的函数”的规则被称为策略函数(Policy Function)。
动态规划与最优控制的关系
最优控制亦即“
汉密尔顿函数”,贝尔曼方程和汉密尔顿函数都是用于解决动态过程的最优问题,都是关于状态变量、控制变量和时间的一个函数(实质是泛函)。
不同的是,
汉密尔顿函数是通过取任意一个时点实现最优从而求取整个动态过程的最优,而贝尔曼方程是通过将多级最优决策转化为多个单级最优决策从而求取整个动态过程的最优,所以贝尔曼方程还叫做动态规划的基本递推方程。
此外,贝尔曼方程还能用于处理非线性的动态优化,这是汉密尔顿函数做不到的。
基本原理
最优化原理一个最优策略,具有如下性质:不论初始状态和
初始决策(第一步决策)如何,以第一步决策所形成的阶段和状态作为初始条件来考虑时,余下的决策对余下的问题而言也必构成
最优策略。
最优化原理体现了动态规划方法的基本思想。
嵌入原理
一个具有已知初始状态和固定步数的过程总可以看作是初始状态和步数均不确定的一族过程中的一个特殊情况。这种把所研究的过程嵌入一个过程族的原理称为嵌入原理。
通过研究过程族的最优策略族的共同性质得出一般通解,此通解自然也适用于原来的特殊问题。动态规划的基本方法就是根据嵌入原理把一个多步决策问题化为一系列较简单的一步决策问题,可显著降低数学处理上的难度。
贝尔曼方程的基本形式
问题的基本形式可以描述为:
Max ∑β^tF(X(t),U(t))
s.t. X(t+1)=G(X(t),U(t)),t=0,1,2,3……
X(t=0)=X0,初始状态给定,而其后任意时间的状态变量数值都是可变的。
定义值函数为:
V(X(t),t)=Max ∑β^tF(X(t),U(t)),β∈(0,1)
所以,任意阶段t的贝尔曼方程就可以表示为
U(X(t),t)=Max F(X(t),U(t))+βV(X(t+1),t+1)
贝尔曼方程解的基本形式直接给出,证明过程太复杂,此处不详列。
∂F/∂U(t)+β(∂V/∂X(t+1))(∂G/∂U(t+1))=0
此方程还可以转化成为动态规划最优化条件的
欧拉方程,方法是将贝尔曼方程的解与贝尔曼方程对X(t+1)求偏导的结果联立求解。