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.