5
$\begingroup$

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"

$\endgroup$

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – Michael
    Sep 2, 2015 at 23:59
  • $\begingroup$ @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! $\endgroup$ Sep 3, 2015 at 10:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.