Método de Newton

Método de Newton

Si es definida positiva (o definida negativa) para todo , el algoritmo converge rápidamente. Esta convergencia está garantizada independiente del valor de sólo si es estrictamente convexa (cóncava).

En la realidad, sin embargo, la convergencia es a menudo alcanzada para la mayoría de las funciones si se escoge un punto de partida aceptable.

Una desventaja de este método es que éste requiere cálculos de la segunda derivada parcial de en cada iteración. Si es cuadrática, la matriz Hessiana no es función de , y por lo tanto es una matriz constante para todas las iteraciones. Computacionalmente, es muy deseable no calcular en cada iteración. Por esta razón, funciones no lineales son a menudo aproximadas por formas cuadráticas para el propósito de determinar puntos estacionarios.

Minimizar

=

Algoritmo de Newton

Dada una aproximación inicial , una tolerancia y un número máximo de iteraciones , para

, hacer

Paso 1. Definir

Paso 2. Resolver para el sistema de ecuaciones lineales:

Paso 3. Calcular

Paso 4. Si entonces es una aproximación al punto crítico. Si no, hacer y volver al paso 2.

Ejemplo

Maximizar

Resolviendo el sistema de ecuaciones

Comenzar con la aproximación inicial:

k 0 1 2 3

0 0.75 0.975 0.999695

0 0 0 0

Comenzar con la aproximación inicial:

k 0 1 2 3 4 5

15 8.538 5.3457 3.8229 3.185527 3.014517

10 0 0 0 0 0

Ejercicios

1) Maximizar

Métodos del Gradiente

Método del ascenso más pronunciado o método de la pendiente más inclinada

La terminación del método del gradiente ocurre en un punto donde el vector gradiente se anula. Esta es sólo una condición necesaria para la optimización. El óptimo no se puede verificar a menos que se sepa a priori que la función f(x) es cóncava o convexa.

Suponga que se maximiza f(x). Sea x0 el punto inicial desde el cual comienza el procedimiento y determine , el gradiente de en el punto .

La idea del método es determinar una trayectoria particular a lo largo de la cual es máxima en un punto dado. Este resultado se logra si se seleccionan puntos sucesivos y tales que , donde es un parámetro llamado tamaño de paso óptimo.

El parámetro se determina de modo que resulte en la mejora más grande de . En otras palabras, si una función se define de manera que entonces es el valor de que maximiza . Notar que es una función en una sola variable, con .

El procedimiento termina cuando dos puntos sucesivos y son aproximadamente iguales. Esto equivale a tener y dado que se satisface la condición necesaria en .

Si el problema es de minimización entonces

y

Algoritmo

Paso 1. Hacer , elegir la tolerancia y una aproximación inicial

Paso 2. Obtener

Paso 3. Obtener en función de

Paso 4. Resolver el problema

Paso 5. Hacer

Paso 6. Evaluar en

Paso 7. Si , el proceso se detiene.

En caso contrario, hacer e ir al

...