Limitación del módulo de optimización de Mathematica

Question

Tengo una pregunta sobre la capacidad de optimización global de Mathematica. Encontré este texto relacionado con la caja de herramientas de NAG (kind of white paper).

Ahora traté de resolver el caso de prueba del documento. Como se esperaba, Mathematica fue bastante rápido en resolverlo.

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 

salida era

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

Uno puede ver los puntos visitados por la rutina de optimización.

{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}}]]` 

Ahora pensé de resolver el mismo problema en dimensión superior. Para los problemas de cinco variables, las matemáticas comenzaron a caer en las trampas del mínimo local, incluso cuando se permite un gran número de puntos de búsqueda.

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 

La producción no era lo que deseábamos ver. Tomó 49 segundos en mi máquina core2duo y todavía es un mínimo local.

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

Luego intenté SimulatedAnealing con 100000 iteraciones.

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

La salida todavía no era conforme.

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

Ahora Mathematica tiene un algoritmo de optimización exacto llamado Minimizar. Que como se espera, debe fallar en la practicidad, pero falla muy rápido a medida que aumenta el tamaño del problema.

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 

salida está perfectamente bien.

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

Pero si uno cambia el tamaño del problema un paso más allá con n = 4 se muestra el resultado. La solución no aparece por mucho tiempo en mi computadora portátil.

Ahora la pregunta simple ¿alguien aquí piensa que hay una manera de numéricamente resolver este problema de manera eficiente en Mathematica para casos dimensionales? Vamos a compartir nuestras ideas y experiencia. Sin embargo, uno debe recordar que es un problema de optimización global no lineal de referencia. La mayoría de los algoritmos numéricos de búsqueda/minimización de raíz generalmente buscan el mínimo local.

BR

P

Answer 1

El aumento de los puntos iniciales me permite llegar al mínimo global:

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]]; 

Estas son las llamadas. Sin embargo, el tiempo puede no ser demasiado eficiente, pero con algoritmos aleatorizados, uno tiene que tener suficientes muestras iniciales o una buena sensación para la función.

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

Answer 2

Ha visto this page de la documentación? Repasa los métodos admitidos por NMinimize, con ejemplos para cada uno. Uno de los ejemplos de SimulatedAnnealing es la función de Rastgrin (o una muy similar), y los documentos sugieren que debe aumentar el tamaño de la perturbación para obtener buenos resultados.