0

我正在尝试使用用户图上的二进制最小切割来检测社区。为此，我尝试使用本文所示的 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。

有人可以指出我到底做错了什么。这会有很大帮助。提前致谢 ！

4

2 回答 2

2

这个问题是你的约束

  y'* pi1 * y == alpha

(其中alpha = e'*pi1*e) 不是凸约束。考虑 size(y) = [2 1] 并且 pi1 是恒等式的二维情况，那么上面的约束是

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

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

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

它还告诉您问题：“无效约束 {convex} == {real constant}”。这告诉您您正在尝试将凸函数约束为等于常数。

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

于 2014-04-09T23:16:48.737 回答
0

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

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

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

您需要验证解决方案（或选择其中一个解决方案）是否满足等式约束。希望它适用于OP。

于 2014-04-21T22:10:51.477 回答