最大化有界变量的方差

Question

令 x_1, ..., x_i,..., x_p 为 p 个实数，使得 0 <= x_i <= b 对所有一世。也就是说，每个 x_i 可以取 0 到 b 之间的任何值。我想找到使它们之间的方差最大化的 {x_i} 的值。

你有什么提示吗？我想将此结果用于我的示例代码。或者，这个问题不是很明确吗？

一开始我想到的是x_1=0，x_2=...=x_p=b，但是后来我发现这并没有使p时的方差最大化有点大。

谢谢

Answer 1

评论之后，我对你的问题做了一些数值证明的试验。还有一些工作要做，但我希望它能让你走上正轨。此外，我已经使用了 python，我不知道这是否适合您。您肯定可以在 matlab 和 R.

中找到等效的方法

我使用众所周知的属性方差 = E[X^2] - E[X]^2，使导数更容易。（如果您有疑问，请查看 wiki）。

python 包 scipy.optimize 有一个方法 minimize 可以最小化函数的数值。您可以 select 一个解决问题的算法；我不太熟悉可能的算法，我一直在寻找众所周知的普通梯度下降（好吧，至少我希望你知道），我认为封闭的算法可能是 SLSQP，但老实说我不是 100% 确定细节。

最后，我没有确定您要最小化的函数是凸函数，也没有确定它是否具有局部最小值，但结果看起来不错。

我在下面 python 中给你代码，以防有用，但底线是我建议你：

选一个language/package你熟悉的
选择优化算法
最好能证明函数是凸的（这样解收敛）
设置要进行证明的参数

代码如下。希望对你有帮助。

我不会post导数的代数，我希望你能自己做。而且你必须考虑到你正在最大化而不是最小化，所以你必须乘以-1，正如我希望非常清楚地解释的那样here（寻找"maximizing"）。

设置，

In [1]:

from scipy.optimize import minimize
import numpy as np

您正在最大化的函数，即方差（记住技巧 E[X^2] - E[X]^2 和 -1），

In [86]:

def func(x):
    return (-1) * (np.mean([xi**2 for xi in x]) - np.mean(x)**2)

那个函数对向量x的每个xi的导数，（希望你能求导得到相同的结果），

In [87]:

def func_deriv(x):
    n = len(x)
    l = []
    for i in range(n):
        res = (2 * x[i] / n) - ((2/(n**2)) * (x[i] + sum([x[j] for j in range(n) if j != i])))
        l +=  [(-1) * res]
    return np.array(l)

其实我在写这个函数的时候犯了很多错误，无论是导数还是python实现。但是有一个技巧很有帮助，就是用数值的方式来检查导数，通过在每个维度上加减一个小的epsilon并计算曲线的斜率see wiki。这将是近似导数的函数，

In [72]:

def func_deriv_approx(x, epsilon=0.00001):
    l = []
    for i in range(len(x)):
        x_plus = [x[j]+((j == i)*epsilon) for j in range(len(x))]
        x_minus = [x[j]-((j == i)*epsilon) for j in range(len(x))]
        res = (-1) * (func(x_plus) - func(x_minus)) / (2*epsilon)
        l += [res]
    return l

然后我检查了 func_deriv_approx 和 func_deriv 的一堆值。

以及最小化本身。如果我将值初始化为我们怀疑是正确的解决方案，它工作正常，它只迭代一次并给出预期结果，

In [99]:

res = minimize(func, [0, 0, 10, 10], jac=func_deriv, bounds=[(0,10) for i in range(4)],
               method='SLSQP', options={'disp': True})
Optimization terminated successfully.    (Exit mode 0)
            Current function value: -25.0
            Iterations: 1
            Function evaluations: 1
            Gradient evaluations: 1

In [100]:

print(res.x)
[  0.   0.  10.  10.]

（请注意，您可以使用您想要的长度，因为 func 和 func_deriv 是以接受任何长度的方式编写的）。

你可以这样随机初始化，

In [81]:

import random
xinit = [random.randint(0, 10) for i in range(4)]

In [82]:

xinit
Out[82]:
[1, 2, 8, 7]

然后最大化是，

In [83]:

res = minimize(func, xinit, jac=func_deriv, bounds=[(0,10) for i in range(4)],
               method='SLSQP', options={'disp': True})
Optimization terminated successfully.    (Exit mode 0)
            Current function value: -25.0
            Iterations: 3
            Function evaluations: 3
            Gradient evaluations: 3
In [84]:

print(res.x)
[  1.27087156e-13   1.13797860e-13   1.00000000e+01   1.00000000e+01]

或者最终长度 = 100，

In [85]:

import random
xinit = [random.randint(0, 10) for i in range(100)]

In [91]:

res = minimize(func, xinit, jac=func_deriv, bounds=[(0,10) for i in range(100)],
               method='SLSQP', options={'disp': True})
Optimization terminated successfully.    (Exit mode 0)
            Current function value: -24.91
            Iterations: 23
            Function evaluations: 22
            Gradient evaluations: 22
In [92]:

print(res.x)
[  2.49143492e-16   1.00000000e+01   1.00000000e+01  -2.22962789e-16
  -3.67692105e-17   1.00000000e+01  -8.83129256e-17   1.00000000e+01
   7.41356521e-17   3.45804774e-17  -8.88402036e-17   1.31576404e-16
   1.00000000e+01   1.00000000e+01   1.00000000e+01   1.00000000e+01
  -3.81854094e-17   1.00000000e+01   1.25586928e-16   1.09703896e-16
  -5.13701064e-17   9.47426071e-17   1.00000000e+01   1.00000000e+01
   2.06912944e-17   1.00000000e+01   1.00000000e+01   1.00000000e+01
  -5.95921560e-17   1.00000000e+01   1.94905365e-16   1.00000000e+01
  -1.17250430e-16   1.32482359e-16   4.42735651e-17   1.00000000e+01
  -2.07352528e-18   6.31602823e-17  -1.20809001e-17   1.00000000e+01
   8.82956806e-17   1.00000000e+01   1.00000000e+01   1.00000000e+01
   1.00000000e+01   1.00000000e+01   3.29717355e-16   1.00000000e+01
   1.00000000e+01   1.00000000e+01   1.00000000e+01   1.00000000e+01
   1.43180544e-16   1.00000000e+01   1.00000000e+01   1.00000000e+01
   1.00000000e+01   1.00000000e+01   2.31039883e-17   1.06524134e-16
   1.00000000e+01   1.00000000e+01   1.00000000e+01   1.00000000e+01
   1.77002357e-16   1.52683194e-16   7.31516095e-17   1.00000000e+01
   1.00000000e+01   3.07596508e-17   1.17683979e-16  -6.31665821e-17
   1.00000000e+01   2.04530928e-16   1.00276075e-16  -1.20572493e-17
  -3.84144993e-17   6.74420338e-17   1.00000000e+01   1.00000000e+01
  -9.66066818e-17   1.00000000e+01   7.47080743e-17   4.82924982e-17
   1.00000000e+01  -9.42773478e-17   1.00000000e+01   1.00000000e+01
   1.00000000e+01   1.00000000e+01   1.00000000e+01   5.01810185e-17
  -1.75162038e-17   1.00000000e+01   6.00111991e-17   1.00000000e+01
   1.00000000e+01   7.62548028e-17  -6.90706135e-17   1.00000000e+01]

最大化有界变量的方差

Maximizing variance of bounded variables

statistics

variance

maximization