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

  • $\begingroup$ 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... $\endgroup$ – karnok Jul 13 '11 at 14:07

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


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.

  • $\begingroup$ Yes, I mean $x_i,y_i$ non-negative. $\endgroup$ – ogn Jul 13 '11 at 14:35
  • $\begingroup$ 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. $\endgroup$ – ogn Jul 14 '11 at 11:41
  • $\begingroup$ 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. $\endgroup$ – ogn Jul 14 '11 at 12:21
  • $\begingroup$ 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. $\endgroup$ – joriki Jul 14 '11 at 13:10
  • $\begingroup$ Thanks! I think this bound is correct. $\endgroup$ – ogn Jul 15 '11 at 9:07

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.