Lower bound of a function 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). 
 A: 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.
