WQS 二分

WQS 二分用来求凸函数在一个给定位置处的函数值。如果一个函数 $f(x)$ 是凸函数，则有 $f^{\prime \prime }(x)⩽0$ 恒成立。考虑 $f$ 在 $x_0$ 处的切线，表示为一条斜率为 $k$ 的直线 $y=kx+b$，代入点 $(x_0,f(x_0))$ 则得到 $f(x_0)=k{x}_0+b$。希望对于某一个 $x$ 求出 $f(x)$。

另一方面，考虑问题 ${\max }_x(f(x)-kx)$。记 $g(x):=f(x)-kx$ 则式子转化为 ${\max }_{x}g(x)$。求导得到 $g^{\prime }(x)=f^{\prime }(x)-k$，令导数等于 $0$ 得到驻点 $x=x_0$，又因为 $f$ 是凸函数，所以这 $x_0$ 就是极大值点。因此，${\max }_{x}g(x)=g(x_0)=f(x_0)-k{x}_0=b$。

这说明可以通过求解问题 ${\max }_x(f(x)-kx)$ 从而由 $k$ 同时得到 $x_0$ 和 $f(x_0)$ 的值，因为 $x_0$ 就是这个新函数 $g$ 的极大值点，而 $f(x_0)$ 就是 $g$ 的极大值。又因为 $f$ 是凸函数，所以 $k=f^{\prime }(x)$ 随着 $x$ 的增加而单调递减。所以我们可以二分 $k$ 的值，通过计算 ${\max }_x(f(x)-kx)$ 可以知道切点 $x_0$ 是在目标位置的左边还是右边，从而缩短查找区间的长度一半。二分结束后，就得到了目标位置处的 $k$ 值，也可以直接计算出 $f$ 在目标位置处的函数值了。

TIP

对于定义域和值域都是整数的函数，由于它的差分值一定是个整数，所以可以在整数范围内二分这个 $k$，而不需要浮点数运算。这样可以避免精度问题。

WQS 二分实际上实现的是从单个点处的性质到整体的性质的转化。最常见的问题就是从 $n$ 个数里恰好选出 $k$ 个，求最小代价。恰好选出 $k$ 个可能不是那么好算，使用 WQS 二分就可以转化成从 $n$ 个数里选出任意个，求最小代价。