【算法】关于凸函数的一个等价形式的应用 (有增补)-永无岛

UPD on 2021/2/10 :
想到可能因为年代过于久远，2014 年集训队论文中的一个小结论要找的话稍微有点麻烦，这里直接挂出来算了。

前置芝士:
$$上凸函数 \Leftrightarrow \forall x_{1},x_{2} \in 定义域,f(\frac{x_{1}+x_{2}}{2}) \geq \frac{f(x_{1})+f(x_{2})}{2}$$
注：这个上凸定义不严谨，极端情况下一些直线也会被这个定义定义为上凸的。
应用：
1. $$\large 极值点左偏 \Leftarrow 1 阶导上凸 \Leftarrow 3 阶导 \leq 0$$
右边的等价符号显然，只论证左边的推导符号。
$1$阶导上凸 $\rightarrow \forall x_{1},x_{2} \in$ 定义域,$f'(\frac{x_{1}+x_{2}}{2}) \geq \frac {f'(x_{1})+f'(x_{2})}{2}$
假设 $x_{1}$,$x_{2}$是关于极值点对称的两个点，就有: $0 \geq \frac{f'(x_{1})+f'(x_{2})}{2}$
即 $f'(x_{2})<-f'(x_{1})$
从图像的角度理解，就是从极值点往两边，左边的函数值始终比关于极值点对称的右边一点的下降速度更快。
借鉴高中物理微元法（其实就是定性分析）可得，
若该极值为极小值，则 $f(x_{2})<f(x_{1})$, 要找一个值 $x_{3}$满足 $f(x_{3})=f(x_{2})$的话，就有 $x_{2}+x_{3}>2x_{0}$
其他情况同理分析。
2.2014 集训队论文 余行江《矩阵命题报告》
这篇论文中提到了一个结论：
如果对于一张完全二分图，建立源汇，源向左边的 $n$ 个点连容量为 $1-k$ ，费用为 $0$ 的边；左边的每个点和右边的每个点都连容量为 $inf$ ，费用为 $a_{i,j}$(随意) 的边；右边的每个点向汇连容量为 $1+k$ ，费用为 $0$ 的边。那么，这张图的最大费用流是关于 k 的上凸函数。
证明：
首先根据上凸函数的性质，我们要证的就是，$\forall x_{1},x_{2} \in [-1,1]$, 若当 $k=x_{1},x_{2}$时的最大收益为 $f(x_{1}),f(x_{2})$时，则 $f(\frac{x_{1}+x_{2}}{2})\geq \frac{f(x_{1})+f(x_{2})}{2}$, 也就是对于 $k=\frac{x_{1}+x_{2}}{2}$, 存在一种方案使得收益不小于 $\frac{f(x_{1})+f(x_{2})}{2}$。
这个是可以根据 $f(x_{1})$和 $f(x_{2})$的方案构造出来的，把两个方案在二分图中间的每条边的流量缩减到一半，再拼起来，收益是 $\frac{f(x_{1})+f(x_{2})}{2}$，而且满足二分图两边关于流量的限制。

个人觉得上面的第二个应用开拓了一种新的证明思路，在对一些打表或猜测得出的结论的证明中可能会有一些作用。