CAMA : ma40 Méthode du gradient conjugué

Cours du 24 / 05

Méthode du gradient conjugue

Si on a calculé le

$\mu$ optimal alors la plus forte pente

$\mathrm{\nabla }J({\mathbf{x}}^{k+1})$ sera orthogonale à la pente qui définie la droite sur laquelle on cherche

$\mu$. On a donc

$$\mathrm{\nabla }J({\mathbf{x}}^{k+1}{)}^T.\mathrm{\nabla }J({\mathbf{x}}^k)=0$$
Le minimum suivant

${\mathbf{x}}^{\mathbf{k}\mathbf{+}\mathbf{2}}$ sera le minimum de l'espace généré par

$\mathrm{\nabla }J({\mathbf{x}}^{k+1})$ et

$\mathrm{\nabla }J({\mathbf{x}}^k)$.

On ne sait pas si

${\mathbf{x}}^{\mathbf{k}\mathbf{+}\mathbf{3}}$ sera calculé le long de la direction

$\mathrm{\nabla }J({\mathbf{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

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

La fonctionnelle à minimiser est :

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

• Si A est symétrique, son gradient est
  $\mathrm{\nabla }J(\mathbf{x})=A\mathbf{x}-\mathbf{b}$

Si on calcule

${\mathbf{x}}^{\mathbf{k}}$ comme avant on a l'orthogonnalité de 2 directions successives.

Que se passe-t-il si

${\mathbf{x}}^{\mathbf{k}}\mathbf{+}\mathbf{1}$ minimise

$J$ dans l'espace

$G_k$ généré par toutes les directions précédentes ?

$$J({\mathbf{x}}^{k+1})=\underset{\mathbf{v}\in {\mathbf{G}}_{\mathbf{k}}}{min}J({\mathbf{x}}^k+\mathbf{v})$$
avec

${\mathbf{G}}_{\mathbf{k}}=span\{{\mathbf{d}}^0,{\mathbf{d}}^1,\dots ,{\mathbf{d}}^k\}=\{\mathbf{v}=\sum _{i=0}^k{\alpha }_i{\mathbf{d}}^i\mathrm{\forall }{\alpha }_i\in ℝ\}$.

Toutes les dérivées partielles par rapport aux vecteurs de

${\mathbf{G}}_{\mathbf{k}}$ sont nulles :

$$\mathrm{\nabla }J({\mathbf{x}}^{k+1}).\mathbf{w}=0\mathrm{\forall }\mathbf{w}\in {\mathbf{G}}_{\mathbf{k}}$$

Cela se vérifie si

$\mathbf{w}$ est un des vecteurs de la base:

$$\mathrm{\nabla }J({\mathbf{x}}^{k+1}).{\mathbf{e}}_i=\left[\begin{array}{c}\partial J/\partial x_1\\ \partial J/\partial x_2\\ ⋮\\ \partial J/\partial x_i\\ ⋮\\ \partial J/\partial x_n\end{array}\right].\left[\begin{array}{c}0\\ 0\\ ⋮\\ 1\\ ⋮\\ 0\end{array}\right]=\frac{\partial J}{\partial x_i}({\mathbf{x}}^{k+1})$$

La dérivée partielle de

$J$ dans une direction

$\mathbf{w}$ de

${\mathbf{G}}_{\mathbf{k}}$ est nulle revient a dire

$\mathrm{\nabla }J({\mathbf{x}}^{k+1})$ est orthogonal à

$\mathbf{w}$.

Générer les directions

${\mathbf{d}}^i$

La formule itérative devient :

$${\mathbf{x}}^{k+1}={\mathbf{x}}^k-{\mu }^k{\mathbf{d}}^k$$

• Pour calculer les
  ${\mathbf{d}}^k$ on utilise la formule des dérivées partielles de
  $J$ par rapport à un vecteur
  $\mathbf{w}\in {\mathbf{G}}_{\mathbf{k}}$ où elles sont nulles.
• ${\mathbf{d}}^i$ génèrent l'espace
  ${\mathbf{G}}_{\mathbf{k}}$, il suffit que les dérivées partielles de
  $J$ par rapport
  ${\mathbf{d}}^i$ soient nulles
  
  $$\mathrm{\nabla }J({\mathbf{x}}^{k+1}).{\mathbf{d}}^i=0\mathrm{\forall }i\le k(1)$$

En déroulant les calculs on obtient :

$$\begin{array}{rl}\mathrm{\nabla }J({\mathbf{x}}^k).{\mathbf{d}}^i-{\mu }^{k}A{\mathbf{d}}^k.{\mathbf{d}}^i& =0\mathrm{\forall }i\le k\end{array}$$

• Si
  $i<k$, le premier terme est nul :
  $$A{\mathbf{d}}^k.{\mathbf{d}}^i=0\mathrm{\forall }i<k(2)$$
  • On a les conditions pour construire la nouvelle direction
    ${\mathbf{d}}^k$
    $${\mathbf{d}}^k=\mathrm{\nabla }J({\mathbf{x}}^k)-\sum _{i=0}^{k-1}\frac{A\mathrm{\nabla }J({\mathbf{x}}^k).{\mathbf{d}}^i}{A{\mathbf{d}}^i.{\mathbf{d}}^i}{\mathbf{d}}^i$$
• Si
  $i=k$, on obtient la valeur nécessaire
  ${\mu }^k$ pour garantir que
  $\mathrm{\nabla }J({\mathbf{x}}^{k+1}).{\mathbf{d}}^k=0$ :
  $${\mu }^k=\frac{\mathrm{\nabla }J({\mathbf{x}}^k).{\mathbf{d}}^k}{A{\mathbf{d}}^k.{\mathbf{d}}^k}=\frac{(A{\mathbf{x}}^k-b).{\mathbf{d}}^k}{A{\mathbf{d}}^k.{\mathbf{d}}^k}$$

Propriété

L'ensemble des gradients de

$J$ aux points

${\mathbf{x}}^{\mathbf{i}}$ forment une base de l'espace

${\mathbf{G}}_{\mathbf{k}}$ :

$$\mathrm{\nabla }J({\mathbf{x}}^{k+1})\perp \mathrm{\nabla }J({\mathbf{x}}^i)\mathrm{\forall }i\le k$$