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!
Asked
Active
Viewed 421 times
1 Answers
0
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.
madnessweasley
- 1,723
-
Thanks for your answer! For your first statement, is there a theory that states the solution must be one of the extreme points, or I have to prove this case by case? For the determination of extreme points, does (1/2b,1/2b,0,...0) and (b/n,b/n,...,b/n) also considered as extreme points? If so there would be infinite number of extreme points. Thanks for you answer! – wondermaster Apr 09 '20 at 08:33
-
@wondermaster Here is a proof for polyhedral feasible regions. To determine extreme points, note that there have to be $n$ linearly independent active constraints at candidate extreme points. – madnessweasley Apr 09 '20 at 08:37
-
thanks, i think the answer is sufficient. – wondermaster Apr 09 '20 at 08:47