Metodo De Optimizacion Sin Restricciones

MÉTODO DE OPTIMIZACIÓN SIN RESTRICCIONES

1- MÉTODO DE GRADIENTE.

Sea J: H → R un funcional diferenciable Gateaux. Entonces

El método de gradiente está basado en la siguiente observación: si tomamos

v = −Grad J (u) y 0 < λ << 1, se obtiene

Que debe ser negativo si λ es suficientemente pequeño. Por tanto, si λ es suficientemente pequeño,

y la sucesión es monótona decreciente.

Metodos de Descenso :

• Descenso con paso fijo:

• Descenso con paso optimal:

Teorema : Si J es diferenciable con continuidad, acotada por debajo y coerciva, entonces el método de gradiente con paso optimal converge.

Observación: La elección del paso optimal requiere un proceso de minimización en una variable que puede no ser sencillo. Sin embargo, existen otros métodos para encontrar pasos de descenso eficaces.

Ejemplo: Algoritmo.

2- MÉTODO DE NEWTON.

El método de Newton se aplica en la aproximación de raíces de una ecuación o sistema de ecuaciones. En nuestro caso vamos a aplicarlo para calcular el punto crítico.

Al igual que el método de gradiente se trata de un método iterativo en el que el nuevo candidato se obtiene a partir del anterior mediante la fórmula.

donde vn es solución del sistema

El método de Newton converge muy rápidamente pero tiene el inconveniente de que requiere el cálculo de la segunda derivada del funcional. Es posible evitar esta dificultad trabajando con una aproximación de la derivada segunda J´´(un), lo que da lugar a los métodos conocidos como cuasi-Newton.

Ejemplo: Algoritmo.

3- MÉTODO DE DIRECCIONES CONJUGADAS.

Este método fue propuesto originalmente en 1964 [Powell, 1964] y se le considera el método de búsqueda directa más exitoso, particularmente cuando se hace uso de las modificaciones sugeridas por Zangwill (1967) y Brent (1973).

Este algoritmo usa efectivamente la historia de las iteraciones para construir direcciones para la aceleración y al mismo tiempo evita degenerar en una secuencia de búsquedas coordinadas. Además, el método se basa en el uso de una función cuadrática, por lo cual cuenta con una base teórica sólida.

Hay 2 razones principales para elegir un modelo cuadrático:

 Es el tipo más simple de función no lineal a minimizarse (las funciones lineales no pueden manejar óptimos interiores), y por tanto, cualquier técnica general debe trabajar bien en una cuadrática si ésta tendrá éxito con una función general.

 Cerca del óptimo, todas las funciones no lineales pueden aproximarse mediante una cuadrática (esto se debe a que, en ese caso, la parte lineal de la expansión de Taylor debe desvanecerse). Por tanto, el comportamiento del algoritmo en la cuadrática dará alguna indicación sobre cómo convergerá el algoritmo en el caso de funciones generales.

La motivación principal de este algoritmo se deriva de la observación de que si una función cuadrática de N variables se puede transformar de tal forma que sea simplemente la suma de cuadrados perfectos, entonces puede obtenerse el óptimo después de efectuar exactamente N búsquedas sobre una variable, cada una de ellas con respecto a cada una de las variables transformadas.

El proceso de transformar una función cuadrática de la forma:

En una suma de cuadrados perfectos es equivalente a encontrar una matriz de transformación T tal que el término cuadrático es reducido a una forma diagonal.

Por tanto, dada la forma cuadrática:

La transformación deseada:

Producirá:

Donde D es una matriz diagonal, esto es, sus elementos son distintos de cero sólo si i = j.

Hagamos que tj sea la j-ésima columna de T. Entonces la transformación de la ecuación expresa el hecho de que estamos reescribiendo cada vector x como una combinación lineal de los vectores columna tj :

En otras palabras, en vez de escribir x en términos del sistema de coordenadas estándar representado por el conjunto de vectores e(i) estamos expresándolo en términos de un nuevo sistema de coordenadas dado por el conjunto de vectores tj .

Adicionalmente, puesto que diagonaliza la cuadrática, este conjunto de vectores tj corresponde a los ejes principales de la forma cuadrática.

Gráficamente, esto corresponde a tomar una función cuadrática general con términos cruzados (ver figura del acetato siguiente) y realinear los nuevos ejes coordenados de manera que coincidan con los ejes mayores y menores de la cuadrática como se muestra en la figura incluida 2 acetatos adelante.

Gráficas:

Para resumir, tomando la cuadrática a través de la transformación, realmente estamos escogiendo un nuevo sistema coordenado para la cuadrática que coincida con los ejes principales de la cuadrática. Consecuentemente, las búsquedas unidimensionales realizadas en el espacio de las variables transformadas (z) corresponden simplemente a búsquedas unidireccionales a lo largo de cada uno de los ejes principales de la cuadrática.

Puesto que los ejes principales son los mismos que en el vector tj, las búsquedas unidimensionales realmente se efectúan a lo largo de cada uno de estos vectores.

4- MÉTODO DE GRADIENTE CONJUGADO

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.

Supongamos que queremos resolver el siguiente sistema de ecuaciones lineales

Ax = b

Donde la n-por-n matriz A es simétrica (i.e., AT = A), definida positiva (i.e., xTAx > 0 para todos los vectores no cero x en Rn), y real. Denotamos la única solución de este sistema por x*.

 Método Exacto

Decimos que dos vectores no cero u y v son conjugados (con respecto a A) si

...