MA3711 Optimización Matemática

Método de Newton
Héctor Ramı́rez C.

En esta sección estudiaremos en detalle el métodos de Newton para resolver el problema irres-
tricto
mı́nn f (x), (P)
x∈R

donde f : Rn→ R es al menos dos veces continuamente diferenciable. Como ya hemos dicho,
eventualmente Rn puede ser reemplazado por un abierto no vacı́o Θ de Rn . Los métodos que
veremos en esta sección se pueden adecuar fácilmente.
Suponiendo que ∇2 f (xk ) es una matriz definida positiva, entonces la dirección de Newton-
Kantorovich viene dada por:
−1
dN 2
k := −[∇ f (xk )] ∇f (xk ), (1)
mientras para definir la dirección de cuasi-Newton, suele “aproximar” este Hessiano por una matrix
simétrica definida positiva Mk , obteniendo la dirección:

dCN
k := −[Mk ]−1 ∇f (xk ). (2)

En lo que sigue explicaremos la motivación de estas elecciones y los resultados teóricos de

convergencia que la sustentan.

1. Motivación
Para resolver el problema (P) podemos reemplazar f por su aproximación cuadrática en la
iteración xk :
1
qk (x) := f (xk ) + ∇f (xk )> (x − xk ) + (x − xk )> ∇2 f (xk )(x − xk ).
2
Notemos que si ∇2 f (xk ) es una matriz definida positiva, entonces qk es estrictamente convexa, y
por lo tanto tiene un sólo mı́nimo global. Ası́, si en cada iteración k minimizamos qk y esta solución
la tomamos como nuestra próxima iteración, obtenemos la iteración de Newton:

xk+1 = xk − [∇2 f (xk )]−1 ∇f (xk ) = xk + dN

k . (3)

Observación 1. Lo anterior puede también interpretarse como la iteración de Newton asociada a

resolver el sistema de ecuaciones F (x) = 0 con F (x) = ∇f (x).

1
 2. Convergencia local
Con lo anterior, el método de descenso asociado a la dirección dN
k , llamado método de Newton-
Kantorovich, tiene la siguiente forma:

Paso 0 Sea ε > 0 una tolerancia dada. Elegimos x0 iteración inicial e inicializamos el contador de
iteraciones k = 0.

Paso 1 Si k∇f (xk )k < ε parar1 . El punto xk es un punto crı́tico aproximado. Si no, pasar al Paso 2.

Paso 2 Actualizar la iteración xk+1 = xk + dN

k , el contador de k + 1 → k y volver al Paso 1.

Un método Cuasi-Newton corresponde simplemente a reemplazar dN CN en el Paso 2,

k por dk
para cierta elección (por determinar) de la matriz Mk .
A continuación presentamos el resultado de convergencia (local) asociado a estos métodos.

Teorema 2. Sea x̄ mı́nimo local de (P) tal que f es dos veces continuamente diferenciable en una
vecindad de x̄, y ∇2 f (x̄) es una matriz definida positiva. Luego, si x0 y Mk están suficientemente
cerca de x̄ y ∇2 f (x̄), respectivamente, entonces el método de Cuasi-Newton (o Newton cuando
Mk = ∇2 f (xk )) converge, en el sentido que siempre para con un punto crı́tico aproximado. Más
aún, la velocidad de convergencia es lineal:

xk+1 − x̄ = O(kxk − x̄k) (Lineal)

Más aún, en caso que Mk → ∇2 f (xk ), la velocidad de convergencia es superlineal:

xk+1 − x̄ = o(kxk − x̄k) (Superlineal)

Finalmente, si el Hessiano de f es localmente Lipschitz en x̄ (i.e., f es clase C 2,1 en una vecindad

de x̄) y Mk − ∇2 f (xk ) = O(kxk − x̄k), entonces la velocidad de convergencia es cuadrática:

xk+1 − x̄ = O(kxk − x̄k2 ) (Cuadrática)

Cómo en el resultado anterior la convergencia es válida sólo para x0 cercanos a la solución x̄,
diremos que la convergencia es local. Esto es claramente una desventaja ya que muchas veces no
tenemos una aproximación de la solución. Sin embargo, a pesar de su simple implementación, los
métodos de Newton o Cuasi-Newton pueden llegar a ser muy rápidas (convergencia cuadrática)
bajo hipótesis muy débiles.

Corolario 3. Para el método de Newton, bajo todas las hipótesis del Teorema 2, se tiene además

∇f (xk ) = O(kxk − x̄k2 )

Demostración. Propuesto.

Ejemplo 4. Minimizar la función f (x) = x + e−3x usando el método de Newton.

1
Muchas veces se consideran también otros criterios de parada como que kxk+1 − xk k < ε.

2
3. Métodos de Cuasi-Newton
Las dos actualizaciones más conocidas para los métodos de Cuasi-Newton son las siguientes:

3.1. Davidson-Fletcher-Powell

Mk+1 = (I − γk qk p> > >

k )Mk (I − γk pk qk ) + γk qk qk . (DFP)
donde pk := xk+1 − xk , gk := ∇f (xk+1 ) − ∇f (xk ) y γk := 1/qk> pk .
Esto entrega la siguiente fórmula de actualización para la inversa Hk := Mk−1 :

Hk qk qk> Hk
Hk+1 = Hk − + γk pk p>
k. (DFP’)
qk> Hk qk

3.2. Broyden-Fletcher-Goldfarb-Shanno

Mk pk p>
k Mk
Mk+1 = Mk − >
+ γk qk qk> . (BFGS)
p k Mk p k

Esto entrega la siguiente fórmula de actualización para la inversa Hk := Mk−1 :

Hk+1 := (I − γk pk qk> )Hk (I − γk qk p> >

k ) + γk pk pk . (BFGS’)

En un método de Cuasi-Newton, basta usar la fórmula de actualización de la inversa.

La motivación para estas elecciones, ası́ como sus resultados de convergencia, se estudian en el
curso Optimización No Lineal. Pueden también consultar el libro:
Nocedal, J., Wright, S. Numerical Optimization. Springer, NY, USA, 1999.

3
 4. Globalización del Método de Newton
En esta sección veremos como modificar el método de Newton de manera que su convergencia
sea global. Para esto, modificaremos la iteración, incluyendo un paso αk > 0, quedando de la forma:

xk+1 = xk + αk dN
k

Esto vuelve entonces a la forma usual de un método descenso. Más aún, notemos que un punto
crı́tico de f se obtiene resolviendo el problema auxiliar
1
mı́nn φ(x) := k∇f (x)k2 . (Pφ )
x∈R 2
y que la dirección de Newton-Kantorovich es una dirección de descenso para φ en cualquier xk tal
que ∇f (xk ) 6= 0. En efecto:

∇φ(x)> dN > 2 2 −1 2
k = −∇f (xk ) ∇ f (xk )[∇ f (xk )] ∇f (xk ) = −k∇f (xk )k < 0.

Por lo que vamos a considerar un método de descenso tomando como dirección dN k a condición
que esta dirección exista, es decir, que ∇2 f (xk ) sea invertible, a pesar de que esta puede no ser
dirección de descenso para f en xk .

Paso 0 Sea ε > 0 una tolerancia dada y β ∈ (0, 21 ]. Elegimos x0 iteración inicial e inicializamos el
contador de iteraciones k = 0.

Paso 1 Si k∇f (xk )k < ε o si ∇2 f (xk ) es singular, entonces parar. Si se paro por el primer criterio,
entonces el punto xk es un punto crı́tico aproximado. Si no, pasar al Paso 2.

Paso 2 Calcular paso αk > 0 usando una búsqueda lineal de Armijo, es decir, tomar αk = β j , para
cierto j, tal que se satisface

f (xk + αk dk ) ≤ f (xk ) + wαk ∇f (xk )> dk , (4)

donde w ∈ (0, 21 ) está fijo.

Paso 3 Actualizar la iteración xk+1 = xk + αk dN

k , el contador de k + 1 → k y volver al Paso 1.

Lamentablemente el anterior método puede parar con una iteración mal definida o incluso no de-
crecer la función valor en una iteración dada. Sin embargo, aún podemos demostrar la convergencia
global del método propuesto. Para eso, probemos primero el siguiente lema:

Lema 5 (Aceptación asintótica del paso unitario). Sea x̄ mı́nimo local de (P) tal que ∇2 f (x̄) es
definida positiva. Si x0 está suficientemente cerca de x̄, entonces xk converge superlinealmente a x̄
y
f (xk + dk ) ≤ f (xk ) + w∇f (xk )> dk , (5)
para k suficientemente grande.

4
 Estamos ahora en condiciones de probar la convergencia (global) del método propuesto.

Teorema 6. Sea f dos veces continuamente diferenciable y {xk } sucesión generada por el método
de Newton globalizado, la cual suponemos está bien definida. Tenemos lo siguiente:

i) Sea x̄ tal que ∇f (x̄) = 0 y ∇2 f (x̄) es definida positiva. Si x0 está suficientemente cerca de
x̄, entonces xk converge superlinealmente a x̄ y αk = 1 para todo k. Más aún, si f es de
clase C 2,1 en una vecindad de x̄ (y x0 está en dicha vecindad), entonces la convergencia es
cuadrática.

ii) Sea x̄ punto de acumulación de {xk } tal que ∇2 f (x̄) es definida positiva. Entonces la conclu-
sión i) es también cierta salvo que αk = 1 sólo para k suficientemente grande.

iii) Sea f una función fuertemente convexa y x̄ su único mı́nimo local. Entonces, xk converge
superlinealmente a x̄ y αk = 1 para todo k suficientemente grande.

Recordemos que la definición de fuertemente convexa y sus principales propiedades:

Definición 7. Diremos que f : Rn → R es fuertemente convexa si su dominio es convexo y si

existe c > 0 tal que para todo x1 , x2 ∈ domf , λ ∈ [0, 1] se tiene que
c
f (λx1 + (1 − λ)x2 ) ≤ λf (x1 ) + (1 − λ)f (x2 ) − λ(1 − λ)kx1 − x2 k2
2
Proposición 8. Sea f : Rn → R tal que su dominio es convexo. Las siguientes aseveraciones son
equivalentes:

1. f es fuertemente convexa, con constante c > 0.

2. f (·) − 2c k · k2 es convexa.

3. Si f es diferenciable, entonces ∇f es fuertemente monotono, con constante c > 0, es decir:

(∇f (x1 ) − ∇f (x2 ))> (x1 − x2 ) ≥ ckx1 − x2 k2 , ∀x1 , x2 ∈ domf.

4. Si f es diferenciable, entonces
c
f (x1 ) − f (x2 ) ≥ ∇f (x2 )> (x1 − x2 ) + kx1 − x2 k2
2

5. Si f es dos veces continuamente diferenciable, entonces ∇2 f (x) − 2c I es semidefinida positiva

para todo x ∈ domf .

Demostración. Propuesto.

5
 Una forma de suplir las deficiencias del método anterior es utilizando una dirección de cuasi-
Newton, dCN k = −Mk−1 ∇f (xk ) en lugar de la dirección de Newton. En efecto, eligiendo Mk de
manera que se “suficientemente”definida positiva, se asegura que dCNk sea dirección de descenso y
que esté siempre bien definida, por lo que el método de (Cuasi-)Newton globalizado estarı́a bien
definido y converge globalmente, y muy rápido localmente, bajo suposiciones razonables sobre Mk .
Algunas posibilidades son Mk sea dado por iteración DFP, BFGS o algo de la forma Mk =
∇2 f (x
k ) + Dk con Dk matriz diagonal suficientemente definida positiva.

Los resultados de convergencia asociados a estas elecciones se estudian en el curso Optimización

No Lineal. Pueden también consultar el libro:
Nocedal, J., Wright, S. Numerical Optimization. Springer, NY, USA, 1999.