四边形不等式/决策单调性

四边形不等式

对于函数 \(w(x,y)\)，如果对于所有的 \(a\leq b \leq c \leq d\) 都满足

\[w(a,c)+w(b,d)\leq w(a,d)+w(b,c)\]
则称其满足四边形不等式。还有一种等效写法对于 \(l2\)，则必有 \(b-a\) 或 \(d-c\) 有一项大于等于 \(2\)，即求证

\[w(b-1,c)+w(b,d)\leq w(b-1,d)+w(b,c)\]
为 \(b-1\leq b\leq c\leq d\) 的归纳结果证毕。
</blockquote>四边形不等式有一些性质

• \(w_1,w_2\) 满足四边形不等式，有常数 \(c_1,c_2\leq 0\)，则 \(c_1w_1+c_2w_2\) 同样满足四边形不等式。
  
• 对于任意函数 \(f,g\)，函数 \(w(i,j)=f(i)-g(j)\) 必然满足四边形不等式。
  
• 对于一个凸函数 \(h\)，如果 \(w\) 满足区间包含性和四边形不等式，那么 \(w^{'}(i,j)=h(w(i,j))\) 也满足四边形不等式。
  

区间包含性指对于 \(a\leq b\leq c\leq d\)，有 \(w(a,d)\geq w(b,c)\)。
决策单调性

对于函数 \(f(i)\)，令 \(\text{opt(i)}\) 表示所有能让 \(f(i)\) 取到最值的 \(j\) 的集合，之后通常只考虑 \(\text{opt(i)}\) 的最值即可。令 \(p_i=\max \text{opt(i)}\)（当然最小值也可以）称为最优决策点。
离线情况

对于函数

\[f(i)=\min_{1\leq j\leq i}\{ w(j,i)\}\]
有决策单调性

\[i