Mathematica优化模块的局限性

Question

Mathematica优化模块的局限性

wolfram-mathematicanumericalmathematical-optimization

10

我有一个关于Mathematica的全局优化能力的问题。我偶然发现了与NAG工具箱相关的这段文本（一种白皮书）(kind of white paper)。

现在，我尝试解决来自论文的测试用例。正如预期的那样，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}}]]`

NMinimize的收敛路径

现在，我想在更高的维度上解决同样的问题。对于五个变量的问题，即使允许大量的搜索点，Mathematica也容易陷入局部最小值的陷阱。

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}}}

然后尝试了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中有一种有效的方式以数值方式高效地解决更高维度的情况？让我们分享我们的想法和经验。然而，应该记住这是一个基准非线性全局优化问题。大多数数值根查找/最小化算法通常搜索局部最小值。敬礼， P

- PlatoManiac

2个回答

3

你看过这个页面的文档吗？它介绍了NMinimize支持的各种方法，并提供了每种方法的示例。其中一个模拟退火的示例是Rastgrin的函数（或者是一个非常相似的函数），文档建议你增加扰动大小以获得良好的结果。

- JPL

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Sasha · Accepted Answer

增加初始点可以让我达到全局最小值：

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.}}}