3
$\begingroup$

Given $x \geq y > 0$ and an integer $n$. We want to minimize the following term $\sum_{i=1}^n (x_i^2 - x_iy_i)$ over $(x_1,\ldots,x_n)$, $(y_1,\ldots,y_n)$ non-negative such that $\sum_{i=1}^n x_i = x$ and $\sum_{i=1}^n y_i = y$. Could we express the lower bound as a function of $x$ and $y$ (and probably $n$)?

For example, $\sum_{i=1}^n (x_i^2 - x_iy_i) \geq -y^2/4$. However, is there a better bound?

What happen if we modify the simplex as the following: $\sum_i x_i \leq x$, $\sum_i y_i \leq y$ and $\sum_i y_i \leq \sum_i x_i$. (All $x$ and $y$ are non-negative).

  • 0
    You could introduce $z_i=x_i-y_i$ then it's just $\sum_{i=1}^n x_iz_i$ (like a dot-product) where $\sum_{i=1}^n z_i = x-y$... Don't know if that helps at all...2011-07-13

1 Answers 1

5

The best lower bound is $(x^2-xy-(n-1)y^2/4)/n$. First note that the objective function and the constraints are linear in the $y_i$. Thus the minimum with respect to the $y_i$ (for fixed $x_i$) must be attained at one of the corners of the regular simplex defined by the constraints. Without loss of generality, we can take $y_1=y$ and $y_i=0$ otherwise.

Now write the desired vector $\vec x$ as $\vec x=x_1\vec e_1+\vec x_\perp$ with $\vec x_\perp\perp\vec e_1$, where $\vec e_1$ is the vector $(1,0,0,\dotsc)$. Then the objective function takes the value

$$\vec x\cdot(\vec x-\vec y)=(x_1\vec e_1+\vec x_\perp)\cdot(x_1\vec e_1+\vec x_\perp-y\vec e_1)=x_1(x_1-y)+\vec x_\perp^2\;.$$

For fixed $x_1$, this will be minimal if $\vec x_\perp$ has equal components $x_\perp$ for all $i\neq1$. Then $x_1+(n-1)x_\perp=x$, and thus $x_\perp=(x-x_1)/(n-1)$. This allows us to express the objective function as a function of $x_1$ alone:

$$ \begin{eqnarray} x_1(x_1-y)+\vec x_\perp^2 &=& x_1(x_1-y)+(n-1)\left(\frac{x-x_1}{n-1}\right)^2 \\ &=& x_1(x_1-y)+\frac{(x-x_1)^2}{n-1} \\ &=& \frac n{n-1}\left(x_1-\frac{x+(n-1)y/2}n\right)^2+\frac{x^2-xy-(n-1)y^2/4}n\;. \end{eqnarray} $$

The minimum $(x^2-xy)/n$ is attained at

$$x_1=\frac{x+(n-1)y/2}n\;,$$

which leads to

$$ x_\perp=\frac{x-x_1}{n-1}=\frac{x-y/2}{n}>0\;, $$

so this vector fulfills the constraints and is therefore the global minimum.

  • 0
    Yes, I mean $x_i,y_i$ non-negative.2011-07-13
  • 0
    Hi @joriki! I am afraid that the bound is not correct. Let's take an example. Let $n$ be a large integer and $k = \sqrt{n}$. Let $x = y = 1$ and define $x_1 = 1/k, x_2 = \ldots = x_n = \frac{1}{n-1}(1-1/k)$ and $y_1 = 1, y_2 = \ldots = y_n = 0$. Now $\sum_i (x_i^2 -x_iy_i) = \frac{1}{k^2} - \frac{1}{k} + (n-1)\cdot \frac{(1-1/k)^2}{(n-1)^2} \approx \frac{2}{n} - \frac{1}{\sqrt{n}} < 0$ --- which is strictly smaller than the given bound.2011-07-14
  • 0
    Following your scheme, a small mistake is at the line before "the minimum $(x^2 - xy)/n$ is attained at". The correct minimum should be $\frac{4x(x-y) - (n-1)y^2}{n}$ instead of $(x^2 - xy)/n$. That looks correct now.2011-07-14
  • 0
    Thanks for spotting the error. However, I think you've got an extra factor of $4$ in your expression -- I believe I merely omitted the term quadratic in $y$, and the other terms were correct. I've edited the answer to correct the mistake.2011-07-14
  • 0
    Thanks! I think this bound is correct.2011-07-15
  • 0
    By curiosity, one question raises. What happen if we modify the simplex as the following: $\sum_i x_i \leq x$, $\sum_i y_i \leq y$ and $\sum_i y_i \leq \sum_i x_i$. (All $x$ and $y$ are non-negative). If we don't add the inequality $\sum_i y_i \leq \sum_i x_i$ then the question trivially follows your answer.2011-07-15