L’algorithme ADMM 

La méthode des multiplicateurs Pour résoudre le problème de recherche de pointselle (5.3), une première méthode, appelée méthode des multiplicateurs, a été proposée. Elle consiste `a alterner une minimisation partielle du lagrangien augmenté en les variables primales (x,z) et une étape de montée de gradient en la variable duale y. Cela conduit `a l’algorithme suivant : on initialise avec y0 ∈ Z ∗ , puis on effectue pour tout n ∈ N les mises-`a-jours suivantes    (xn+1,zn+1) = argmin (x,z)∈X×Z Lλ(x,yn,z) yn+1 = yn + σ ∂Lλ ∂y (xn+1,yn,zn+1) qui s’écrit encore    (xn+1,zn+1) = argmin (x,z)∈X×Z  G(x) + F(z) + hyn,K x − zi + 1 2 λ kK x − zk 2  yn+1 = yn + σ (K xn+1 − zn+1). On notera que la méthode des multiplicateurs, telle qu’elle est écrite ici, suppose l’existence d’un minimum unique pour la fonction (x,z) 7→ Lλ(x,yn,z), ce qui n’est a priori pas le cas. Directions alternées La méthode des multiplicateurs transforme le problème de minimisation du problème composite (5.1) en une série de problèmes de minimisations o`u les variables sont `a nouveau couplées, donc plus difficiles `a résoudre. Pour s’affranchir de cette difficulté, on peut choisir de remplacer la minimisation partielle du lagrangien en (x,z) en deux problèmes de minimisations séparées en x et z. Les deux minimisations peuvent se faire en parallèle `a partir de l’itération (xn,yn,zn) :    xn+1 = argmin x∈X Lλ(x,yn,zn) zn+1 = argmin z∈Z Lλ(xn,yn,z) ou bien, dans le cas de l’ADMM, de manière successive, en mettant `a jour l’une de deux variables primales entre les deux minimisations partielles, par exemple :    xn+1 = argmin x∈X Lλ(x,yn,zn) zn+1 = argmin z∈Z Lλ(xn+1,yn,z

Choix des paramètres

Le théorème 14 est valable tant qu’on parvient `a choisir les pas de temps τ et σ et le paramètre de relaxation θ qui satisfont les contraintes imposées. La valeur minimale des ω correspondant donne alors le taux de convergence de l’algorithme. On va étudier ici plusieurs choix possibles, ainsi que les taux de convergence associés. On procèdera de la manière suivante : 1. On fixe τ > 0. 2. On cherche les conditions sur σ pour que les inégalités (5.15) existent pour au moins un θ (i.e. pour que le membre de gauche soit inférieur au membre de droite). 3. On minimise la quantité (θ + 1)/(σδ + 2) par rapport `a θ vérifiant (5.15) et par rapport `a σ vérifiant les conditions déterminées `a l’étape précédente. 4. On compare ce minimum `a 1/(τ γ+1) puis on en déduit une borne inférieure ω ∗ (τ ) pour ω grâce `a (5.16). 5. On minimise enfin ω ∗ (τ ) par rapport `a τ puis on en déduit le taux optimal ω ∗ ainsi que le taux ω˜ correspondant sur la convergence des itérées. On adaptera évidemment cette procédure lorsqu’un ou plusieurs paramètres seront fixés au préalable.

Application `a l’ADMM

On commence par rappeler que les itérations de l’ADMM sont équivalentes aux itérations de l’algorithme PDHG avec sur-relaxation étudié dans la section précédente, mais appliqué `a un autre problème. Ainsi, on pourra utiliser les résultats de convergence pour en déduire le taux de convergence ergodique optimal d’ADMM. Par ailleurs, on remarquera qu’une légère relaxation d’un des pas dans l’ADMM permet théoriquement d’en accélérer la convergence.

Taux de convergence de l’ADMM classique

Utilisons le théorème 16 pour calculer le taux de convergence optimal de l’algorithme (5.41). Pour pouvoir l’appliquer, il nous faut tout d’abord vérifier que g est fortement convexe. Or, si G est fortement convexe (de paramètre γ), alors GK est fortement convexe, de paramètre γ/L2 . En effet, il est suffisant de montrer G ∗ K est différentiable et que son gradient ∇G ∗ K est lipschitzien de constante L 2 /γ (voir chapitre 1). C’est bien le cas ici car G ∗ K(y + h) = G ∗  K∗ (y + h)  = G ∗ (K∗ y + K∗h) = G ∗ (K∗ y) + h∇G ∗ (K∗ y),K∗hi +o(kK∗hk). Par conséquent, g est fortement convexe, de paramètre γ˜ = γ/L2 . On a par ailleurs par hypothèse que f ∗ est fortement convexe, de paramètre δ. On pose dans ce cas le conditionnement κ = (1/δ)/γ˜ = L 2 /(γδ).

Comparaison théorique avec FISTA et PDHG 

On peut comparer les taux théoriques obtenus pour chacun des quatre algorithmes considérés dans cette section, qui sont l’ADMM, l’ADMM modifié, PDHG sur-relaxé et FISTA (cas fortement convexe). Ainsi, la figure 5.1 affiche la valeur des taux théoriques minimaux en fonction du conditionnement. Ainsi, il apparaît que, comme prévu, l’ADMM classique affiche le taux le moins bon, que l’ADMM modifié et PDHG offrent le même taux, qui est légèrement moins bon que celui de FISTA. Tous les taux tendent vers 1 lorsque le problème est mal conditionné. 5.4.3 Premier test quadratique On commence dans ce paragraphe par comparer numériquement les performances de l’ADMM et de l’ADMM modifié sur un exemple simple.