# upper bound for linear fractional program

Consider the fraction: $$\frac{|c_1^\top z + b_1|}{c_2^\top z+b_2}$$ where $c_1,c_2 \in \mathbb{R}^n$ and $z \in S=\{x \in \mathbb{R}^n: c_2^\top x +b_2 >0 \}$. What is the supremum of this fraction with respect to $z \in S$ ? Ignore the trivial cases where $c_1=0$ and/or $c_2 = 0$.

• Are you looking for a computational method to compute this or an analytical expression? – skr Oct 19 '17 at 5:32
• I am looking for an analytical expression in terms of the problem parameters. – Kcafe Oct 19 '17 at 22:39
• @skr: I have rewritten my answer in response to your comment. I hope that it is clearer now. – John Bentin Oct 20 '17 at 11:34

## 1 Answer

The task is to maximize$$\rho(\pmb x):=\frac{|\pmb c_1^\top\pmb x+b_1|}{\pmb c_2^\top\pmb x+b_2}$$over $\pmb x\in S:=\{\pmb x\in\Bbb R^n:\pmb c_1^\top\pmb x+b_2>0\}$, where $\pmb c_1$ and $\pmb c_2$ are nonzero. We distinguish the following two cases. In Case 1, $\pmb c_2^\top\pmb x+b_2=0$ implies that $\pmb c_1^\top\pmb x+b_1=0$ for all $\pmb x\in\Bbb R^n$. Otherwise Case 2 holds: that is, there is some $\pmb u\in \Bbb R^n$ such that $$\pmb c_2^\top\pmb u+b_2=0\quad\text{ and }\quad\varepsilon:= |\pmb c_1^\top\pmb u+b_1|>0.$$We deal with Case 1 first. This is when the hyperplane $\{\pmb x\in\Bbb R^n:\pmb c_1^\top\pmb x+b_1=0\}$ is contained within the hyperplane $\{\pmb x\in\Bbb R^n:\pmb c_2^\top\pmb x+b_2=0\}$. Since both hyperplanes have dimension $n-1$, they coincide. Therefore there is some real $\lambda\neq0$ such that $\pmb c_1^\top\pmb x+b_1=\lambda(\pmb c_2^\top\pmb x+b_2)$ for all $\pmb x\in\Bbb R^n$. Thus $\pmb c_1=\lambda\pmb c_2$ and $b_1=\lambda b_2$. Hence $\rho(\pmb x)=|\lambda\pmb c_2^\top\pmb x+\lambda b_2|/|\pmb c_2^\top\pmb x+b_2|=|\lambda|$, and this constant is consequently the supremum (and infimum) of $\rho$.

In the remaining (and general) Case 2, let $\pmb x=\pmb u+\varepsilon\delta\pmb c_2$, where $\delta>0$. Then$$\rho(\pmb x)=\frac{|\pmb c_1^\top\pmb u+b_1+\varepsilon\delta\pmb c_1^\top\pmb c_2|}{\varepsilon\delta\pmb c_2^\top\pmb c_2}\geqslant\frac{|\pmb c_1^\top\pmb u+b_1|-\varepsilon\delta|\pmb c_1^\top\pmb c_2|}{\varepsilon\delta\pmb c_2^\top\pmb c_2}=\frac1{\delta\pmb c_2^\top\pmb c_2}-\frac{|\pmb c_1^\top\pmb c_2|}{\pmb c_2^\top\pmb c_2}.$$By choosing $\delta$ small enough, the above quantity can be made arbitrarily large, and so the supremum of $\rho$ is $\infty$.

• I guess there are some typos wich make the answer not correct. For example in case 1: $c_2^\top X +b_2 =0$. I don't see why this is considered ? – Kcafe Oct 23 '17 at 0:09
• @Kcafe: We are not considering the case $\pmb c_2^\top\pmb x+b_2=0$. What we are considering in Case 1 is when an implication holds: please read the statement carefully. When the implication holds, so does a particular relationship between the constant coefficients. It is the condition when this relationship holds, namely when a certain proportionality holds between the coefficients, that is considered. With Case 1 out of the way, it is possible (in Case 2) to find a vector $\pmb u$ (which is not in $S$) in order to construct $\pmb x=\pmb u+\varepsilon\delta\pmb c_2$, which is in $S$. – John Bentin Oct 23 '17 at 7:45