同义词动态规划方程(动态规划方程)一般指贝尔曼方程
贝尔曼方程是动态规划(Dynamic Programming)这些数学最佳化方法能够达到最佳化的必要条件。此方程把“决策问题在特定时间点的值”以“来自初始选择的报酬比从初始选择衍生的决策问题的值”的形式表示。借此这个方式把动态最佳化问题变成简单的子问题,而这些子问题遵守从贝尔曼所提出来的“最佳化还原理”。
- 中文名
- 贝尔曼方程
- 外文名
- Bellman Equation
- 别 名
- 动态规划方程
- 基本原理
- 最优化原理和嵌入原理
- 提出者
- 理查·贝尔曼(Richard Bellman)
- 学 科
- 数学、经济学
- 类 型
- 数学术语
来源
播报编辑
几乎所有的可以用最佳道祝控制理论(Optimal Control Theory)解决的问题也可以通过分析合适的贝尔曼方程得到解决。然而,贝尔曼方程通常指离散时间(discrete-time)最佳化问题的动态规划方程台局墓碑旬埋。
处理连续时间(cont院脚催inuous-time)最佳化问题上,也有类似那些偏微分方程,称作汉密尔顿-雅克比-贝尔曼方程(Hamilton–Jacobi–Bellman Equation,HJB Equation)。
简介
播报编辑
特点和应用范围 :
若多阶段决策过程为连续型,则动态规划与变分法处理的问题有共同之处。动态规划原理可用来将变分法问题归结为多阶段决策过程,用动态规划的贝尔曼方程求解。在最优控制理论中动态规划方法比极大值原理更为适用 [1],但动态规划还缺少严格的逻辑基础。
60年代,В.Г.沃尔昌斯基对动态规划方法作了数学论证。
动态规划方法的五个特点:
解析概念
播报编辑
动态规划 [3]是把一个规划问题转化为抽象状态之间的转移,因此,它需要追踪决策背景情况随时间的变化。作正确决策所需要当前情况的信息被称作是状态(State)(贝尔曼,1957,Ch. III.2)。例如,为了决定每一个时间要花一些钱,人们必须要知道他们初始财富的量,此例中财富就是一种状态变数(State Variables),或简称状态(State),当然也可能还有其他的种类。
控制变数(Control Variables)是控制理论中描述输入的变量 [1],简称控制(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