orden del tema
TRANSCRIPT
![Page 1: Orden del Tema](https://reader035.vdocumento.com/reader035/viewer/2022070815/62c6246fcfa52d4850049ff8/html5/thumbnails/1.jpg)
Gradiente Conjugado Lineal
Orden del Tema
1 Gradiente Conjugado LinealDirecciones ConjugadasSolución mediante Direcciones ConjugadasAlgoritmo Direcciones Conjugadas IterativoGradiente Conjugado-Versión PreliminarForma práctica de GC
2 / 62
![Page 2: Orden del Tema](https://reader035.vdocumento.com/reader035/viewer/2022070815/62c6246fcfa52d4850049ff8/html5/thumbnails/2.jpg)
Gradiente Conjugado Lineal
Direcciones ConjugadasSolución mediante Direcciones ConjugadasAlgoritmo Direcciones Conjugadas IterativoGradiente Conjugado-Versión PreliminarForma práctica de GC
Problema de optimización
Se quiere resolver, mediante un algoritmo iterativo, el problemade optimización sin restricciones
minx∈Rnf(x) =1
2xTQx− bTx (1)
donde Q es una matriz simétrica y definida positiva.
Note que es equivalente a resolver el sistema de ecuaciones
Qx = b (2)x∗ = Q−1b (3)
3 / 62
![Page 3: Orden del Tema](https://reader035.vdocumento.com/reader035/viewer/2022070815/62c6246fcfa52d4850049ff8/html5/thumbnails/3.jpg)
Gradiente Conjugado Lineal
Direcciones ConjugadasSolución mediante Direcciones ConjugadasAlgoritmo Direcciones Conjugadas IterativoGradiente Conjugado-Versión PreliminarForma práctica de GC
Ejemplo en 2D
Para ello, consideremos el caso particular en R2
min(x,y)∈R2f(x, y) =1
2λ1(x− a)2 +
1
2λ2(y − b)2 (4)
con λ1, λ2 > 0.
Note que en este caso:
f(x, y) = f1(x) + f2(y) (5)∇f(x, y) = [f ′1(x), f ′2(y)]T (6)
Además (x, y)∗ = (a, b)
4 / 62
![Page 4: Orden del Tema](https://reader035.vdocumento.com/reader035/viewer/2022070815/62c6246fcfa52d4850049ff8/html5/thumbnails/4.jpg)
Gradiente Conjugado Lineal
Direcciones ConjugadasSolución mediante Direcciones ConjugadasAlgoritmo Direcciones Conjugadas IterativoGradiente Conjugado-Versión PreliminarForma práctica de GC
Ejemplo
Sea dado (xk, yk) y la actualización en la dirección de máximodescenso,
xk+1 = xk − αxf ′1(xk) (7)yk+1 = yk − αyf ′2(yk) (8)
donde αx y αy solo los tamaños de paso.
5 / 62
![Page 5: Orden del Tema](https://reader035.vdocumento.com/reader035/viewer/2022070815/62c6246fcfa52d4850049ff8/html5/thumbnails/5.jpg)
Gradiente Conjugado Lineal
Direcciones ConjugadasSolución mediante Direcciones ConjugadasAlgoritmo Direcciones Conjugadas IterativoGradiente Conjugado-Versión PreliminarForma práctica de GC
Ejemplo
Supongamos que f ′1(xk) 6= 0 y f ′2(yk) 6= 0. Si además, αx y αyson tamaños de paso exactos en cada dirección (se usadescenso coordenado)
αx =xk − af ′1(xk)
(9)
xk+1 = xk − αxf ′1(x) = xk −xk − af ′1(xk)
f ′1(xk) = a (10)
similarmente yk+1 = b. Luego (xk+1, yk+1) = (x, y)∗ = (a, b), esdecir, para cualquier punto (xk, yk) se llega al óptimo en unaiteración!!
6 / 62
![Page 6: Orden del Tema](https://reader035.vdocumento.com/reader035/viewer/2022070815/62c6246fcfa52d4850049ff8/html5/thumbnails/6.jpg)
Gradiente Conjugado Lineal
Direcciones ConjugadasSolución mediante Direcciones ConjugadasAlgoritmo Direcciones Conjugadas IterativoGradiente Conjugado-Versión PreliminarForma práctica de GC
Observaciones
• El ejemplo anterior es una forma cuadrática orientada enlos ejes• Si se aplica máximo descenso coordenado con tamaño de
paso exacto, se llega al óptimo, en una iteración.• Notar que el problema es separable en cada variable!, ie
f(x, y) =1
2[x, y]
[λ1 00 λ2
] [xy
]− [a, b]
[xy
]+ cte
es decir, la matriz es diagonal
7 / 62
![Page 7: Orden del Tema](https://reader035.vdocumento.com/reader035/viewer/2022070815/62c6246fcfa52d4850049ff8/html5/thumbnails/7.jpg)
Gradiente Conjugado Lineal
Direcciones ConjugadasSolución mediante Direcciones ConjugadasAlgoritmo Direcciones Conjugadas IterativoGradiente Conjugado-Versión PreliminarForma práctica de GC
Gradiente Conjugado
Se podrán usar las ideas anteriores al caso general?
minx∈Rnf(x) =1
2xTQx− bTx (11)
8 / 62
![Page 8: Orden del Tema](https://reader035.vdocumento.com/reader035/viewer/2022070815/62c6246fcfa52d4850049ff8/html5/thumbnails/8.jpg)
Gradiente Conjugado Lineal
Direcciones ConjugadasSolución mediante Direcciones ConjugadasAlgoritmo Direcciones Conjugadas IterativoGradiente Conjugado-Versión PreliminarForma práctica de GC
Gradiente Conjugado
Basados en el ejemplo en R2, la idea sería diagonalizar Q
f(y) =1
2yTΛy − b̃Ty (12)
donde Q = UΛUT , y = UTx y b̃ = bU, donde Λ es diagonal yU es ortogonal.
Luego, la solución es muy facil, ie y = Λ−1b̃ y x = Uy.
El problema es que habría que descomponer la matriz Q, locual es computacionalmente costoso, se puede hacer algomejor?
9 / 62
![Page 9: Orden del Tema](https://reader035.vdocumento.com/reader035/viewer/2022070815/62c6246fcfa52d4850049ff8/html5/thumbnails/9.jpg)
Gradiente Conjugado Lineal
Direcciones ConjugadasSolución mediante Direcciones ConjugadasAlgoritmo Direcciones Conjugadas IterativoGradiente Conjugado-Versión PreliminarForma práctica de GC
Orden del Tema
1 Gradiente Conjugado LinealDirecciones ConjugadasSolución mediante Direcciones ConjugadasAlgoritmo Direcciones Conjugadas IterativoGradiente Conjugado-Versión PreliminarForma práctica de GC
10 / 62
![Page 10: Orden del Tema](https://reader035.vdocumento.com/reader035/viewer/2022070815/62c6246fcfa52d4850049ff8/html5/thumbnails/10.jpg)
Gradiente Conjugado Lineal
Direcciones ConjugadasSolución mediante Direcciones ConjugadasAlgoritmo Direcciones Conjugadas IterativoGradiente Conjugado-Versión PreliminarForma práctica de GC
Direcciones Conjugadas
Sea Q una matriz simétrica y definida positiva. Dos vectoresd1,d2 se dicen conjugados con respecto a Q o simplementeQ-ortogonales si dT1 Qd2 = 0.
Un conjunto de vectores d0,d1, · · · ,dk son mutuamenteQ-ortogonales si dTi Qdj = 0 para i 6= j.
11 / 62
![Page 11: Orden del Tema](https://reader035.vdocumento.com/reader035/viewer/2022070815/62c6246fcfa52d4850049ff8/html5/thumbnails/11.jpg)
Gradiente Conjugado Lineal
Direcciones ConjugadasSolución mediante Direcciones ConjugadasAlgoritmo Direcciones Conjugadas IterativoGradiente Conjugado-Versión PreliminarForma práctica de GC
Proposición Direcciones Conjugadas
Proposición: Sea Q una matriz simétrica definida positiva. Siel conjunto de vectores d0,d1, · · · ,dk son mutuamenteQ-ortogonales entonces son linealmente independientes.
12 / 62
![Page 12: Orden del Tema](https://reader035.vdocumento.com/reader035/viewer/2022070815/62c6246fcfa52d4850049ff8/html5/thumbnails/12.jpg)
Gradiente Conjugado Lineal
Direcciones ConjugadasSolución mediante Direcciones ConjugadasAlgoritmo Direcciones Conjugadas IterativoGradiente Conjugado-Versión PreliminarForma práctica de GC
DemostraciónSupongamos que existen números reales αi, i = 0, 1, · · · , kpara los que se cumple
k∑j=0
αjdj = 0, (13)
Premultiplicando por dTi Q ( con i = 0, 1, · · · , k)k∑j=0
αjdTi Qdj = dTi Q0, (14)
como para i 6= j se cumple dTi Qdj = 0 entonces
αidTi Qdi = 0, (15)
y por tanto αi = 0 para i = 0, 1, · · · , k. Con lo cual se concluyela demostración.
13 / 62
![Page 13: Orden del Tema](https://reader035.vdocumento.com/reader035/viewer/2022070815/62c6246fcfa52d4850049ff8/html5/thumbnails/13.jpg)
Gradiente Conjugado Lineal
Direcciones ConjugadasSolución mediante Direcciones ConjugadasAlgoritmo Direcciones Conjugadas IterativoGradiente Conjugado-Versión PreliminarForma práctica de GC
Orden del Tema
1 Gradiente Conjugado LinealDirecciones ConjugadasSolución mediante Direcciones ConjugadasAlgoritmo Direcciones Conjugadas IterativoGradiente Conjugado-Versión PreliminarForma práctica de GC
14 / 62
![Page 14: Orden del Tema](https://reader035.vdocumento.com/reader035/viewer/2022070815/62c6246fcfa52d4850049ff8/html5/thumbnails/14.jpg)
Gradiente Conjugado Lineal
Direcciones ConjugadasSolución mediante Direcciones ConjugadasAlgoritmo Direcciones Conjugadas IterativoGradiente Conjugado-Versión PreliminarForma práctica de GC
Solución mediante Direcciones Conjugadas
• Sea D = {d0,d1, · · · ,dn−1} un conjunto de direccionesconjugadas (previamente conocidas o dadas) conrespecto a una matriz simétrica y definida positiva Q.• De acuerdo a la proposición anterior el conjunto D es
linealmente independiente por lo tanto D es una base deRn.• Supongamos adicionalmente que x∗ es la solución del
problema de optimización.• Luego, podemos expresar x∗, de forma única, como una
combinación lineal usando la base D
15 / 62
![Page 15: Orden del Tema](https://reader035.vdocumento.com/reader035/viewer/2022070815/62c6246fcfa52d4850049ff8/html5/thumbnails/15.jpg)
Gradiente Conjugado Lineal
Direcciones ConjugadasSolución mediante Direcciones ConjugadasAlgoritmo Direcciones Conjugadas IterativoGradiente Conjugado-Versión PreliminarForma práctica de GC
Algoritmo Básico de las Direcciones Conjugadas
x∗ =
n−1∑j=0
αjdj (16)
Premultiplicando por dTi Q, usando (2) y por el hecho de quedTi Qdj = 0 para i 6= j (por ser direcciones conjugadas),obtenemos los coeficientes de la combinación lineal:
dTi Qx∗ =n−1∑j=0
αjdTi Qdj (17)
αidTi Qdi = dTi Qx∗ (18)
αi =dTi b
dTi Qdi(19)
16 / 62
![Page 16: Orden del Tema](https://reader035.vdocumento.com/reader035/viewer/2022070815/62c6246fcfa52d4850049ff8/html5/thumbnails/16.jpg)
Gradiente Conjugado Lineal
Direcciones ConjugadasSolución mediante Direcciones ConjugadasAlgoritmo Direcciones Conjugadas IterativoGradiente Conjugado-Versión PreliminarForma práctica de GC
Solución mediante Direcciones Conjugadas
Finalmente,
x∗ =
n−1∑j=0
dTj b
dTj Qdjdj (20)
Notar que• El uso de direcciones Q-conjugadas permite calcular los
coeficientes, debido a que al premultiplicaradecuadamente por una de las direcciones, todos lostérminos de la derecha se anulan salvo un término.• Al mismo tiempo, los coeficientes de la combinación lineal
se pudieron expresar en términos de informaciónconocida, ie, las direcciones conjugadas, Q y b.
17 / 62
![Page 17: Orden del Tema](https://reader035.vdocumento.com/reader035/viewer/2022070815/62c6246fcfa52d4850049ff8/html5/thumbnails/17.jpg)
Gradiente Conjugado Lineal
Direcciones ConjugadasSolución mediante Direcciones ConjugadasAlgoritmo Direcciones Conjugadas IterativoGradiente Conjugado-Versión PreliminarForma práctica de GC
Orden del Tema
1 Gradiente Conjugado LinealDirecciones ConjugadasSolución mediante Direcciones ConjugadasAlgoritmo Direcciones Conjugadas IterativoGradiente Conjugado-Versión PreliminarForma práctica de GC
18 / 62
![Page 18: Orden del Tema](https://reader035.vdocumento.com/reader035/viewer/2022070815/62c6246fcfa52d4850049ff8/html5/thumbnails/18.jpg)
Gradiente Conjugado Lineal
Direcciones ConjugadasSolución mediante Direcciones ConjugadasAlgoritmo Direcciones Conjugadas IterativoGradiente Conjugado-Versión PreliminarForma práctica de GC
Sea dado un conjunto de direcciones conjugadas D.Definamos gk
def= ∇f(xk) = Qxk − b.
Dado un punto inicial x0, generemos la secuencia
xk+1 = xk + αkdk (21)
donde αk = − gTk dkdTk Qdk
es el minimizador de f(·) a lo largo de larecta xk + αdk
19 / 62
![Page 19: Orden del Tema](https://reader035.vdocumento.com/reader035/viewer/2022070815/62c6246fcfa52d4850049ff8/html5/thumbnails/19.jpg)
Gradiente Conjugado Lineal
Direcciones ConjugadasSolución mediante Direcciones ConjugadasAlgoritmo Direcciones Conjugadas IterativoGradiente Conjugado-Versión PreliminarForma práctica de GC
αk = arg mı́nαf(xk + αdk) (22)
De donde se obtiene
∇T f(xk + αdk)dk = 0 (23)(Q(xk + αdk)− b)Tdk = 0 (24)
(gk + αQdk)Tdk = 0 (25)
αk = −gTk dk
dTkQdk(26)
Luego gTk+1dk = 0
20 / 62
![Page 20: Orden del Tema](https://reader035.vdocumento.com/reader035/viewer/2022070815/62c6246fcfa52d4850049ff8/html5/thumbnails/20.jpg)
Gradiente Conjugado Lineal
Direcciones ConjugadasSolución mediante Direcciones ConjugadasAlgoritmo Direcciones Conjugadas IterativoGradiente Conjugado-Versión PreliminarForma práctica de GC
Algoritmo Básico de las Direcciones Conjugadas
Require: x0, D = {d0,d1, · · · ,dn−1}Ensure: x∗
1: Hacer k = 0, gk = Qxk − b2: while k < n y ‖gk‖ 6= 0 (No conveja) do3: αk = − gTk dk
dTk Qdk4: xk+1 = xk + αkdk5: gk+1 = Qxk+1 − b6: k = k + 17: end while
21 / 62
![Page 21: Orden del Tema](https://reader035.vdocumento.com/reader035/viewer/2022070815/62c6246fcfa52d4850049ff8/html5/thumbnails/21.jpg)
Gradiente Conjugado Lineal
Direcciones ConjugadasSolución mediante Direcciones ConjugadasAlgoritmo Direcciones Conjugadas IterativoGradiente Conjugado-Versión PreliminarForma práctica de GC
Conjugate Direction Theorem
Para cualquier x0 ∈ Rn, la sucesión {xk} generada usando elalgoritmo anterior converge a la solución x∗ en a lo sumo npasos.
22 / 62
![Page 22: Orden del Tema](https://reader035.vdocumento.com/reader035/viewer/2022070815/62c6246fcfa52d4850049ff8/html5/thumbnails/22.jpg)
Gradiente Conjugado Lineal
Direcciones ConjugadasSolución mediante Direcciones ConjugadasAlgoritmo Direcciones Conjugadas IterativoGradiente Conjugado-Versión PreliminarForma práctica de GC
Demostración
Como D es un conjunto de vectores linealmenteindependiente, entonces podemos escribir
x∗ − x0 =
n−1∑j=0
σjdj (27)
de forma única para ciertos σj .
23 / 62
![Page 23: Orden del Tema](https://reader035.vdocumento.com/reader035/viewer/2022070815/62c6246fcfa52d4850049ff8/html5/thumbnails/23.jpg)
Gradiente Conjugado Lineal
Direcciones ConjugadasSolución mediante Direcciones ConjugadasAlgoritmo Direcciones Conjugadas IterativoGradiente Conjugado-Versión PreliminarForma práctica de GC
DemostraciónA partir de
x∗ − x0 =
n−1∑j=0
σjdj (28)
Premultiplicando por dTkQ, y por el hecho de que dTkQdj = 0para k 6= j,
dTkQ(x∗ − x0) =
n−1∑j=0
σjdTkQdj (29)
σk =dTkQ(x∗ − x0)
dTkQdk(30)
24 / 62
![Page 24: Orden del Tema](https://reader035.vdocumento.com/reader035/viewer/2022070815/62c6246fcfa52d4850049ff8/html5/thumbnails/24.jpg)
Gradiente Conjugado Lineal
Direcciones ConjugadasSolución mediante Direcciones ConjugadasAlgoritmo Direcciones Conjugadas IterativoGradiente Conjugado-Versión PreliminarForma práctica de GC
Demostración
σk =dTkQ(x∗ − x0)
dTkQdk
=dTkQx∗ − dTkQx0
dTkQdk
=dTk (b−Qxk)
dTkQdk,pues Qx∗ = b y dTkQxk = dTkQx0
= −gTk dk
dTkQdk,pues gk = Qxk − b
Luego σk = αk con lo que se concluye la demostración.
25 / 62
![Page 25: Orden del Tema](https://reader035.vdocumento.com/reader035/viewer/2022070815/62c6246fcfa52d4850049ff8/html5/thumbnails/25.jpg)
Gradiente Conjugado Lineal
Direcciones ConjugadasSolución mediante Direcciones ConjugadasAlgoritmo Direcciones Conjugadas IterativoGradiente Conjugado-Versión PreliminarForma práctica de GC
Demostración: Comentario
A partir de σk = αk, definiendo D := [d0,d1, · · · ,dn−1]
x∗ = x0 +
n−1∑k=0
σkdk = x0 + Dσ
xn = x0 +
n−1∑k=0
αkdk = x0 + Dα
se tiene xn = x∗
26 / 62
![Page 26: Orden del Tema](https://reader035.vdocumento.com/reader035/viewer/2022070815/62c6246fcfa52d4850049ff8/html5/thumbnails/26.jpg)
Gradiente Conjugado Lineal
Direcciones ConjugadasSolución mediante Direcciones ConjugadasAlgoritmo Direcciones Conjugadas IterativoGradiente Conjugado-Versión PreliminarForma práctica de GC
Orden del Tema
1 Gradiente Conjugado LinealDirecciones ConjugadasSolución mediante Direcciones ConjugadasAlgoritmo Direcciones Conjugadas IterativoGradiente Conjugado-Versión PreliminarForma práctica de GC
27 / 62
![Page 27: Orden del Tema](https://reader035.vdocumento.com/reader035/viewer/2022070815/62c6246fcfa52d4850049ff8/html5/thumbnails/27.jpg)
Gradiente Conjugado Lineal
Direcciones ConjugadasSolución mediante Direcciones ConjugadasAlgoritmo Direcciones Conjugadas IterativoGradiente Conjugado-Versión PreliminarForma práctica de GC
Algoritmo Gradiente Conjugado
La idea del Algoritmo Gradiente Conjugado se basa en elAlgoritmo de las direcciones conjugadas, pero sin conocer lasdirecciones conjugadas a priori.
Se comienza selecciónando la primera dirección d0 = −g0 y elresto
dk+1 = −gk+1 + βk+1dk
donde βk+1 se seleccióna de modo que dk y dk+1 seanQ-conjugados.
28 / 62
![Page 28: Orden del Tema](https://reader035.vdocumento.com/reader035/viewer/2022070815/62c6246fcfa52d4850049ff8/html5/thumbnails/28.jpg)
Gradiente Conjugado Lineal
Direcciones ConjugadasSolución mediante Direcciones ConjugadasAlgoritmo Direcciones Conjugadas IterativoGradiente Conjugado-Versión PreliminarForma práctica de GC
Algoritmo Gradiente Conjugado
Para calcular βk+1 basta premultiplicar por dTkQ en la igualdaddk+1 = −gk+1 + βk+1dk
dk+1 = −gk+1 + βk+1dk
dTkQdk+1 = −dTkQgk+1 + βk+1dTkQdk
−dTkQgk+1 + βk+1dTkQdk = 0
βk+1 =gTk+1Qdk
dTkQdk
Ver algoritmo siguiente (versión preliminar)
29 / 62
![Page 29: Orden del Tema](https://reader035.vdocumento.com/reader035/viewer/2022070815/62c6246fcfa52d4850049ff8/html5/thumbnails/29.jpg)
Gradiente Conjugado Lineal
Direcciones ConjugadasSolución mediante Direcciones ConjugadasAlgoritmo Direcciones Conjugadas IterativoGradiente Conjugado-Versión PreliminarForma práctica de GC
Algoritmo Gradiente Conjugado
Algorithm 1 GC-Versión PreliminarRequire: x0
Ensure: x∗
1: Hacer g0 = Qx0 − b,d0 = −g0, k = 02: while ‖gk‖ 6= 0 (No conveja) do3: αk = − gTk dk
dTk Qdk4: xk+1 = xk + αkdk5: gk+1 = Qxk+1 − b = ∇f(xk+1)
6: βk+1 =dTk Qgk+1
dTk Qdk7: dk+1 = −gk+1 + βk+1dk8: k = k + 19: end while
30 / 62
![Page 30: Orden del Tema](https://reader035.vdocumento.com/reader035/viewer/2022070815/62c6246fcfa52d4850049ff8/html5/thumbnails/30.jpg)
Gradiente Conjugado Lineal
Direcciones ConjugadasSolución mediante Direcciones ConjugadasAlgoritmo Direcciones Conjugadas IterativoGradiente Conjugado-Versión PreliminarForma práctica de GC
Orden del Tema
1 Gradiente Conjugado LinealDirecciones ConjugadasSolución mediante Direcciones ConjugadasAlgoritmo Direcciones Conjugadas IterativoGradiente Conjugado-Versión PreliminarForma práctica de GC
31 / 62
![Page 31: Orden del Tema](https://reader035.vdocumento.com/reader035/viewer/2022070815/62c6246fcfa52d4850049ff8/html5/thumbnails/31.jpg)
Gradiente Conjugado Lineal
Direcciones ConjugadasSolución mediante Direcciones ConjugadasAlgoritmo Direcciones Conjugadas IterativoGradiente Conjugado-Versión PreliminarForma práctica de GC
Forma práctica de GC
Algunas relaciones• xk+1 = xk + αkdk• gk+1 = Qxk+1 − b• gk+1 = gk + αkQdk• Qxk+1 = Qxk + αkQdk• Qxk+1 − b = Qxk − b+ αkQdk• gk+1 = gk + αkQdk
32 / 62
![Page 32: Orden del Tema](https://reader035.vdocumento.com/reader035/viewer/2022070815/62c6246fcfa52d4850049ff8/html5/thumbnails/32.jpg)
Gradiente Conjugado Lineal
Direcciones ConjugadasSolución mediante Direcciones ConjugadasAlgoritmo Direcciones Conjugadas IterativoGradiente Conjugado-Versión PreliminarForma práctica de GC
Forma práctica de GC
Algunas relaciones• xk+1 = xk + αkdk• gk+1 = Qxk+1 − b• gk+1 = gk + αkQdk• Qxk+1 = Qxk + αkQdk• Qxk+1 − b = Qxk − b+ αkQdk• gk+1 = gk + αkQdk
32 / 62
![Page 33: Orden del Tema](https://reader035.vdocumento.com/reader035/viewer/2022070815/62c6246fcfa52d4850049ff8/html5/thumbnails/33.jpg)
Gradiente Conjugado Lineal
Direcciones ConjugadasSolución mediante Direcciones ConjugadasAlgoritmo Direcciones Conjugadas IterativoGradiente Conjugado-Versión PreliminarForma práctica de GC
Forma práctica de GC
Algunas relaciones• xk+1 = xk + αkdk• gk+1 = Qxk+1 − b• gk+1 = gk + αkQdk• Qxk+1 = Qxk + αkQdk• Qxk+1 − b = Qxk − b+ αkQdk• gk+1 = gk + αkQdk
32 / 62
![Page 34: Orden del Tema](https://reader035.vdocumento.com/reader035/viewer/2022070815/62c6246fcfa52d4850049ff8/html5/thumbnails/34.jpg)
Gradiente Conjugado Lineal
Direcciones ConjugadasSolución mediante Direcciones ConjugadasAlgoritmo Direcciones Conjugadas IterativoGradiente Conjugado-Versión PreliminarForma práctica de GC
Forma práctica de GC
Algunas relaciones• xk+1 = xk + αkdk• gk+1 = Qxk+1 − b• gk+1 = gk + αkQdk• Qxk+1 = Qxk + αkQdk• Qxk+1 − b = Qxk − b+ αkQdk• gk+1 = gk + αkQdk
32 / 62
![Page 35: Orden del Tema](https://reader035.vdocumento.com/reader035/viewer/2022070815/62c6246fcfa52d4850049ff8/html5/thumbnails/35.jpg)
Gradiente Conjugado Lineal
Direcciones ConjugadasSolución mediante Direcciones ConjugadasAlgoritmo Direcciones Conjugadas IterativoGradiente Conjugado-Versión PreliminarForma práctica de GC
Forma práctica de GC: Algunas relaciones
Otras relaciones• xk − xi⊥Qdj , j ∈ {0, 1, · · · , i− 1}, ie, xTkQdj = xTi Qdj
• xk − xi⊥Qdk, 0 ≤ i ≤ k, ie, xTkQdk = xTi Qdk• gk − gi⊥dj , j ∈ {0, 1, · · · , i− 1}, i.e., gTk dj = gTi dj
• gk − gi⊥dk, 0 ≤ i ≤ k, i.e., gTk dk = gTi dk
Luego• xTkQdk = xT0 Qdk• gTk dk = gT0 dk
33 / 62
![Page 36: Orden del Tema](https://reader035.vdocumento.com/reader035/viewer/2022070815/62c6246fcfa52d4850049ff8/html5/thumbnails/36.jpg)
Gradiente Conjugado Lineal
Direcciones ConjugadasSolución mediante Direcciones ConjugadasAlgoritmo Direcciones Conjugadas IterativoGradiente Conjugado-Versión PreliminarForma práctica de GC
Forma práctica de GC: Algunas relaciones
xk = xk−1 + αk−1dk−1 = xk−2 + αk−2dk−2 + αk−1dk−1
= xi +
k−1∑s=i
αsds
Luego
xk − xi ⊥Q dj , i.e., xTkQdj = xTi Qdj
j ∈ {0, 1, · · · , i− 1}xk − xi ⊥Q dk, i.e., x
TkQdk = xTi Qdk
34 / 62
![Page 37: Orden del Tema](https://reader035.vdocumento.com/reader035/viewer/2022070815/62c6246fcfa52d4850049ff8/html5/thumbnails/37.jpg)
Gradiente Conjugado Lineal
Direcciones ConjugadasSolución mediante Direcciones ConjugadasAlgoritmo Direcciones Conjugadas IterativoGradiente Conjugado-Versión PreliminarForma práctica de GC
Forma práctica de GC:Algunas relaciones
gk = gk−1 + αk−1Qdk−1 = gk−2 + αk−2Qdk−2 + αk−1Qdk−1
= gi +
k−1∑s=i
αsQds
Luego
gk − gi ⊥ dj , i.e., gTk dj = gTi dj
j ∈ {0, 1, · · · , i− 1}gk − gi ⊥ dk, i.e., g
Tk dk = gTi dk
35 / 62
![Page 38: Orden del Tema](https://reader035.vdocumento.com/reader035/viewer/2022070815/62c6246fcfa52d4850049ff8/html5/thumbnails/38.jpg)
Gradiente Conjugado Lineal
Direcciones ConjugadasSolución mediante Direcciones ConjugadasAlgoritmo Direcciones Conjugadas IterativoGradiente Conjugado-Versión PreliminarForma práctica de GC
Forma práctica de GC
Otras relaciones• gTk+1dk = 0
• αk = − gTk dkdTk Qdk
• βk+1 =gTk+1Qdk
dTk Qdk
• dk+1 = −gk+1 + βk+1dk
36 / 62
![Page 39: Orden del Tema](https://reader035.vdocumento.com/reader035/viewer/2022070815/62c6246fcfa52d4850049ff8/html5/thumbnails/39.jpg)
Gradiente Conjugado Lineal
Direcciones ConjugadasSolución mediante Direcciones ConjugadasAlgoritmo Direcciones Conjugadas IterativoGradiente Conjugado-Versión PreliminarForma práctica de GC
Forma práctica de GC
Proposicion
Si {d0,d1, · · · ,dk} son Q-ortogonales entonces,
gTk+1di = 0
gTk+1gi = 0
para i = 0, 1, · · · , k
37 / 62
![Page 40: Orden del Tema](https://reader035.vdocumento.com/reader035/viewer/2022070815/62c6246fcfa52d4850049ff8/html5/thumbnails/40.jpg)
Gradiente Conjugado Lineal
Direcciones ConjugadasSolución mediante Direcciones ConjugadasAlgoritmo Direcciones Conjugadas IterativoGradiente Conjugado-Versión PreliminarForma práctica de GC
Forma práctica de GC
Prueba de la Primera relaciónSi i = k es claro que se cumple
gTk+1di = 0
pues si αk es el tamaño de paso exacto
0 = φ′(αk) = ∇f(xk + αkdk)Tdk = gTk+1dk
38 / 62
![Page 41: Orden del Tema](https://reader035.vdocumento.com/reader035/viewer/2022070815/62c6246fcfa52d4850049ff8/html5/thumbnails/41.jpg)
Gradiente Conjugado Lineal
Direcciones ConjugadasSolución mediante Direcciones ConjugadasAlgoritmo Direcciones Conjugadas IterativoGradiente Conjugado-Versión PreliminarForma práctica de GC
Forma práctica de GC
Prueba de la Primera relaciónSi i < k y usando la Q-ortogonalidad, la relación de la laminaanterior y la relacion
gk+1 = gi+1 +
k∑s=i+1
αsQds
Se concluye que
gTk+1di = 0
39 / 62
![Page 42: Orden del Tema](https://reader035.vdocumento.com/reader035/viewer/2022070815/62c6246fcfa52d4850049ff8/html5/thumbnails/42.jpg)
Gradiente Conjugado Lineal
Direcciones ConjugadasSolución mediante Direcciones ConjugadasAlgoritmo Direcciones Conjugadas IterativoGradiente Conjugado-Versión PreliminarForma práctica de GC
Forma práctica de GC
Prueba de la Segunda relaciónPara ello, podemos usar la relacion para 0 ≤ i ≤ k
di = −gi + βidi−1
gi = −di + βidi−1
y con la primera parte de la proposición
gTk+1gi = gTk+1(−di + βidi−1) = 0
40 / 62
![Page 43: Orden del Tema](https://reader035.vdocumento.com/reader035/viewer/2022070815/62c6246fcfa52d4850049ff8/html5/thumbnails/43.jpg)
Gradiente Conjugado Lineal
Direcciones ConjugadasSolución mediante Direcciones ConjugadasAlgoritmo Direcciones Conjugadas IterativoGradiente Conjugado-Versión PreliminarForma práctica de GC
Recalculando el tamaño de paso αk
• αk = − gTk dkdTk Qdk
• gTk di = 0, i = 0, 1, · · · , k − 1
• dk = −gk + βkdk−1
Luego
• αk =gTk gkdTk Qdk
41 / 62
![Page 44: Orden del Tema](https://reader035.vdocumento.com/reader035/viewer/2022070815/62c6246fcfa52d4850049ff8/html5/thumbnails/44.jpg)
Gradiente Conjugado Lineal
Direcciones ConjugadasSolución mediante Direcciones ConjugadasAlgoritmo Direcciones Conjugadas IterativoGradiente Conjugado-Versión PreliminarForma práctica de GC
Recalculando el βk+1
• βk+1 =gTk+1Qdk
dTk Qdk
• gTk di = 0, i = 0, 1, · · · , k − 1
• dk = −gk + βkdk−1• αkQdk = gk+1 − gk
Luego
• βk+1 =gTk+1gk+1
gTk gk
42 / 62
![Page 45: Orden del Tema](https://reader035.vdocumento.com/reader035/viewer/2022070815/62c6246fcfa52d4850049ff8/html5/thumbnails/45.jpg)
Gradiente Conjugado Lineal
Direcciones ConjugadasSolución mediante Direcciones ConjugadasAlgoritmo Direcciones Conjugadas IterativoGradiente Conjugado-Versión PreliminarForma práctica de GC
Algoritmo Gradiente Conjugado
Algorithm 2 GC (Estandar)Require: x0
Ensure: x∗
1: Hacer g0 = Qx0 − b,d0 = −g0, k = 02: while ‖gk‖ 6= 0 (No conveja) do3: αk =
gTk gkdTk Qdk
= − gTk dkdTk Qdk
4: xk+1 = xk + αkdk5: gk+1 = Qxk+1 − b = ∇f(xk+1)
6: βk+1 =gTk+1gk+1
gTk gk=gTk+1Qdk
dTk Qdk7: dk+1 = −gk+1 + βk+1dk8: k = k + 19: end while
43 / 62