CVXPY中cp.outer与决策变量结合的DCP错误及解决咨询

问题背景 #

我正在解决机器学习计算图中为每个算子（v）选择最优并行化算法的问题：

• 每个算法关联计算成本c_v与通信成本d_v，向量规模n为可选算法数量
• s_v是算子v的布尔（独热）选择向量，c_v、d_v为成本向量
• 第二项考虑算子间的重分片成本：n×n矩阵R_vu表示算子u从v获取输入时，二者并行化算法选择对应的通信成本
• 由于第二项是二次项，我尝试引入形状为(n,n)的新变量e_uv并展平R_vu矩阵进行线性化处理

原代码 #

import cvxpy as cp
import numpy as np

n = 10

nodes = [
    {
        "compute_cost_vector": np.random.randint(0, 10, n),
        "all_input_nodes": [],
        "opt_var": None,
    },
    {
        "compute_cost_vector": np.random.randint(0, 10, n),
        "all_input_nodes": [0],
        "opt_var": None,
    },
]

expr = 0
const = []

for node in nodes:
    opt_var = cp.Variable(n, boolean=True)
    node["opt_var"] = opt_var

    const += [cp.sum(opt_var) == 1]

    expr += opt_var.T @ node["compute_cost_vector"]

    for in_node_idx in node["all_input_nodes"]:
        in_node = nodes[in_node_idx]
        in_opt_var = in_node["opt_var"]

        resharding_cost = np.random.randint(
            1, 10, size=(opt_var.shape + in_opt_var.shape)
        )
        flattened_resharding_cost = np.matrix.flatten(resharding_cost)

        e_var = cp.Variable(opt_var.shape + in_opt_var.shape, boolean=True)
        expr += cp.vec(e_var).T @ flattened_resharding_cost

        const += [cp.sum(e_var) == 1, e_var == cp.outer(opt_var, in_opt_var)]

prob = cp.Problem(cp.Minimize(expr), const)
prob.solve()

运行错误 #

cvxpy.error.DCPError: Problem does not follow DCP rules. Specifically:
The following constraints are not DCP:
var16 == reshape(var8, (10, 1), F) @ reshape(var1, (1, 10), F) , because the following subexpressions are not:
|--  reshape(var8, (10, 1), F) @ reshape(var1, (1, 10), F)

问题原因 #

1. DCP规则硬性限制：CVXPY的DCP规则要求约束必须是凸函数≤凹函数、凹函数≥凸函数，或仿射等式/不等式。cp.outer(opt_var, in_opt_var)本质是二次双线性项，既非凸也非凹，完全不符合DCP的凸性判定标准——哪怕变量是布尔类型，CVXPY的DCP检查也不会额外利用变量的约束放宽规则。
2. 线性化思路错误：直接用e_var = cp.outer(...)的等式约束尝试线性化二次项，本身就是非线性约束，无法通过DCP校验。

解决方法 #

用一组线性约束替代非线性的外积等式，利用独热布尔向量的特性，把e_var[i][j] = opt_var[i] * in_opt_var[j]的逻辑转化为线性约束：

• e_var[i][j] ≤ opt_var[i]：仅当opt_var[i]为1时，e_var[i][j]才可能为1
• e_var[i][j] ≤ in_opt_var[j]：仅当in_opt_var[j]为1时，e_var[i][j]才可能为1
• e_var[i][j] ≥ opt_var[i] + in_opt_var[j] - 1：当opt_var[i]和in_opt_var[j]同时为1时，e_var[i][j]必须为1

修改后的代码如下：

import cvxpy as cp
import numpy as np

n = 10

nodes = [
    {
        "compute_cost_vector": np.random.randint(0, 10, n),
        "all_input_nodes": [],
        "opt_var": None,
    },
    {
        "compute_cost_vector": np.random.randint(0, 10, n),
        "all_input_nodes": [0],
        "opt_var": None,
    },
]

expr = 0
const = []

for node in nodes:
    opt_var = cp.Variable(n, boolean=True)
    node["opt_var"] = opt_var

    const += [cp.sum(opt_var) == 1]

    expr += opt_var.T @ node["compute_cost_vector"]

    for in_node_idx in node["all_input_nodes"]:
        in_node = nodes[in_node_idx]
        in_opt_var = in_node["opt_var"]

        resharding_cost = np.random.randint(1, 10, size=(n, n))
        flattened_resharding_cost = resharding_cost.flatten()

        e_var = cp.Variable((n, n), boolean=True)
        expr += cp.vec(e_var).T @ flattened_resharding_cost

        # 线性约束替代非线性外积等式
        const += [cp.sum(e_var) == 1]
        for i in range(n):
            for j in range(n):
                const += [e_var[i,j] <= opt_var[i]]
                const += [e_var[i,j] <= in_opt_var[j]]
                const += [e_var[i,j] >= opt_var[i] + in_opt_var[j] - 1]

prob = cp.Problem(cp.Minimize(expr), const)
prob.solve()

# 输出求解结果
print("算子选择结果：")
for idx, node in enumerate(nodes):
    print(f"算子{idx}: {node['opt_var'].value}")
print(f"最小总成本：{prob.value}")

逻辑解释 #

这组线性约束完全等价于外积的逻辑：由于opt_var和in_opt_var都是独热向量，只有当opt_var[i]和in_opt_var[j]同时为1时，e_var[i][j]才会被约束为1，其余情况必然为0，和外积结果一致。所有约束均为线性，符合CVXPY的DCP规则，可正常求解。

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