Can the Dinkelbach method solve nonlinear fractional programming problems?

1.1k Views Asked by At

Can the Dinkelbach method solve nonlinear fractional programming problems, where the functions in the numerator and denominator are not necessarily quadratic and not convex either?

If not is there a variant or a hybrid version of Dinkelbach's method that caters to these cases?

1

There are 1 best solutions below

5
On

Denote the problem as $$\min_{x \in X} \frac{f(x)}{g(x)}$$ and define: $$h(\lambda) = \min_{x \in X} \{ f(x)-\lambda g(x) \}$$ When $g(x) \geq 0$ for all $x$ in $X$, it is still imminent that $h(\lambda) \leq 0$ if and only if $\min_{x \in X} \frac{f(x)}{g(x)} \leq \lambda$. The problem now is to find the smallest $\lambda$ such that $h(\lambda) \leq 0$.

Without concavity of $g$, the subproblem for computing $h(\lambda)$ is not convex, so it may be hard to compute $h(\lambda)$. However, the function $h$, being the minimum of functions that are affine in $\lambda$, is still concave. Therefore, it is still straightforward to find the optimal $\lambda$ with, e.g., bisection search.