Óptimos locales frente a globales

Por qué el solver no encuentra el mínimo más pequeño

En general, los solvers devuelven un mínimo local (u óptimo). El resultado puede ser un mínimo global (u óptimo), pero este resultado no está garantizado.

• Un mínimo local de una función es un punto en el que el valor de la función es menor que en puntos cercanos, pero posiblemente mayor que en un punto alejado.

• Un mínimo global es un punto en el que el valor de la función es menor que en otros puntos factibles.

Los solvers de Optimization Toolbox™ suelen encontrar un mínimo local. (Este mínimo local puede ser un mínimo global). Encuentran el mínimo en la cuenca de atracción del punto inicial. Para obtener más información acerca de las cuencas de atracción, consulte Cuencas de atracción.

Las siguientes son excepciones a esta regla general.

• Los problemas de programación lineal y los problemas de programación cuadrática definida positiva son convexos, con regiones factibles convexas, así que solo tienen una cuenca de atracción. Según las opciones especificadas, linprog ignora los puntos iniciales que proporciona el usuario y quadprog no necesita uno, aunque, en ocasiones, puede acelerar una minimización proporcionando un punto inicial.

• Las funciones de Global Optimization Toolbox, como simulannealbnd, intentan buscar más de una cuenca de atracción.

Buscar un mínimo más pequeño

Si necesita un mínimo global, debe encontrar un valor inicial para el solver en la cuenca de atracción de un mínimo global.

Puede establecer valores iniciales para buscar un mínimo global de estas formas:

• Utilice una cuadrícula regular de puntos iniciales.

• Utilice puntos aleatorios tomados de una distribución uniforme si todas las coordenadas del problema están acotadas. Utilice puntos tomados de distribuciones normales, exponenciales o aleatorias de otro tipo si algunos componentes están desacotados. Cuanto menos sepa de la ubicación del mínimo global, más dispersa debe ser la distribución aleatoria. Por ejemplo, las distribuciones normales rara vez muestrean más de tres desviaciones estándar con respecto a sus medias, pero una distribución Cauchy (densidad 1/(π(1 + x²))) realiza muestras muy dispares.

• Utilice puntos iniciales idénticos con perturbaciones aleatorias añadidas en cada coordenada: acotadas, normales, exponenciales o de otro tipo.

• Si tiene una licencia de Global Optimization Toolbox, utilice el solver GlobalSearch (Global Optimization Toolbox) o el solver MultiStart (Global Optimization Toolbox). Estos solvers generan de forma automática puntos de inicio aleatorios dentro de los límites.

Cuanto más sepa sobre los posibles puntos iniciales, más centrada y exitosa será la búsqueda.

Cuencas de atracción

Si una función objetivo f(x) es suave, el vector –∇f(x) señala en la dirección donde f(x) se reduce más rápido. La ecuación de descenso más pronunciado, en concreto,

$$\frac{d}{dt}x(t)=-\nabla f(x(t)),$$

proporciona una trayectoria x(t) que va a un mínimo local a medida que t aumenta. En general, los valores iniciales x(0) que están cerca unos de otros proporcionan las trayectorias de descenso más pronunciadas que tienden hacia el mismo punto mínimo. La cuenca de atracción para el descenso más pronunciado es el conjunto de valores iniciales que lleva al mismo mínimo local.

Esta figura muestra dos mínimos de una dimensión. La figura muestra diferentes cuencas de atracción con distintos estilos de línea e indica las direcciones del descenso más pronunciadas con flechas. En esta figura y en las siguientes, los puntos negros representan mínimos locales. Cada trayectoria de descenso más pronunciada, que empieza en un punto x(0), se dirige al punto negro de la cuenca que contiene x(0).

Cuencas de una dimensión

Esta figura muestra cómo las trayectorias de descenso más pronunciadas pueden ser más complicadas en más dimensiones.

Una cuenca de atracción que muestra trayectorias de descenso más pronunciadas desde distintos puntos de inicio

Esta figura muestra trayectorias y cuencas de atracción incluso más complicadas.

Varias cuencas de atracción

Las restricciones pueden dividir una cuenca de atracción en varias partes. Por ejemplo, considere minimizar y sujeto a:

y ≥ |x|

y ≥ 5 – 4(x–2)².

Esta figura muestra las dos cuencas de atracción con los puntos finales.

 Código para generar la figura

myabs = @(x) abs(x);
mycurve = @(x) 5 - 4.*(x-2).^2;
myline = @(x) max(myabs(x),mycurve(x));
mybrdr = @(x) 1 + heaviside(x-2);
myarea = @(x,y) heaviside(y - myline(x)).*mybrdr(x);
% myarea = 0 where infeasible, 1 when x < 2, 2 when x > 2
marinv = @(x,y) 1./myarea(x,y); % removes the infeasible region

plot(0,0,'k.','MarkerSize',25,'LineWidth',2);
hold on
grid on
plot(11/4,11/4,'k.','MarkerSize',25,'LineWidth',2);
fplot(mycurve,'k',[.9 3],'LineWidth',2)
fplot(myline,[-2 5],'k','LineWidth',2)
fsurf(marinv,[-2 5 -1,6],'EdgeColor','none','FaceAlpha',0.5)
colormap jet

Escriba plottools en la línea de comandos para añadir flechas utilizando la herramienta de dibujar flechas.

Las trayectorias de descenso más pronunciadas son líneas rectas que bajan a los límites de restricciones. Para los límites de restricciones, las trayectorias de descenso más pronunciadas bajan siguiendo los límites. El punto final es (0,0) o (11/4,11/4), dependiendo de si el valor x inicial está por encima o por debajo de 2.

Temas relacionados

• Mejorar los resultados