1
$\begingroup$

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$.

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

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$.

$\endgroup$
  • $\begingroup$ 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 ? $\endgroup$ – Kcafe Oct 23 '17 at 0:09
  • $\begingroup$ @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$. $\endgroup$ – John Bentin Oct 23 '17 at 7:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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