u200b 记优化问题(1-2)的最优解为 。若某一场景中需求 的取值为 ,那么显然 可能与 差别很大。一个很自然的想法是:能否给优化问题(1-2)添加一个约束 。考虑到 是一个分片线性函数,那么该约束等价为 其中 表示需求 的所有可能的取值构成的集合。 上述约束过强,若 足够大,那么很有可能没有 能够满足上述约束,即优化问题不可行。进而我们可以考虑添加这样一个约束: 的概率小于阈值 。这就是一个 chance constraint ,表示如下 亦即 我们来看看 的形式 于是乎chance constraint (1-7)等价于 相对于约束(1-5)来说,约束(1-8)宽松了很多。 u200b 我们对报童问题进行拓展,考虑一个多阶段问题。假定公司需要在一个时间长度为 的经营活动中做决策。在第 个时间段,需求是一个随机变量,记为 ,其中 。在开始阶段,即 时,我们已知当前存货量为 。在每个阶段,即 时,公司观测到当前存货量为 ,然后公司决定购入一些货物,使得存货量更新为 ,显然 ;库存量更新之后,公司观测到需求量 ( 是 的一个实例),于是在 时段开始时,库存量 。注意 可能为正也可能为负,为负数时表示拖欠或者交付延误。 时段公司的代价如下 其中 表示购买成本, 表示延误成本, 表示库存成本。一般来说, , 。 u200b 目标是所有时间段的代价和的期望最小,可写为如下优化问题 u200b 若 ,那么优化问题(1-9)与优化问题(1-2)是等价的。 时,情况就复杂很多了。记 表示截止到时间 时的历史需求构成的随机过程,记 表示 的一个实例。在 时间段开始时,我们不知道 ,但是我们很有可能知道 在 情况下的条件概率分布。假定我们知道该条件分布。 u200b 最后一个时间段,即 ,我们观测到了 ,然后我们求解下述优化问题: 亦即求解如下问题 u200b 显然优化问题(1-10)或者(1-11)的目标函数最优解时一个关于 以及 的函数,我们将其记为 u200b 在 时,我们求解如下优化问题 注意到 ,优化问题(1-12)可以写为 u200b 显然优化问题(1-12)或者(1-13)的目标函数最优解时一个关于 以及 的函数,我们将其记为 u200b 类似地对于 ,我们求解如下优化问题 u200b 最后在 时,求解如下问题 u200b 我们再来回顾下优化问题(1-10)-(1-14)。从 开始,我们需要回溯求出函数 。一般来说,很难或者几乎不可能求出上述函数。如果假定 是"阶段独立"(stagewise independent)的,那么情况会变得简单很多。所谓的"阶段独立"是指, 与 独立。那么优化问题(1-10)-(1-14)中的条件期望就直接转换了期望。目标函数最优值也就可以写为 。此时,我们可以对 以及 进行离散化,对于每一个 我们求解相应的 。但是该方法面临着维数灾难,如果 以及 可取值较多,那么该方法几乎不可行。后面章节我们会谈到,动态规划利用了函数的凸性来降低维数带来的灾难。 u200b 假定我们已经求解出来了优化问题(1-10)-(1-14)。记最优解为 。对于 , 是 以及 的函数。而 仅仅与 有关。在"阶段独立"的假设下, 仅仅是关于 的函数。考虑到 自身是由 与 决定。所以,我们考虑将决策视为关于 的函数,即 。这样的一组决策,我们称为实行策略,或者简称策略,policy。策略是指基于当前阶段可获得的信息来做出何种决策的规则。 u200b 我们可以将优化问题(1-9)理解为在所有可能的策略中,寻找代价期望最少的策略。动态规划问题求解出来的解即为最优策略。在"阶段独立"的情况下,我们假定 是下列无约束优化问题的解。 我们可以证明上述目标函数关于 是凸函数,并且当 逼近于无穷大时,函数值为正无穷大。因而,上述优化问题一定存在最优解。再考虑函数的凸性,可知 时最优策略。当没有"阶段独立"的假设时,结论依然成立,不过此时 与 有关。 u200b 我们证明优化问题(1-15)的目标函数时一个凸函数,无论"阶段独立"是否成立。 u200b 记 , 是任意两个数, , . u200b 证毕。 记 ,那么依据章节1.1.1中的分析,该函数是一个关于 的凸函数。给定 ,记 关于 最优解为 ,那么 注意函数 是关于 的凸函数。关于它的证明略,可依据二次函数画图理解。那么 是关于 的凸函数。 我们再来观察 ,如式(1-13)所示,目标函数中与 相关的部分可以写为关于 的凸函数(注意包含了一个仿射变换,以及一个求期望运算,都是保凸的)。该凸函数再约束 下求最优值,那么所得目标函数是一个关于 的函数,同上,该函数关于 凸。进而 是关于 的凸函数。 以此类推,可证明 是关于 的凸函数。 那么依据仿射变换跟期望运算的保凸性,可知优化问题(1-15)的目标函数时一个凸函数,无论"阶段独立"是否成立。