如何在CVXPY中高效实现最小N个非零元素的求和约束？

要在CVXPY+MOSEK的混合整数规划中实现你需要的约束，核心难点是CVXPY不支持对符号变量使用运行时布尔索引（比如(A@x)[A@x > epsilon]），必须通过辅助变量和约束来模拟“筛选非零元素”+“取最小N个求和”的逻辑。以下是高效且严谨的实现方案：

核心思路 #

引入二进制辅助变量标记“非零元素”，结合大M约束建立标记与变量取值的关联，再通过构造辅助变量让非标记元素在sum_smallest计算中被排除，最终实现目标约束。

具体实现步骤与代码 #

1. 定义变量与参数 #

首先定义整数变量x，以及二进制辅助变量y（用于标记每个A@x元素是否为“非零”，即≥epsilon），同时计算大M值（A@x元素的最大可能取值，用于约束）。

2. 建立标记与取值的约束 #

通过大M约束确保：

• 若y_i=1，则(A@x)_i ≥ epsilon（标记为非零）
• 若(A@x)_i > epsilon，则y_i=1（非零元素必须被标记）

3. 构造辅助变量实现筛选 #

构造z变量，让非标记元素（y_i=0）的z_i值极大，这样sum_smallest(z, N)只会选中标记为非零的元素里最小的N个。

完整代码示例 #

import cvxpy as cp
import numpy as np

# 假设已知参数：A(m×n), b, epsilon, N，以及x的上下界x_lb, x_ub
m, n = A.shape

# 定义变量：x为整数变量（根据实际需求调整是否为混合整数）
x = cp.Variable(n, integer=True)
# 二进制变量：y_i=1表示(A@x)_i为非零元素（≥epsilon）
y = cp.Variable(m, boolean=True)

# 计算大M：(A@x)_i的最大可能取值，确保覆盖所有情况
row_l1_norms = np.linalg.norm(A, ord=1, axis=1)
M = row_l1_norms @ np.full(n, x_ub) + 1e3  # 加安全冗余避免数值问题

# 计算A@x
Ax = A @ x

# 约束1：标记为非零的元素必须≥epsilon
constraints = [Ax >= epsilon * y]

# 约束2：元素>epsilon时必须被标记为非零（大M约束）
constraints += [Ax <= epsilon + M * (1 - y)]

# 约束3：至少存在N个非零元素（否则目标约束无意义）
constraints += [cp.sum(y) >= N]

# 构造辅助变量z：非标记元素的z值极大，不会被sum_smallest选中
z = Ax + M * (1 - y)

# 目标约束：最小N个非零元素的和≥b
constraints += [cp.sum_smallest(z, N) >= b]

# 定义你的目标函数（示例为最小化x的和）
objective = cp.Minimize(cp.sum(x))

# 调用MOSEK求解
prob = cp.Problem(objective, constraints)
prob.solve(solver=cp.MOSEK, verbose=True)

关键细节说明 #

• 大M的选择：必须足够大以覆盖A@x的所有可能取值，可通过矩阵行的L1范数乘以变量上界计算，再添加冗余避免数值误差。
• 数值稳定性：epsilon不宜过小，否则MOSEK可能因精度问题出现约束违反，建议根据问题规模选择1e-4~1e-2量级的值。
• sum_smallest的作用：CVXPY的sum_smallest(z, N)是凸函数，MOSEK支持在混合整数规划中处理这类凸约束，无需额外转换。

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