0

ユーザーのグラフでバイナリ最小カットを使用してコミュニティを検出しようとしています。この目的のために、この論文に示されているように、フィードラー法の変形を使用しようとしています。これは彼らがそれを形式化した方法です：

ここに画像の説明を入力

現在、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 が ID である 2 次元のケースを考えてみると、上記の制約は次のようになります。

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

これは、y が円の半径上にあることを要求することと同じです。これは凸制約ではありません。

CVX は、規律ある凸最適化用に設計されています。これは、モデルが凸型であることを保証する方法で、プリミティブからモデルを構築する必要があることを意味します。モデルには凸ではない制約が含まれているため、CVX はエラーを発行します:「統制された凸プログラミング エラー」。

また、「無効な制約{凸} == {実定数}」という問題も示しています。これは、凸関数を定数に等しくなるように制約しようとしていることを示しています。

このモデルを CVX で解決したい場合は、モデルを凸になるように再定式化する必要があります。再定式化できない場合は、非線形 (noncovex) ソルバーを使用してみてください。たとえば、MATLAB に含まれるfminconは、この制約を処理できる必要があります。fminconはかなり小規模なモデル用に設計されていることに注意してください。大規模な非線形非コベックス モデルでは、おそらくSNOPTやKNITROなどのソルバーを使用する必要があります。

于 2014-04-09T23:16:48.737 に答える