Mathematica中的二次規劃

Question

我正在研究最大獨立集問題的二次鬆弛（第22頁here），並且發現FindMaximum對於我嘗試的每個圖都會失敗，除非我以最優解作爲出發點。這些二次方程式有10-20個變量，所以我期望它們是可以解決的。

1. 有沒有辦法讓Mathematica解決這樣的二次方案？
2. 在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}}} 

Answer 1

似乎Maximize將更好地爲您服務。這裏是你的函數，它返回的2個結果列表的修改版本 - 「手動」之一，由Maximize獲得的一個：

Clear[findIVSet]; 
findIVSet[g_Graph] := 
Module[{Ag, A, cons, vars, indSet, indSetFromMaximize, xOpt}, 
    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}]; 
    {indSet, DeleteCases[vars /. (Last@ 
    Maximize[{vars.A.vars, cons}, vars,Integers] /. (x[i_] -> 1) :> (x[i] -> i)), 0]}]; 

下面是結果：

In[32]:= graphs = GraphData /@ {"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}}}; 


In[33]:= sets = findIVSet /@ graphs 

Out[33]= {{{1, 2, 3, 8, 10, 11, 17, 20}, {5, 6, 7, 8, 14, 15, 17, 18}}, 
{{2, 4, 6, 11, 12}, {2, 4, 6, 11, 12}}, {{2, 7, 10, 12, 16, 18}, {8, 11, 13, 16, 17, 18}}, 
{{1, 4, 7, 12}, {4, 7, 9, 12}}, {{2,3, 8, 9}, {2, 3, 8, 9}}, {{1, 4, 7, 10}, {2, 5, 8, 9}}, 
{{1, 4, 7, 10}, {2, 4, 7, 9}}, {{2, 4, 5, 8}, {3, 6, 7, 9}}, {{2, 5, 8, 9}, {2, 5, 8, 9}}, 
{{1, 3, 7, 10}, {4, 5, 8, 9}}, {{1, 6, 8, 9}, {2, 3, 6, 10}}, {{1, 6, 7, 12}, {4, 5, 9, 10}}, 
{{3, 4, 7, 8, 12}, {3, 4, 7, 8, 12}}, {{1, 5, 8, 9}, {4, 5, 10, 11}}, 
{{1, 5, 6, 9, 10}, {3, 4, 7, 8, 12}}, {{3, 4, 7, 9, 10}, {3, 4, 7, 9, 10}}} 

他們是對於「手動」和那些來自Maximize的那些，並不總是相同的，但是對於獨立集合，有一個以上的解決方案。從Maximize結果都是獨立的組，這是很容易驗證：

In[34]:= MapThread[IndependentVertexSetQ, {graphs, sets[[All, 2]]}] 

Out[34]= {True, True, True, True, True, True, True, True, True, True, True, True, True, 
True, True,True} 

Answer 2

IMO，FindMaximum並不在這裏工作的原因是你的函數的野性。我在變量空間中嘗試了1,048,576個採樣，並且沒有達到比零更高的值。您的最佳起始值爲-20。

In[10]:= (x[1]^2 + x[2]^2 + x[3]^2 - 2 x[3] x[4] + x[4]^2 - 
    2 x[2] (x[3] + x[4]) + x[5]^2 - 2 x[3] x[6] - 2 x[5] x[6] + 
    x[6]^2 - 2 x[5] x[7] + x[7]^2 - 2 x[6] x[8] - 2 x[7] x[8] + 
    x[8]^2 - 2 x[7] x[9] + x[9]^2 - 2 x[1] (x[2] + x[5] + x[9]) - 
    2 x[4] x[10] - 2 x[8] x[10] - 2 x[9] x[10] + x[10]^2 /. 
Thread[vars -> #]) & @@@ Tuples[{0.0, 0.333, 0.667, 1.0}, 10] // Max 

Out[10]= 0。

In[11]:= (x[1]^2 + x[2]^2 + x[3]^2 - 2 x[3] x[4] + x[4]^2 - 
2 x[2] (x[3] + x[4]) + x[5]^2 - 2 x[3] x[6] - 2 x[5] x[6] + 
x[6]^2 - 2 x[5] x[7] + x[7]^2 - 2 x[6] x[8] - 2 x[7] x[8] + 
x[8]^2 - 2 x[7] x[9] + x[9]^2 - 2 x[1] (x[2] + x[5] + x[9]) - 
2 x[4] x[10] - 2 x[8] x[10] - 2 x[9] x[10] + x[10]^2 /. 
Thread[vars -> #]) & @@@ {xOpt} 

Out[11]= {-20} 

Answer 3

可能試試包裝位於here的方法。參見問題8

丹尼爾Lichtblau 沃爾夫勒姆研究