分数规划

Published: by Creative Commons Licence

  • 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$。