0

我正在尝试使用 Picos 包解决以下半定程序。实际上，这是解决 3 个子图情况下的 maxcut 问题的 SDP 松弛。

import picos as pic

maxcut = pic.Problem()    
Y=maxcut.add_variable('Y',(47,47),'symmetric')

WW = 2/3*nx.adjacency_matrix(G).todense()
for i in range(47):
   for j in range(i+1,47):
       WW[i,j]=0
W=pic.new_param('W',WW)


maxcut.add_constraint(Y>>0)
maxcut.add_constraint(pic.tools.diag_vect(Y)==1)
maxcut.add_list_of_constraints([Y[i]> -0.5 for i in range(47*47)])


maxcut.set_objective('max',W|(1-Y))

print (maxcut)
maxcut.solve(verbose = 0)

print ('bound from the SDP relaxation: {0}'.format(maxcut.obj_value()))

我得到以下输出：

---------------------
optimization problem  (SDP):
1128 variables, 2256 affine constraints, 1128 vars in 1 SD cones

Y   : (47, 47), symmetric

maximize 〈 W | -Y + |1| 〉
such that
Y ≽ |0|
diag(Y) = |1|
[2209 constraints (first: Y[0] > -0.5)]
---------------------
bound from the SDP relaxation: 41.67318021477081

问题是，虽然我要求 Y 是半正定maxcut.add_constraint(Y>>0)的，但当我检查它的特征值时，并不是所有的特征值都是非负的。

当我删除对角线 ( 上的约束时maxcut.add_constraint(pic.tools.diag_vect(Y)==1)，这个问题就解决了。但是，我确实需要这个约束。

如果您能建议我的代码有什么问题，那就太好了...提前谢谢您！

4

1 回答 1

0

我试图在我的电脑上重现你的代码。但是，变量“nx”和 $G$ 似乎没有被定义。我在解决 SDP 时也遇到了类似的问题；也许您可能需要施加类似于

maxcut.add_constraint(Y-10 ** (-3) >>0)

这将确保您的特征值大于 $10^{-3}$。

于 2017-06-02T03:11:43.143 回答