带固定数量零元素约束的NNLS问题建模方法咨询

你的问题本质是支撑集大小固定为$k=n-p$的非负最小二乘问题，不需要暴力遍历所有组合，可通过以下方式精确建模：

精确MIQP（混合整数二次规划）建模 #

引入n个0-1二进制指示变量$z_i \in {0,1}$，用来标记每个$x_i$是否为非零值：

• $z_i=1$ 表示$x_i$允许取非负值
• $z_i=0$ 表示强制$x_i=0$

完整模型形式如下：
$$
\begin{aligned}
\min_{x,z} \quad & |Ax - b|2^2 \
\text{s.t.} \quad & x_i \geq 0, \quad \forall i=1,2,...,n \
& z_i \in {0,1}, \quad \forall i=1,2,...,n \
& \sum{i=1}^n z_i = n-p \
& x_i \leq M \cdot z_i, \quad \forall i=1,2,...,n
\end{aligned}
$$

对模型参数和约束的说明：

• 约束$\sum_{i=1}^n z_i = n-p$直接保证恰好有p个$z_i$取0，对应恰好p个$x_i$被强制为0，完全匹配约束要求
• 最后一组是大M联动约束，M为足够大的正常数：因为x本身非负，当$z_i=0$时$x_i \leq 0$结合非负约束就直接锁定$x_i=0$；当$z_i=1$时这个约束不会限制$x_i$的正常取值
• 注意M不要盲目取极大值，否则会引入数值误差，实操中可以先求解无零元素约束的普通NNLS得到参考解，取参考解中x最大元素的1.5~2倍作为M即可

这个模型可以直接调用现成的MIQP求解器（比如开源的SCIP，商业的Gurobi/CPLEX）求解，求解器内置的分支定界、割平面算法会自动剪枝无效的零位置组合，效率远高于手动遍历所有$C_n^p$种组合。

关于遍历子问题方案的说明 #

你考虑的遍历所有零位置组合、每个组合求解固定支撑集的NNLS子问题，属于该问题的暴力枚举解法，仅在n规模极小、组合数$C_n^p$在可接受范围内时可用。比如n=20、p=10时组合数约18万，还可以勉强跑完；但如果n=30、p=15，组合数就达到1.55亿，暴力枚举完全不具备可行性。

如果对求解精度要求不高、n规模很大，也可以采用非负稀疏最小二乘的近似算法，比如非负正交匹配追踪（Non-negative OMP）、迭代硬阈值类算法快速得到近似解。

内容的提问来源于stack exchange，提问作者Hiu leong Ng