分数规划

把比值优化 max f/g 转化为参数化判定 max(f-λg),用二分答案或 Dinkelbach 求零点。

标签 数学 / 分数规划 / 二分答案 / 最优化

定义

设 𝑆 为可行集,𝑓,𝑔:𝑆→ℝ,且 𝑔(𝑥)>0。分数规划是求

𝜆∗=max𝑥∈𝑆𝑓(𝑥)𝑔(𝑥)

或对应的最小值。𝑆 为有限集或组合结构时称为离散分数规划;𝑆⊆{0,1}𝑛 的情形见 01 分数规划。

参数化判定

对 𝜆∈ℝ,令

𝐹(𝜆)=max𝑥∈𝑆(𝑓(𝑥)−𝜆𝑔(𝑥)).

因为 𝑔(𝑥)>0,

𝐹(𝜆)≥0当且仅当𝜆≤𝜆∗.

所以 𝜆∗ 是 𝐹 的零点。𝐹 是仿射函数族的逐点上确界,因而凸且单调不增。

二分答案

在包含 𝜆∗ 的区间 [𝐿,𝑅] 上二分。每次取 𝑚=𝐿+𝑅2,求 𝐹(𝑚):

  • 若 𝐹(𝑚)≥0,则 𝜆∗≥𝑚,令 𝐿=𝑚;
  • 否则 𝜆∗<𝑚,令 𝑅=𝑚。

二分到区间长度小于精度。每次判定只需回答一个参数化问题:在 𝑆 上最大化 𝑓(𝑥)−𝑚𝑔(𝑥),或判断其最大值是否非负。

Dinkelbach 算法

从任一 𝜆0 开始,重复

𝑥𝑘∈argmax𝑥∈𝑆(𝑓(𝑥)−𝜆𝑘𝑔(𝑥)),𝜆𝑘+1=𝑓(𝑥𝑘)𝑔(𝑥𝑘).

若 𝐹(𝜆𝑘)=0,则 𝜆𝑘=𝜆∗,停止。有限可行集上有限步终止;实际实现常与二分答案二选一。

与拟凹规划的关系

若 𝑆 是凸集,𝑓,𝑔 是仿射函数,则水平集

{𝑥∈𝑆:𝑓(𝑥)𝑔(𝑥)≥𝜆}

等于

{𝑥∈𝑆:𝑓(𝑥)−𝜆𝑔(𝑥)≥0},

后者是凸集。因此最大化比值是拟凹规划;分数规划把它化为一族线性判定。对一般 𝑓,𝑔,同样的转化仍成立,只是判定问题不再线性。

常见误解

  • 忽略 𝑔(𝑥)>0:𝑔 变号时不能直接乘以 𝑔,𝐹 的单调性也会失效。
  • 把分数规划等同于二分答案:二分只是求 𝐹 零点的一种方法,Dinkelbach 也可用。
  • 把 𝐹(𝜆)≥0 理解为“某个固定 𝑥 最优”:它只说明存在 𝑥 的比值不低于 𝜆。
  • 最小化比值时套用最大化判据:方向要反过来。
  • 认为分数规划会自动降低判定难度:它只把比值问题化为参数化问题,子问题本身仍需高效算法。
源码位置