四边形不等式优化学习笔记
学会，但没完全学会
参考 肖然的博客
四边形不等式
原形式
有一个双变量函数 $f(x,y)$，如果对于 $\forall a\le b\le c\le d$，都满足 $f(a,d)+f(b,c)\ge f(a,c)+f(b,d)$ 则称其满足 四边形不等式。
等价形式
对于 $\forall a<b$，都有 $f(a,b+1)+f(a+1,b)\ge f(a,b)+f(a+1,b+1)$。
这一形式的必要性显然，下证其充分性：
若 $a+1<b$ 则：
\[\begin{aligned}
f(a,b+1)+f(a+1,b)&\ge f(a,b)+f(a+...
