Descenso de gradiente y descenso de gradiente conjugado

Para un proyecto, tengo que implementar estos dos métodos y comparar cómo funcionan en diferentes funciones.

Parece que el método de gradiente conjugado está destinado a resolver sistemas de ecuaciones lineales de

$$A\mathbf{x} = \mathbf{b}$$

Donde es una matriz n-por-n que es simétrica, positiva definida y real.$A$

Por otro lado, cuando leo sobre el gradiente de descenso , veo el ejemplo de la función Rosenbrock , que es

$$f(x_1,x_2) = (1-x_1)^2+100(x_2-x_1^2)^2$$

Tal como lo veo, no puedo resolver esto con un método de gradiente conjugado. ¿O extraño algo?

El descenso gradual y el método de gradiente conjugado son algoritmos para minimizar las funciones no lineales, es decir, funciones como la función de Rosenbrock

$f(x_1,x_2) = (1-x_1)^2 + 100(x_2 - x_1^2)^2$

o una función cuadrática multivariada (en este caso con un término cuadrático simétrico)

$f(x) = \frac{1}{2} x^T A^T A x - b^T A x.$

Ambos algoritmos también son iterativos y están basados ​​en la dirección de búsqueda. Para el resto de esta publicación, y serán vectores de longitud ; y son escalares, y los superíndices denotan el índice de iteración. El descenso de gradiente y el método de gradiente conjugado se pueden usar para encontrar el valor que resuelve$x$$d$$n$$f(x)$$\alpha$$x^*$

$\min f(x)$

Ambos métodos comienzan desde una suposición inicial, , y luego calculan la siguiente iteración usando una función de la forma$x^0$

$x^{i+1} = x^i + \alpha^i d^i.$

En palabras, el siguiente valor de se encuentra comenzando en la ubicación actual , y moviéndose en la dirección de búsqueda para cierta distancia . En ambos métodos, la distancia para moverse se puede encontrar mediante una búsqueda de línea (minimice sobre ). También se pueden aplicar otros criterios. Donde los dos métodos difieren es en su elección de . Para el método de gradiente, . Para el método de gradiente conjugado, el procedimiento de Grahm-Schmidt se utiliza para ortogonalizar los vectores de gradiente. En particular, , pero entonces es igual$x$$x^i$$d^i$$\alpha^i$$f(x^i + \alpha^i d^i)$$\alpha_i$$d^i$$d^i = -\nabla f(x^i)$$d^0 = -\nabla f(x^0)$$d^1$$-\nabla f(x^1)$ menos la proyección de ese vector en tal que . Cada vector de gradiente posterior se ortogonaliza frente a todos los anteriores, lo que conduce a propiedades muy buenas para la función cuadrática anterior.$d^0$$(d^1)^Td^0 = 0$

La función cuadrática anterior (y las formulaciones relacionadas) también es de donde proviene la discusión de resolver usando el método de gradiente conjugado, ya que el mínimo de esa se logra en el punto donde .$Ax = b$$f(x)$$x$$Ax = b$

En este contexto, ambos métodos pueden considerarse problemas de minimización de la función: Cuando es simétrico, entonces se minimiza cuando .

$$\phi(\boldsymbol{x}) = \frac{1}{2}\boldsymbol{x}^T\boldsymbol{A}\boldsymbol{x} - \boldsymbol{x}^T\boldsymbol{b}$$ $\boldsymbol{A}$$\phi$$\boldsymbol{A}\boldsymbol{x} = \boldsymbol{b}$

El descenso de gradiente es el método que busca iterativamente un minimizador al mirar en la dirección del gradiente. El gradiente conjugado es similar, pero las direcciones de búsqueda también deben ser ortogonales entre sí en el sentido de que .$\boldsymbol{p}_i^T\boldsymbol{A}\boldsymbol{p_j} = 0 \; \; \forall i,j$