决策单调性
最优决策点 J(i) 随 i 单调;每个决策的最优位置连续。单交叉是更强的两两比较条件。标签 动态规划 / 决策单调性 / 单交叉
定义
考虑 1D/1D 动态规划
记
多个最小值取最小的 。若
称最优决策点具有单调性。
区间结构
若 单调,则对每个决策 ,集合
是一段区间,可能为空。因为若 且 ,则对任意 ,
所以 。
非空的 按下标 排列,互不相交。若 和下一个出现的决策 都有非空区间,则
其中 ,。这给出了把最优决策按区间维护的基础。
判定
单调不是自动成立的。当 与 无关时,若权重矩阵 满足 Monge 性,则 。这是常用的充分条件,但不是必要条件;也可以直接证明 的单调性。
单交叉
当 依赖 时,权重不再是一个固定矩阵;单交叉需要在固定 和 后单独验证。
对两个决策 ,固定 和 ,考虑
若 在 增大时符号最多改变一次,并且新决策 优于旧决策 的位置构成一个后缀,则称两个决策满足单交叉。
单交叉比 单调更强: 单调只描述最终最优决策的次序,单交叉则限制任意两个决策的相对优劣。没有单交叉时,一个新决策可能在旧决策区间的中间更优,只用一个分界无法正确截断区间。
常见误区
- 单调不是自动成立的;需要单独证明。
- 单调不能推出单交叉;依赖两两比较只有一个分界的方法还需要额外条件。
- 多个最小值时要固定取最小的 ,否则 的边界可能不唯一。
- 单调描述的是决策下标,不是 的单调性。