Unidad 4: Métodos de optimización sin restricciones

 Método del Gradiente 

En matemática, el método del gradiente conjugado es un algoritmo para resolver numéricamente los sistemas de ecuaciones lineales cuyas matrices son simétricas y definidas positivas. Es un método iterativo, así que se puede aplicar a los sistemas dispersos que son demasiado grandes para ser tratados por métodos directos como la descomposición de Cholesky. Tales sistemas surgen frecuentemente cuando se resuelve numéricamente las ecuaciones en derivadas parciales.

El método del gradiente conjugado se puede utilizar también para resolver los problemas de optimización sin restricciones como la minimización de la energía.

El método del gradiente biconjugado proporciona una generalización para matrices no simétricas. Varios métodos del gradiente conjugado no lineales buscan los mínimos de las ecuaciones no lineales.

  Método del Newton

En análisis numérico, el método de Newton (conocido también como el método de Newton-Raphson o el método de Newton-Fourier) es un algoritmo para encontrar aproximaciones de los ceros o raíces de una función real. También puede ser usado para encontrar el máximo o mínimo de una función, encontrando los ceros de su primera derivada.

El método de Newton es un método abierto, en el sentido de que no está garantizada su convergencia global. La única manera de alcanzar la convergencia es seleccionar un valor inicial lo suficientemente cercano a la raíz buscada. Así, se ha de comenzar la iteración con un valor razonablemente cercano al cero (denominado punto de arranque o valor supuesto). La relativa cercanía del punto inicial a la raíz depende mucho de la naturaleza de la propia función; si ésta presenta múltiples puntos de inflexión o pendientes grandes en el entorno de la raíz, entonces las probabilidades de que el algoritmo diverja aumentan, lo cual exige seleccionar un valor supuesto cercano a la raíz. Una vez que se ha hecho esto, el método linealiza la función por la recta tangente en ese valor supuesto. La abscisa en el origen de dicha recta será, según el método, una mejor aproximación de la raíz que el valor anterior. Se realizarán sucesivas iteraciones hasta que el método haya convergido lo suficiente.

Direcciones Conjugadas

Las direcciones conjugadas son una generalización de las direcciones ortogona- les y pueden ser construidas de diversas formas usando gradientes como vectores de base. Sea A una matrix de nxn.

Para lograr velocidad lineal, la convergencia del método del gradiente es lenta, aún en el caso de funciones cuadráticas. Sin embargo en búsqueda de un método de convergencia más rápida, se toma como opción utilizar la noción de direcciones conjugadas u ortogonales.

Dos direcciones si y sj se dice que son conjugadas una con respecto al otro si: (s i ) T Q (s j ) = 0.

En general un conjunto de n direcciones de búsqueda linealmente independientes s0 , s1 , s2,...sn-1 se dice que son conjugadas con respecto a una matriz definida positiva Q si(s i ) T Q (s j ) ≤ i ≠ j ≤ − n-1

En optimización la matriz Q es el Hessiano de la función objetivo. Para una función cuadrática de n variables, para la cual H es una matriz constante, el método garantiza que se puede alcanzar el óptimo en n etapas, si en cada etapa se optimiza en la correspondiente dirección conjugada. Las direcciones conjugadas no son únicas, se debe especificar una dirección inicial para que el resto queden determinadas.

Metodo de Davidon-Fletcher-Powell

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.

Desde la publicación de la fórmula de Davidon, se han propuesto varios métodos más que resultan de usar diferentes valores de β, y, z en la ecuación.

Una de las dificultades prácticas comunes de estos métodos es la tendencia de A(k+1) a estar mal condicionada, lo que causa una mayor dependencia a un procedimiento de reinicializacion.

Metodo Cuasi-Newton

Los métodos cuasi-Newton son métodos que se utilizan para encontrar ceros o máximos y mínimos locales de funciones, como una alternativa al método de Newton. Se pueden usar si el jacobiano o el hessiano no están disponibles o son demasiado costosos de calcular en cada iteración. El método de Newton "completo" requiere el jacobiano para buscar ceros, o el hessiano para encontrar extremos.