5
$\begingroup$

$v$ is a vector of length $n$, where $v_1 = 1$ and every element $v_i \in [0,1]$

$w = \| v \|_1^1 = \sum_i |v_i| = \sum_i v_i$
$x = \| v \|_2^2 = \sum_i |v_i|^2 = \sum_i v_i^2$
$y = \| v \|_3^3 = \sum_i |v_i|^3 = \sum_i v_i^3$
$z = \| v \|_4^4 = \sum_i |v_i|^4 = \sum_i v_i^4$

Can you recommend a strategy for achieving a bound on

$$f = \frac{w z - x y + \sqrt{w^2 z^2 - 6 w x y z + 4 w y^3 + 4 x^3 z - 3 x^2 y ^2 }}{2 (w y - x^2)}$$

for all possible $v$ described above and where the denominator is nonzero: $(w y - x^2) \neq 0$ ? The nonzero denominator implies that the vector $v$ has an element $v_{i\neq 1} \in (0,1)$, which can be seen by assuming all elements are $\in \{0,1\}$ and yielding a contradiction. Thus it can be shown that when the denominator equals zero, the numerator also equals zero (because $w = x = y = z$). When I've simulated numerically (choosing values in $v_{2 \ldots n}$ uniformly in $[0,1]$ a million times), and have observed that $f$ is generally quite close to $1$.

Can you help me find a bound (even a loose bound) $f \in [lower(n), upper(n)]$? I've tried starting from the KKT criteria to define $v$ that maximizes (or, alternatively, minimizes) $f$, but the expression was so messy that Mathematica choked even when using a small vector length $n$.

Optimizing over $w, x, y, z$, which should each be $\in [0, n]$ and where $w \geq x \geq y \geq z$ (because, e.g. $v_i \geq v_i^2 \rightarrow w \geq x$); however, that is still not constrained enough, because it allows that the denominator can be close to zero when the numerator is nonzero (e.g., $w \approx x \approx y << z$. But there is no vector $v$ where $w \approx x \approx y << z$: $\| v \|_p^p$ is decreasing, concave up, meaning that $z - y < y - x$, and thus $z$ cannot jump quickly if $w \approx x \approx y$. But even with this additional constraint on $w,x,y,z$, I have not been able to find a bound on $f$.

I've also tried letting $\alpha$ denote an element of $v_{i\neq 1} \in (0,1)$ so that $w = 1 + \alpha + \| u \|_1^1$, $y=1 + \alpha^2 + \| u \|_2^2$, etc., where $u$ is a vector of length $n-2$ and all elements in $[0,1]$, and then maximizing (or minimizing) $f$ with respect to $w',x',y',z',\alpha$, where $w' = \| u \|_1^1, x' = \| u \|_2^2, \ldots$, but have also not yet found success.

Do you see appropriate additional constraint(s) that will adequately describe that $w,x,y,z$ behave as norms (without letting $v$ creep back into the problem)? Do you see any place where I can massage $f$ into some larger (or smaller for the lower bound) expression that permits a loose bound? Or, more generally, can you recommend a plan of attack?

In case you're interested, I've come to this problem through statistics; $f$ is an estimate that should ideally be 1, and I'm trying to bound the error of my estimate. Note that this problem is equivalent to

$$ max( roots( nullSpace \left[ \begin{array}{ccc} \|v\|_1^1 & \|v\|_2^2 & \|v\|_3^3 \\ \|v\|_2^2 & \|v\|_3^3 & \|v\|_4^4 \\ \end{array} \right] ) ) )$$

Thank you for any advice or ideas you have.

$\endgroup$
4
  • $\begingroup$ Which function do you denote by $\| v \|_p^p$? $\endgroup$ Oct 11, 2015 at 3:23
  • $\begingroup$ Good point, I just edited to show that this is in $L_p$ space. $\endgroup$
    – user
    Oct 11, 2015 at 11:24
  • $\begingroup$ It could help if you tell us where this problem comes from. $\endgroup$ Oct 11, 2015 at 13:52
  • $\begingroup$ I've updated to show an equivalent linear algebra formulation. $\endgroup$
    – user
    Oct 11, 2015 at 16:42

1 Answer 1

3
+50
$\begingroup$

Experimentally, $$0.7 <\ f \ \le\ 1.$$

The upper bound is rigorous. First we show $wy-x^2=\sum_{i<j}v_i v_j (v_i-v_j)^2 \ge 0$. Then we can use this to simplify the upper bound to $(wy-x^2)+(xz-y^2)-(wz-xy) = \sum_{i<j} v_i v_j(1-v_i)(1-v_j)(v_i-v_j)^2 \ge 0$. The extreme case is $v$ of any length of the form $$v=(1,1/2,\ldots,1/2),\ f=1.$$

The lower bound is more conjectural. Experimentation suggests looking at $v$'s of the form $(1,a,b,\ldots,b)$. For these $v$, we can show that the value of $f$ approaches $b$ as $v$ grows longer, so long as $(1-b)^3 \le a(b-a)^3$. We minimize $b$ subject to that constraint with $a=0.176$, $b=0.704$. Those values give the apparently extreme case where $v$ is long and of the form $$v=(1,\,0.176,\,0.704,\,\ldots,\,0.704),\ f=0.704.$$

$\endgroup$
5
  • $\begingroup$ Nice! For the upper bound, can you explain how you get $w y -x^2 \geq 0$ implies $f \leq (wy−x^2)+(xz−y^2)−(wz−xy)$? I can't quite see it... $\endgroup$
    – user
    Oct 13, 2015 at 16:01
  • $\begingroup$ $f$ is of the form $(a+\sqrt{b})\,/\,c$ with $c \ge a \ge 0$. So $f \le 1$ is equivalent to $(c-a)^2 - b \ge 0$. And as it happens $(c-a)^2 -b = 4c( (wy-x^2)+(xz-y^2)-(wz-xy))$. $\endgroup$
    – user44143
    Oct 13, 2015 at 16:44
  • $\begingroup$ Ah, very good reasoning. I had also observed similar numerical bounds (and the same phenomenon for the worst-case $(1, a, b, \ldots b)$ vector for the lower bound), but hadn't been able to formalize it at all. By the way, did you get the $a = 0.176$ from calculus or from experiments? $\endgroup$
    – user
    Oct 13, 2015 at 21:12
  • $\begingroup$ L = Limit[ f /. {w -> 1 + a + n b, x -> 1 + a^2 + n b^2, y -> 1 + a^3 + n b^3, z -> 1 + a^4 + n b^4}, n -> Infinity]; S = Simplify[L, Assumptions -> 0 < a < b < 1]; NMinimize[{b, S[[1, 1, 2]], 0 < a < b < 1}, {a, b}] $\endgroup$
    – user44143
    Oct 13, 2015 at 22:11
  • $\begingroup$ Thanks for your thoughts on the problem. I've awarded the bounty, and I'll wait a bit on accepting the answer just in case anyone has an idea for how to prove the lower bound (i.e., why vectors of the form $(1, a, b, ... b)$ achieve the minimum). $\endgroup$
    – user
    Oct 18, 2015 at 1:33

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.