Mathematica優化模塊的限制

我對Mathematica的全局優化功能有疑問。我遇到了與NAG工具箱(kind of white paper)相關的文本。Mathematica優化模塊的限制

現在我試着從論文中解決測試案例。正如預期的那樣，Mathematica解決這個問題的速度非常快。

n=2; 
fun[x_,y_]:=10 n+(x-2)^2-10Cos[2 Pi(x-2)]+(y-2)^2-10 Cos[2 Pi(y-2)]; 
NMinimize[{fun[x,y],-5<= x<= 5&&-5<= y<= 5},{x,y},Method->{"RandomSearch","SearchPoints"->13}]//AbsoluteTiming

產量爲

{0.0470026,{0.,{x->2.,y->2.}}}

可以看到通過優化程序訪問點。

{sol, pts}=Reap[NMinimize[{fun[x,y],-5<= x<= 5&&-5<= y<= 5},{x,y},Method->`{"RandomSearch","SearchPoints"->13},EvaluationMonitor:>Sow[{x,y}]]];Show[ContourPlot[fun[x,y],{x,-5.5,5.5},{y,-5.5,5.5},ColorFunction->"TemperatureMap",Contours->Function[{min,max},Range[min,max,5]],ContourLines->True,PlotRange-> All],ListPlot[pts,Frame-> True,Axes-> False,PlotRange-> All,PlotStyle-> Directive[Red,Opacity[.5],PointSize[Large]]],Graphics[Map[{Black,Opacity[.7],Arrowheads[.026],Arrow[#]}&,Partition[pts//First,2,1]],PlotRange-> {{-5.5,5.5},{-5.5,5.5}}]]`

Convergence path of NMinimize

現在我想在更高的層面解決同一問題的。對於五個變量的數學問題，即使在允許大量搜索點的情況下，數學開始陷入局部最小值的陷阱。

n=5;funList[x_?ListQ]:=Block[{i,symval,rule}, 
i=Table[ToExpression["x$"<>ToString[j]],{j,1,n}];symval=10 n+Sum[(i[[k]]-2)^2-10Cos[2Pi(i[[k]]-2)],{k,1,n}];rule=MapThread[(#1-> #2)&,{i,x}];symval/.rule]val=Table[RandomReal[{-5,5}],{i,1,n}];vars=Table[ToExpression["x$"<>ToString[j]],{j,1,n}];cons=Table[-5<=ToExpression["x$"<>ToString[j]]<= 5,{j,1,n}]/.List-> And;NMinimize[{funList[vars],cons},vars,Method->{"RandomSearch","SearchPoints"->4013}]//AbsoluteTiming

輸出不是我們希望看到的。在我的core2duo機器上花了49秒，仍然是當地的最低要求。

{48.5157750,{1.98992,{x$1->2.,x$2->2.,x$3->2.,x$4->2.99496,x$5->1.00504}}}

然後嘗試使用SimulatedAnealing進行100000次迭代。

NMinimize[{funList[vars],cons},vars,Method->"SimulatedAnnealing",MaxIterations->100000]//AbsoluteTiming

產量仍不理想。

{111.0733530,{0.994959,{x$1->2.,x$2->2.99496,x$3->2.,x$4->2.,x$5->2.}}}

現在Mathematica有一個名爲Minimize的精確優化算法。正如預期的那樣，實際上會失敗，但隨着問題規模的增加，它會很快失敗。

n=3;funList[x_?ListQ]:=Block[{i,symval,rule},i=Table[ToExpression["x$"<>ToString[j]],{j,1,n}];symval=10 n+Sum[(i[[k]]-2)^2-10Cos[2 Pi(i[[k]]-2)],{k,1,n}];rule=MapThread[(#1-> #2)&,{i,x}];symval/.rule]val=Table[RandomReal[{-5,5}],{i,1,n}];vars=Table[ToExpression["x$"<>ToString[j]],{j,1,n}];cons=Table[-5<=ToExpression["x$"<>ToString[j]]<= 5,{j,1,n}]/.List-> And;Minimize[{funList[vars],cons},vars]//AbsoluteTiming

輸出完全沒問題。

{5.3593065,{0,{x$1->2,x$2->2,x$3->2}}}

但是，如果將n = 4更進一步改變問題的大小，您會看到結果。我的筆記本中很久沒有出現解決方案。

現在的問題很簡單，這裏有人認爲有一種方法數字在Mathematica高效解決這個問題的高維情況？讓我們分享我們的想法和經驗。但是應該記住，它是一個基準非線性全局優化問題。大多數數值根發現/最小化算法通常搜索局部最小值。

來源

2011-07-08 PlatoManiac

增加初始點可以讓我獲得全球最低：

n = 5; 

funList[x_?ListQ] := Total[10 + (x - 2)^2 - 10 Cos[2 Pi (x - 2)]] 

val = Table[RandomReal[{-5, 5}], {i, 1, n}]; 
vars = Array[Symbol["x$" <> ToString[#]] &, n]; 
cons = Apply[And, Thread[-5 <= vars <= 5]];

這些都是調用。雖然時間可能不太有效，但隨機算法必須有足夠的初始樣本，或者對函數有良好的感覺。

In[27]:= NMinimize[{funList[vars], cons}, vars, 
    Method -> {"DifferentialEvolution", 
    "SearchPoints" -> 5^5}] // AbsoluteTiming 

Out[27]= {177.7857768, {0., {x$1 -> 2., x$2 -> 2., x$3 -> 2., 
    x$4 -> 2., x$5 -> 2.}}} 

In[29]:= NMinimize[{funList[vars], cons}, vars, 
    Method -> {"RandomSearch", "SearchPoints" -> 7^5}] // AbsoluteTiming 

Out[29]= {609.3419281, {0., {x$1 -> 2., x$2 -> 2., x$3 -> 2., 
    x$4 -> 2., x$5 -> 2.}}}

來源

2011-07-08 17:50:31 Sasha

手動命名像'x $ 1'，'x $ 2'等變量不是不安全，因爲'Module'也通過類似的重命名進行本地化嗎？這樣做是否會導致可變的衝突？ – Szabolcs

@Szabolcs我不會推薦在程序中使用它，但在交互式會話中是安全的。我的小實驗表明'Module'知道躲避碰撞。 'Set @@ {Symbol [「x」<> ToString [$ ModuleNumber]]，17};打印[{$ ModuleNumber，Symbol [「x」<> ToString [$ ModuleNumber]]}];模塊[{x}，x]' – Sasha

你見過的文件this page？它回顧了NMinimize支持的方法，並給出了每個方法的示例。其中一個SimulatedAnnealing示例是Rastgrin的函數（或者一個非常相似），並且文檔建議您需要增加擾動大小以獲得良好結果。

來源

2011-07-08 17:08:44 JPL

Mathematica優化模塊的限制

回答

相關問題