Lien de la note Hackmd
Cours du 24 / 05
Méthode du gradient conjugue
Si on a calculé le $\mu$ optimal alors la plus forte pente $\nabla J ({\bf x}^{k+1})$ sera orthogonale à la pente qui définie la droite sur laquelle on cherche $\mu$. On a donc \(\nabla J ({\bf x}^{k+1})^T \, . \, \nabla J ({\bf x}^k) = 0\) Le minimum suivant ${\bf x^{k+2}}$ sera le minimum de l’espace généré par $\nabla J ({\bf x}^{k+1})$ et $\nabla J ({\bf x}^k)$.
On ne sait pas si ${\bf x^{k+3}}$ sera calculé le long de la direction $\nabla J ({\bf x}^k)$.
Une recherche optimale du minimum d’une fonction convexe dans un espace $\mathbb{R}^n$ ne devrait pas prendre plus de $n$ itérations si on est capable de calculer le $\mu$ optimal dans la direction choisie. On cherche le minimum dans les directions des vecteurs de la base de notre espace $\mathbb{R}^n$ afin de trouver le minimum global.
Générer une base de $\mathbb{R}^n$
Si on veut trouver notre minimum global en $n$ itérations au maximum, il faut que nos directions ne soient pas redondantes et que les $n$ premières directions génèrent $\mathbb{R}^n$ ou en forment une base. La nouvelle direction $d^k$ doit être orthogonale à toutes les directions précédentes et permet de trouver une base qui génère un espace de dimension $k + 1$.
Le cas ${\bf Ax = b}$
La fonctionnelle à minimiser est : \(J({\bf x}) = \frac{1}{2} \, {\bf x}^T \, A \, {\bf x} - {\bf b}\, . {\bf x}\)
- Si A est symétrique, son gradient est $\nabla J({\bf x}) = A \; {\bf x} - {\bf b}$
Si on calcule ${\bf x^k}$ comme avant on a l’orthogonnalité de 2 directions successives.
Que se passe-t-il si ${\bf x^k+1}$ minimise $J$ dans l’espace $G_k$ généré par toutes les directions précédentes ? \(J({\bf x}^{k+1}) = \min_{\bf v \in G_k} J({\bf x}^k + {\bf v})\) avec ${\bf G_k} = span{ {\bf d}^0, {\bf d}^1,\dots, {\bf d}^k} = \left{ {\bf v} = \sum_{i=0}^{k} \alpha_i \, {\bf d}^i \quad \forall \alpha_i \in ℝ \right}$.
Toutes les dérivées partielles par rapport aux vecteurs de ${\bf G_k}$ sont nulles : \(\nabla J({\bf x}^{k+1}) \, . \, {\bf w} = 0 \quad \forall {\bf w} \in {\bf G_k}\)
La dérivée partielle de $J$ dans une direction ${\bf w}$ de ${\bf G_k}$ est nulle revient a dire $\nabla J({\bf x}^{k+1})$ est orthogonal à ${\bf w}$.
Générer les directions ${\bf d}^i$
La formule itérative devient : \({\bf x}^{k+1} = {\bf x}^k - µ^k\, {\bf d}^k\)
- Pour calculer les ${\bf d}^k$ on utilise la formule des dérivées partielles de $J$ par rapport à un vecteur ${\bf w \in G_k}$ où elles sont nulles.
- ${\bf d}^i$ génèrent l’espace ${\bf G_k}$, il suffit que les dérivées partielles de $J$ par rapport ${\bf d}^i$ soient nulles \(\nabla J({\bf x}^{k+1}) \, . \, {\bf d}^i = 0 \quad \forall i \le k \qquad (1) \\\)
En déroulant les calculs on obtient : \(\begin{align} \nabla J({\bf x}^{k}) \, . \, {\bf d}^i - µ^k \, A \, {\bf d}^k \, . \, {\bf d}^i &= 0 \quad \forall i \le k \\ \end{align}\)
- Si $i \lt k$, le premier terme est nul : \(A \, {\bf d}^k \, . \, {\bf d}^i = 0 \quad \forall i < k \qquad (2)\)
- On a les conditions pour construire la nouvelle direction ${\bf d}^k$ \({\bf d}^k = \nabla J({\bf x}^k) - \sum_{i=0}^{k-1} \frac{A\, \nabla J({\bf x}^k) \, . \, {\bf d}^i} {A\, {\bf d}^i \, . \, {\bf d}^i} \; {\bf d}^i\)
- Si $i =k$, on obtient la valeur nécessaire $µ^k$ pour garantir que $\nabla J({\bf x}^{k+1}) \, . \, {\bf d}^k = 0$ : \(µ^k = \frac{\nabla J({\bf x}^{k}) \, . \, {\bf d}^k} {A \, {\bf d}^k \, . \, {\bf d}^k} = \frac{(A \, {\bf x}^{k} - b) \, . \, {\bf d}^k} {A \, {\bf d}^k \, . \, {\bf d}^k} \\ \,\)
Propriété
L’ensemble des gradients de $J$ aux points $\bf{x}^i$ forment une base de l’espace ${\bf G_k}$ : \(\nabla J({\bf x}^{k+1}) \perp \nabla J({\bf x}^i) \quad \forall i \le k\)