[Math] How is the variance equivalent to the following

convex optimizationconvex-analysisconvex-geometryconvex-hullsvariance

I am working through a problem that asks if the set, $P$ is convex.

Note that $P$ is a set of pdfs. Each member $p \in P$ describes a pdf – a vector of real numbers that are probabilities. The assignment is to determine if the set of all pdfs (all $p$'s) subject to a restriction on the variance, is a convex set.

These are the restrictions on $p$, including the inequality for the variance of all of all of the $p$'s:

  • $p$ is a vector of probabilities, $p \in \mathbb{R}^+$

  • probability simplex, which is of course a restriction on $p$
    $P = \{p \, \vert \sum_{i=1}^{n}{p_i} = 1 , p \ge 0\}$

  • $p_i$ is the probability that random variable $x$ is $x=a_i$ with $x \in \mathbb{R}$

  • $var(x) \ge \alpha\ $and$ \,\,var(x) = \sum_{i=1}^n{(x_i-E[x])^2}\}$

  • $\alpha \in \mathbb{R}$ and $var(x) = \sum_{i=1}^n{(x_i-E[x])^2}$ and $E[x]=\sum_{i=1}^np_ix_i$

Now, in the Solutions to the homework I see

In the solutions to my homework, it says that that "$var(x) \ge \alpha$ can be reformulated as $\sum_{i=1}^np_ia_i^2+(\sum_{i=1}^np_ia_i)^2 \le \alpha$".

This is obviously convex…so I can see the answer from there.

But, my question is how can this inequality $var(x) \ge \alpha$ be reformulated as $\sum_{i=1}^np_ia_i^2+(\sum_{i=1}^np_ia_i)^2 \le \alpha$ ?

EDIT
Here is the homework question in full. I am particularly asking about parts (f) and (g):

enter image description here

And here is the solution:

enter image description here

If you'd like any more information, please let me know.

Best Answer

First we know that $$ \mathbf{Var}(x) = Ex^2 - (E(x))^2 = \sum_{i=1}^np_i a_i^2 - (\sum_{i=1}^np_ia_i) ^2 \geq \alpha $$ The set is equilvalent to $$ - \sum_{i=1}^np_i a_i^2 + (\sum_{i=1}^np_ia_i) ^2 \leq \alpha $$ Define $b = [-a_1^2,-a_2^2,...,-a_n^2], A = aa^T $​​​, then it is equilvalent to $$ -b^Tp + p^TAp \leq \alpha $$ With $-b^p, p^TAp$ are both convex function about $x$, $f(p) = -b^Tp + p^TAp $ is also convex. With the image of $f$ with $f(x) \leq \alpha$, the image of $f$ is convex. Then the inverse image $p$ is also convext.

Proof done.

Note: A is positive semidefinite, such that $p^TAP$ is convex .

Related Question