分数规划
把比值优化 max f/g 转化为参数化判定 max(f-λg),用二分答案或 Dinkelbach 求零点。标签 数学 / 分数规划 / 二分答案 / 最优化
定义
设 为可行集,,且 。分数规划是求
或对应的最小值。 为有限集或组合结构时称为离散分数规划; 的情形见 01 分数规划。
参数化判定
对 ,令
因为 ,
所以 是 的零点。 是仿射函数族的逐点上确界,因而凸且单调不增。
二分答案
在包含 的区间 上二分。每次取 ,求 :
- 若 ,则 ,令 ;
- 否则 ,令 。
二分到区间长度小于精度。每次判定只需回答一个参数化问题:在 上最大化 ,或判断其最大值是否非负。
Dinkelbach 算法
从任一 开始,重复
若 ,则 ,停止。有限可行集上有限步终止;实际实现常与二分答案二选一。
与拟凹规划的关系
若 是凸集, 是仿射函数,则水平集
等于
后者是凸集。因此最大化比值是拟凹规划;分数规划把它化为一族线性判定。对一般 ,同样的转化仍成立,只是判定问题不再线性。
常见误解
- 忽略 : 变号时不能直接乘以 , 的单调性也会失效。
- 把分数规划等同于二分答案:二分只是求 零点的一种方法,Dinkelbach 也可用。
- 把 理解为“某个固定 最优”:它只说明存在 的比值不低于 。
- 最小化比值时套用最大化判据:方向要反过来。
- 认为分数规划会自动降低判定难度:它只把比值问题化为参数化问题,子问题本身仍需高效算法。