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