分数规划

Published: April 05, 2019 by Daltao

• Categories:
• algorithm 101

• Tags:

假设存在两个实值函数$A(x)$和$B(x)$，其中$B(x)$值域为$\mathbb{R}^+$。要求下面分数的最大值：

$$\frac{A(x)}{B(x)}$$

我们需要定义一个辅助函数$H_c(x)$，其定义如下：

$$H_c(x)=A(x)-c\cdot B(x)$$

同时我们定义函数$H(c)$：

$$H(c)=\max\{H_c(x)|x\in \mathbb{R} \}$$

对于任意实数$a$，$b$，有

$$H_a(x)-H_b(x)=(b-a)B(x)$$

由于$B(x)$的取值始终为正数，因此容易得到对于任意$x\in \mathbb{R}$，都有$a > b \Rightarrow H_b(x) > H_a(x)$，可以推得$H(c)$是严格单调递减函数。

假设$c_0=\max(\left\{\frac{A(x)}{B(x)} | x \in \mathbb{R}\right\})$，即我们要求的结果，可以给出下面不等式

$$c_0\geq \frac{A(x)}{B(x)} \Rightarrow A(x)-c_0B(x)\leq 0$$

其中等号可以在某个特殊的x值取到，因此有$H(c_0)=0$。考虑到$H$函数的严格单独递减性质，因此如果我们能找到某个点$c'$满足$H(c')=0$，那么我们就可以直接确定$c'=c_0$。利用$H$函数的严格单调递减性质来对$c_0$进行二分查找，我们可以只需要计算$O(\log_2(|C|))$次$H$函数，就可以得到想要的$c_0$。