Te haré un trato. Puedo explicarlo con los elementos básicos de matemáticas, pero agregaré bloques de intuición a lo largo del camino. ¿Acuerdo?
*sacudir*
Vamos a entrar en eso.
- ¿Por qué las personas crearon números complejos?
- ¿Por qué es imposible encontrar el logaritmo discreto de una curva elíptica aleatoria con un punto base conocido?
- ¿Se puede escribir [matemáticas] \ pi [/ matemáticas] como [matemáticas] a ^ b [/ matemáticas] donde [matemáticas] a [/ matemáticas] y [matemáticas] b [/ matemáticas] son algebraicas y [matemáticas] b [ / matemáticas] es irracional?
- ¿Es matemáticamente imposible que NO haya otra forma de vida en este universo que no sea la nuestra?
- Cómo demostrar que [math] \ neg (P \ Rightarrow Q) [/ math] es lógicamente equivalente a [math] P \ land (\ neg Q) [/ math]
El método de gradiente conjugado en pocas palabras
El método CG es un medio para resolver eficientemente el sistema de ecuaciones [math] \ mathbf {Ax} = \ mathbf {b} [/ math] cuando [math] \ mathbf {A} [/ math] es un simétrico positivo real definido matriz y [math] \ mathbf {x} [/ math] es un vector de longitud [math] D [/ math]. El algoritmo se basa en la equivalencia entre resolver el sistema y encontrar el mínimo de una determinada función [math] f (\ cdot) [/ math]. Una comprensión geométrica de [math] f (\ cdot) [/ math] nos permite navegar eficientemente hacia el mínimo y resolver el sistema.
El método CG resuelve [math] \ mathbf {Ax} = \ mathbf {b} [/ math] rápidamente, dado que [math] \ mathbf {A} [/ math] tiene una buena forma.
Entonces, ¿qué es [matemáticas] f (\ cdot) [/ matemáticas] ?
Bueno, es este tipo raro:
[math] f (\ mathbf {x}) = \ frac {1} {2} \ mathbf {x} ^ {T} \ mathbf {Ax} – \ mathbf {b} ^ {T} \ mathbf {x} [ /matemáticas]
que en general se conoce como la forma cuadrática. Debido a la simetría de [math] \ mathbf {A} [/ math], tenemos:
[math] \ nabla f (\ mathbf {x}) = \ mathbf {Ax} – \ mathbf {b} [/ math]
Dado que [math] \ mathbf {A} [/ math] es simétrico y positivo definido, podemos estar seguros de que solo existe un [math] \ mathbf {x} ^ {*} [/ math] tal que [math] \ nabla f (\ mathbf {x} ^ {*}) = \ mathbf {0} [/ math], lo que resolvería claramente nuestro sistema. Entonces, a partir de este punto, nos ocupamos únicamente de minimizar [math] f (\ cdot) [/ math].
Nuestra respuesta es la misma respuesta de otro problema: un problema en el que, si somos inteligentes, tenemos una hoja de ruta hacia la solución. Entonces, resolvamos ese otro problema.
¿Por qué [math] f (\ cdot) [/ math] es fácil de optimizar?
Imaginemos dibujar la topología de la función comenzando desde el mínimo y expandiéndose hacia afuera con líneas de contorno. Entonces, preguntamos: “¿Qué define el conjunto de vectores desde el punto mínimo de modo que todos produzcan el mismo valor de [math] f (\ cdot) [/ math]? ” Escribamos cualquier punto arbitrario [math] \ mathbf { x} _ {0} [/ math] como [math] \ mathbf {x} _ {0} = \ mathbf {x} ^ {*} + \ mathbf {e} _ {0} [/ math] e inspecciona:
[matemáticas] \ begin {eqnarray *} f (\ mathbf {x}) & = & \ frac {1} {2} (\ mathbf {x} ^ {*} + \ mathbf {e} _ {0}) ^ {T} \ mathbf {A} (\ mathbf {x} ^ {*} + \ mathbf {e} _ {0}) – \ mathbf {b} ^ {T} (\ mathbf {x} ^ {*} + \ mathbf {e} _ {0}) \\ & = & f (\ mathbf {x} ^ {*}) + \ frac {1} {2} \ mathbf {e} _ {0} ^ {T} \ mathbf {A} \ mathbf {e} _ {0} \ end {eqnarray *} [/ math]
Entonces, la diferencia en el valor se debe completamente a la interacción entre el término de error y [math] \ mathbf {A} [/ math].
En otras palabras, si imaginamos que [math] \ mathbf {x} [/ math] era un vector de longitud 2, entonces podríamos imaginar líneas de contorno de [math] f (\ mathbf {x}) [/ math] como:
donde cada eje representa uno de los dos elementos que componen [math] \ mathbf {x} [/ math]. Entonces, dos puntos producirán la misma [matemática] f (\ cdot) [/ matemática] si caen en la misma elipse centrada alrededor de nuestra respuesta. ¿Esto comienza a sentirse útil?
Ok, ahora explotemos la simetría de [math] \ mathbf {A} [/ math] – podemos expresarlo en su descomposición de valor propio:
[matemáticas] \ begin {eqnarray *} \ mathbf {A} = \ sum_ {i} \ lambda_ {i} \ mathbf {q} _ {i} \ mathbf {q} _ {i} ^ {T} \ end { eqnarray *} [/ math]
donde [math] \ forall i [/ math], [math] \ lambda_ {i}> 0 [/ math]. Como sabemos que un [math] \ mathbf {A} [/ math] simétrico producirá [math] \ mathbf {q} _ {i} [/ math] ‘s que forman una base sobre [math] \ mathbb {R} ^ {D} [/ math], podemos escribir [math] \ mathbf {e} _ {0} = \ sum_ {i} c_ {i} \ frac {\ mathbf {q} _ {i}} {\ sqrt {\ lambda_ {i}}} [/ math]. Piense en esto en un nuevo espacio de coordenadas (lo llamaremos el espacio propio), donde cada eje corresponde a un vector propio escalado y las [matemáticas] c [/ matemáticas] son las coordenadas que se asignan a [matemáticas] \ mathbf {e} _ {0} [/ math] en el espacio estándar. Ahora,
[matemáticas] \ begin {eqnarray *} \ mathbf {e} _ {0} ^ {T} \ mathbf {A} \ mathbf {e} _ {0} & = & \ Big [\ sum_ {i} c_ {i } \ frac {\ mathbf {q} _ {i}} {\ sqrt {\ lambda_ {i}}} \ Big] ^ {T} \ Big [\ sum_ {i} \ lambda_ {i} \ mathbf {q} _ {i} \ mathbf {q} _ {i} ^ {T} \ Big] \ Big [\ sum_ {i} c_ {i} \ frac {\ mathbf {q} _ {i}} {\ sqrt {\ lambda_ {i}}} \ Big] \\ & = & \ sum_ {i} c_ {i} ^ {2} \ end {eqnarray *} [/ math]
Entonces, dos puntos arrojarán el mismo valor de [math] f (\ cdot) [/ math] si sus representaciones en el espacio propio están a la misma distancia del origen (se encuentran en la misma [math] D [/ math] esfera tridimensional centrada en la solución).
Podemos encontrar otra forma de pensar “dos puntos producirán el mismo valor de [math] f (\ cdot) [/ math] si caen en la misma elipse”. Es decir: [math] \ mathbf {A } [/ math] tiene vectores propios en el mismo director que las líneas rojas aquí:
Ahora escriba esos dos puntos verdes como una combinación lineal de esas líneas rojas, produciendo dos coordenadas para cada punto. Si trazáramos esas coordenadas en un nuevo espacio de coordenadas (el espacio propio), ¡se encontrarían en el mismo círculo!
Esta idea se generaliza a la perfección a dimensiones superiores
Entonces, ¿por qué es útil esta esfera? Bueno, por una razón muy importante: si nos movemos en una dirección hasta que la derivada direccional en esa dirección sea cero (equivalentemente, el gradiente es ortogonal a la dirección en la que estamos viajando), ¡entonces el mínimo cae en algún lugar del plano ortogonal a nuestra dirección! En otras palabras, hemos terminado de viajar en esa dirección. Esta es la idea que hace que CG sea tan malo.
En el mundo del espacio propio (mundo circular del ejemplo anterior), nunca tenemos que volver a explorar las direcciones viajadas.
Ahora tenemos que formalizar esto. Hacemos eso con el concepto de [math] \ mathbf {A} [/ math] -ortogonality. Dos vectores [math] \ mathbf {v} _ {1} [/ math] y [math] \ mathbf {v} _ {2} [/ math] son [math] \ mathbf {A} [/ math] -ortogonal iff [matemáticas] \ mathbf {v} _ {1} ^ {T} \ mathbf {A} \ mathbf {v} _ {2} = \ mathbf {c} _ {1} ^ {T} \ mathbf {c} _ {2} = 0 [/ math] (donde [math] \ mathbf {v} _ {i} = \ boldsymbol {\ Lambda} ^ {- \ frac {1} {2}} \ mathbf {Q} \ mathbf {c} _ {i} [/ math] que es la misma forma de representación que usamos para [math] \ mathbf {e} _ {0} [/ math]). Dichos vectores también pueden denominarse conjugados con respecto a [math] \ mathbf {A} [/ math].
Dos vectores son [math] \ mathbf {A} [/ math] -ortogonalidad si son ortogonales en el espacio propio. Esta será una herramienta útil para determinar en qué direcciones viajar.
El algoritmo
Finalmente, podemos considerar la optimización en sí misma. Al igual que con cualquier optimización iterativa, construiremos una secuencia de puntos [matemáticas] \ {\ mathbf {x} _ {0}, \ mathbf {x} _ {1}, \ cdots, \ mathbf {x} _ {n } \} [/ math] que avanza hacia nuestra solución en [math] \ mathbf {x} _ {n} \ approx \ mathbf {x} ^ {*} [/ math], comenzando con [math] \ mathbf {x } _ {0} = \ mathbf {0} [/ math]. Cada punto se determinará como una nueva dirección, [math] \ mathbf {A} [/ math] -ortogonal a todas las direcciones anteriores, recorrida desde un punto anterior. Más específicamente, [math] \ mathbf {x} _ {k} = \ sum_ {i = 1} ^ {k} \ alpha_ {i} \ mathbf {d} _ {i} [/ math] o [math] \ mathbf {x} _ {k} = \ mathbf {x} _ {k-1} + \ alpha_ {k} \ mathbf {d} _ {k} [/ math]. Convenientemente, podemos determinar estos coeficientes cuando consideramos el punto de solución [math] \ mathbf {x} _ {n} = \ sum_ {i = 1} ^ {n} \ alpha_ {i} \ mathbf {d} _ {i }[/matemáticas]:
[matemáticas] \ begin {eqnarray *} \ mathbf {Ax} _ {n} & = & \ sum_ {i = 1} ^ {n} \ alpha_ {i} \ mathbf {Ad} _ {i} \\ \ mathbf {d} _ {k} ^ {T} \ mathbf {Ax} _ {n} & = & \ mathbf {d} _ {k} ^ {T} \ sum_ {i = 1} ^ {n} \ alpha_ { i} \ mathbf {Ad} _ {i} \\ \ mathbf {d} _ {k} ^ {T} \ mathbf {b} & = & \ alpha_ {k} \ mathbf {d} _ {k} ^ { T} \ mathbf {Ad} _ {k} \\ \ implica \ alpha_ {k} & = & \ frac {\ mathbf {d} _ {k} ^ {T} \ mathbf {b}} {\ mathbf {d } _ {k} ^ {T} \ mathbf {Ad} _ {i}} \ end {eqnarray *} [/ math]
Entonces, dadas nuestras instrucciones, [math] \ mathbf {A} [/ math] y [math] \ mathbf {b} [/ math], conocemos los coeficientes.
A medida que construimos una secuencia de puntos, necesitamos determinar dos cosas. Un conjunto de direcciones para viajar consecutivamente y un conjunto de coeficientes para indicarnos qué tan lejos viajar en esas direcciones. Si forzamos la ortogonalidad [math] \ mathbf {A} [/ math] consecutiva, entonces automáticamente conoceremos los coeficientes dados las direcciones.
Ahora necesitamos determinar las direcciones. Para hacer esto, obedecemos la lección de descenso de gradiente dentro de la restricción de que las nuevas direcciones son [matemáticas] \ mathbf {A} [/ matemáticas] – ortogonales a las antiguas. Entonces determinamos el gradiente negativo actual (el “residual”) [math] \ mathbf {r} _ {k} = \ mathbf {b} – \ mathbf {Ax} _ {k} [/ math] y restamos el componente eso no es [math] \ mathbf {A} [/ math] -ortogonal a las anteriores, dando [math] \ mathbf {d} _ {k} [/ math].
Antes de continuar, necesitamos analizar una proyección [math] \ mathbf {A} [/ math] (mi propio término) para que sepamos qué restar del residuo. Desde el punto de vista conceptual, calcular una proyección [math] \ mathbf {A} [/ math] de un vector sobre otro es realizar la proyección en la representación del espacio propio de estos vectores y transformar esa proyección en el espacio original. Deje [math] \ mathbf {A} = \ mathbf {Q} \ boldsymbol {\ Lambda} \ mathbf {Q} ^ {T} [/ math]. Para dos vectores [math] \ mathbf {v} _ {1} [/ math] y [math] \ mathbf {v} _ {2} [/ math], primero escribiríamos sus representaciones como [math] \ mathbf { v} _ {1} = \ boldsymbol {\ Lambda} ^ {- \ frac {1} {2}} \ mathbf {Q} \ mathbf {c} _ {1} [/ math] y de manera similar para [math] \ mathbf {v} _ {2} [/ math]. La proyección en el espacio propio es
[matemáticas] \ textrm {proj} _ {\ mathbf {c} _ {2}} (\ mathbf {c} _ {1}) = \ frac {\ mathbf {c} _ {1} ^ {T} \ mathbf {c} _ {2}} {\ mathbf {c} _ {2} ^ {T} \ mathbf {c} _ {2}} \ mathbf {c} _ {2} [/ math]
Entonces la proyección [math] \ mathbf {A} [/ math], escrita en términos de nuestros vectores originales, es
[matemáticas] \ begin {eqnarray *} \ textrm {proj} _ {\ mathbf {v} _ {2}} ^ {\ mathbf {A}} (\ mathbf {v} _ {1}) & = & \ boldsymbol {\ Lambda} ^ {- \ frac {1} {2}} \ mathbf {Q} \ textrm {proj} _ {\ mathbf {c} _ {2}} (\ mathbf {c} _ {1}) \ \ & = & \ boldsymbol {\ Lambda} ^ {- \ frac {1} {2}} \ mathbf {Q} \ frac {\ mathbf {c} _ {1} ^ {T} \ mathbf {c} _ { 2}} {\ mathbf {c} _ {2} ^ {T} \ mathbf {c} _ {2}} \ mathbf {c} _ {2} \\ & = & \ boldsymbol {\ Lambda} ^ {- \ frac {1} {2}} \ mathbf {Q} \ frac {\ mathbf {v} _ {1} ^ {T} \ mathbf {A} \ mathbf {v} _ {2}} {\ mathbf {v } _ {2} ^ {T} \ mathbf {A} \ mathbf {v} _ {2}} \ mathbf {c} _ {2} \\ & = & \ frac {\ mathbf {v} _ {1} ^ {T} \ mathbf {A} \ mathbf {v} _ {2}} {\ mathbf {v} _ {2} ^ {T} \ mathbf {A} \ mathbf {v} _ {2}} \ mathbf {v} _ {2} \ end {eqnarray *} [/ math]
Entonces ahora podemos escribir nuestra dirección:
[matemáticas] \ begin {eqnarray *} \ mathbf {d} _ {k} & = & \ mathbf {r} _ {k} – \ textrm {proj} _ {\ {\ mathbf {d} _ {1}, \ cdots, \ mathbf {d} _ {k-1} \}} ^ {\ mathbf {A}} (\ mathbf {r} _ {k}) \\ & = & \ mathbf {r} _ {k} – \ sum_ {i} ^ {k-1} \ frac {\ mathbf {r} _ {k} ^ {T} \ mathbf {A} \ mathbf {d} _ {i}} {\ mathbf {d} _ {i} ^ {T} \ mathbf {A} \ mathbf {d} _ {i}} \ mathbf {d} _ {i} \ end {eqnarray *} [/ math]
Realice un descenso de gradiente estándar, pero aplique un ajuste que garantice que las nuevas direcciones sean [math] \ mathbf {A} [/ math] -ortogonality a las antiguas.
Y ahora sabemos cómo producir nuestra serie de puntos * [matemática] \ {\ mathbf {x} _ {0}, \ mathbf {x} _ {1}, \ cdots, \ mathbf {x} _ {n} \ }[/matemáticas].
Sabemos cómo producir coeficientes y direcciones, ¡así que tenemos nuestra hoja de ruta hacia la solución!
Envolviendolo
Finalmente, el algoritmo toma la siguiente forma. Comience en un punto inicial y ejecute el siguiente procedimiento de un paso: calcule el residual, reste la proyección [math] \ mathbf {A} [/ math] de ese residual en las direcciones previamente viajadas, produciendo una dirección. Sabemos cómo viajar de manera óptima en esa dirección, así que hazlo. El algoritmo termina cuando el residuo es suficientemente pequeño. ** **
El método de gradiente conjugado se basa en las propiedades geométricas muy agradables de una matriz simétrica, positiva y definitiva [math] \ mathbf {A} [/ math]. Los explotamos al pensar en el espacio propio de [math] \ mathbf {A} [/ math], donde la solución se encuentra en el centro de una esfera. Debido a las propiedades de una esfera, podemos viajar muy rápidamente a la respuesta.
* Esto hace que parezca que producir cada [math] \ mathbf {d} _ {k} [/ math] requiere almacenar todas las direcciones antiguas y realizar muchas multiplicaciones de matriz de vectores. Afortunadamente, todos los términos de suma, excepto aquellos para los que [math] i = k-1 [/ math] son 0. Esto se debe a que [math] \ mathbf {r} _ {k} [/ math] se determina en un punto [math ] \ mathbf {x} _ {k} [/ math] para el que no podemos acercarnos a la solución explorando las direcciones exploradas previamente. Entonces, todo lo que no es cero de [math] \ mathbf {r} _ {k} [/ math] se debe a direcciones aún no exploradas: es [math] \ mathbf {A} [/ math] -ortogonal al direcciones exploradas.
** En la práctica, el algoritmo se ve un poco diferente de cómo se ha explicado. Las diferencias son el resultado de atajos computacionales que no son relevantes para la idea detrás del método CG.
Aprendí sobre CG de este gran recurso. Si desea fortalecer su intuición de álgebra lineal, le recomiendo leer esto.
