CVXPY中布尔变量矩阵乘法违反DCP规则的问题及解决方法咨询

问题背景 #

需要求解的优化问题：

• 最大化目标函数：y @ A @ x
• 约束条件：sum(x) == 1、sum(y) == 1
  其中A是元素全为正值的(n,m)矩阵，x是长度m的布尔向量，y是长度n的布尔向量。

例如给定A = [[87, 96, 127, 46], [155, 166, 92, 11], [111, 163, 126, 112]]，最优解为x = [0,1,0,0]、y = [0,1,0]，对应结果166。但直接用CVXPY编写代码会抛出DCPError，提示目标函数y @ A @ x曲率为UNKNOWN，不符合DCP规则。尝试将A设为CVXPY变量、启用QCP求解等方法均无效。

错误原因 #

CVXPY的DCP规则要求目标函数和约束必须满足凸/凹性。而y @ A @ x本质是布尔变量的二次乘积项（y的元素和x的元素相乘后再加权求和），属于非凸表达式，直接编写会违反DCP规则，导致报错。此外，将已知常量A设为CVXPY变量完全没必要，反而混淆了优化变量和输入参数。

解决办法 #

方法1：直接利用问题本质求解（最优方案） #

根据约束sum(x)==1和sum(y)==1，x、y都是one-hot向量（仅一个元素为1，其余为0）。此时y @ A @ x等价于取矩阵A中某一行某一列的交叉元素——x中1所在列与y中1所在行的对应元素。因此问题简化为寻找矩阵A的最大元素，对应的行和列就是y、x的one-hot位置。

代码实现：

import numpy as np

# 示例矩阵
A = np.array([[87, 96, 127, 46], [155, 166, 92, 11], [111, 163, 126, 112]])
max_val = A.max()
# 获取最大元素的行、列索引
row_idx, col_idx = np.unravel_index(A.argmax(), A.shape)

# 构造布尔向量x和y
x = np.zeros(A.shape[1], dtype=int)
x[col_idx] = 1
y = np.zeros(A.shape[0], dtype=int)
y[row_idx] = 1

print(f"最优x: {x}")
print(f"最优y: {y}")
print(f"最大值: {max_val}")

方法2：用CVXPY的大M法转化为线性规划（适合扩展场景） #

如果需要保留CVXPY框架（比如后续扩展约束），可以通过大M法将二次目标转化为线性约束：

1. 引入线性变量z，令z等于目标函数y @ A @ x
2. 利用大M构造线性约束，确保当y[i]=1且x[j]=1时，z等于A[i,j]；其他情况约束不生效

代码实现：

import cvxpy as cp
import numpy as np

A = np.array([[87, 96, 127, 46], [155, 166, 92, 11], [111, 163, 126, 112]])
rows, cols = A.shape
M = A.max() * 10  # 取足够大的常数，确保约束生效

x = cp.Variable(cols, boolean=True)
y = cp.Variable(rows, boolean=True)
z = cp.Variable()

constraints = [
    cp.sum(x) == 1,
    cp.sum(y) == 1,
]

# 添加z与A元素关联的线性约束
for i in range(rows):
    for j in range(cols):
        # 当y[i]=1且x[j]=1时，z ≤ A[i,j]；否则约束自动满足
        constraints.append(z <= A[i,j] + (1 - y[i])*M + (1 - x[j])*M)
        # 当y[i]=1且x[j]=1时，z ≥ A[i,j]；否则约束自动满足
        constraints.append(z >= A[i,j] - (1 - y[i])*M - (1 - x[j])*M)

objective = cp.Maximize(z)
prob = cp.Problem(objective, constraints)
prob.solve()

print(f"最优x: {x.value.astype(int)}")
print(f"最优y: {y.value.astype(int)}")
print(f"最大值: {z.value}")

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