Dinkelbach's algorithm

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 valueIf $r_{\ast }={\max }_{X}A/B$, then $F(r)>0$ for $r<r_{\ast }$, $F(r_{\ast })=0$, and $F(r)<0$ for $r>r_{\ast }$. 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_{k}B$ and updateThe values increase while staying below $r_{\ast }$. Their limit must be $r_{\ast }$: 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. ^[ref]