分式规划

分式规划（fractional programming）研究目标含函数比值的优化。分母的符号、是否可能为零，以及分子分母的曲率，是变换能否保持原问题含义的关键。以下在正分母下，把最大化比值转成一串不含除法的子问题。

收益和投入的比值

考虑教学模型 $\underset{0\le x\le 3}{max}R(x)=(4x-x^2)/(1+x)$。分子表示设定的净产出，分母为正的投入尺度。最大化分子单独会选择二，但比值在二处仅为4/3，未必最好。求导得到 $$R^{\prime }(x)=\frac{(4-2x)(1+x)-(4x-x^2)}{(1+x{)}^2}=\frac{4-2x-x^2}{(1+x{)}^2}.$$ 分子在非负区间严格递减，在 $x^{\ast }=\sqrt{5}-1$ 过零，故比值先增后减，全局最大值为 ${\eta }^{\ast }=6-2\sqrt{5}\approx 1.527864$。

比值在 √5−1 处最优，x=2 虽最大化分子却有更低比值。

比值最优等价于参数函数的零点

设C非空紧集，f、g连续，且对所有 $x\in C$ 有 $g(x)>0$。紧性给出 $g_{min}>0$，比值达到最大值η*。定义 $$\Phi (\eta )=\underset{x\in C}{max}\{f(x)-\eta g(x)\}.$$ 在比值最大点处，若η小于η*，差值 $g(x)({\eta }^{\ast }-\eta )>0$，所以Φ为正；若η等于η*，每点差值都非正且最优点取零；若η大于η*，每点差值都不超过 $-(\eta -{\eta }^{\ast })g_{min}<0$。因此 $\Phi (\eta )=0$ 当且仅当η=η*。这就是参数化处理的核心等价关系。

给定ηk，精确求出子问题最大点xk，再置 ${\eta }_{k+1}=f(x_k)/g(x_k)$，称为Dinkelbach型更新。若初始η0不大于η*，则 $\Phi ({\eta }_k)\ge 0$，并有 $${\eta }_{k+1}-{\eta }_k=\frac{\Phi ({\eta }_k)}{g(x_k)}\ge 0,{\eta }_{k+1}\le {\eta }^{\ast }.$$ 序列单调有界，故有极限。g在紧集上有有限上界，参数函数Φ连续（甚至按这个上界Lipschitz），所以上式使Φ在极限处为零，极限必为η*。精确解子问题和正分母在证明中都不可省略。

Φ 的正负区分当前参数小于或大于最佳比值。

主例子问题为最大化 $-x^2+(4-\eta )x-\eta$，其全局最大点是 $(4-\eta )/2$ 在区间上的截断。由η0=0开始，先选x0=2，更新η1=4/3；再选x1=4/3，更新η2=32/21；随后很快接近精确值。每轮最大化的是扣除η倍投入后的差，而非原分子。

仿射分式变换及边界

若分子 $c^{𝖳}x+d$、分母 $e^{𝖳}x+h>0$ 都仿射，可令 $t=1/(e^{𝖳}x+h)>0,y=tx$，则归一化 $e^{𝖳}y+ht=1$，约束 $Gx\le b$ 化为 $Gy\le bt$，目标化为 $c^{𝖳}y+dt$。逆变换x=y/t证明t为正时逐点等价。若允许t=0，可能只代表原问题趋向无穷远时的极限值，不能把y/t当成可恢复的有限解。

变式把投入固定为一，则最大化 $4x-x^2$，解回到二、目标四，说明分母影响决策而不只是改变单位。反例 $1/x$ 在 $0<x\le 1$ 上最大化时没有有限最优值；虽然分母逐点为正，但可行集不紧、分母没有正下界，前面的收敛论证不能直接套用。分母可能正负变号时，乘不等式也会改变方向，需要另行分区。

可运行的参数化迭代

函数只用标准库，输入η0、容限及预算，返回参数、子问题解和残差，不改写输入。专用于上述凹二次子问题，每轮解析解为常数成本，历史为 $O(K)$。一般分式规划的难点可能完全在内层全局优化；把内层局部解当精确最大值，会破坏Φ的符号和证书。

Python 3

import math

def fractional_iteration(initial=0.0,tolerance=1e-12,budget=20):
    optimum = 6-2*math.sqrt(5)
    if initial > optimum or tolerance <= 0:
        raise ValueError("initial ratio must not exceed optimum in this demo")
    eta,trace = float(initial),[]
    for _ in range(budget):
        x = min(3.0,max(0.0,(4-eta)/2))
        f,g = 4*x-x*x,1+x
        residual = f-eta*g
        next_eta = f/g
        trace.append((eta,x,residual,next_eta))
        eta = next_eta
        if abs(residual) <= tolerance:
            break
    return trace

for row in fractional_iteration():
    print(tuple(round(v,12) for v in row))
assert abs(fractional_iteration()[-1][1]-(math.sqrt(5)-1)) < 1e-9