最优化问题

       动态规划(Dynamic programming)是用来优化一个随机问题的最优解。随机问题是仅仅我们优化的目标是随机的，最优解指的是在统计平均上的最优。

       比較权威的參考资料：Dimiri P. Bertsekas, Dynamic Programming and Optimal Control, 3rd ed., Athena Scientific, Belmont, Massachusetts,2005

一般优化问题描写叙述

<script type="math/tex; mode=display" id="MathJax-Element-1">\mathop {min}\limits_{u\in \mathcal{U}} g(u)</script>

•  u <script type="math/tex" id="MathJax-Element-2">~u~</script>是最优化问题的决策
•  g(u) <script type="math/tex" id="MathJax-Element-3">~g(u)~</script>是决策的代价函数

•  U <script type="math/tex" id="MathJax-Element-4">~\mathcal{U}~</script>是全部决策 ui <script type="math/tex" id="MathJax-Element-5">~u_i~</script>的集合

  动态规划的优化问题能够分为：

  1. 随机优化问题：

          由于代价函数存在一个随机变量w<script type="math/tex" id="MathJax-Element-6">w</script>，因此最优解的优化目标是代价函数的统计平均。
  

  g(u)=EwG(u,w)
  <script type="math/tex; mode=display" id="MathJax-Element-7">g(u) = E_w{G(u,w)}</script>
  1. 确定优化问题：

         这个问题代价函数是一个确定函数。

       怎样区分这两个问题呢？我们能够观察系统是否存在随机性，这个随机性是体如今系统之中的，而不是这个系统。

举个栗子，优化一个随机网络是个确定性问题，即给定随意网络结构，找到最短路径。由于网络尽管是随机的，可是优化的目标在确定以后是不变的。

然而优化一个随时变化的网络是一个随机问题。即一边进行优化。网络结构一边在变的问题。
       动态规划正是能够解决每个步骤都有随机变量 w <script type="math/tex" id="MathJax-Element-8">~w~</script>影响的目标函数，怎样在全局取得统计平均上最优解的问题。后面我们能够看到每个决策都会利用 w <script type="math/tex" id="MathJax-Element-9">~w~</script>的信息。

随机动态规划的结构

离散时间系统

<script type="math/tex; mode=display" id="MathJax-Element-10">x_{k+1} =f_k(x_k,u_k,w_k), k=0,1,\ldots,N-1</script>

当中：

•  k <script type="math/tex" id="MathJax-Element-11">~k~</script>：表示离散时间<script type="math/tex" id="MathJax-Element-12">\color{red}{时间}</script>（也能够看作是步骤）。

•  xk <script type="math/tex" id="MathJax-Element-13">~x_k~</script>：表示在时间 k <script type="math/tex" id="MathJax-Element-14">~k~</script>的状态<script type="math/tex" id="MathJax-Element-15">\color{red}{状态}</script>，该状态具有马尔科夫性，即当前状态已经包括决策所须要的各种信息，与之前的状态无关。当前状态将会參与决策。

•  uk <script type="math/tex" id="MathJax-Element-16">~u_k~</script>：表示在时间 k <script type="math/tex" id="MathJax-Element-17">~k~</script>所输出的控制<script type="math/tex" id="MathJax-Element-18">\color{red}{控制}</script>，即再时间 k <script type="math/tex" id="MathJax-Element-19">~k~</script>在集合 U <script type="math/tex" id="MathJax-Element-20">~\mathcal{U}~</script>中选择的控制信息。

•  wk <script type="math/tex" id="MathJax-Element-21">~w_k~</script>：是一个随机变量<script type="math/tex" id="MathJax-Element-22">\color{red}{随机变量}</script>，这个随机变量将会影响代价函数。
•  N <script type="math/tex" id="MathJax-Element-23">~N~</script>：表示控制的窗体时间。

离散时间系统代价函数

<script type="math/tex; mode=display" id="MathJax-Element-24">E\left\{\sum\limits_{k=0}^{N-1} g_k(x_k,u_k,w_k)~+~g_N(x_N)\right\}</script>

我们的优化目标就是优化这个系统的平均代价。

能够看到这个代价是每个决策的代价和终于状态代价的统计平均。

反馈

    前面描写叙述了动态规划的目的，动态规划为了优化一个随机函数。

它的解是平均意义上的最优，并非每次都是最优。动态规划问题能够分为随机优化问题以及确定优化问题。当中确定优化问题能够每次都取得最优解（算法导论上面介绍的就是确定优化问题，这仅仅是动态优化的冰山一角。）。

    动态规划除了能够分为随机动态规划和确定动态规划，还能够分为带反馈和不带反馈(feed back)。也有人叫做开环(open-loop)和闭环(closed-loop)。这个命名可能会导致我们理解错误。

由于，反馈并非指的前一级对后一级的反馈。而是当前状态xk<script type="math/tex" id="MathJax-Element-25">x_k</script>依据wk<script type="math/tex" id="MathJax-Element-26">w_k</script>得出的uk<script type="math/tex" id="MathJax-Element-27">u_k</script>导致的状态跳转。

如图：

    可见反馈真正的意义是，依据如今的状态以及信息wk<script type="math/tex" id="MathJax-Element-28">w_k</script>做决策做决策，并记录这个过程的状态跳转。

第一个栗子：随机动态优化问题

       如果系统是一个零售商的进货系统。进货是周期性的。如果一个周期需求是 wk <script type="math/tex" id="MathJax-Element-29">~w_k~</script>显然需求是一个随机变量，库存是 xk <script type="math/tex" id="MathJax-Element-30">~x_k~</script>。同一时候也表示这个系统的状态。我们的进货量 uk <script type="math/tex" id="MathJax-Element-31">~u_k~</script>也就是我们的决策。所以每一次周期完成后的库存能够表示为xk+1 = xk+uk?wk<script type="math/tex" id="MathJax-Element-32">x_{k+1}~=~x_k+u_k-w_k</script>。

因此我们能够建立例如以下模型：

这个离散时间系统就能够描写叙述为：

<script type="math/tex; mode=display" id="MathJax-Element-33">x_{k+1}~=~f_k(x_k,u_k,w_k)~=~x_k+u_k-w_k</script>

其代价函数会随着时间叠加，所以这个系统的代价函数为：

<script type="math/tex; mode=display" id="MathJax-Element-34"> E\left\{\sum\limits_{k=0}^{N-1}(cu_k+r(x_k))+R(x_N)\right\}</script>

我们能够看到每个周期其代价都会叠加，到最后会有一个终于状态的代价（为什么有这个代价呢？最好还是如果没有这个代价，在第N?2<script type="math/tex" id="MathJax-Element-35">N-2</script>个周期我们进货量为正无穷。定能满足需求。

可是这明显是不合理的。

）

第二个栗子：确定动态优化问题

    确定一个确定系统操作顺序问题：我们要找到A,B,C,D的最佳操作顺序。

当中有几个限制：
1. A必须在B之前运行，C必须在D之前运行
2. 必须从A和C開始，即起始状态必须为:SA<script type="math/tex" id="MathJax-Element-36">S_A</script>或者SC<script type="math/tex" id="MathJax-Element-37">S_C</script>
3. 状态 m <script type="math/tex" id="MathJax-Element-38">~m~</script>到 n <script type="math/tex" id="MathJax-Element-39">~n~</script>的跳转代价是 Cmn <script type="math/tex" id="MathJax-Element-40">~C_{mn}~</script>
则能够画出一个相似二叉树的图：

显然仅仅须要遍历整个图我们就可以找到一个最优解。

第三个栗子：来点复杂的无线网络问题

    系统描写叙述：我们须要在 N <script type="math/tex" id="MathJax-Element-247">~N~</script>个时隙中发送 M <script type="math/tex" id="MathJax-Element-248">~M~</script>个数据包，当中有几个限制：
1. 信道条件有两种：好的（概率为：p<script type="math/tex" id="MathJax-Element-249">p</script>）。坏的（概率为： 1?p <script type="math/tex" id="MathJax-Element-250">~1-p~</script>）
2. 在好的和坏的信道以下都能够传包。不同信道条件下传包的代价不同。好信道的代价为 PG <script type="math/tex" id="MathJax-Element-251">~P_G~</script>。

坏的信道的代价为 PB <script type="math/tex" id="MathJax-Element-252">~P_B~</script>
3.  N <script type="math/tex" id="MathJax-Element-253">~N~</script>个发送时隙完成后，最后剩余 m <script type="math/tex" id="MathJax-Element-254">~m~</script>个数据包的代价为 C(m) <script type="math/tex" id="MathJax-Element-255">~C(m)~</script>

以下我们依据已知的知识对系统建模：

• 系统状态： (mk,Hk) <script type="math/tex" id="MathJax-Element-256">~(m_k,H_k)~</script>： mk <script type="math/tex" id="MathJax-Element-257">~m_k~</script>表示剩余数据包的数量， Hk <script type="math/tex" id="MathJax-Element-258">~H_k~</script>表示信道条件。

• 控制信息： uk <script type="math/tex" id="MathJax-Element-259">~u_k~</script>有两个取值，0（表示不发送），1（表示发送）。

• 随机变量 w <script type="math/tex" id="MathJax-Element-260">~w~</script>:表示信道变化
• 系统描写叙述：mk+1=mk?uk,Hk+1=wk<script type="math/tex" id="MathJax-Element-261">m_{k+1} = m_k - u_k, H_{k+1} = w_k</script>
• 开销函数：
  
  E{∑k=0N?1g((mk,Hk),uk)+C(mN)}
  <script type="math/tex; mode=display" id="MathJax-Element-262">E\left\{\sum\limits_{k=0}^{N-1} g((m_k,H_k),u_k)+C(m_N)\right\}</script>
  问题解答见：http://blog.csdn.net/sylar_d/article/details/50900521

小结

经过以上栗子我们看出，动态规划问题具有以下几点特性：
1. 控制是局部的，仅仅取决于当前的状态xk<script type="math/tex" id="MathJax-Element-57">x_k</script>
2. 状态具有马尔科夫性。

3. 动态规划系统具有以下特性：

• 系统描写叙述： xk+1=fk(xk,uk,wk),k=0,1,…,N?1 <script type="math/tex" id="MathJax-Element-58">~x_{k+1}=f_k(x_k,u_k,w_k),k=0,1,\ldots,N-1~</script>
• 控制约束： uk∈U(xk) <script type="math/tex" id="MathJax-Element-59">~u_k \in \mathcal{U}(x_k)~</script>
• 随机概率分布： Pk(wk)=Pk(?|xk,uk) <script type="math/tex" id="MathJax-Element-60">~P_k(w_k) = P_k(·|x_k,u_k)~</script>
• 策略：有一系列的策略 π={μ0,…,μN?1} <script type="math/tex" id="MathJax-Element-61">~\pi=\{\mu_0,\ldots,\mu_{N-1}\}~</script>当中每个 μk <script type="math/tex" id="MathJax-Element-62">~\mu_k~</script>都将状态 xk <script type="math/tex" id="MathJax-Element-63">~x_k~</script>依照映射 uk=μk(xk) <script type="math/tex" id="MathJax-Element-64">~u_k = \mu_k(x_k)~</script>映射成为一个决策。
• 代价函数：从x0<script type="math/tex" id="MathJax-Element-65">x_0</script>開始的策略 π <script type="math/tex" id="MathJax-Element-66">~\pi~</script>的代价函数为：
  
  Jπ(x0)=E{∑k=0N?1gk(xk,μk(xk),wk)+gN(xN)}
  <script type="math/tex; mode=display" id="MathJax-Element-67">J_{\pi}(x_0) = E\left\{\sum\limits_{k=0}^{N-1}g_k(x_k,\mu_k(x_k),w_k)+g_N(x_N)\right\}</script>
• 最优策略：
  
  J?(x0)=minπJπ(x0)
  <script type="math/tex; mode=display" id="MathJax-Element-68">J^*(x_0) = \mathop {min}\limits_{\pi}J_{\pi}(x_0)</script>
• 最优策略 π? <script type="math/tex" id="MathJax-Element-69">~\pi^*~</script>必须满足：
  
  Jπ?(x0)=J?(x0)
  <script type="math/tex; mode=display" id="MathJax-Element-70">J_{\pi^*}(x_0) = J^*(x_0)</script>