Min cut using matlab cvx

Question

Я пытаюсь обнаружить сообщества, используя двоичный min cut на графике пользователей. Для этого я пытаюсь использовать вариант метода Фидлера, как показано в статье this. Это, как они оформили его:

Теперь я пытаюсь сделать это с помощью пакета CVX в MATLAB. Вот мой код:

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]; 

Similary, pi1 = pi2.

И tou1 = pi1 - A1, и tou2 = pi2 - A2.

Может кто-то указать, что именно я делаю неправильно. Это было бы очень полезно. Заранее спасибо !

Answer 1

Эта проблема в том, что ваше ограничение

y'* pi1 * y == alpha 

(где alpha = e'*pi1*e) не является выпуклым ограничение. Рассмотрим двумерный случай, когда размер (у) = [2 1] и PI1 тождественный, то ваше ограничение выше

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

Это эквивалентно тому, у лежать на радиусе окружности. Это не выпуклое ограничение.

CVX предназначенный для дисциплинированный выпуклый оптимизатор. Это означает, что вы должны построить свою модель из примитивов таким образом, чтобы модель была выпукла. Так как ваша модель включает ограничение, которое не является выпуклым CVX, возникает ошибка: «Дисциплинированная ошибка выпуклого программирования».

Он также говорит о проблеме: «Недопустимое ограничение {convex} == {real constant}". Это говорит о том, что вы пытаетесь ограничить выпуклую функцию равной константе.

Если вы хотите решить эту модель с помощью CVX, вам нужно будет переформулировать модель как выпуклую. Если вы не можете переформулировать его, вы можете попробовать использовать нелинейный (noncovex) решатель. Например, fmincon, включенный в MATLAB, должен иметь возможность справиться с этим ограничением. Обратите внимание, что fmincon предназначен для довольно небольших моделей, для крупномасштабных нелинейных моделей noncovex вы, вероятно, захотите использовать решатель, такой как 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 

Вы должны проверить, если решение (или выбрать одно из решений) удовлетворяет ограничение равенства. Надеюсь, что это работает для OP.