Algorithme de descente par coordonnées[modifier | modifier le code]

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[modifier | modifier le code]

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.

Choix de la direction de descente $i_{t}\in [1,n]$ .
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[modifier | modifier le code]

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^[1], 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[modifier | modifier le code]

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.

Calcul des mises à jour[modifier | modifier le code]

Minimisation[modifier | modifier le code]

Gradient[modifier | modifier le code]

Résultats de convergence[modifier | modifier le code]

Choix de coordonnées cyclique[modifier | modifier le code]

Choix de coordonnées aléatoire[modifier | modifier le code]

Intérêt[modifier | modifier le code]

↑ (en) M. J. D. Powell, « On search directions for minimization algorithms », Mathematical Programming, vol. 4, n^o 1,‎ 1^er décembre 1973, p. 193–201 (ISSN 1436-4646, DOI 10.1007/BF01584660, lire en ligne, consulté le 16 avril 2021)

[1] (en) M. J. D. Powell, « On search directions for minimization algorithms », Mathematical Programming, vol. 4, n^o 1,‎ 1^er décembre 1973, p. 193–201 (ISSN 1436-4646, DOI 10.1007/BF01584660, lire en ligne, consulté le 16 avril 2021)

[1]