El método de Newton (P)

Minimizar f ( x)
x a„n

En el método de Newton la dirección de búsqueda se define como:

[

]

−1

d ( x ) = − 2 f ( x ) f T ( x )
La dirección de búsqueda se encuentra minimizando el problema:

~
Minimizar f ( x + d)
~

donde f es la aproximación cuadrática de f en x .
Teorema: el método de Newton definido por la iteración xk +1 = xk + d( xk )
tiene convergencia local con orden de convergencia p ≥ 2 .
1


El método de Newton
(P)

Minimizar f ( x)
x a„

n

6

4

f ( x ) = x T Qx
1 1 
Q=
1 10 



x0 = (10, 1)T

2

0

-2

-4

-6
-4

-2

0

2

4

Rojo: Steepest descent
Azul: Newton

6

8

10

12

2


El método de Newton
(P)

Minimizar f ( x)
x a„n

Correcciones:
1) Introducir búsqueda lineal
a) La dirección puede no ser de descenso.
b) El orden de convergencia puede ser menor de 2.
2) Modificar la matriz del sistema lineal.

3


El método de las direcciones
conjugadas
(P)

Minimizar f ( x) =

1 T
x Qx − b T x
2

Con Q positivadefinida

x a„n
En el método de las direcciones conjugadas se conocen n direcciones d i ≠ 0
que satisfacen:
dT Qd j = 0, i ≠ j
i
En el método de las direcciones conjugadas se considera d k como dirección de
búsqueda del paso k . La iteración queda definida como:

xk +1 = xk + α k d k

αk = −

f ( xk )d k
dT Qd k
k
4


El método de las direcciones
conjugadas
(P)

Minimizar f ( x) =

1 T
x Qx − b T x
2

x a„n
Teorema: El método de las direcciones conjugadas converge a la solución.
Teorema (Expanding subspace theorem):
Sea Bk = [d 0 ,, d k −1 ], la sucesión generada por el algoritmo tiene la propiedad
que xk minimiza f en el espacio x0 + Bk .

5


El método del gradiente
conjugado
(P)

Minimizar f ( x) =

1 T
x Qx − b T x
2

x a„n
T
Sea g k = f ( xk ) .

Comenzando por x0 , el método define d0 = −g 0 y, en la iteración k :

xk +1 = xk + α k d k
gT d k
αk = − Tk
d k Qd k
d k +1 = −g k +1 + β k d k
gT +1Qd k
β k = kT
d k Qd k
6


El método del gradiente
conjugado
(P)

Minimizar f ( x) =

1 T
x Qx − b T x2

x a„n
Teorema: El método del gradiente conjugado es un método de direcciones
conjugadas. Si el método no termina en xk (g k ≠ 0) , en el paso k se cumple:

a) [g 0 , g1 , …, g k ] = [g 0 , Qg 0 , …, Q k g 0 ]
b) [d 0 , d1 , …, d k ] = [g 0 , Qg 0 ,…, Q k g 0 ]
c) dT Qd i = 0, i < k
k
d ) α k = gT g k / dT Qd k
k
k
e) β k = gT +1g k +1 / gT g k
k
k
7


MGC – extensión a problemas
no cuadráticos.
(P)

Minimizar f ( x)
x a„n

Caso cuadrático

xk +1 = xk + α k d k

αk = −

T
k

g dk
dT Qd k
k

d k +1 = −g k +1 + β k d k

βk =

T
k +1
T
k

g Qd k
d Qd k

Caso no cuadrático
Fletcher-Reeves

Polak-Riviere

xk +1 = xk + α k d k

xk +1 = xk + α k d k

α k = arg min

α k = arg min

d k +1 = −g k +1 + β k d k

d k +1 = −g k +1 + β k d k

gT +1g k +1
βk = k T
gk gk

(g k +1 − g k )T g k +1
βk =
gT g k
k

α

α

Convergencia global del MGC: no se puede garantizar a menos que se reinicie
el procedimiento cada m pasos (Steepest descent + Spacer step theorem).
8