凸约束和优化中的欧氏距离

Question

初学者风格，关于凸优化的一般问题。作为具体学习 cvxpy 和一般凸优化的一部分，正在尝试基本（假想）几何（希望是凸）优化问题。给定 2D 单位正方形（线段）中的两个点，找到满足边界框和欧几里德距离约束的 [x1,y1] 和 [x2,y2] 的最佳值。看来使用距离下界的约束不是凸的。请参阅示例 Python/cvxpy 代码。

我的问题：考虑到欧几里得距离如此常见/基本，是否可以将其表示为凸约束和凸优化问题？在我深入研究 SOC、PSD 等之前，他们能解决这个问题吗？或者必须使用非凸优化包。 （可能还有其他类型的算法来解决这个假想的问题，但这里只对优化方法感兴趣）。

在我开始像“凸优化 - 欧几里德距离几何”等论文之前，只需要一些指导技巧来引导我走向正确的方向。已经检查了 cvxpy 示例和源代码，没有找到类似的东西。

def setUp(self):
    self.xy1 = VarCvx(shape=(2,), name='xy1', var_id=0, nonneg=True)
    self.xy2 = VarCvx(shape=(2,), name='xy2', var_id=1, nonneg=True)

def testMinimizeNorm(self):
    """
    cvxpy.error.DCPError: Problem does not follow DCP rules. Specifically:
        The following constraints are not DCP:
        0.1 <= Pnorm(xy1 + -xy2, 2) , because the following subexpressions are not:
        |--  0.1 <= Pnorm(xy1 + -xy2, 2)
    """
    constraints = [
        self.xy1 >= 0,
        self.xy2 >= 0,
        self.xy1 <= 10,
        self.xy2 <= 10,
        cvx.norm(self.xy1 - self.xy2, 2) <= 0.9, # works fine
        cvx.norm(self.xy1 - self.xy2, 2) >= 0.1, # doesn't work
    ]
    objective = Minimize(cvx.norm(self.xy1 - self.xy2, 2))
    problem = Problem(objective, constraints)
    self.solveAndPrint(problem)

Answer 1

范数下界不是凸约束，因此问题不是凸的。

要理解它，您可以查看该函数的EpiGraph。

如果我们研究 R，那么范数平方就是该数的平方。 x^2 图上方的集合是凸函数。 所以上限创建了一个凸集。

它下面的集合不是凸集，只需在两条边之间画一条线即可。