用matlab cvx实现最小切割

Question

我正在尝试在用户图上使用二进制最小切割来检测社区。为此，我尝试使用this论文中所示的Fiedler方法的变体。这是他们是如何将其形式化的：

​

​

现在，我正在尝试使用matlab中的CVX包来实现这一点。下面是我的代码：

tou = ((beta/ (e' * pi1 * e)) * tou1) + (((1 - beta) / (e' * pi2 * e)) * tou2);
n = 6;
cvx_begin
    variable y(n)
    minimize( y' * tou * y )
    subject to
        y' * pi1 * y == e' * pi1 * e
        y' * pi2 * y == e' * pi2 * e
        y' * pi1 * e == 0
        y' * pi2 * e == 0
cvx_end

但它向我显示了以下错误：

Disciplined convex programming error:
Invalid constraint: {convex} == {real constant}

Error in ==> cvx.eq at 12
b = newcnstr( evalin( 'caller', 'cvx_problem', '[]' ), x, y, '==' );

Error in ==> fiedler at 16
y' * pi1 * y == e' * pi1 * e

其中，A1是定义如下的矩阵：

A1 = [0 3 2 0 0 0; 3 0 3 1 0 0; 2 3 0 0 0 0; 0 1 0 0 4 2; 0 0 0 4 0 3; 0 0 0 2 3 0];

类似地，A2 = A1。

pi1是一个矩阵，是一个对角矩阵，它的值等于该特定行中A1的所有值的总和。这样做我会得到

pi1 = [5 0 0 0 0 0; 0 7 0 0 0 0; 0 0 5 0 0 0; 0 0 0 7 0 0; 0 0 0 0 7 0; 0 0 0 0 0 5];

类似的，pi1 = pi2。

tou1 = pi1 - A1和tou2 = pi2 - A2。

有人能指出我到底做错了什么吗？这会有很大的帮助。提前感谢！

Answer 1

这个问题是你的约束

  y'* pi1 * y == alpha

(其中alpha = e'*pi1*e )不是凸面约束。考虑二维情况，其中size(y) =2 1，pi1是单位，那么上面的约束是

       y(1)^2 + y(2)^2 == alpha

这相当于要求y位于圆的半径上。这不是凸约束。

CVX是为有规律的凸优化而设计的。这意味着您必须以一种确保模型是凸的方式从基元构建模型。由于您的模型包含一个不是凸的约束，CVX会发出错误：“纪律性凸编程错误”。

它还告诉你这个问题：“无效约束{凸} == {实常量}”。这告诉你，你正试图约束一个凸函数等于一个常量。

如果你想用CVX解决这个模型，你需要将模型重新表述为凸的。如果你不能重新定义它，你可以尝试使用一个非线性(非凸)求解器。例如，MATLAB中包含的fmincon应该能够处理此约束。请注意，fmincon是为相当小的规模模型设计的，对于大型非线性非凸模型，您可能希望使用SNOPT或KNITRO等求解器。

Answer 2

对于原始问题，等式约束通常可以通过将等号(=)替换为<=来放松。大多数情况下，解决方案将满足等式约束(但不能保证)。

原来的问题可以放松如下：

tou = ((beta/ (e' * pi1 * e)) * tou1) + (((1 - beta) / (e' * pi2 * e)) * tou2);
n = 6;
cvx_begin
 variable y(n)
 minimize( y' * tou * y )
 subject to
     y' * pi1 * y <= e' * pi1 * e
     y' * pi2 * y <= e' * pi2 * e
     y' * pi1 * e <= 0
     y' * pi2 * e <= 0
cvx_end

您需要验证解决方案(或选择其中一个解决方案)是否满足相等约束。希望这对行动有效。