Dinkelbach method is used to solve a fractional programming problem, especially for convex nonlinear fractional programming (NLFP) by successively solving a sequence of simplified nonlinear programming.
Let us consider a non-linear fractional programming
\[ \max_{x} \frac{f(x)}{g(x)}, ~~s.t.,~~ h(x)\le 0. \]
Note that the functions \(f\) and \(g\) are continuous and \(h(x)\le 0\) is bounded.
- Consider a function
\[ F(\lambda_k) = \max_{x}\{(f(x)-\lambda_k g(x)) : h(x)\le 0\} \]
Note that the maximizer \(x_0\) is the optimal solution of the original problem if \(F=0\). {: .notice–success}
- Step 1: starting with \(\lambda_0=0\), we get
\[ F(\lambda_0) = \max_{x}\{f(x): h(x)\le 0 \}. \]
Let us define the maximizer as \(x_0\). Then, we can manually update the value of \(\lambda\) as
\[ \lambda_1 = \frac{f(x_0)}{g(x_0)} \] - Step 2~n: Again obtain the solution of \(F(\lambda_n)\). - Stopping criterion: \(F(\lambda_k)\le \epsilon\)
Intuition: Let us assume that we have a \(\lambda < \max f/g\), i.e., there exists a value of \(x\) that satisfying \(\lambda<f/g\). This means that \(f-\lambda g >0\). As the value of \(\lambda\) increases, \(F(\lambda)\) monotonically decreasing. That is, there exists a unique solution.