Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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... –  user826788 Jul 13 '11 at 14:07

1 Answer 1

up vote 5 down vote accepted

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.

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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