Mathematica 中的二次规划
我正在研究最大独立集问题的二次松弛（p.22 此处 ），并发现 FindMaximum 对于我尝试的每个图表都会失败，除非我将最佳解决方案作为起点。这些二次规划有 10-20 个变量，所以我希望它们是可解的。
- 有没有办法让 Mathematica 求解这样的二次规划？
- 是否有一些可以轻松从 Mathematica 中调用的二次编程包？
这是 FindMaximum 失败的示例，然后是在解决方案中初始化的工作 FindMaximum
setupQuadratic[g_Graph] := (
Ag = AdjacencyMatrix[g];
A = IdentityMatrix[Length@VertexList@g] - Ag;
cons = And @@ Table[0 <= x[v] <= 1, {v, VertexList@g}];
vars = x /@ VertexList[g];
indSet = FindIndependentVertexSet@g;
xOpt = Array[Boole[MemberQ[indSet, #]] &, {Length@VertexList@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}}}
I'm looking at quadratic relaxation of maximum independent set problem (p.22 here), and found that FindMaximum fails for every graph I try, unless I give it optimal solution as the starting point. These quadratic programmes have 10-20 variables, so I expect them to be solvable.
- Is there a way to make Mathematica solve such quadratic programmes?
- Is there some quadratic programming package that's easy to call from within Mathematica?
Here's an example of failing FindMaximum, followed by working FindMaximum initialized at the solution
setupQuadratic[g_Graph] := (
Ag = AdjacencyMatrix[g];
A = IdentityMatrix[Length@VertexList@g] - Ag;
cons = And @@ Table[0 <= x[v] <= 1, {v, VertexList@g}];
vars = x /@ VertexList[g];
indSet = FindIndependentVertexSet@g;
xOpt = Array[Boole[MemberQ[indSet, #]] &, {Length@VertexList@g}];
);
g = GraphData[{"Cubic", {10, 11}}];
setupQuadratic[g];
FindMaximum[{vars.A.vars, cons}, vars]
FindMaximum[{vars.A.vars, cons}, Thread[{vars, xOpt}]]
Here are other graphs I tried
{"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}}}
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
可以尝试位于此处的包中显示的方法。参见问题 8
Daniel Lichtblau
沃尔夫勒姆研究公司
Might try method shown in package located here. See problem 8
Daniel Lichtblau
Wolfram Research
看来
Maximize会更好地为您服务。这是您的函数的修改版本，它返回 2 个结果的列表 - “手动”结果和通过Maximize获得的结果：以下是结果：
“手动”结果并不总是相同” 和那些来自
Maximize的，但是还有更多独立组的一个解决方案。
Maximize的结果都是独立的集合，很容易验证：It seems that
Maximizewill serve you better. Here is a modified version of your function, which returns a list of 2 results - the "manual" one and the one obtained byMaximize:Here are the results:
They are not always the same for "manual" ones and those from
Maximize, but then there is more thanone solution for an independent set. The results from
Maximizeare all independent sets, which is easily verified:IMO，FindMaximum 在这里不起作用的原因是你的函数的野性。我尝试了在可变空间中包含 1,048,576 个样本的网格，但没有一个获得比零更高的值。您的最佳起始值为-20。
输出[10]= 0。IMO, the reason FindMaximum doesn't work here is the wild nature of your function. I tried a grid with 1,048,576 samples in variable space and none achieve a higher value than zero. Your optimum starting value gets -20.
Out[10]= 0.