Convexity of Variance Minimization

Question

$X$ is a discrete random variable taking value $x_n$ with probability $1/N$ for $n=1, \ldots,N$. I would like to set the $x_n$ values in an optimization problem. My objective is to minimize the variance while satisfying a set of constraints.

So the problem is:

\begin{array}{ll} & \min\limits_{\{x_n\}_{n=1}^N}{\operatorname{Var}(X)} \\ & \text{s.t.} \ \ldots \end{array}

Denote $x = \begin{pmatrix} x_1 & \ldots & x_n\end{pmatrix}^\top$. So in this discrete distribution, the variance is: $$\operatorname E[X^2] -\operatorname E[X]^2 = \frac{1}{N} \sum_{n=1}^N x_n^2 - \frac{1}{N^2} \left( \sum_{n=1}^N x_n \right)^2 = \frac{x^\top x}{N} - \frac{(\mathbf{e}^\top x)(x^\top \mathbf{e})}{N^2}.$$

My questions are:

1. The variance is not convex, so minimization is hard, right? Is there a common method for this?
2. Is there any convex function which results in a low variance after being minimized?

Edit: The variance may be convex based on the comments. We can show that $$\operatorname E[X^2] -\operatorname E[X]^2 = \frac{x^\top \left( I - \tfrac{\mathbf{e}\mathbf{e}^\top}{N}\right) x}{N},$$ so to show this is convex, we need to show that $I - \tfrac{\mathbf{e}\mathbf{e}^\top}{N}$ is a p.s.d. matrix. That is itself a challenge. I need to see the proof of how this is p.s.d, or if one can properly write down how the variance can be shown as a closed-form norm expression as in the comments.

To show the variance is $\ell^2$-norm-representable we need to have $a^\top a = I - \tfrac{\mathbf{e}\mathbf{e}^\top}{N}$ for some $a$. Finding $a$ will also make it.

Edit-2: Ok, I got the comment. He follows the $\operatorname{Var}(X) = \operatorname E[(X - \operatorname E[X])^2]$ approach, then it is obvious.

Answer 1

It holds $$ \begin{array}{rcl} \operatorname V(x) &= &\dfrac1N\left\| x-\dfrac{e^\top x}{N} e \right\|^2 \\ & = & \dfrac1N\left(x^\top x+\dfrac{(e^\top x)^2 e^\top e}{N^2}-2\dfrac{(e^\top x)^2}N\right) \\ & = & \dfrac{x^\top x}{N} - \dfrac{(e^\top x)^2}{N^2}. \end{array} $$ So you are minimizing the $\ell^2$-norm of an affine expression which is known to be convex.

The problem $$ \begin{array}{lcl} \min & \dfrac{\|x-e u\|}{N} & \\ \mbox{s.t.} & \dfrac{e^\top x}{N} - u & = & 0 \\ \end{array} $$ provides a nice interpretation since $u$ is the average. Note the problem tries to make all the $x$ equal to the average value.

Alternatively the last problem can be stated as $$ \begin{array}{lcl} \min & \dfrac{s}{N}&\\ \mbox{s.t.} & \dfrac{e^\top x}{N} - u &=0 \\ &(s;x-e u) &\in Q. \\ \end{array} $$ where $Q$ is a quadratic cone. This provides another convexity proof because the quadratic cone is convex. Hence, the problem can be solved using SOCP also known as conic quadratic optimization.