动态规划与随机控制1953年，R . Bellman 等人，根据某类多阶段序贯决策问题的特点，提出了著名的“最优性原理”。

在这个原理的指导下，他将此类多阶段决策问题转变为一系列的互相联系的单阶段决策问题，然后，逐个阶段予以解决，最后再形成总体解决。

从而创建了求解优化问题的新方法——动态规划。

1957年，他的名著《动态规划》出版。

1.离散型动态规划离散型确定性动态规划在解决美式期权问题时，我们通常采用倒向递推的方法来比较即时执行价格与继续持有价格。

这是利用动态规划原理的一个典型例子。

Richard Bellman在1953年首次提出动态规划原理.最优化原理：无论过去的状态和决策如何，相对于前面的决策侧所形成的的状态而言，余下的决策序列必然构成最优子策略.求解最短路径问题：来看下面一个具体的例子：我们要求从Q点到T点的最短路径其基本思想是分阶段求出各段到T点的最短路径：•Ⅳ：C1—T 3•Ⅲ--Ⅳ: B1—C1—T 4•Ⅱ--Ⅲ--Ⅳ：A2—B1—C1—T 7•Ⅰ--Ⅱ--Ⅲ--Ⅳ：•Q—A2—B1—C1—T 11•Q--A3—B1—C1—T 11•Q--A3—B2—C2—T 11从以上分析可以看出最短路径不唯一。

最短路径解的特点•1、可以将全过程求解分为若干阶段求解；------多阶段决策问题•2、在全过程最短路径中，将会出现阶段的最优路径；-----递推性•3、前面的终点确定，后面的路径也就确定了，且与前面的路径（如何找到的这个终点）无关；-----无后效性•3、逐段地求解最优路径，势必会找到一个全过程最优路径。

-----动态规划离散型不确定性动态规划离散型不确定性动态规划的特点就是每一阶段的决策不是确定的，是一个随机变量，带有一定的随机性，因此处理起来就相对复杂些。

一个动态规划的经典问题：你打算与一个你遇到的最富有的人结婚，你的最优策略是什么？这里做几点基本的假设：1、如果碰到满足你要求的人，他无条件接受；2、有N 个人供你选择；3、每个备选对象的财富值都服从[0, 1].区间上的均匀分布;那么你要找具有最大期望财富值的结婚对象的最优策略是什么?这是一个看似简单但是很难解决的问题.通常的方法是顺序递推法，如果首先考虑碰到第一个人的财富，接着考虑碰到下一个人的财富值与第一个人的财富值进行比较，依次进行下去，但是你期望下一个对象的财富值的确定是一个很复杂的问题，并且很难进行比较.因此这里我们考虑倒向递推的方法进行计算，我们首先逆向考虑一个简单的问题就是假如你只面对2个人的情况，当你只碰到倒数第一个人时，我们认为他的财富期望值为0.5，我们知道，你将选择与倒数第二个对象结婚时只有在他的财富值大于0.5的情况下，否则你将与倒数第一个对象结婚。

一般的，我们用N V 表示倒数第一个人的财富期望值，用1N W-表示表示倒数第二个人的财富值，假设你的最优行动时在倒数第二步，则倒数第二个人的财富期望值为：11111[](1)N N N N N N N V P E WW V P V -----=⨯|>+-⨯,这里 11()N N N P P W V --≡>一般的倒向递推公式就是：∙ 设 1()k k k P P W V +≡>,11()[](1)11NN k k k k k k k V E W V P E W W V P V k N ++==⨯|>+-⨯,=-,,,(1)k W 是倒数第k 个人的财富值，k V 是你在倒数第k 阶段的最优策略的财富期望值。

如果我们把取10N =，则此时我们可以算出10861V =.2.连续型动态规划问题确定性控制问题给定0x ∈ℜ，考虑一个如下控制问题0()(()())[0](0)x t b t x t u t a e t T x x =,,,..∈,,⎧⎨=,⎩ （2）()[0]u T U ⋅:,→是允许控制集，[0]{()A T u ,=⋅ 在[0]}T ,上可测 , U 是一个度量空间,0T >,[0]b T U :,⨯ℜ⨯→ℜ 为一给定的映射.则最优控制问题就是在控制系统（2）的条件下极小化如下成本函数(())(()())(())over [0]TJ u f t x t u t dt h x T A T ⋅=,,+,,,⎰ （3）对于给定的映射f 和h 。

值函数的确定设()[0)s y T ,∈,⨯ℜ；在区间[]s T ,考虑以下控制系统：()(()())[]()x t b t x t u t a e t s T x s y =,,,..∈,,⎧⎨=,⎩这里控制()[]{()|()u A s T u u ⋅∈,=⋅⋅是区间[]}s T ,上可测函数。

则成本函数就是如下函数：(())(()())(())TsJ s y u f t x t u t dt h x T ,;⋅=,,+.⎰现在我们来定义如下形式的值函数：()[]()(())for any ()[0)()()u A s T V s y inf J s y u s y T V T y h y ⋅∈,,=,;⋅,,∈,⨯ℜ⎧⎨,=.⎩ （4）这里值函数就是在允许控制集的范围内，找出所有成本函数中的极小化函数并且满足一定的终止条件的函数。

定理 1.贝尔曼最优化原理 假设U 是可分的度量空间, f 和h 是一致连续，并且存在常数0L >使得对于()()()()t x u b t x u f t x u h x φ,,=,,,,,,，有ˆˆ|()()|||ˆ|(0)|for any [0]t x u t xu L x x t u L t T x xu U φφφ,,-,,≤-,,,≤,∈,,,∈ℜ,∈. 则对于任何()[0)s y T ,∈,⨯ℜ和任意ˆ0s sT ≤≤≤有：{}ˆˆ[]ˆˆ()(()())((()))su A s s sV s y inf f t x t u t dt V sx s u ∈,,=,,+,;⋅,⎰（5）方程（5）就是我们通常所讲的动态规划方程。

也就是说，全局最优一定导致局部最优，这也是贝尔曼原理的精髓。

定理2. HJB equation 如果值函数1([0])V C T ∈,⨯ℜ：则V 是如下带有终止条件的一阶偏微分方程（HJB equation ）的解inf{()()}0|()()[0]t x u Ut T v b t x u v f t x u v h x t x T ∈=+,,+,,=,⎧⎪⎨=,,∈,⨯ℜ.⎪⎩ （6）定理的简要证明：固定u U ∈，让()x ⋅为控制()u t u ≡的相应状态轨迹，由贝尔曼原理ˆˆ()(())(())ssV s y f t x t u dt V s x s ,≤,,+,⎰，由()()0t x V b t x u V f t x u +,,+,,≥：对于任意u U ∈，有inf {()()}0t u U x V b t x u V f t x u ∈+,,+,,≥另一方面，对于任意ˆ00s sT ε>,≤<≤当ˆ0s s ->充分小，存在ˆ()()[]s u u A s T ε,⋅≡⋅∈,使得ˆˆˆ()()(()())(())ssV s y ss f t x t u t dt V s x s ε,+-≥,,+,⎰，这也就有inf {()t uU xV b t x u V f t x u∈+,,+,,≤。

例：考虑如下系统;30()()(),(0)x t x t u t x x ∙=+=目标函数为221()2f t J x u dt =+⎰ 解：根据以上分析，系统的拉格朗日型值函数为22311(,,,)22H x u t x u u x λλλ=++- 令则HJB equation 为若优化区间为无穷的大，则我们求解以下微分方程：为了求解上述非线性微分方程，将V(x)展开成如下级数形式：令n=4，则得所以最优控制作用为 闭环系统为随机控制问题设()Z t 为一布朗运动，我们考虑如下随机控制系统：0()(()())(()())()[0](0)dx t b t x t u t dt t x t u t dZ t t T x x σ=,,+,,,∈,,⎧⎨=,⎩ （7）定义区间[0]T ,上可测的允许控制集[0]{()A T u ,=⋅，和0{}t t F ≥是适应的，最优随机控制问题就是如下允许集[0]A T ,下的成本函数3222121),(,,0xx V x V x x V x H u x V u H ⎥⎦⎤⎢⎣⎡∂∂-⎥⎦⎤⎢⎣⎡∂∂-=∂∂-=∂∂==∂∂λλ可以得到02121232=+⎥⎦⎤⎢⎣⎡∂∂-⎥⎦⎤⎢⎣⎡∂∂-∂∂x x x V x V t V ((),)0V x t t t∂=∂02232=-⎥⎦⎤⎢⎣⎡+⎥⎦⎤⎢⎣⎡x x dx dV dx dV 0)0(=V 3)()(x x dx dVt t u +-=-=-=λ)()()()()()(333t x t x t x t x t u t x x -=+--=+-= +++++=44332210!41!31!21)(x p x p x p x p p x V 61042310=====p p p p p{}(())(()())(())TJ u Ef t x t u t dt h x T ⋅=,,+.⎰（8）值函数就是如下系统下的极小化函数：设()[0)ns y T ,∈,⨯ℜ，我们考虑区间[]s T ,上以下控制系统()(()())(()())()[]()dx t b t x t u t dt t x t u t dZ t t s T x s y σ=,,+,,,∈,,⎧⎨=,⎩ （9）这里控制()[]u A s T ⋅∈,，成本函数是{}(())(()())(())TsJ s y u E f t x t u t dt h x T ,;⋅=,,+⎰我们定义值函数如下：()[]()inf (())for any ()[0)()()nu A s T V s y J s y u s y T V T y h y ⋅∈,⎧,=,;⋅,,∈,⨯ℜ⎪⎨,=.⎪⎩ （10）定理 3 .贝尔曼最优化原理 对于任意()[0)ns y T ,∈,⨯ℜ和任意ˆ0s sT ≤≤≤有{}ˆˆ[]ˆˆ()inf ((())())((()))su A s s sV s y Ef t x t s y u u t dt V sx s s y u ∈,,=,;,,⋅,+,;,,⋅⎰定理4. HJB equation 如果值函数12([0])nV C T ,∈,⨯ℜ：则V 是以下带有终止条件问题的解：21inf{()()()}02|()()[0]t xx x u U n t T v t x u v b t x u v f t x u v h x t x T σ∈=⎧+,,+,,+,,=,⎪⎨⎪=,,∈,⨯ℜ.⎩ （11）3. Merton’s problem我们假设市场上只有两类资产进行投资：无风险资产（银行储蓄）和风险资产（股票），它们的价格分别定义为()B t 和()S t ，并且由以下方程决定：()()()()[()]dB t rB t dt dS t S t dt dZ t μσ=,⎧⎨=+,⎩ （12）这里0r >是无风险利率；0μ>和0σ>是常数分别称为股票的回报率期望值和波动率。