Maximising a convex function under convex constrains

Question

I would like to obtain the solution for the following problem (which is like maximizing the variance when the mean is under constraints): $$\max_{x_i}\sum_{i=1}^n\left(x_i-\frac{\sum_{i=1}^nx_i}{n}\right)^2$$ $$s.t. x_i\geq0,\; i=1\dots n\\\\a\leq \sum_{i=1}^nx_i\leq b,\; a\geq0,\; b\geq0$$ Numerically I can obtain maximum value $\frac{n-1}{n}b^2$ when $\mathbf{x}=[b,0,\dots,0]$, but i am not able to prove that it always holds. So, can this solution hold for all the cases? Can this problem be solved using some standard technique? I really appreciate any help on this issue!

Answer 1

The maximum of a convex function over a compact convex set is attained at one of the extreme points of the convex set (can you prove this?).

Whenever $a < b$, the extreme points of the polytope $\left\{x \in \mathbb{R}^n_+ \: : \: a \leq \sum_{i=1}^{n} x_i \leq b\right\}$ are $$(a,0,0,\cdots,0), (0,a,0,\cdots,0), \cdots (0,\cdots,0,a)$$ and $$(b,0,0,\cdots,0), (0,b,0,\cdots,0), \cdots (0,\cdots,0,b).$$ It is easy to check that the maximum occurs at any one of the latter set of extreme points.

The case when $a = b$ is simpler.