Scribd
Cargar
13 vistas3 páginas

Método del Gradiente en Optimización

Este documento describe el método del gradiente para resolver sistemas de ecuaciones lineales. Primero, convierte el problema en uno de optimización minimizando una función cuadrática. Luego, itera mejorando una solución inicial mediante pasos en la dirección opuesta al gradiente de la función, donde el tamaño del paso se elige para minimizar la función a lo largo de esa dirección. Finalmente, presenta el algoritmo completo iterando la dirección y tamaño de paso hasta converger a una solución.

Cargado por

Carlos Gonzales
Derechos de autor
© All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PDF, TXT o lee en línea desde Scribd
13 vistas3 páginas

Método del Gradiente en Optimización

Este documento describe el método del gradiente para resolver sistemas de ecuaciones lineales. Primero, convierte el problema en uno de optimización minimizando una función cuadrática. Luego, itera mejorando una solución inicial mediante pasos en la dirección opuesta al gradiente de la función, donde el tamaño del paso se elige para minimizar la función a lo largo de esa dirección. Finalmente, presenta el algoritmo completo iterando la dirección y tamaño de paso hasta converger a una solución.

Cargado por

Carlos Gonzales
Derechos de autor
© All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PDF, TXT o lee en línea desde Scribd

Método del gradiente

para resolver sistemas de ecuaciones lineales

Objetivos. Deducir las fórmulas del “método de gradiente”. Más precisamente, es el


método del descenso en el sentido del antigradiente.

1. De un sistema de ecuaciones lineales a un problema de optimización. Sea


A ∈ Mn (R) una matriz real simétrica, y sea b ∈ Rn . Definimos f : Rn → R mediante la
fórmula
1
f (x) = x> Ax − x> b.
2
−1
Denotemos por u al vector A b. Entonces para cada x ∈ Rn
1
f (x) = f (u) + (x − u)> A(x − u).
2
En particular, si A es estrictamente positiva definida, entonces f (x) > f (u) para cada
x ∈ Rn \ {0}.

Demostración.
1 1
f (x) − f (u) = x> Ax − u> Au − (x − u)> b
2 2
Usamos la igualdad b = Ax:
1 1
= x> Ax − u> Au − (x − u)> Au
2 2
1 1 1
= (x − u) Ax + u> Ax − u> Au − (x − u)> Au
>
2 2 2
1 1 >
= (x − u) Ax + u A(x − u) − (x − u)> Au
>
2 2
Aplicamos la simetrı́a de A:
1 1
= (x − u)> Ax − (x − u)> Au
2 2
1
= (x − u)> A(x − u).
2
2. Gradiente de la función f . Ya sabemos calcular el gradiente de las formas lineales
y cuadráticas. En nuestro caso,

(grad f )(x) = Ax − b.

Método del gradiente para sistemas lineales, página 1 de 3


3. Derivada direccional de la función f . Sean x y p dos vectores fijos. Definimos
g : R → R mediante la regla
g(α) = f (x + αp).
Entonces
g 0 (α) = αp> Ap − p> (b − Ax). (1)

Demostración. Método I. Usar la fórmula para la derivada direccional:

g 0 (α) = p> (grad f )(x + αp).

Método II. Primero calcular la función g:


1
g(α) = (x + αp)> A(x + αp) − (x + αp)> b
2
1 2 >  1
= α p Ap + α pAx> − p> b + x> Ax − x> b.
2 2
Luego sacar la derivada de g:

g 0 (α) = αp> Ap − p> (b − Ax).

4. Ideas del método del gradiente.

Construir una sucesión de puntos x(0) , x(1) , x(2) , . . ., en cada paso intentando dismi-
nuir el valor de f (x).
x(s+1) := x(s) + αs p(s) ,
donde el vector p(s) y el número αs > 0 se eligen de cierta manera.

Poner p(s) igual al antigradiente de la función f en el punto x(s) .

Eligir αs minimizando la función f sobre la recta x(s) + αp(s) .

5. Elegir la dirección.

p(s) := −(grad f )(x(s) ) = b − Ax(s) .

La expresión b − Ax(s) es el residuo r(s) del problema Ax = b en el punto x(s) .

6. Elegir el paso. Definimos la función g : R → R,

g(α) := f (x(s) + αr(s) ).

Ya hemos deducido una fórmula (1) para la derivada de g. La función g alcanza su mı́nimo
en el punto
(r(s) )> r(s)
αs = (s) > (s) .
(r ) Ar

Método del gradiente para sistemas lineales, página 2 de 3


7. El cambio del residuo en un paso.

r(s+1) − r(s) = Ax(s) − Ax(s+1) = −αs Ar(s) .

8. Algoritmo del antigradiente.

Entrada: A, b, ε, smax.

Salida: x, s.

s ← 0;

x ← 0;

r ← b;

Mientras (krk ≥ ε) ∧ (s < smax):

p ← Ar;
r> r
α← ;
r> Ar
x ← x + αr;

r ← r − αAr;

s ← s + 1;

Regresar x y s.

Método del gradiente para sistemas lineales, página 3 de 3

También podría gustarte