Utilisateur:Pamango/Brouillon Descente Coordonnees

Algorithme de descente par coordonnées

L'algorithme de descente par coordonnées désigne un algorithme d'optimisation. Il vise à minimiser une fonction à valeurs réelles définie sur un espace euclidien comme $\mathbb {R} ^{n}$ en la minimisant itérativement selon chacune de ses coordonnées.

C'est un cas particulier d'Algorithme à directions de descente, où les directions de descente possibles sont limitées à chacune des coordonnées de la fonction.

L'algorithme

L'algorithme de descente par coordonnées repose sur l'idée que minimiser la valeur d'une fonction selon une seule de ses variable est généralement un problème plus simple que de la minimiser directement.

Algorithme de descente par coordonnées — Soit une fonction $f:\mathbb {R} ^{n}\rightarrow \mathbb {R}$, un point initial $x_{0}\in \mathbb {R} ^{n}$ et nombre total d'itérations $T$. L'algorithme de descente par coordonnées définit une suite d'itérés $x^{1},x^{2},\ldots \in \mathbb {E}$, jusqu'à ce qu'un test d'arrêt soit satisfait. Tant que $t<T$, il passe de $x^{t}$ à $x^{t+1}$ par les étapes suivantes.

1. Choix de la direction de descente $i_{t}\in [1,n]$.
2. Descente $x^{t+1}=\arg \min _{\gamma \in \mathbb {R} }f(x_{1}^{t},\dots ,x_{i_{t}-1}^{t},\gamma ,x_{i_{t}+1}^{t},\dots ,x_{n}^{t})$.

En pratique, la minimisation de chaque coordonnée n'a pas besoin d'être exacte pour que l'algorithme soit efficace. Pour les fonctions différentiables, une version populaire de l'algorithme se rapprochant de l'algorithme du gradient consiste à effectuer un pas de gradient selon la coordonnée choisie.

L'exemple de Powell

En l'absence d'hypothèses de régularité sur la fonction minimisée, l'algorithme de descente par coordonnées ne converge pas nécessairement. Il peut en effet arriver que l'algorithme reste bloqué dans une boucle infinie, c'est le cas notamment pour la fonction :

$$f(x_{1},x_{2},x_{3})=-(x_{1}x_{2}+x_{2}x_{3}+x_{1}x_{3})+\sum _{i=1}^{3}\max(|x_{i}|-1,0)^{2}.$$

En revanche, notamment si la fonction minimisée est convexe, l'algorithme converge vers le minimum global de la fonction.

Choix de la direction de descente

Un choix de coordonnée naturel est le choix cylique les coordonnées, c'est-à-dire $i_{t+1}=i_{t}+1\%n$. C'est souvent ce qui est fait dans l'implémentation de l'algorithme. Cependant, cela rend la preuve de convergence de l'algorithme plus difficile.

Une variante de l'algorithme consiste à choisir la coordonnée à mettre à jour en la tirant selon un certaine distribution $p$ sur $[1,n]$. Cela permet notamment de mettre à jour plus souvent les coordonnées selon lesquels la fonction diminue plus vite, et a été très étudié en théorie, notamment parce qu'il facilite la preuve de convergence de l'algorithme.