我正在研究最大独立集问题的二次松弛(第22页here),并且发现FindMaximum
对于我尝试的每个图都会失败,除非我以最优解作为出发点。这些二次方程式有10-20个变量,所以我期望它们是可以解决的。Mathematica中的二次规划
- 有没有办法让Mathematica解决这样的二次方案?
- 在Mathematica中是否有一些易于调用的二次编程包?
这里的失败FindMaximum
的例子,其次是工作FindMaximum
在解决
setupQuadratic[g_Graph] := (
Ag = AdjacencyMatrix[g];
A = IdentityMatrix[[email protected]@g] - Ag;
cons = And @@ Table[0 <= x[v] <= 1, {v, [email protected]}];
vars = x /@ VertexList[g];
indSet = [email protected];
xOpt = Array[Boole[MemberQ[indSet, #]] &, {[email protected]@g}];
);
g = GraphData[{"Cubic", {10, 11}}];
setupQuadratic[g];
FindMaximum[{vars.A.vars, cons}, vars]
FindMaximum[{vars.A.vars, cons}, Thread[{vars, xOpt}]]
这里初始化其他图表我试图
{"DodecahedralGraph", "FruchtGraph", "TruncatedPrismGraph", \
"TruncatedTetrahedralGraph", {"Cubic", {10, 2}}, {"Cubic", {10,
3}}, {"Cubic", {10, 4}}, {"Cubic", {10, 6}}, {"Cubic", {10,
7}}, {"Cubic", {10, 11}}, {"Cubic", {10, 12}}, {"Cubic", {12,
5}}, {"Cubic", {12, 6}}, {"Cubic", {12, 7}}, {"Cubic", {12,
9}}, {"Cubic", {12, 10}}}
您链接的文件是非常好的。谢谢! – 2011-03-01 12:19:22