四边形不等式/决策单调性
四边形不等式对于函数 \(w(x,y)\)，如果对于所有的 \(a\leq b \leq c \leq d\) 都满足
\
则称其满足四边形不等式。还有一种等效写法对于 \(l2\)，则必有 \(b-a\) 或 \(d-c\) 有一项大于等于 \(2\)，即求证
\
为 \(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)}\)（当然最小值也可以）称为最优决策点。
离线情况
对于函数
\
有决策单调性
\[i
页:
[1]