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.

Algoritmos de optimización no lineales no restringidos

Definición de optimización no restringida

La minimización no restringida es el problema de encontrar un vector x que es un mínimo local a una función escalar f(x):

minxf(x)

El término restricciones significa que no se coloca ninguna restricción en el rango de x.

algoritmo de fminunc trust-region

Métodos de la confianza-región para la minimización no lineal

Muchos de los métodos utilizados en Optimization Toolbox™ Solvers se basan en regiones de confianza, un concepto simple pero poderoso en la optimización.

Para entender el enfoque de la región de confianza para la optimización, considere el problema de minimización no restringida, minimice f(x), donde la función toma argumentos vectoriales y devuelve escalares. Suponga que está en un punto x en n-Space y desea mejorar, es decir, pasar a un punto con un valor de función inferior. La idea básica es aproximar f con una función más simple q, que refleja razonablemente el comportamiento de la función f en un barrio N alrededor del punto x. Este vecindario es la región de confianza. Un paso de ensayo s se computa reduciendo al mínimo (o aproximadamente reduciendo al mínimo) el excedente N. Este es el subproblema de la región de confianza,

mins{q(s), sN}.(1)

El punto actual se actualiza para ser x + s si f(x + s) < f(x); de lo contrario, el punto actual permanece inalterado y N, la región de confianza, se encoge y se repite el cálculo del paso de prueba.

Las preguntas clave en la definición de un enfoque específico de la región de confianza para minimizar la f(x) son cómo elegir y calcular la aproximación q (definida en el punto actual x), cómo elegir y modificar la región de confianza N, y Cómo resolver con precisión el subproblema confianza-región. Esta sección se centra en el problema no restringido. Las secciones posteriores discuten complicaciones adicionales debido a la presencia de restricciones en las variables.

En el método estándar de la región de confianza ([48]), la aproximación cuadrática q se define por los dos primeros términos de la aproximación de Taylor a F en x; la vecindad N es generalmente esférica o elipsoide en forma. Matemáticamente el subproblema de la confianza-región se indica típicamente

min{12sTHs+sTg  such that  DsΔ},(2)

donde g es el gradiente de f en el punto actual x, H es la matriz del hessian (la matriz simétrica de los segundos derivados), D es una matriz de escalamiento diagonal, Δ es un escalar positivo, y ∥. ∥ es el 2-Norm. Existen buenos algoritmos para resolver Ecuación 2 (ver [48]); Estos algoritmos típicamente implican el cómputo de un eigensystem completo y un proceso de Newton aplicado a la ecuación secular

1Δ1s=0.

Tales algoritmos proporcionan una solución exacta a Ecuación 2. Sin embargo, requieren tiempo proporcional a varios factorizaciones de H. Por lo tanto, para problemas a gran escala es necesario un enfoque diferente. Se han propuesto varias estrategias de aproximación y heurística, basadas en Ecuación 2, en la bibliografía ([42] y [50]). El enfoque de aproximación seguido en Optimization Toolbox Solvers es restringir el subproblema de la región de confianza a un S subespacial de dos dimensiones ([39] y [42]). Una vez que el subespacio S se ha calculado, el trabajo para solucionar Ecuación 2 es trivial incluso si se necesita la información completa del valor propio/vector (puesto que en el subespacio, el problema es solamente de dos dimensiones). El trabajo dominante se ha trasladado ahora a la determinación del subespacio.

El subespacio S de dos dimensiones se determina con la ayuda de un proceso de gradiente conjugado precondicionado descrito a continuación. El solucionador define S como el espacio lineal atravesado por s1 y s2, donde s1 está en la dirección del gradiente g, y s2 es una aproximación Newton Dirección, es decir, una solución para

Hs2=g,(3)

o una dirección de curvatura negativa,

s2THs2<0.(4)

La filosofía detrás de esta opción de S es forzar la convergencia global (vía la dirección más escarpada de la pendiente o la dirección negativa de la curvatura) y alcanzar la convergencia local rápida (vía el paso del neutonio, cuando existe).

Un bosquejo de la minimización no restringida usando ideas de la confianza-región es ahora fácil de dar:

  1. Formule el subproblema bidimensional de la confianza-región.

  2. Resuelve Ecuación 2 para determinar el paso de prueba s.

  3. Si f(x + s) < f(x)Entonces x = x + s.

  4. Ajuste Δ.

Estos cuatro pasos se repiten hasta la convergencia. La dimensión de la confianza-región Δ se ajusta según reglas estándares. En particular, se reduce si no se acepta el paso de prueba, es decir, f(x + s) ≥ f(x). Vea [46] y [49] para una discusión de este aspecto.

los solucionadores de Optimization Toolbox tratan algunos casos especiales importantes de f con funciones especializadas: menos cuadrados no lineales, funciones cuadráticas, y mínimos-cuadrados lineares. Sin embargo, las ideas algorítmicas subyacentes son las mismas que para el caso general. Estos casos especiales se discuten en secciones más últimas.

Método de gradiente de conjugado precondicionado

Una manera popular de resolver los sistemas definidos positivos simétricos grandes de ecuaciones lineares Hp = –g es el método de gradientes de conjugado precondicionado (PCG). Este enfoque iterativo requiere la capacidad de calcular los productos vectoriales matriciales de la forma H·v donde v es un vector arbitrario. La matriz definida positiva simétrica M es un precondicionador para H. Es decir M = C2Donde C–1HC–1 es una matriz bien acondicionada o una matriz con valores propios agrupados.

En un contexto de minimización, puede asumir que la matriz de hessian H es simétrica. Sin embargo, H se garantiza para ser positivo definido solamente en el vecindario de un minimizador fuerte. El algoritmo PCG sale cuando se encuentra una dirección de curvatura negativa (o cero), es decir, dTHd ≤ 0. La dirección de la salida de PCG, p, es una dirección de la curvatura negativa o un aproximado (tol controla cómo aproximado) solución al sistema del neutonio Hp = –g. En cualquiera de los casos, p se utiliza para ayudar a definir el subespacio bidimensional utilizado en el enfoque de la región de confianza discutido en Métodos de la confianza-región para la minimización no lineal.

algoritmo de fminunc quasi-newton

Fundamentos de la optimización no restringida

Aunque existe un amplio espectro de métodos para la optimización sin restricciones, los métodos se pueden categorizar ampliamente en términos de la información derivada que es o no se utiliza. Los métodos de búsqueda que sólo utilizan evaluaciones de funciones (por ejemplo, la búsqueda simplex de Nelder y Mead [30]) son más adecuados para problemas que no son lisos o tienen un número de discontinuidades. Los métodos de gradiente son generalmente más eficientes cuando la función a minimizar es continua en su primera derivada. Los métodos de orden superior, como el método de Newton, sólo son realmente adecuados cuando la información de segundo orden es fácilmente calculada, porque el cálculo de la información de segundo orden, utilizando la diferenciación numérica, es computacionalmente costoso.

Los métodos de degradado utilizan la información sobre la pendiente de la función para dictar una dirección de búsqueda donde se cree que el mínimo miente. El más simple de estos es el método de descenso más empinado en el que una búsqueda se realiza en una dirección, –∇f(x)Donde f(x) es el gradiente de la función objetiva. Este método es muy ineficiente cuando la función a minimizar tiene valles estrechos largos como, por ejemplo, es el caso para Función de Rosenbrock

f(x)=100(x2x12)2+(1x1)2.(5)

El mínimo de esta función está en x = [1,1]Donde f(x) = 0. Un mapa de contorno de esta función se muestra en la figura de abajo, junto con la ruta de la solución al mínimo para una implantación de descenso más pronunciada comenzando en el punto [-1.9, 2]. La optimización se terminó después de 1000 iteraciones, aún una distancia considerable del mínimo. Las áreas negras son donde el método está continuamente en zigzag de un lado del valle a otro. Tenga en cuenta que hacia el centro de la gráfica, una serie de pasos más grandes se toman cuando un punto aterriza exactamente en el centro del valle.

Figura 6-1, Método de descenso más empinado en la función de Rosenbrock

Esta función, también conocida como función del plátano, es notoria en ejemplos no restringidos debido a la forma en que la curvatura se dobla alrededor del origen. La función de Rosenbrock se utiliza en esta sección para ilustrar el uso de una variedad de técnicas de optimización. Los contornos se han trazado en incrementos exponenciales debido a la inclinación de la pendiente que rodea el valle en forma de U.

Para obtener una descripción más completa de esta cifra, incluidos los scripts que generan los puntos iterativos, consulte Minimización de la función bananera.

Métodos quasi-Newton

De los métodos que utilizan la información de gradiente, los más favorecidos son los métodos cuasi-Newton. Estos métodos acumulan información de curvatura en cada iteración para formular un problema de modelo cuadrático de la forma

minx12xTHx+cTx+b,(6)

donde la matriz del hessian, H, es una matriz simétrica definida positiva, c es un vector constante, y b es una constante. La solución óptima para este problema ocurre cuando los derivados parciales de x van a cero, es decir,

f(x*)=Hx*+c=0.(7)

El punto de solución óptimo, x*, se puede escribir como

x*=H1c.(8)

Los métodos de Newton-Type (en contraposición a los métodos cuasi-Newton) calculan H directamente y proceden en una dirección de descenso para localizar el mínimo después de un número de iteraciones. Calcular H numéricamente implica una gran cantidad de cómputo. Los métodos de cuasi-neutonio evitan esto usando el comportamiento observado de f(x) y f(x) para generar información de curvatura para hacer una aproximación a H utilizando una técnica de actualización adecuada.

Se ha desarrollado un gran número de métodos de actualización de la arpillera. Sin embargo, se cree que la fórmula de Broyden [3], Fletcher [12], [20]y Shanno (BFGS) es la más efectiva para su uso en un método de propósito general. [37]

La fórmula dada por BFGS es

Hk+1=Hk+qkqkTqkTskHkskskTHkTskTHksk,(9)

Donde

sk=xk+1xk,qk=f(xk+1)f(xk).

Como punto de partida, H0 se puede establecer en cualquier matriz simétrica positiva definida, por ejemplo, la matriz de identidad I. Para evitar la inversión de la Hde Hesse, se puede derivar un método de actualización que evita la inversión directa de H mediante una fórmula que hace una aproximación del hessian inverso H–1 en cada actualización. Un procedimiento bien conocido es la fórmula de DFP de davidon [7], Fletcher, y Powell [14]. Esto utiliza la misma fórmula que el método BFGS (Ecuación 9) excepto que Qk se sustituye por sk.

La información de gradiente se suministra a través de gradientes calculados analíticamente, o derivadas de derivados parciales utilizando un método de diferenciación numérica mediante diferencias finitas. Esto implica perturbar cada una de las variables de diseño, x, a su vez y calcular la tasa de cambio en la función objetiva.

En cada iteración principal, k, se realiza una búsqueda de línea en la dirección

d=Hk1f(xk).(10)

El método quasi-Newton es ilustrado por la ruta de la solución en Función de Rosenbrock en Figura 6-2, Método BFGS en la función de Rosenbrock. El método puede seguir la forma del valle y converge al mínimo después de 140 evaluaciones de la función usando solamente gradientes finitos de la diferencia.

Figura 6-2, Método BFGS en la función de Rosenbrock

Para obtener una descripción más completa de esta cifra, incluidos los scripts que generan los puntos iterativos, consulte Minimización de la función bananera.

Búsqueda de línea

Búsqueda de línea es un método de búsqueda que se utiliza como parte de un algoritmo de optimización más grande. En cada paso del algoritmo principal, el método de búsqueda de línea busca a lo largo de la línea que contiene el punto actual, xk, paralelamente al Dirección de búsqueda, que es un vector determinado por el algoritmo principal. Esto es, el método encuentra la siguiente iteración xk+1 de la forma

xk+1=xk+α*dk,(11)

Donde xk denota la iteración actual, Dk es la dirección de búsqueda, y α* es un parámetro de longitud de paso escalar.

El método de búsqueda de línea intenta disminuir la función objetiva a lo largo de la línea xk + α*dk minimizando repetidamente los modelos de interpolación polinomiales de la función objetiva. El procedimiento de búsqueda de líneas tiene dos pasos principales:

  • La fase Bracketing determina el rango de puntos en la línea xk+1=xk+α*dk para ser buscado. El Soporte corresponde a un intervalo que especifica el rango de valores de α.

  • El paso Seccionamiento divide el bracket en subintervalos, en los cuales el mínimo de la función objetiva es aproximado por Interpolación polinómica.

La longitud de paso que resulta α satisface las condiciones de Wolfe:

f(xk+αdk)f(xk)+c1αfkTdk,(12)
f(xk+αdk)Tdkc2fkTdk,(13)

donde c1 y c2 son constantes con 0 < c1 < c2 < 1.

La primera condición (Ecuación 12) requiere que Αk disminuye suficientemente la función objetiva. La segunda condición (Ecuación 13) asegura que la longitud del paso no sea demasiado pequeña. Los puntos que satisfacen ambas condiciones (Ecuación 12 y Ecuación 13) se llaman puntos aceptables.

El método de búsqueda de línea es una implementación del algoritmo descrito en la sección 2-6 de [13]. Consulte también [31] para obtener más información sobre la búsqueda de línea.

Actualización del hessian

Muchas de las funciones de optimización determinan la dirección de búsqueda actualizando la matriz de hessian en cada iteración, utilizando el método BFGS (Ecuación 9). La función fminunc también proporciona una opción para utilizar el método de DFP proporcionado en Métodos quasi-Newton (establecer HessUpdate en 'dfp' en options para seleccionar el método de DFP). El hessian, H, se mantiene siempre para ser positivo definido de modo que la dirección de la búsqueda, d, esté siempre en una dirección de la pendiente. Esto significa que para algún paso arbitrariamente pequeño α en la dirección d, la función objetiva disminuye de magnitud. Usted logra la determinación positiva de H asegurándose de que H se inicialice para ser definido positivo y después de eso qkTsk (de Ecuación 14) es siempre positivo. El término qkTsk es un producto del parámetro de longitud de paso de búsqueda de línea Αk y una combinación de la dirección de la búsqueda d con las evaluaciones pasadas y actuales del gradiente,

qkTsk=αk(f(xk+1)Tdf(xk)Td).(14)

Siempre consigues la condición de que qkTsk es positivo realizando una búsqueda de línea suficientemente precisa. Esto se debe a que la dirección de búsqueda, d, es una dirección de descenso, por lo que Αk y el gradiente negativo –∇f(xk)Td son siempre positivas. Así, el posible término negativo –∇f(xk+1)Td puede ser hecho tan pequeño en magnitud como sea necesario aumentando la exactitud de la búsqueda de la línea.