Esta página aún no se ha traducido para esta versión. Puede ver la versión más reciente de esta página en inglés.

Local vs global optima

¿Por qué el solucionador no encuentra el mínimo más pequeño?

En general, los solucionadores devuelven un mínimo local. El resultado puede ser un mínimo global, pero no hay garantía de que lo sea. Esta sección describe por qué los solucionadores se comportan de esta manera, y da sugerencias de maneras de buscar un mínimo global, si es necesario.

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

  • Un mínimo es un punto en el que el valor de la función es menor que en todos los demás puntos factibles.Global

Generalmente, los solucionadores encuentran un óptimo local.Optimization Toolbox™ (Este óptimo local puede ser un óptimo global.) Encuentran lo óptimo en el punto de partida.Cuenca de atracción Para obtener más información sobre cuencas de atracción, consulte.Cuencas de atracción

Hay algunas excepciones a esta regla general.

  • La programación lineal y los problemas de programación cuadrática positivos definidos son convexos, con regiones viables convexas, por lo que sólo hay una cuenca de atracción. De hecho, bajo ciertas opciones de opción, ignora cualquier punto de inicio proporcionado por el usuario, y no requiere uno, aunque el suministro de uno a veces puede acelerar una minimización.linprogquadprog

  • Global Optimization Toolbox funciones como, por ejemplo, intentar buscar más de una cuenca de atracción.simulannealbnd

Búsqueda de un mínimo menor

Si necesita un óptimo global, debe encontrar un valor inicial para su solucionador en la cuenca de atracción de un óptimo global.

Sugerencias de formas de establecer los valores iniciales para buscar un óptimo global:

  • Utilice una rejilla regular de puntos iniciales.

  • Utilice puntos aleatorios extraídos de una distribución uniforme si el problema tiene delimitadas todas sus coordenadas. Utilice puntos extraídos de distribuciones normales, exponenciales o aleatorias, si algunos componentes no están delimitados. Cuanto menos sepas sobre la ubicación del óptimo global, más spread-out debe ser tu distribución aleatoria. Por ejemplo, las distribuciones normales raramente muestrean más de tres desviaciones estándar de sus medios, pero una distribución de Cauchy (densidad 1/(π(1 + x2))) hace muestras enormemente dispares.

  • Utilice puntos iniciales idénticos con perturbaciones aleatorias añadidas en cada coordenada, delimitadas, normales, exponenciales u otras.

  • Si tiene un Global Optimization Toolbox licencia, utilice los o solucionadores.GlobalSearchMultiStart Estos solucionadores generan automáticamente puntos de inicio aleatorios dentro de los límites.

Cuanto más sepas sobre posibles puntos iniciales, más enfocado y exitoso será tu búsqueda.

Cuencas de atracción

Si una función objetiva f(x) es suave, el vector –∇f(x) puntos en la dirección donde f(x) disminuye más rápidamente. La ecuación de descenso más empen, es decir

ddtx(t)=f(x(t)),

produce una ruta x(t) que va a un mínimo local como t se vuelve grande. Generalmente, los valores iniciales x(0) que están cerca unos de otros dan caminos de descenso más escarpan que tienden al mismo punto mínimo. El descenso más empinante es el conjunto de valores iniciales que conducen al mismo mínimo local.Cuenca de atracción

La figura siguiente muestra los mínimos de 2 1 dimensiones. La figura muestra diferentes cuencas de atracción con diferentes estilos de línea, y muestra las direcciones de descenso más escarpado con flechas. Para esto y las siguientes figuras, los puntos negros representan los mínimos locales. Todas las rutas de descenso más empinadas, comenzando en un punto x(0), va al punto negro en la cuenca que contiene x(0).

Las cuencas unidimensionales

La figura siguiente muestra cómo las rutas de descenso más empinadas pueden ser más complicadas en más dimensiones.

Una cuenca de atracción, mostrando caminos de descenso más escarpan desde varios puntos de partida

En la siguiente figura se muestran caminos y cuencas de atracción aún más complicados.

Varias cuencas de atracción

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

  • y ≥ |x|

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

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

 Código para generar la figura

Las trayectorias de descenso más empinadas son líneas rectas hasta los límites de restricción. A partir de los límites de restricción, las rutas de descenso más empinadas viajan a lo largo de los límites. El punto final es (0, 0) o (11/4, 11/4), dependiendo de si el valor inicial es superior o inferior a 2.x