以一定数量的零为约束的Nnls问题

Question

我正在做一个优化问题，最小化Ax和b的平方差。

A是m*n的矩阵，其中x是一个非负n向量。我想添加一个约束，向量x的n个元素中的p为零

我应该如何表述条件?这听起来有nCp集的nnls优化问题。

感谢

Answer 1

标准的表述是添加基数约束:

min ||Ax-b||^2
x[i] ≤ δ[i]*U
sum(i,δ[i]) = n-p
δ[i] ∈ {0,1}
x[i] ∈ [0,U]  

这是一个MIQP(混合整数二次规划)模型。U是x[i]的上界(不应该太大)。δ[i]为二元决策变量有意义:

δ[i] = 1:  variable x[i] is allowed to vary between 0 and U
δ[i] = 0:  variable x[i] must be zero  

有些冗余:模型同时计算x和δ。(这就是所谓的"变量"意思。)

MIQP求解器随时可用。