如何在Mosek中实现变量向量最多一个元素非零的约束

核心处理逻辑 #

你提到的x0 * x1 <= 0约束属于非凸双线性约束，不能直接输入Mosek求解，我们可以通过引入二进制变量将其转化为混合整数线性规划（MILP）的凸约束形式，Mosek原生支持MILP问题求解。

由于你的两个变量均满足非负约束，二者乘积小于等于0等价于最多有一个变量取非零值，可以按以下方式转化：

• 引入二进制变量y ∈ {0, 1}
• 新增两个线性约束：
  • x0 <= c0 * y
  • x1 <= c1 * (1 - y)

约束等价性说明 #

• 当y=1时，x1的上界被限制为0，只能取0，x0可以在[0, c0]范围内自由取值
• 当y=0时，x0的上界被限制为0，只能取0，x1可以在[0, c1]范围内自由取值
  完全匹配你需要的约束效果。

完整建模步骤 #

1. 定义三类变量：连续变量x0、x1，二进制决策变量y
2. 输入原生边界约束：0 <= x0 <= c0、0 <= x1 <= c1
3. 输入转化后的两个互斥线性约束
4. 输入线性优化目标 max A@X + B（即max A[0]*x0 + A[1]*x1 + B）
5. 直接调用Mosek的混合整数规划求解接口即可得到最优解

扩展说明 #

如果后续变量规模扩展到n个，要求最多k个变量非零，都可以用类似的大M约束加二进制变量的方式转化，Mosek对中小规模的混合整数问题求解效率表现优秀。

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