Métodos de optimizacion sin restricciones

 Metodo del gradiente

El gradiente es un vector en un punto x que proporciona la dirección (local) de máxima variación de la función. El vector gradiente es un vector ortogonal al contorno de la función en el punto. Por lo tanto, en la búsqueda de un mínimo la dirección de movimiento será contragradiente:

s^k =−∇f (x)

En el método de máximo descenso la transición de un punto x^k a otro x^k+1 viene dada por la siguiente expresión:

x^k+1 =x^k +∆x^k =x^k +λ^k s^k =x^k −λ^k ∇f (x^k )

dónde: ∆x^k = Vector desde x^k hasta x^k+1

s^k = Dirección de búsqueda de máximo descenso   

_λ^k = Escalar que determina la longitud de paso en la dirección s^k

El gradiente negativo da la dirección de movimiento, pero no la longitud de dicho movimiento. Por lo tanto, existen varios procedimientos posibles dependiendo de la elección de _λ^k. Entre los diversos métodos que existen para la selección de la longitud de paso, dos merecen una mención especial. El primero de ellos emplea una búsqueda unidireccional en la dirección del gradiente. El segundo, específica a priori la longitud del paso para cada iteración. Claramente la principal dificultad con la segunda aproximación es que a menudo no se sabe a priori la longitud de paso adecuada. ¿Cómo se debería cambiar esta longitud de paso y como debería reducirse a medida que nos aproximamos al mínimo para conseguir la convergencia? una ilustración nos indicará el problema: Supongamos una función cuadrática de dos variables como la de la figura siguiente:

Oscilación del método de máximo descenso

Si en cada paso se realiza una optimización total en la dirección contraria al gradiente los pasos sucesivos del método de máximo descenso son ortogonales uno con respecto al anterior. Este resultado, que parece peculiar, ocurre para una determinada f(x) debido a que la derivada de f(x) a lo largo de la línea s(λ) viene dado, utilizando la regla de la cadena por:

En el paso final de la búsqueda queremos que df/dx_i=0 y por lo tanto s^T ∇f(x^(k+1) )=0. En la práctica, por lo tanto, no es deseable llevar a cabo suboptimizaciones con demasiada precisión. Mientras que el método del gradiente puede producir progresos muy satisfactorios en la reducción de f(x) en las primeras iteraciones tiende a hacerse muy lento en las últimas, alargando excesivamente los cálculos.

El algoritmo práctico lo podemos resumir en los siguientes pasos:

1.      Elegir un valor inicial x⁰. En pasos sucesivos será x^k.

2.      Calcular, analítica o numéricamente las derivadas parciales

(∂f(X))/(∂x_j )      j=1,2,3…,n

3.      Calcular el vector de búsqueda

s=-∇f(X^k)

4.      Usar la relación x^k+1 = x^k +λ^k s^k para obtener el siguiente punto. El valor de λ^k puede ser de valor fijo o calculado en cada paso mediante una búsqueda unidireccional.

5.      Comparar f (x^k+1) con f (x^k ). Si el cambio es menor que una tolerancia preespecificada terminar, en caso contrario volver al paso dos y continuar con las iteraciones.

Un método estricto de descenso máximo puede terminar en cualquier punto estacionario, es decir, puede llegar a un mínimo local o a un punto de silla. Para asegurarnos que tipo de resultado hemos obtenido debemos asegurarnos que la matriz Hessiana es definida positiva. Por otra parte, la dificultad básica del método de gradiente es que es muy sensible al escalado de f(x) por lo que la convergencia puede ser muy lenta y producirse un número enorme de oscilaciones. Desde este punto de vista el método del gradiente no es muy efectivo.

Método del gradiente conjugado

El método del gradiente conjugado debido a Fletcher y Reeves (1964) combina las características de la convergencia cuadrática del método de las direcciones conjugadas con las del método del gradiente. El método supone una importante mejora del método del gradiente con sólo un pequeño incremento en el esfuerzo de cálculo. El método del gradiente conjugado, esencialmente, combina la información obtenida del vector gradiente con la información acerca del vector gradiente de iteraciones previas. Lo que hace el método es calcular la nueva dirección de búsqueda utilizando una combinación lineal del gradiente en la etapa considerada y el de la etapa anterior. La principal ventaja del método es que necesita almacenar muy poca cantidad de información con lo que puede ser programado fácilmente incluso en calculadoras.

Los pasos de cálculo se comentan a continuación:

1.      En x⁰ (punto inicial) calcular f(x⁰) y calcular s⁰ =−∇f (x⁰)

2.      Almacenar ∇f (x⁰) y calcular x¹= x⁰ + λ⁰ s⁰ minimizando λ mediante una búsqueda unidireccional en la dirección s⁰.

3.      Calcular f(x¹) ∇f(x¹) la nueva dirección de búsqueda es una combinación lineal de s⁰ y ∇f(x¹):

para la etapa k-ésima la relación es:

Para una función cuadrática se puede demostrar que dos direcciones de búsqueda son conjugadas. Después de n iteraciones conviene comenzar otra vez desde el principio tomando el último punto k=n como nuevo punto de partida.

4.      Realizar el test de convergencia, (la función objetivo ha disminuido), y terminar el algoritmo cuando ‖sk‖ sea menor que alguna tolerancia preestablecida.

Algunas de las dificultades que aparecen en el método de Powell también aparecen en el método del gradiente conjugado. Se puede producir una dependencia lineal de las direcciones de búsqueda. Esto se puede eliminar reiniciando el proceso cada cuatro o cinco etapas completas.

Método de Newton

El método de Newton hace uso de la aproximación de segundo orden de la función utilizando las derivadas segundas con respecto a cada una de las variables independientes. De esta forma es posible tener en cuenta la curvatura de la función en el punto e identificar las mejores direcciones de búsqueda.

El mínimo de f(x) se obtiene diferenciando la aproximación cuadrática de f(x) con respecto a cada una de las variables e igualando a cero. Así:

∇f (x) =∇f (x^k )+H(x^k ) ∆x^k

O bien

x^k+1 − x^k = ∆x^k = −[H(x^k)]⁻¹ ∇f (x^k)

Si f(x) es una función cuadrática el mínimo se alcanza en un único paso. Pero para una función general no lineal el óptimo no se alcanza en un único paso, por lo que se puede modificar la ecuación anterior para introducir el parámetro de longitud de paso, con lo que queda:

x^k+1 − x^k = ∆x^k = −[H(x^k)]⁻¹ ∇f (x^k)

Obsérvese que la dirección s viene ahora dada por:

s _{= −}[H(x^k )]⁻¹ ∇f (x^k )

La longitud de paso se puede calcular vía cualquier método de optimización numérica de los ya comentados o bien analíticamente con lo que se obtendría:

En el método de Newton estrictamente hablando el valor de λ es la unidad. El problema también se puede resolver sin necesidad de invertir la matriz hessiana resolviendo directamente el sistema de ecuaciones lineales en ∆x, aplicando la factorización adecuada y evitando los errores de redondeo, en la medida de lo posible, que puedan aparecer como consecuencia del proceso de inversión de matrices.

H(x^k )∆x^k =−∇f (x^k )

El método de Newton es el método de minimización más rápido, cuando funciona bien.

Direcciones conjugadas

Las direcciones conjugadas son una generalización de las direcciones ortogonales y pueden ser construidas de diversas formas usando gradientes como vectores de base.

Sea A una matriz de nxn. Un conjunto de n vectores S se dice que es conjugado si se cumple la siguiente ecuación.

La definición anterior puede ser vista como una generalización de las direcciones ortogonales. La convergencia cuádratica en la minimzación de funciones cuádraticas es una propiedad demostrada de las direcciones conjugadas y todos los métodos que las usen tendrán convergencia cuádratica para ese tipo de funciones. Una función cuádratica puede ser usada para aproximar una función más general siempre y cuando se este cerca de un punto óptimo, esta propiedad ha sido aprovechada por el método del gradiente conjugado. El método del gradiente conjugado es una modificación del método del descenso empinado, en la que el gradiente ha sido reemplazado por direcciones conjugadas y estas direcciones son calculadas utilizando gradientes como vectores base.

Método de Quasi-Newton

Estos métodos son similares a los métodos de gradiente conjugado en el sentido de que se basan principalmente en propiedades de las funciones cuadráticas. Sin embargo, en el método del gradiente conjugado, la principal fortaleza de la búsqueda se deriva del uso de las direcciones conjugadas de búsqueda, mientras que los métodos de Quasi-Newton están diseñados para imitar más directamente las características positivas del método de Newton pero usando sólo información de primer orden.

Todos los métodos de este grupo generan las direcciones a usarse para generar el siguiente punto con:

Donde A^k es una matriz de NxN a la que se le denomina métrica.

Método de metrica variable

A los métodos que emplean direcciones de esta forma, se les suele llamar métodos de métrica variable, porque A cambia a cada iteración. Para ser precisos, un método de métrica variable es un método Quasi-Newton si está diseñado de tal forma que satisfaga la siguiente propiedad cuadrática:

Desafortunadamente, la literatura no es precisa ni consistente en el uso de estos términos, por lo que algunos autores sugieren usar los de manera intercambiable. Esto es apropiado, puesto que ambas expresiones son de igual importancia en el diseño y ejecución de estos métodos.

Supongamos una recursión para estimar la inversa de la matriz Hessiana:

Dondees una corrección a la métrica actual.

La idea es formar  tal que la secuencia A⁽⁰⁾, A⁽¹⁾, A⁽²⁾, . . . ,A^(k+1) aproxime H^-1=∇²f(x^*)^-1, porque al lograr esto, una búsqueda lineal adicional producirá x^* si f(x) es cuadrática.

Obviamente, se espera que el éxito de este mecanismo en funciones cuadráticas nos haría tener éxito con funciones no lineales generales.

Método de Davidon-Fletcher-Powell

Este también es un método Quasi-Newton, para minimizar una función f en Rⁿ. Consiste en generar aproximaciones sucesivas de la inversa de la matriz Hessiana de la función f.

El algoritmo consiste en los siguientes pasos:

1.      Elegir un punto inicial X⁰ y tolerancias ϵ₁,ϵ₂  y ϵ₃

2.   Encontrar ∇f(X⁰) y hacer: s⁰=-∇f(X⁰)

3.      Encontrar λ⁰ tal que: f(X⁰)+λ⁰ s⁰ se minimice con una tolerancia ϵ₁.

Hacer X¹=X⁰+λ⁰ s⁰  y k=1

Calcular ∇f(X¹)

4.   Hacer: s^k= -A^k ∇f(x^k)

5.      Encontrar λ^k tal que:

f(X^k )+λ^k s^k sea mínima con una tolerancia

Hacer X^(k+1)=X^k+λ^k s^k

6.   

Si es así, terminar.

Sino k = k + 1. Ir al paso 4.

El método de Davidon-Fletcher-Powell ha sido y sigue siendo una técnica de gradiente ampliamente utilizada. El método tiende a ser robusto; esto es, típicamente tiende a tener un buen comportamiento en una amplia variedad de problemas prácticas.

La mayor desventaja de este tipo de métodos es su necesidad de almacenar la matriz A de N×N.