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 sin restricciones

La minimización sin restricciones es el problema de encontrar un vector que sea un mínimo local a una función escalar ():xfx

minxf(x)

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

Algoritmofminunctrust-region

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

Muchos de los métodos utilizados en los solucionadores se basan en un concepto simple pero potente en la optimización.Optimization Toolbox™trust regions,

Para comprender el enfoque de optimización de la región de confianza, considere el problema de minimización sin restricciones, minimice (), donde la función toma argumentos vectoriales y devuelve escalares.fx Supongamos que está en un punto en el espacio y desea mejorar, es decir, pasar a un punto con un valor de función inferior.xn La idea básica es aproximarse con una función más simple, que refleja razonablemente el comportamiento de la función en un vecindario alrededor del punto.fqfNx Este vecindario es la región de confianza. Un paso de prueba se calcula minimizando (o aproximadamente minimizando) más.sN Este es el subproblema de la región de confianza,

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

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

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

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

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

donde está el gradiente de en el punto actual, es la matriz de hessian (la matriz simétrica de segundo derivados), es una matriz de escalado diagonal, Δ es un escalar positivo, y ∥. ∥ es la norma 2.gfxHD Existen buenos algoritmos para resolver (ver); Estos algoritmos suelen implicar el cálculo de todos los valores propios y un proceso de Newton aplicado a laEcuación 2[48]H ecuación secular

1Δ1s=0.

Estos algoritmos proporcionan una solución precisa.Ecuación 2 Sin embargo, requieren tiempo proporcional a varias factorizaciones de.H Por lo tanto, para problemas a gran escala es necesario un enfoque diferente. Varias estrategias de aproximación y heurística, basadas en, se han propuesto en la literatura (y).Ecuación 2[42][50] El enfoque de aproximación seguido en los solucionadores es restringir el subproblema de la región de confianza a un subespacio bidimensional (y).Optimization ToolboxS[39][42] Una vez que se ha calculado el subespacio, el trabajo a resolver es trivial incluso si se necesita información completa de eigenvalue/Eigenvector (ya que en el subespacio, el problema es sólo bidimensional).SEcuación 2 La obra dominante se ha desplazado ahora a la determinación del subespacio.

El subespacio bidimensional se determina con la ayuda de unS proceso de gradiente conjugada precondicionado descrito a continuación. El solucionador define como el espacio lineal extendido porSs1 Ys2Dóndes1 está en la dirección del degradado ygs2 es un aproximado 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 elección es forzar la convergencia global (a través de la dirección de descenso más pronunciada o dirección de curvatura negativa) y lograr una rápida convergencia local (a través del paso de Newton, cuando existe).S

Un boceto de minimización sin restricciones utilizando ideas de la región de confianza es ahora fácil de dar:

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

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

  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 región de confianza Δ se ajusta según las reglas estándar. En particular, se disminuye si no se acepta el paso de prueba, es decir, f(x + s) ≥ f(x). Ver y para una discusión de este aspecto.[46][49]

solucionadores tratan algunos casos especiales importantes de funciones especializadas: mínimos cuadrados no lineales, funciones cuadráticas y mínimos cuadrados lineales.Optimization Toolboxf Sin embargo, las ideas algorítmicas subyacentes son las mismas que para el caso general. Estos casos especiales se discuten en secciones posteriores.

Método de gradiente conjugada precondicionado

Una forma popular de resolver los grandes sistemas de ecuaciones lineales definidas de manera simétrica y positiva Hp = –g es el método de los degradados de conjugación preacondicionados (PCG). Este enfoque iterativo requiere la capacidad de calcular los productos de vector de matriz de la forma, donde es un vector arbitrario.H·vv La matriz definida simétrica positiva es unaM preacondicionador Para.H Es decir M = C2Dónde C–1HC–1 es una matriz bien acondicionadas o una matriz con valores eigenados agrupados.

En un contexto de minimización, puede suponer que la matriz de Hessian es simétrica.H Sin embargo, está garantizado para ser positivo definitivo sólo en el vecindario de un fuerte minimizador.H El algoritmo PCG sale cuando se encuentra una dirección de curvatura negativa (o cero), es decir, dTHd ≤ 0. La dirección de salida PCG,, o bien una dirección de curvatura negativa o una solución aproximada (controla la aproximación) al sistema Newtonptol Hp = –g. En ambos casos se utiliza para ayudar a definir el subespacio bidimensional utilizado en el enfoque de la región de confianza discutido en.pMétodos de la región de confianza para la minimización no lineal

Algoritmofminuncquasi-newton

Fundamentos de la optimización sin restricciones

Aunque existe un amplio espectro de métodos para la optimización sin restricciones, los métodos se pueden clasificar ampliamente en términos de la información derivada que es o no se utiliza. Los métodos de búsqueda que solo utilizan evaluaciones de funciones (p. ej., la búsqueda simplex de Nelder y Mead) son los más adecuados para problemas que no son suaves o tienen un número de discontinuidades.[30] 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 se calcula fácil y fácilmente, porque el cálculo de la información de segundo orden, utilizando la diferenciación numérica, es computacionalmente costoso.

Los métodos de gradiente utilizan 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 empen en el que una búsqueda se realiza en una dirección, –∇f(x)Dónde f(x) es el degradado de la función objetiva. Este método es muy ineficiente cuando la función que se va a minimizar tiene valles estrechos largos como, por ejemplo, es el caso de La función de Rosenbrock

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

El mínimo de esta función se encuentra en x = [1,1]Dónde f(x) = 0. En la figura siguiente se muestra un mapa de contorno de esta función, junto con la ruta de la solución al mínimo para una implementación de descenso más pronunciada que comienza en el punto [-1.9, 2]. La optimización se finalizó después de 1000 iteraciones, todavía una distancia considerable desde el mínimo. Las áreas negras son donde el método está continuamente zigzagueando de un lado del valle a otro. Tenga en cuenta que hacia el centro de la trama, un número 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 inclinado en la función de Rosenbrock

Esta función, también conocida como la función banana, es notoria en ejemplos sin restricciones 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 figura, incluidos los scripts que generan los puntos iterativos, consulte.Función de banana minimización

Métodos quasi-Newton

De los métodos que utilizan la información de degradado, los más favorecidos son los métodos quasi-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 Hessiana, es una matriz simétrica definida positivamente, es un vector constante, y es una constante.Hcb La solución óptima para este problema se produce cuando los derivados parciales de ir a cero, es decir,x

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

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

x*=H1c.(8)

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

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

La fórmula dada por BFGS es

Hk+1=Hk+qkqkTqkTskHkskskTHkTskTHksk,(9)

Dónde

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

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

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

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

d=Hk1f(xk).(10)

El método quasi-Newton se ilustra mediante la ruta de la solución en La función de Rosenbrock en.Figura 6-2, Método BFGS en la función de Rosenbrock El método es capaz de seguir la forma del valle y converge al mínimo después de 140 evaluaciones de función utilizando sólo gradientes de diferencia finita.

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

Para obtener una descripción más completa de esta figura, incluidos los scripts que generan los puntos iterativos, consulte.Función de banana minimización

Búsqueda de línea

es un método de búsqueda que se utiliza como parte de un algoritmo de optimización mayor.Line search En cada paso del algoritmo principal, el método de búsqueda de líneas busca a lo largo de la línea que contiene el punto actual, Xk, paralela a la, que es un vector determinado por el algoritmo principal.search direction Es decir, el método busca la siguiente iteraciónxk+1 del formulario

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

Dónde 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íneas intenta reducir la función objetiva a lo largo de la línea xk + α*dk minimizando repetidamente los modelos de Interpolación polinómica de la función objetiva. El procedimiento de búsqueda en línea tiene dos pasos principales:

  • La fase determina el rango de puntos en la líneabracketing xk+1=xk+α*dk que se buscará. El corresponde a un intervalo que especifica el rango de valores de.bracketα

  • El paso divide el soporte en subintervalos, en los que el mínimo de la función objetiva se aproxima por Interpolación polinómica.sectioning

La longitud de paso resultante α satisface las condiciones de Wolfe:

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

Dóndec1 Yc2 son constantes con 0 <c1 <c2 < 1.

La primera condición () requiere queEcuación 12 Αk disminuye suficientemente la función objetiva. La segunda condición () garantiza que la longitud del paso no sea demasiado pequeña.Ecuación 13 Se llaman los puntos que satisfacen ambas condiciones (y).Ecuación 12Ecuación 13acceptable points

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

La actualización de hessian

Muchas de las funciones de optimización determinan la dirección de la búsqueda actualizando la matriz de hessian en cada iteración, utilizando el método BFGS ().Ecuación 9 La función también proporciona una opción para utilizar el método DFP dado en (establecido en para seleccionar el método DFP).fminuncMétodos quasi-NewtonHessUpdate'dfp'options El hessian,,, siempre se mantiene para ser positivo definitivo para que la dirección de la búsqueda,, siempre está en una dirección de descenso.Hd Esto significa que para algún paso arbitrariamente pequeño en la dirección, la función objetiva disminuye en magnitud.αd Se logra una definición positiva de asegurando que se inicializa para ser positivo definitivo y a partir de entoncesHH qkTsk (de) siempre es positivo.Ecuación 14 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 búsqueda con evaluaciones de gradiente pasadas y presentes,d

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

Siempre logras la condición de que qkTsk es positivo mediante la realización de una búsqueda de línea lo suficientemente precisa. Esto se debe a que la dirección de búsqueda, es una dirección de descenso, de modo qued Αk y el degradado negativo –∇f(xk)Td siempre son positivas. Por lo tanto, el posible término negativo –∇f(xk+1)Td se puede hacer tan pequeña en magnitud como sea necesario incrementando la precisión de la búsqueda de línea.

Consulte también

Temas relacionados