CVXPY求解转化后的SDP问题时约束严重违反求助

约束错误排查与修正 #

你构造的扩展矩阵约束逻辑方向正确，但当前实现可能因数值精度或约束表述方式导致偏差。原问题中，0-1变量x满足x_i² = x_i，对应到扩展矩阵X=[[Y, x],[xᵀ,1]]，等价于X[i,i] = X[i, n-1]（i=0到n-2），同时X必须是秩1的半正定矩阵（PSD），且X[n-1,n-1]=1。

修正后的CVXPY代码 #

将约束直接表述为元素等式，避免构造Q矩阵，减少数值误差：

import cvxpy as cp
import numpy as np

n = 8
np.random.seed(1)

# 构造C矩阵（n阶，右下角为0）
C = np.zeros((n, n))
C[:n-1, :n-1] = np.random.randn(n-1, n-1)

# 定义变量：对称半正定矩阵
X = cp.Variable((n, n), PSD=True, symmetric=True)

constraints = []
# 约束X最后一个对角元为1
constraints.append(X[n-1, n-1] == 1)
# 约束x_i² = x_i → X[i,i] = X[i, n-1]
for i in range(n-1):
    constraints.append(X[i, i] == X[i, n-1])

# 原目标：Tr(C@X) = Tr(C[:n-1,:n-1] @ Y)
prob = cp.Problem(cp.Minimize(cp.trace(C @ X)), constraints)
prob.solve(solver=cp.MOSEK, verbose=True)

print("X is")
print(np.round(X.value, 4))
print("C is")
print(C)

核心问题：凸松弛的局限性 #

上述代码求解的是原组合优化问题的凸松弛版本，仅保证X是满足约束的PSD矩阵，但无法保证X的秩为1（原问题中X必须是秩1的外积矩阵）。因此，松弛解可能不对应任何0-1向量x，看起来约束被“违反”（实际是松弛解偏离了原问题的可行域）。

针对原问题的可行解法 #

因为n较小（n=8对应7个0-1变量），可以直接用整数规划建模，避免矩阵松弛：

import cvxpy as cp
import numpy as np

n = 8
np.random.seed(1)
C = np.random.randn(n-1, n-1)

# 直接定义0-1变量x
x = cp.Variable(n-1, boolean=True)
Y = cp.outer(x, x)

prob = cp.Problem(cp.Minimize(cp.trace(C @ Y)))
prob.solve(solver=cp.GUROBI)  # 需要安装GUROBI/CPLEX等支持整数规划的求解器

print("最优x：", x.value)
print("最优Y：", Y.value)

说明 #

• 若必须使用矩阵形式求解原组合问题，需要在凸松弛的基础上加入分支定界或随机化（如随机舍入）方法，将松弛解转化为可行的0-1向量解。
• 整数规划求解器（如GUROBI、CPLEX、SCIP）能直接处理0-1变量约束，对于小维度问题（n≤20）效率很高。

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