决策单调性

最优决策点 J(i) 随 i 单调;每个决策的最优位置连续。单交叉是更强的两两比较条件。

标签 动态规划 / 决策单调性 / 单交叉

定义

考虑 1D/1D 动态规划

𝑓(𝑖)=min𝐿(𝑖)≤𝑗≤𝑅(𝑖)𝑄𝑖,𝑗(𝑓(𝑗)).

记

𝐽(𝑖)≝argmin𝐿(𝑖)≤𝑗≤𝑅(𝑖)𝑄𝑖,𝑗(𝑓(𝑗)),

多个最小值取最小的 𝑗。若

𝐽(𝑖)≤𝐽(𝑖+1),

称最优决策点具有单调性。

区间结构

若 𝐽 单调,则对每个决策 𝑗,集合

𝐼(𝑗)={𝑖:𝐽(𝑖)=𝑗}

是一段区间,可能为空。因为若 𝑖<𝑘 且 𝐽(𝑖)=𝐽(𝑘)=𝑗,则对任意 𝑖<𝑡<𝑘,

𝑗=𝐽(𝑖)≤𝐽(𝑡)≤𝐽(𝑘)=𝑗,

所以 𝐽(𝑡)=𝑗。

非空的 𝐼(𝑗) 按下标 𝑗 排列,互不相交。若 𝑗 和下一个出现的决策 𝑗′ 都有非空区间,则

𝑒𝑗+1=𝑠𝑗′,

其中 𝐼(𝑗)=[𝑠𝑗,𝑒𝑗],𝐼(𝑗′)=[𝑠𝑗′,𝑒𝑗′]。这给出了把最优决策按区间维护的基础。

判定

𝐽 单调不是自动成立的。当 𝑄𝑖,𝑗(𝑓(𝑗))=𝑤(𝑖,𝑗) 与 𝑓(𝑗) 无关时,若权重矩阵 𝑤 满足 Monge 性,则 𝐽(𝑖)≤𝐽(𝑖+1)。这是常用的充分条件,但不是必要条件;也可以直接证明 𝐽 的单调性。

单交叉

当 𝑄𝑖,𝑗 依赖 𝑓(𝑗) 时,权重不再是一个固定矩阵;单交叉需要在固定 𝑓(𝑗) 和 𝑓(𝑘) 后单独验证。

对两个决策 𝑗<𝑘,固定 𝑓(𝑗) 和 𝑓(𝑘),考虑

𝐷(𝑖)=𝑄𝑖,𝑗(𝑓(𝑗))−𝑄𝑖,𝑘(𝑓(𝑘)).

若 𝐷(𝑖) 在 𝑖 增大时符号最多改变一次,并且新决策 𝑘 优于旧决策 𝑗 的位置构成一个后缀,则称两个决策满足单交叉。

单交叉比 𝐽 单调更强:𝐽 单调只描述最终最优决策的次序,单交叉则限制任意两个决策的相对优劣。没有单交叉时,一个新决策可能在旧决策区间的中间更优,只用一个分界无法正确截断区间。

常见误区

  • 𝐽 单调不是自动成立的;需要单独证明。
  • 𝐽 单调不能推出单交叉;依赖两两比较只有一个分界的方法还需要额外条件。
  • 多个最小值时要固定取最小的 𝑗,否则 𝐼(𝑗) 的边界可能不唯一。
  • 𝐽 单调描述的是决策下标,不是 𝑓(𝑖) 的单调性。
源码位置