方差最小化的凸性


14

$ X $ 是一個離散隨機變量,其值為 $ x_n $ ,概率為 $ 1 / N $ 表示 $ n = 1,\ ldots,N $ 。我想在優化問題中設置 $ x_n $ 值。我的目標是在滿足一組約束的同時最大程度地減少方差。

所以問題是:

">開始{array} {ll}&\ min \ limits _ {\ {x_n \} _ {n = 1} ^ N} {\ operatorname {Var}(X)} \\&\ text {st} \ \ ldots \ end {array}

表示 $ x = \ begin {pmatrix} x_1&\ ldots&x_n \ end {pmatrix} ^ \ top $ 。因此,在這種離散分佈中,方差為: $$ \操作者名稱E [X ^ 2]-\操作者名稱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?

編輯:根據註釋,方差可能是凸的。我們可以證明 $$ \ operatorname E [X ^ 2]-\ operatorname E [X] ^ 2 = \ frac {x ^ \ top \ left(I-\ tfrac {\ mathbf {e}\ mathbf {e} ^ \ top} {N} \ right)x} {N},$$ 因此,為了證明這是凸的,我們需要證明 $ I-\ tfrac {\ mathbf {e} \ mathbf {e} ^ \ top} {N} $ 是psd矩陣。這本身就是一個挑戰。我需要查看這是p.s.d的證明,或者是否可以正確地寫下方差如何如註釋中所示的封閉形式的範式表達式所示。

要顯示方差為 $ \ ell ^ 2 $ -norm-representable,我們需要使 $ a ^ \top a = I-\ tfrac {\ mathbf {e} \ mathbf {e} ^ \ top} {N} $ 對於某些 $ a $ 。找到 $ a $ 也可以。

編輯2:好,我收到了評論。他遵循 $ \ operatorname {Var}(X)= \ operatorname E [(X-\ operatorname E [X])^ 2] $ 的方法,明顯。

12

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.