如何改写CVXPY中不符合DCP规则的测距残差项以满足凸优化要求？

我需要根据静态锚点的相对距离和角度测量值计算目标的实时位置，用CVXPY构建优化问题时，代码里的range_differences += cp.square(cp.norm(x[t] - sim.anchors[i]) - range_)项不符合DCP规则，该怎么调整才能满足要求？原代码如下：

def solve_task10(sim, mu):
    x = cp.Variable((T, 2))

    cost = 0
    for t in range(1, T):
        # sum((|x-ak| - r)^2)
        range_differences = 0
        for i in range(4):
            range_, angle, velocity = sim.get_anchor_stamped_measurment(i, t)
            range_differences += cp.square(cp.norm(x[t] - sim.anchors[i]) - range_)

        # |v_est - v|^2
        v_estimated = (
            x[t] - x[t - 1]
        )  # Difference between x at time t and x at time t-1
        velocity_difference = mu * cp.square(cp.norm(v_estimated - velocity))

        cost += range_differences + velocity_difference

    objective = cp.Minimize(cost)
    constraints = [x[0] == np.array([0, 0])]
    problem = cp.Problem(objective, constraints)
    problem.solve(solver=cp.ECOS)

    return x.value

为什么原代码违反DCP规则 #

CVXPY的DCP规则要求目标函数必须是凸函数，约束必须是凸集。原代码中的cp.square(cp.norm(x[t] - sim.anchors[i]) - range_)展开后为cp.square(cp.norm(...)) - 2*range_*cp.norm(...) + range_**2：

• cp.square(cp.norm(...))是凸函数（二次型）
• -2*range_*cp.norm(...)是凹函数（凸函数乘以负数）
• 凸函数加凹函数的结果不是凸函数，因此整个项不符合DCP要求，无法被CVXPY的求解器处理。

两种合规的调整方案 #

方案1：改用绝对值损失（简单直接）

把平方损失替换为绝对值损失，cp.abs(cp.norm(x[t] - sim.anchors[i]) - range_)是凸函数，完全符合DCP规则。虽然损失函数和原平方损失不同，但在多数定位场景下依然能得到合理结果，代码修改如下：

def solve_task10(sim, mu):
    x = cp.Variable((T, 2))

    cost = 0
    for t in range(1, T):
        range_differences = 0
        for i in range(4):
            range_, angle, velocity = sim.get_anchor_stamped_measurment(i, t)
            # 替换为绝对值损失
            range_differences += cp.abs(cp.norm(x[t] - sim.anchors[i]) - range_)

        v_estimated = x[t] - x[t - 1]
        velocity_difference = mu * cp.square(cp.norm(v_estimated - velocity))

        cost += range_differences + velocity_difference

    objective = cp.Minimize(cost)
    constraints = [x[0] == np.array([0, 0])]
    problem = cp.Problem(objective, constraints)
    problem.solve(solver=cp.ECOS)

    return x.value

方案2：用二阶锥规划（SOCP）保留平方损失特性

如果希望保留平方损失的统计特性（比如适配高斯噪声），可以引入辅助变量将问题转化为SOCP形式，这也是CVXPY支持的凸优化类型：

def solve_task10(sim, mu):
    x = cp.Variable((T, 2))
    # 为每个时间步的每个锚点引入辅助变量v，用来表示距离差的绝对值
    v = cp.Variable((T, 4))

    cost = 0
    constraints = [x[0] == np.array([0, 0])]
    
    for t in range(1, T):
        range_sum = 0
        for i in range(4):
            range_, angle, velocity = sim.get_anchor_stamped_measurment(i, t)
            anchor = sim.anchors[i]
            # 添加约束：v[t,i] >= | ||x[t] - anchor|| - range_ |
            constraints.append(cp.norm(x[t] - anchor) - range_ <= v[t, i])
            constraints.append(range_ - cp.norm(x[t] - anchor) <= v[t, i])
            # 用v的平方代替原平方项
            range_sum += cp.square(v[t, i])

        v_estimated = x[t] - x[t - 1]
        velocity_difference = mu * cp.square(cp.norm(v_estimated - velocity))

        cost += range_sum + velocity_difference

    objective = cp.Minimize(cost)
    problem = cp.Problem(objective, constraints)
    # SOCP求解器推荐用ECOS或SCS
    problem.solve(solver=cp.ECOS)

    return x.value

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