如何高效选取K条无重复序列使其求和结果的方差最小

首先利用方差的线性展开性质，可将目标函数做等价转换，避免每次选完序列再重新计算求和后的方差：
设选中K条序列的索引集合为$I$，求和后的序列为$S = \sum_{i \in I} x_i$，则：
$$
var(S) = \sum_{i \in I} var(x_i) + 2\sum_{i<j, i,j \in I} cov(x_i, x_j)
$$
其中$var(x_i)$是单条序列的方差，$cov(x_i,x_j)$是两条序列的协方差。所有$var(x_i)$和$cov(x_i,x_j)$都可以预先一次性计算，后续优化过程无需再访问原始序列，大幅降低计算开销。
以Python为例预计算代码如下：

import numpy as np
# X为N行T列的数组，每一行对应一条实值序列
cov_mat = np.cov(X)

预计算的时间复杂度为$O(N^2 T)$（T为序列长度），之后所有组合的目标值都可以通过协方差矩阵直接计算。

• 小规模场景（N≤25）：直接用位遍历所有符合选K条条件的组合即可，N=20时总共有18万多组合，结合预计算的协方差矩阵，单次遍历仅需毫秒级耗时，完全满足严苛的时间要求。
• 中等规模场景（N≤100）：可将问题建模为带基数约束的0-1二次规划问题，目标是最小化$w^T \Sigma w$，约束为$\sum_{i=1}^N w_i = K$、$w_i \in {0,1}$，其中$\Sigma$是预计算的协方差矩阵，直接调用整数规划求解器即可快速得到全局最优解。

针对N更大、对精度要求不是100%的场景，可选用以下低复杂度方案：

• 贪心算法：初始化选中集为空，第一步选单条方差最小的序列加入集合；之后每一步遍历剩余未选序列，计算将其加入当前选中集后目标函数的增量，选增量最小的序列加入，直到选满K条。时间复杂度仅为$O(NK)$，绝大多数场景下得到的解和最优解差距不超过5%。
• 启发式优化算法：如果N到数百级别，可选用模拟退火、遗传算法等启发式算法，通常在几十次迭代内就能得到非常接近最优的解。

• 前置过滤：先过滤掉单条方差远高于平均水平的序列，比如单条方差排前20%的序列可直接排除（除非K特别大必须选满），这类序列无论和其他序列怎么组合，都会拉高整体方差。
• 优先筛选低协方差组合：协方差为负的序列组合会显著降低整体方差，可先把两两协方差为负的序列对拎出来作为初始候选池，再从候选池里做后续选择。

内容的提问来源于stack exchange，提问作者tkw954