= Dinkelbach's algorithm
{c}
To maximize $A(x)/B(x)$ on a nonempty <compact> feasible set $X$, assume $A,B$ are continuous and $B>0$. Define the parametric optimal value
$$
F(r)=\max_{x\in X}[A(x)-rB(x)].
$$
If $r_* =\max_X A/B$, then $F(r)>0$ for $r<r_*$, $F(r_*)=0$, and $F(r)<0$ for $r>r_*$. This follows by comparing each ratio with $r$ and multiplying by its positive denominator.
Starting with a feasible ratio $r_0=A(x_0)/B(x_0)$, choose a global maximizer $x_k$ of $A-r_kB$ and update
$$
r_{k+1}=\frac{A(x_k)}{B(x_k)}=r_k+\frac{F(r_k)}{B(x_k)}.
$$
The values increase while staying below $r_*$. Their limit must be $r_*$: otherwise continuity of $F$ and an upper bound on $B$ would force increments bounded away from zero. A zero residual is an exact certificate. These assumptions give attained subproblems and convergence; a merely local inner optimizer does not provide this certificate. The method replaces a ratio objective by a succession of difference objectives. <On Nonlinear Fractional Programming by Werner Dinkelbach>[Werner Dinkelbach, On Nonlinear Fractional Programming, Management Science13(7),1967, pp492–498; publisher abstract describes the ratio/parametric relationship]{ref}
Back to article page
