# convert a special case of nonlinear fractional programming into a convex problem

Is it possible to convert a fractional problem (maximization) with objective function equal to the ratio of a concave function and convex function ? This question sound impossible but I have read this claim in wikipedia without any reference !

https://en.wikipedia.org/wiki/Nonlinear_programming#Methods_for_solving_the_problem

"If the objective function is a ratio of a concave and a convex function (in the maximization case) and the constraints are convex, then the problem can be transformed to a convex optimization problem using fractional programming techniques"

Here is some insight into Jean's answer, showing what that final problem means. Suppose you transform the problem to finding a vector $(y,t) \in \mathbb{R}^{n+1}$ to solve: \begin{align*} &\mbox{Max: } & tf(y/t) \\ &\mbox{Subject to: } & tg(y/t) \leq 1 \\ & & y/t \in S \\ & & t>0 \\ & & y \in \mathbb{R}^n \end{align*} where $S$ is a convex subset of $\mathbb{R}^n$, the functions $f(\cdot)$ and $g(\cdot)$ are defined over $S$, and $f$ is concave while $g$ is convex. To show this is a convex optimization problem, it suffices to show:

i) The constraints $y/t \in S$, $y \in \mathbb{R}^n$, $t >0$ together specify a convex set.

ii) The function $tf(y/t)$ is concave in the joint variables $(y,t)$.

iii) The function $tg(y/t)$ is convex in $(y,t)$.

To this end, define $A$ as the set of all $(y,t)$ such that $t>0, y \in \mathbb{R}^n, y/t \in S$.

Claim 1: The set $A$ is a convex subset of $\mathbb{R}^{n+1}$.

Proof: Let $(y_1,t_1)$ and $(y_2,t_2)$ be elements if $A$. Let $\theta \in [0,1]$ and define $\overline{\theta} = 1-\theta$. We want to show that $$(\theta y_1 + \overline{\theta}y_2, \theta t_1 + \overline{\theta}t_2) \in A$$ Since $t_1>0$ and $t_2>0$, it follows that $\theta t_1 + \overline{\theta}t_2>0$. It remains to check the ratio condition: $$\frac{\theta y_1 + \overline{\theta} y_2}{\theta t_1 + \overline{\theta}t_2} = \left(\frac{\theta t_1}{\theta t_1 + \overline{\theta}t_2}\right)(y_1/t_1) + \left(\frac{\overline{\theta} t_2}{\theta t_1 + \overline{\theta}t_2}\right)(y_2/t_2) \in S$$ since $S$ is convex and $y_1/t_1 \in S$, $y_2/t_2 \in S$, and this is just a convex combination of $y_1/t_1$ and $y_2/t_2$. $\Box$.

Claim 2: The function $tf(y/t)$ is concave over $(y,t) \in A$.

Proof: Fix $(y_1, t_1)$ and $(y_2, t_2)$ in $A$. Fix $\theta \in [0,1]$ and define $\overline{\theta} = 1-\theta$. Then: \begin{align} \theta t_1f(y_1/t_1) + \overline{\theta}t_2f(y_2/t_2) &= \left(\theta t_1 + \overline{\theta}t_2\right)\left(\frac{\theta t_1f(y_1/t_1) + \overline{\theta}t_2f(y_2/t_2)}{\theta t_1 + \overline{\theta}t_2}\right) \\ &\leq \left(\theta t_1 + \overline{\theta}t_2\right)f\left( \frac{\theta t_1 (y_1/t_1) + \overline{\theta}t_2 (y_2/t_2)}{\theta t_1 + \overline{\theta}t_2}\right)\\ &= \left(\theta t_1 + \overline{\theta}t_2\right)f\left( \frac{\theta y_1 + \overline{\theta}y_2}{\theta t_1 + \overline{\theta}t_2} \right) \end{align} where the inequality holds because the function $f()$ is concave. $\Box$

That the function $tg(y/t)$ is convex over $(y,t) \in A$ follows by a proof similar to that of Claim 2.

https://en.wikipedia.org/wiki/Fractional_programming gives an equivalent concave maximization: define $y=x/g(x)$, $t=1/g(x)$. Then maximizing $f(x)/g(x)$ on $S$ (convex) is said to be "equivalent to maximizing $tf(y/t)$ for $y/t\in S$ subject to $tg(y/t)\le1$, $t\ge0$". Although I don't understand what it means to maximize $tf(y/t)$ for $y/t\in S$, I hope you could find an answer there, or in Schaible's article of 1983.

• I agree that way of stating it in the wiki page is confusing. I try to give some further insight into what that means below. – Michael Sep 2 '15 at 23:59
• @Michael In view of your explanation below, the statement makes perfect sense, as the new minimization is that of a function of $(t,y)$, which I should have understood, poor me! – Jean Duchon Sep 3 '15 at 10:04