Metodo del gradiente

Erik Alex Papa Quiroz

Dr. Universidad Federal de Rio de Janeiro

Modelos y Metodos de Optimizacion con Aplicaciones

Facultad de Ciencias Naturales y Matematica
Callao-Peru

15/02/2013
 Resumen
1 Introduccion
2 Metodo del gradiente
3 Propiedades del metodo del gradiente
4 Implementacion del metodo del gradiente
5 Referencias
 1. Introduccion
En esta seccion, presentamos el metodo del gradiente para
optimizacion irrestricta, veremos sus propiedades de
convergencia debil y fuerte, convergencia global de convergencia
asi como sus tasa de convergencia.
 2. Metodo del gradiente

Considere el problema:

min{f (x) : x Rn }

donde f : Rn R es una funcion continuamente diferenciable.

.
Algoritmo del Maximo Descenso
Dado x0 Rn ,
Para k = 0, 1, ...,
Si f (xk ) = 0, entonces parar.
Caso contrario, hacer

xk+1 = xk k f (xk ),

donde k es escogido por una de las siguientes reglas:

a) Busqueda Lineal Exacta:

k arg min{() = f (xk f (xk )) : 0}

b) Regla de Armijo
Dados los escalares s, , con 0 < < 1 y 0 < < 1, definir

k = s mk ,

donde mk es el menor entero no negativo tal que

f (xk ) f (xk + s m dk ) m sf (xk )T dk ,

donde dk = f (xk ).
Ejemplo 1: Busqueda exacta
Considere el problema

min{x12 + x22 : (x1 , x2 ) R2 }

En este caso f (x1 , x2 ) = x12 + x22 y el gradiente es

f (x1 , x2 ) = (2x1 , 2x2 ).

Realizaremos pasos del metodo de maximo descenso con

busqueda lineal exacta.
Tomemos el punto inicial x0 = (1, 1) entonces

||f (x0 )|| = ||f (1, 1)|| = 2 2 >> 0.

As, x0 no satisface las condiciones del algoritmo.

Luego el escalar 0 es obtenido como:

0 = arg min{() = f (x0 f (x0 )) : 0}.

De los datos tenemos que

x0 f (x0 ) = (1 2, 1 2)

y as
() = (1 2)2 + (1 2)2 .
 1
El mnimo de esta funcion obviamente es 0 = 2 y as el siguiente
punto de la iteracion es
1
x1 = x0 0 f (x0 ) = (1, 1) (2, 2) = (0, 0).
2
Para realizar la siguiente iteracion realizamos el test de parada
obteniendo
||f (x1 )|| = 0
con lo que finaliza el metodo y obtiene el punto de mnimo
x1 = (0, 0).
Ejemplo 2: Busqueda exacta
Ahora considere el problema
1
min{x12 + x22 : (x1 , x2 ) R2 }
2
En este caso f (x1 , x2 ) = x12 + 21 x22 y el gradiente es

f (x1 , x2 ) = (2x1 , x2 ).
Tomemos el punto inicial x0 = (2, 1) entonces f (x0 ) = (4, 1) y as

||f (x0 )|| = ||f (2, 1)|| = 17 >> 0.
Como
x0 f (x0 ) = (2 4, 1 ),
entonces 0 debe minimizar la funcion
1
() = (2 4)2 + (1 )2 .
2
17
Resolviendo el problema tenemos que 0 = 33 y as el nuevo
punto es
 
1 0 0 17 2 16
x = x 0 f (x ) = (2, 1) (4, 1) = , .
33 33 33
Pasamos a la segunda iteracion.
f (x1 ) = ( 4 16
33 , 33 ) y la nueva funcion () es

4 2 2 1 16 16 2
() = ( ) + ( )
33 2 33 33
Luego el valor de 1 debe minimizar la funcion anterior....as
sucesivamente
Ejemplo 1:Armijo
Considere el problema
1
min{x12 + x22 : (x1 , x2 ) R2 }
2
En este caso f (x1 , x2 ) = x12 + 21 x22 y el gradiente es

f (x1 , x2 ) = (2x1 , x2 ).

Consideramos:
1
= , s = 1, = 1/2
2
Tomemos el punto inicial x0 = (2, 1) entonces f (x0 ) = (4, 1) y as

||f (x0 )|| = ||f (2, 1)|| = 17 >> 0.

Para obtener el punto x1 debemos encontrar el valor de 0 tal que

se cumpla la siguiente desigualdad

f (x0 f (x0 )) f (x0 ) (/2)||f (x0 )||2

La desigualdad anterior se convierte en:

1 9 17
(2 4)2 + (1 )2 .
2 2 2
Si damos = 1 entonces tenemos

4 4,

lo que no es verdad.
 1
Si = 2 entonces
1 1
,
8 4
lo que es verdad, entonces 0 = 12 .
El nuevo punto es:
1 1
x1 = (2, 1) (4, 1) = (0, )
2 2
Pasamos a la segunda iteracion.
f (x1 ) = (0, 12 ). La desigualdad a ser verificada es

f (x1 f (x1 )) f (x1 ) (/2)||f (x1 )||2 .

Reemplazando los valores se tiene

1 1 1
(1 )2 ( ).
8 8 2 4
Si tomamos = 1 y verificando en la desigualdad tenemos que
0 0, as el nuevo punto es
1 1
x2 = (0, ) 1(0, ) = (0, 0.)
2 2
Pasamos a la siguiente iteracion.
Como ||f (x2 )|| = 0, entonces el algoritmo finaliza con el punto

x2 = (0, 0).
 3. Propiedades del metodo del gradiente

Propiedad
Usando las busquedas a) y b) tenemos:
La sucesion {f (xk )} es no cresciente, esto es,

f (xk+1 ) f (xk ), k = 0, 1, ...

Observacion
Usando cualquiera de las reglas a) o b), k siempre sera un
numero positivo. En efecto, si en la busqueda unidimensional
obtenemos k = 0, entonces por la condicion de optimalidad se
tiene que
0 (0) = f (xk )T f (xk ) 0,
lo que implica que f (xk ) = 0, lo que contradice el hecho que
f (xk ) 6= 0 segun el algoritmo. Ahora si usamos la busqueda
aproximada es obvio que el parametro k es positivo.
Observacion
El algoritmo es llamado de maximo descenso, por la razon que
entre todas las direcciones dk que satisfacen la condicion

f (xk )dk < 0,

el gradiente negativo f (xk ) es la direccion que da el mayor

decrescimo.
En efecto, para todo dk tal que ||dk || = 1 se tiene que

f (xk )
 
k T
f (x ) = ||f (xk )||.1 = ||f (xk )||||dk || |f (xk )T dk |,
||f (xk )||

donde la ultima desigualdad es por Cauchy-Schwartz. De aqu

obtenemos que

f (xk )
 
k T
f (x ) f (xk )T dk ,
||f (xk )||

dk Rn tal que ||dk || = 1.

Teorema
Sea f : Rn R es una funcion limitada inferiormente y de clase
C1 en Rn . Si {xk } es la sucesion generada por el algoritmo usando
la regla a) o b) entonces

lim f (xk ) = 0.
k+

Ademas, todo punto de acumulacion de {xk } es un punto

estacionario.
 4. Implementacion del metodo de gradiente

Algoritmo de Maximo Descenso

Dado x0 Rn ,
Para k = 0, 1, ...,
Si f (xk ) = 0, entonces parar.
Caso contrario, hacer

xk+1 = xk k f (xk ),

donde k es escogido por la regla de Armijo

Regla de Armijo
Dados los escalares s, , con 0 < < 1 y 0 < < 1, definir

k = s mk ,

donde mk es el menor entero no negativo tal que

f (xk ) f (xk + s m dk ) m sf (xk )T dk .

Consideraciones practicas
I En la practica usualmente se toma el valor de muy
pequeno, i.e,
[105 , 101 ]

I El valor de es elegido usualmente

1 1
< .
2 10
Ejemplo MG1
Considere el problema
1
min{x12 + x22 : (x1 , x2 ) R2 }
2
Consideraremos
x0 = (2, 1)

1
= , s = 1, = 0.1
2
Ejemplo MG2
Considere el problema

min{3x12 + x24 : (x1 , x2 ) R2 }

Consideraremos
x0 = (1, 2)

= 0.5, s = 1, = 0.1
Ejemplo MG4
Considere el problema

min{x12 + x22 + x32 + x42 + x52 : (x1 , x2 ) R2 }

Consideraremos
x0 = (1, 2, 3, 4, 5)

= 0.1, s = 1, = 0.1
Ejemplo MG5
Considere el problema

min{(x1 2)2 + (x1 2x2 )2 : (x1 , x2 ) R2 }

Consideraremos
x0 = (0, 3)
Realizar 7 iteraciones del metodo con

= 0.5, s = 1, = 0.1

x = (2, 1)
Ejemplo MG6
Considere el problema

min{100(x2 x12 )2 + (1 x1 )2 : (x1 , x2 ) R2 }

Consideraremos
x0 = (1.2, 1)
Realizar iteraciones del metodo con

= 0.5, s = 1, = 0.1

x = (1, 1), f = 0
Convergencia lineal
Considere el problema
1
min{ xT Ax bT x : (x1 , x2 ) R2 }
2
donde A es simetrica y definida positiva.
 2
cond(A) 1
f (xk+1 ) f (x ) f (xk ) f (x ) .


cond(A) + 1
Observacion practica
I Note que incluso para valores moderados de cond(A), la cota
superior es cercano a 1.
I Cuando cond(A) es menor que 50 el metodo de maximo
descenso tiene gran chance de tornarse practico.
 5. Referencias

IZMAILOV A. and SOLODOV M., Otimizacao Volume 2, IMPA, Rio de Janeiro,

Brazil, 2007.
CAUCHY, Methode Generale pour la Resolution des Systemes dEquations
Simultanies, Comptes Rendus de Academie des Sciences, Paris, Vol 25, pp.
536-538, 1847.
KIWIEL and MURTY, Convergence of the steepest descent method for
minimization quasiconvex functions, JOTA Journal of Optimization Theory and
Applications, 89 (1) 1996, 221-226.