Что не так с этой реализацией cvxopt Goemans-Williamson? - PullRequest
Новая
       13

Что не так с этой реализацией cvxopt Goemans-Williamson?

0 голосов
/ 28 августа 2018 
from cvxopt import spmatrix,matrix, solvers
from scipy.sparse import coo_matrix
from scipy.sparse import diags

b = 1.*np.zeros(len(G)**2)

for i in np.arange(0,len(G)**2,len(G)+1):
    b[i] = 1.0

A = spmatrix(b,range(len(G)**2),range(len(G)**2))
b = matrix(b)

c = 1.*nx.adjacency_matrix(G).todense().flatten()
c = np.array(c)
c = matrix(c)

sol = solvers.sdp(c.T,A=A,b=b,kktsolver='ldl', options={'kktreg':1e-9})

pcost dcost gap dres k / t

0: 0,0000e + 00 -0,0000e + 00 0e + 00 0e + 00 1e + 00 1e + 00

1: -1,8000e + 10 6,0000e-09 0e + 00 0e + 00 1e + 00 3e-21

Обнаружено свидетельство двойной невозможности.

Очевидно, что решения первичного не ограничены, но я не уверен, что именно не так с моей формулировкой.

C ограничивает то, что стоимость минимизируется только по краям графика. A и b просто используются для реализации ограничения Ax = b, так что диагональ x (если брать матрицу) равна 1.

Разве cvxopt не ограничивает, что x является PSD по умолчанию (если принимать его как матрицу)?

...