分数规划

分数规划用于解决下面的问题：

$$ c\left(x\right)=\frac{a\left(x\right)}{b\left(x\right)},x\in X $$

$$ c_m=c\left(x_0\right)=\max\left\{c\left(x\right)|x\in X\right\} $$

其中b(x)是正值函数，要求我们求c_m。由于|X|可能非常大，我们往往无法进行暴力求解，需要转换问题。

容易发现：

$$ c\left(x\right)=\frac{a\left(x\right)}{b\left(x\right)}\Rightarrow a\left(x\right)-c\left(x\right)b\left(x\right)=0 $$

我们定义如下辅助函数：

$$ h_c\left(x\right)=a\left(x\right)-c\cdot b\left(x\right) $$ $$ h\left(c\right)=\max\left\{h_c\left(x\right)|x\in X\right\} $$

很显然：

$$ u>v\Rightarrow\forall x\in X\left(h_u\left(x\right)-h_v\left(x\right)=\left(v-u\right)b\left(x\right)<0\Rightarrow h_u\left(x\right)<h_v\left(x\right)\right) $$

因此函数h严格递减，且函数h为双射，故h的逆函数g存在，同时g也是双射，且g也严格递减。推导得到：

$$ \left\{\begin{array}{l} \frac{a\left(x\right)}{b\left(x\right)}\le c_m\Rightarrow a\left(x\right)-c_m\cdot b\left(x\right)\le 0\\ a\left(x_0\right)-c_m\cdot b\left(x_0\right)=0 \end{array}\right.\Rightarrow h\left(c_m\right)=0 $$

因此我们得知

$$ c_m=g\left(0\right) $$

假设存在方法f，其可以以O(T)的时间复杂度计算h(c)，那么我们只需要依靠h的递减性质对c做二分，就可以以时间复杂度O(T*log2(C))计算得到c_m。