Descente en gradient et descente en gradient conjugué

Pour un projet, je dois implémenter ces deux méthodes et comparer leurs performances sur différentes fonctions.

Il semble que la méthode du gradient conjugué soit destinée à résoudre des systèmes d'équations linéaires du for

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

Où est une matrice n par n symétrique, définie positive et réelle.$A$

D'un autre côté, quand je lis sur la descente de gradient, je vois l'exemple de la fonction Rosenbrock , qui est

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

Selon moi, je ne peux pas résoudre ce problème avec une méthode de gradient conjugué. Ou est-ce que je manque quelque chose?

La descente par gradient et la méthode du gradient conjugué sont deux algorithmes pour minimiser les fonctions non linéaires, c'est-à-dire des fonctions comme la fonction de Rosenbrock

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

ou une fonction quadratique multivariée (dans ce cas avec un terme quadratique symétrique)

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

Les deux algorithmes sont également itératifs et basés sur la direction de la recherche. Pour le reste de ce post, et seront des vecteurs de longueur ; et sont des scalaires, et les exposants indiquent l'indice d'itération. La descente de gradient et la méthode du gradient conjugué peuvent être utilisées pour trouver la valeur qui résoutd n f ( x ) α x $x$$d$$n$$f(x)$$\alpha$$x^*$

$\min f(x)$

Les deux méthodes partent d'une supposition initiale, , puis calculent l'itération suivante à l'aide d'une fonction du formulaire$x^0$

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

En d'autres termes, la valeur suivante de est trouvée en commençant à l'emplacement actuel et en se déplaçant dans la direction de recherche sur une certaine distance . Dans les deux méthodes, la distance à parcourir peut être trouvée par une recherche de ligne (minimisez sur ). D'autres critères peuvent également être appliqués. Là où les deux méthodes diffèrent, c'est dans leur choix de . Pour la méthode du gradient, . Pour la méthode du gradient conjugué, la procédure de Grahm-Schmidt est utilisée pour orthogonaliser les vecteurs de gradient. En particulier, , mais alors est égalx i d i α i f ( x i + α i d i ) α i d i d i = - ∇ f ( x i ) d 0 = - ∇ f ( x 0 ) d 1 - ∇ f ( x 1$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)$ moins la projection de ce vecteur sur telle que . Chaque vecteur de gradient suivant est orthogonalisé par rapport à tous les précédents, ce qui conduit à de très belles propriétés pour la fonction quadratique ci-dessus.$d^0$$(d^1)^Td^0 = 0$

La fonction quadratique ci-dessus (et les formulations associées) est également à l'origine de la discussion de la résolution de utilisant la méthode du gradient conjugué, car le minimum de cette est atteint au point où .$Ax = b$$f(x)$$x$$Ax = b$

Dans ce contexte, les deux méthodes peuvent être considérées comme des problèmes de minimisation de la fonction: Lorsque est symétrique, alors est minimisé lorsque .

$$\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}$

La descente en gradient est la méthode qui recherche de manière itérative un minimiseur en regardant dans la direction du gradient. Le gradient conjugué est similaire, mais les directions de recherche doivent également être orthogonales les unes aux autres dans le sens où .$\boldsymbol{p}_i^T\boldsymbol{A}\boldsymbol{p_j} = 0 \; \; \forall i,j$