4
$\begingroup$

Let $a_i,b_i,c_i,d_i>0$ for all $1\leq i\leq n$. What is a sharp upper bound on $$\sup_{x_1,\ldots,x_n>0}\frac{\sum_{i,j=1}^n a_ib_jx_ix_j}{\sum_{i,j=1}^n c_id_jx_ix_j}$$

This quantity is always bounded as there is the bound: $$ \frac{\sum_{i,j=1}^n a_ib_jx_ix_j}{\sum_{i,j=1}^n c_id_jx_ix_j}\leq \max_{i,j}\frac{a_ib_jx_ix_j}{c_id_jx_ix_j}=\max_{i,j}\frac{a_ib_j}{c_id_j}.$$ So, we get $$\sup_{x_1,\ldots,x_n>0}\frac{\sum_{i,j=1}^n a_ib_jx_ix_j}{\sum_{i,j=1}^n c_id_jx_ix_j}\leq \min\Big\{\max_{i,j}\frac{a_ib_j}{c_id_j},\max_{i,j}\frac{b_ia_j}{c_id_j}\Big\}.$$ This bound is tight as it is attained for instance when $a_i= r b_i= s c_i = t d_i$ for every $i$ and some $r,s,t>0$. However it is quite conservative.

Can we do better ?

$\endgroup$
  • $\begingroup$ I agree, I missed the positive entries before. By the way: "denominator" and "numerator" are the correct terms. $\endgroup$ – Omnomnomnom Jun 8 '18 at 11:55
  • $\begingroup$ @Omnomnomnom Ok :), sorry if I miswrote it. The positive assumptions, make the question much more interesting (but also quite difficult :D). $\endgroup$ – Hello Jun 8 '18 at 11:56
2
+100
$\begingroup$

I am definitely interested in a factor of 2

OK, here is how to find the true maximum then. We know that the maximum is at least $\Lambda>0$ if we can find $x$ with $$ \langle x,a\rangle\langle x,b\rangle-\Lambda \langle x,c\rangle\langle x,d\rangle=\frac 14[\langle x,a+b\rangle^2-\langle x,a-b\rangle^2 -\Lambda \langle x,c+d\rangle^2+\Lambda \langle x,c-d\rangle^2]\ge 0\,. $$ If we fix $\langle x,a-b\rangle,\langle x,c+d\rangle$, the last expression becomes convex in $x$, so if we can make it non-negative at all, we can do it for some $x$ with at most two non-zero components. Thus we care only about what happens when $n=2$ (but we'll have to consider all pairs $i,j$).

Now we can fix $\langle x,d\rangle=1$ and parameterize admissible $x$ as $x(t), t\in[\alpha,\beta]$ where $x(t)$ is a linear function of $t$. The expression we want to investigate is then $\frac{\langle x,a\rangle\langle x,b\rangle}{\langle x,c\rangle}$. This is a quadratic polynomial of $t$ divided by a linear one. If we look at the equation for the critical points, we see that it reduces to a quadratic equation in $t$, so we have to solve that one, see which critical points lie within the interval, and compare with the endpoints (the last step is not really necessary because we can check all singletons at once in the very beginning). This is not hard to program but the analytic formulae are too ugly to try to write explicitly.

$\endgroup$
  • $\begingroup$ Thank you for your answer. I don't have the time to go right now in the details, but I'll do that soon. There is just one small thing which is puzzling me a bit. How can you get a linear constraint? The denominator is quadratic, so I would have expected a quadratic constraint. $\endgroup$ – Hello Jun 14 '18 at 13:49
  • $\begingroup$ @Hello $\sum_{i,j}x_ix_j=(\sum_j x_j)^2$, isn't it? $\endgroup$ – fedja Jun 14 '18 at 13:50
  • 1
    $\begingroup$ @Hello Ah, you are right :-) I followed the erroneous comment. OK, I'll change it accordingly (we'll have to work with 3 by 3 then :-( ) $\endgroup$ – fedja Jun 14 '18 at 13:54
  • 2
    $\begingroup$ @Hello Take any $x_0$ that makes the expression non-negative. Consider all non-negative $x$ with the same two scalar products as for $x_0$. It is the intersection of a codimension $2$ plane with positive octant (obviously bounded since $c+d$ is positive). On that plane the sum of the remaining two squares is convex, so it is maximized at some vertex of our polytope. All vertices have at most $2$ non-zero coordinates (that is the linear programming mumbo-jumbo: if you have 2 linear equations and 3 or more available unknowns, you can find a non-trivial solution, which will determine a line). $\endgroup$ – fedja Jun 14 '18 at 15:03
  • 1
    $\begingroup$ @Hello You are welcome. I'm glad I could help a bit :-) $\endgroup$ – fedja Jun 14 '18 at 15:15
3
$\begingroup$

I am not sure how useful this will be, but here's another way to think about your result; I think it's a bit too long for a comment.

Let $A = \operatorname{diag}(a)$ denote the diagonal matrix whose diagonal entries are $a_1,\dots,a_n$. Similarly, take $B = \operatorname{diag}(b)$, $C = \operatorname{diag}(c)$, $D = \operatorname{diag}(d)$. Let $\otimes$ denote the Kronecker product, and let $\|\cdot\|_1$ denote the $1$-norm. We have \begin{align*} \max_{x > 0} \frac{\sum_{i,j = 1}^n a_i b_j x_ix_j}{\sum_{i,j = 1}^n c_id_jx_ix_j} &= \max_{x > 0}\frac{\|(A \otimes B)(x \otimes x)\|_1}{\|(C \otimes D)(x \otimes x)\|_1} \\ &\leq \max_{x,y > 0}\frac{\|(A \otimes B)(x \otimes y)\|_1}{\|(C \otimes D)(x \otimes y)\|_1} \\ &= \max_{x,y > 0}\frac{\|(A \otimes B)(C \otimes D)^{-1}(x \otimes y)\|_1}{\|(x \otimes y)\|_1}\\ &\leq \max_{x,y \in \Bbb R^n \setminus \{0\}}\frac{\|(AC^{-1} \otimes BD^{-1})(x \otimes y)\|_1}{\|(x \otimes y)\|_1}\\ &\leq \max_{z \in \Bbb R^{n^2}} \frac{\|(AC^{-1} \otimes BD^{-1})z\|_1}{\|z\|_1} \\ &= \|(AC^{-1} \otimes BD^{-1})\|_1 \end{align*} where $\|(AC^{-1} \otimes BD^{-1})\|_1$ is the induced $1$-norm of $(AC^{-1} \otimes BD^{-1})$. We find that this gives us the same bound, namely $$ \|(AC^{-1} \otimes BD^{-1})\|_1 = \max_{i,j} \frac{a_ib_j}{c_id_j} $$

$\endgroup$
  • $\begingroup$ That is a nice approach :), thanks for pointing it out. I think that sharpness is lost in the same way as in my proof. Indeed, both approaches have in common that you relax the maximum over $(x\otimes x)$ to a maximum over $(x\otimes y)$. In my proof, I basically use $C(a,b,c,d)\leq C(a,b,1,1)C(1,1,c,d)$ (which is the same in the end). This decoupling is quite precisely what I'm fighting against. $\endgroup$ – Hello Jun 8 '18 at 12:25
  • $\begingroup$ A very good point of your, is that, if I'm not mistaking, the OP can be reduced to the study of $$\sup_{x>0}\frac{\sum_{i,j}v_iw_j x_ix_j}{\sum_{i,j}x_ix_j}$$ $\endgroup$ – Hello Jun 8 '18 at 12:31
  • 1
    $\begingroup$ :) I just came the same conclusion :D, namely if $\|x\|_1=1$ then $\sum_{i,j}x_ix_j=1$ and indeed, the problem boils down to $$\sup_{x>0, \|x\|_1 =1} \sum_{i,j}v_iw_jx_ix_j$$ with $v_i = a_i/c_i$ and $w_j=b_j/d_j$. But wait... how comes your supremum is on $i,j$? $\endgroup$ – Hello Jun 8 '18 at 12:54
  • 1
    $\begingroup$ @Hello Looks like that was a mistake on my part $\endgroup$ – Omnomnomnom Jun 8 '18 at 14:36
  • 1
    $\begingroup$ @Hello How good bound do you expect to get? The obvious one cannot be improved more than twice, so are you really sure you want to pick up a big fight for a factor of $2$? $\endgroup$ – fedja Jun 14 '18 at 3:04

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.