5mm71 : Méthodes du premier ordre pour l’optimisation...

Sorbonne Université

Module B6
Éclatement de variables

Sauf mention contraire, X (resp. Y) est un espace de Hilbert, muni du produit

scalaire noté ⟨·, ·⟩ et on note ∥ · ∥ la norme qui découle du produit scalaire.
Dans ce module, on s’intéresse au problème de minimisation suivant
min J(x(1) , . . . , x(n) ) (P)
x=(x(1) ,...,x(n) )∈X1 ×···×Xn

où J : X1 × · · · × Xn → R ∪ {+∞} est une fonction s.c.i. de domaine non vide. On

supposera que ce problème admet au moins une solution.

1 Principe et observations
Dans les applications actuelles de l’optimisation continue, on est amené à gérer des
problèmes de dimension toujours plus grande. La dimension du problème s’entend ici
comme la dimension de l’espace X sur lequel la fonction objectif est optimisée 1 Dans
ces conditions, minimiser directement sur X peut s’avérer techniquement difficile, voire
impossible, ou très coûteux en calculs. L’idée est donc, si le problème le permet, de
réduire la dimension du problème en le scindant en plusieurs problèmes de dimensions
plus petites.
Une stratégie classique et intuitive, que l’on va explorer dans ce module, est de
considérer une stratégie itérative, où à chaque itération, on “gèle” une partie de l’espace X
pour considérer un problème qui est mécaniquement de dimension plus petite. Une fois
ce sous-problème “traité” (plusieurs traitements vont être considérés dans les sections qui
suivent), on met à jour la variable sur laquelle le sous-problème est défini, puis on change
de sous-problème (et de variable associée). Formellement, cela revient à décomposer
l’espace X en n sous-espaces :
X = X1 × · · · × Xn
puis à considérer successivement les problèmes suivants :


min J (x(1) )k+1 , . . . , (x(ℓ−1) )k+1 , x(ℓ) , (x(ℓ+1) )k , . . . , (x(n) )k
x(ℓ) ∈Xℓ

où (x(i) )k correspond à un état donné d’une des sous-variables du problème. Dans cette
configuration, la mise-à-jour est cyclique et déterministe (on choisit un ordre et on s’y
tient). D’autres modes de mises-à-jour peuvent être envisagés, comme le choix d’un ordre
aléatoire pour l’ordre des mises-à-jour. Toutefois, on s’astreint généralement à parcourir
toutes les variables avant de mettre à jour à nouveau une variable. En pratique, l’ordre
aléatoire s’avère plus efficace ; toutefois, pour des raisons de lisibilité, on ne considère ici
que l’ordre cyclique déterministe.
Toujours pour des raisons de lisibilité, on considèrera le problème à deux blocs (n = 2)
min J(x, z) (P2 blocs )
X=(x,z)∈X ×Z
1. Un exemple simple est le traitement d’une image, pour lequel la dimension peut être le nombre de
pixels. L’avènement des appareils photos haute résolution et des écrans hautes résolutions conduisent à
travailler avec des nombres de pixels de plus en plus grands.

Pauline Tan 1 V2.9.2023

5mm71 : Méthodes du premier ordre pour l’optimisation... Sorbonne Université

2 Minimisation alternée ou block-coordinate descent

2.1 Position du problème
On considère le problème (P2 blocs ), dans le cas où chaque fonction partielle
x 7→ J(x, z) et z 7→ J(x, z)
admet un minimiseur pour tout z ∈ Z et x ∈ X respectivement (si son domaine n’est
pas vide) et que ceux-ci sont calculables de manière exacte.
Discutons des conditions d’existence de minimiseurs. Si J est coercive et s.c.i, alors
il est aisé de vérifier que c’est également le cas de ses fonctions partielles. Dans ce
cas, l’existence des minimiseurs est assurée. Une condition plus faible que la coercivité,
mais qui suffira pour cette section, est l’existence d’un point (x0 , z 0 ) ∈ X × Z tel que
l’ensemble niv≤J(x0 ,z0 ) J soit borné. Dans ce cas, pour tout X = (x, z) ∈ niv≤J(x0 ,z0 ) J,
les ensembles de sous-niveau partiels
n o n o
x′ ∈ X | J(x′ , z) ≤ J(x, z) et z ′ ∈ Z | J(x, z ′ ) ≤ J(x, z)
sont bornés, et les fonctions partielles (s.c.i.) x 7→ J(x, z) et z 7→ J(x, z) admettent un
minimiseur z ∗ et x∗ respectivement.

2.2 Algorithme BCD

L’algorithme BCD (pour Block-Coordinate Descent) est la stratégie la plus intuitive
pour résoudre le problème (P2 blocs ) sous les conditions imposées plus haut. Il s’agit
tout simplement d’alterner des minimisations partielles de la fonction J, c’est-à-dire de
considérer les itérations suivantes : 

xk+1 ∈ argmin J x, zk

x∈X
z0 ∈ Z et ∀ k ∈ N,

zk+1 ∈ argmin J xk+1 , z

z∈Z
Notons que les itérées ne sont en général pas définies de manière unique. Pour garantir
leur unicité, la continuité et la coercivité des fonctions partielles suffit.
Pour que les itérées soient bien définies, il suffit que z0 soit choisi de sorte que
dom J(·, z0 ) ̸= ∅ soit ∃ x ∈ X1 , J(x, z0 ) ∈ R

2.3 Propriétés de convergence

Proposition 1 (Convergence du critère)

Soit J : X × Z → R ∪ {+∞}. On suppose qu’il existe (x0 , z 0 ) ∈ dom J

tel que l’ensemble de sous-niveau niv≤J(x0 ,z0 ) J soit borné. On considère la
suite ((xk , zk ))k∈N générée par l’algorithme


xk+1 ∈ argmin J x, zk

x∈X
∀ k ∈ N,

zk+1 ∈ argmin J xk+1 , z

z∈Z

Alors les suites (J(xk , zk ))k∈N et (J(xk+1 , zk ))k∈N sont décroissantes et

convergent vers la même limite.

Démonstration : Il est immédiat que, par optimalité, on a pour tout k ∈ N

J xk+1 , zk ≤ J xk , zk

Pauline Tan 2 V2.9.2023

5mm71 : Méthodes du premier ordre pour l’optimisation... Sorbonne Université

et



J xk+1 , zk+1 ≤ J xk+1 , zk
Les deux suites considérées dans la proposition 1 sont donc décroissantes et minorées,
et par conséquent convergentes. L’identité de leur limite découle de l’encadrement




J xk+1 , zk+1 ≤ J xk+1 , zk ≤ J xk , zk
qui permet de conclure par comparaison. ■

La règle de Fermat assure que les points générés par l’algorithme BCD vérifient



0 ∈ ∂x J xk+1 , zk et 0 ∈ ∂z J xk+1 , zk+1
Lorsque J satisfait les hypothèses de la proposition 1, les deux suites



(xk+1 , zk ) k∈N et (xk , zk ) k∈N
sont bornées, donc admettent chacune une sous-suite qui converge. Notons (x∗ , z ∗ )
et (x̃∗ , z̃ ∗ ) les deux limites respectives. Si, de plus, J est continue, alors
lim J xkj +1 , zkj = J(x∗ , z ∗ ) lim J xk̃j , zk̃j = J(x̃∗ , z̃ ∗ )



et
j→+∞ j→+∞

Ainsi, si les sous-différentiels partiels sont fermés, alors on a

0 ∈ ∂x J x∗ , z ∗ 0 ∈ ∂z J x̃∗ , z̃ ∗



et
Notons que, par unicité de la limite, on a J(x∗ , z ∗ ) = J(x̃∗ , z̃ ∗ ).
Pour aller au-delà de ce premier résultat, il faut faire des hypothèses supplémentaires
sur le problème. Si on suppose que
∀ (x, z) ∈ X × Z, J(x, z) = f (x, z) + χC1 (x) + χC2 (z)
avec f une fonction continûment différentiable, alors les remarques précédentes se tra-
duisent de la manière suivante :
∂J
∂J

xk+1 , zk = 0 et xk+1 , zk+1 = 0
∂x ∂z
Lemme 1

Soit J : X × Z → R ∪ {+∞} une fonction continûment différentiable sur son

domaine. On suppose qu’il existe (x0 , z 0 ) ∈ dom J tel que l’ensemble de sous-
niveau niv≤J(x0 ,z0 ) J soit borné. On considère la suite ((xk , zk ))k∈N générée par
l’algorithme 

xk+1 ∈ argmin J x, zk

x∈X1
∀ k ∈ N,

zk+1 ∈ argmin J xk+1 , z

z∈X2

On suppose que la suite (xk )k∈N est convergente. Alors la suite ((xk , zk ))k∈N est
bornée et admet une sous-suite qui converge. De plus, toute sous-suite conver-
gente de ((xk , zk ))k∈N converge vers un point critique de J.

Démonstration : Par hypothèse, la suite ((xk , zk ))k∈N est bornée. On suppose que
la suite (xkj , zkj )j∈N est convergente, de limite (x∗ , z ∗ ). Alors
∂J
∂J ∗ ∗

0 = lim xkj , zkj = x ,z
j→+∞∂x ∂x
La convergence de la suite des xk implique que
lim xkj +1 , zkj = x∗ , z ∗



j→+∞

Pauline Tan 3 V2.9.2023

5mm71 : Méthodes du premier ordre pour l’optimisation... Sorbonne Université

Par continuité de ∇J, on en déduit que

∂J
∂J ∗ ∗

0 = lim xkj +1 , zkj = x ,z
j→+∞ ∂z ∂z
∗ ∗
Autrement dit, (x , z ) est un point critique de J. ■

Avant de poursuivre, on va montrer que, si J est convexe mais non différentiable,

l’algorithme BCD peut ne pas converger vers un point critique.
Contre-exemple
Non-convergence vers le minimiseur dans le cas non différentiable.
On considère le cas où X = Z = R avec
J(x, z) = |x + z| + 2 |x − z|
Il est aisé de vérifier que, comme combinaison linéaire à coefficients positifs de
combinaisons d’une fonction convexe (la valeur absolue) avec une forme linéaire,
la fonction J est convexe. Appliquons l’algorithme BCD à la minimisation de
cette fonction. Les itérations s’écrivent
 n o
xk+1 ∈ argmin |x + zk | + 2 |x − zk |

x∈R n
∀ k ∈ N, o
zk+1 ∈ argmin |xk+1 + z| + 2 |xk+1 − z|

z∈R

On voit qu’il s’agit dans les deux cas de minimiser la fonction strictement
convexe, continue, affine par morceaux et coercive fa , avec
∀ t ∈ R, fa (t) = |t + a| + 2 |t − a|
Un simple calcul montre que, si a ≥ 0, alors

−3 t + a si t ≤ −a

∀ t ∈ R, fa (t) = −t + 3 a si |t| ≤ a

3t − a si t ≥ a


de sorte que son minimiseur se trouve parmi les deux points a et −a ; or,
puisque fa (a) = 2 a et que fa (−a) = 4 a, il s’ensuit que le minimiseur vaut a.
Ainsi, si z0 > 0, on démontre par récurrence que, pour tout k ∈ N,
xk+1 = zk+1 = x0
La suite générée par l’algorithme BCD est donc constante et convergente, de
limite (x0 , x0 ). Or, il est visible que ce point n’est pas un minimiseur de J, qui
atteint son minimum en (0, 0). Selon la règle de Fermat, ce n’est pas non plus
un point critique.

En réalité, dans l’exemple qui précède, l’algorithme, lorsqu’il n’est pas correctement
initialisé (c’est-à-dire si z0 ̸= 0), ne converge pas vers un point critique, mais un point
vérifiant la double inclusion



0 ∈ ∂x J x, z et 0 ∈ ∂z J x, z
Or, on a vu qu’en général, ces points sont différents des points critiques de J, sauf lorsque
le terme couplant les deux variables est continûment différentiable.
Une conséquence immédiate du lemme précédent est la convergence de la suite des
itérées vers un point critique lorsque cette suite est convergente. En réalité, une condition
importante pour assurer la convergence de l’algorithme BCD est l’unicité des itérées. On
peut en effet considérer l’exemple suivant :

Pauline Tan 4 V2.9.2023

5mm71 : Méthodes du premier ordre pour l’optimisation... Sorbonne Université

Contre-exemple
Non-unicité des itérées. On considère le cas où X = Z = R avec
 n o
max min{1, |x|}, min{1, |z|}


J(x, z) = si (x, z) ∈ [ −1 ; 1 ] × [ −1 ; 1 ]


+∞ sinon
La fonction J admet visiblement un unique minimum, atteint en (0, 0) et qui
vaut 0. Il est aisé de vérifier que si z ∈ {−1, 1}, alors J(x, z) = 1 pour tout x ∈
[ −1 ; 1 ], et vaut +∞ pour x ∈ / [ −1 ; 1 ] (et on démontre un résultat analogue
lorsque x ∈ {−1, 1}). On peut donc initialiser l’algorithme BCD avec z0 = 1 ;
dans ce cas, tout le segment [ −1 ; 1 ] est éligible pour fournir le point suivant x1 .
Si on choisit x1 = 1, alors on peut cette fois choisir n’importe quel point
dans [ −1 ; 1 ] pour définir le point z1 . On voit donc qu’il est possible avec l’algo-
rithme BCD de générer la suite constante égale à (1, 1). Celle-ci est convergente,
mais ne converge pas vers le minimiseur de J. En revanche, si on avait choisit,
avec la même initialisation, x1 = 0, puis z1 = 0, l’algorithme convergerait en
une seule itération avec le minimiseur de J.

Dans la proposition suivante, on considère le cas biconvexe et continue, sous l’hypo-

thèse que les itérées sont définies de manière unique (l’algorithme BCD est alors éga-
lement désigné par le nom ACS ou Alternate Convex Search car chaque sous-problème
d’optimisation est un problème d’optimisation convexe) :

Proposition 2 (Alternate Convex Search)

Soit J : X × Z → R ∪ {+∞} une fonction continue sur son domaine et bi-

convexe. On suppose que dom J = C1 × C2 où C1 ⊂ X et C2 ⊂ Z sont des
ensembles convexes et fermés. On suppose qu’il existe (x0 , z 0 ) ∈ dom J tel que
l’ensemble de sous-niveau niv≤J(x
,z ) J soit borné, et que pour tout z ∈ Z,
0 0

la fonction partielle x 7→ J x, z est strictement convexe. On considère la

suite ((xk , zk ))k∈N générée par l’algorithme


xk+1 = argmin J x, zk

x∈X
∀ k ∈ N,

zk+1 = argmin J xk+1 , z

z∈Z

Alors la suite ((xk , zk ))k∈N est bornée et admet une sous-suite qui converge.
Par ailleurs, la limite (x∗ , z ∗ ) de toute sous-suite convergente de ((xk , zk ))k∈N
vérifie
0 ∈ ∂x J(x∗ , z ∗ ) et 0 ∈ ∂z J(x∗ , z ∗ )
Si, de plus, il existe une décomposition de J de la forme
∀ (x, z) ∈ X × Z, J(x, z) = f (x) + g(z) + h(x, z)
où h est continûment différentiable autour de (x∗ , z ∗ ), alors (x∗ , z ∗ ) est un point
critique de J.

Démonstration : Par hypothèse, la suite ((xk , zk ))k∈N est bornée. On suppose que
la sous-suite ((xkj , zkj ))j∈N est convergente, de limite (x∗ , z ∗ ). Puisque les (xk , zk )
sont dans le domaine de J, et que celui-ci est fermé, il s’ensuit que
lim J(xk , zk ) = lim J(xkj , zkj ) = J(x∗ , z ∗ )
k→+∞ j→+∞

Pauline Tan 5 V2.9.2023

5mm71 : Méthodes du premier ordre pour l’optimisation... Sorbonne Université

• La suite des ∥(xkj +1 , zkj +1 ) − (xkj , zkj )∥ tend vers 0. Par l’absurde, suppo-
sons que ce n’est pas le cas. Alors, en posant
∀ j ∈ N, δj = ∥(xkj +1 , zkj +1 ) − (xkj , zkj )∥
on suppose que la suite (δj )j∈N ne converge pas vers 0. Comme elle est par
ailleurs bornée (car la suite ((xk , zk ))k∈N l’est), elle admet donc une sous-
suite (δjℓ )ℓ∈N qui converge vers un certain α > 0. Pour tout ℓ ∈ N, définissons
le point xkjℓ +1 − xkjℓ
sℓ = ∈X
δjℓ
Puisque ces points appartiennent à la boule fermée unité, qui est compacte
dans X , la suite des sℓ admet une sous-suite (sℓm )m∈N convergente ; notons s∗
sa limite. Pour tout m ∈ N, posons


fm : x 7→ J x, zkjℓ
m

Par hypothèse, cette fonction est strictement convexe et atteint son unique
minimum en xkjℓ +1 . Remarquons que
m

∀ m ∈ N, xkjℓ +1 = xkjℓ + δjℓm sℓm ∈ C1

m m

Soit λ ∈ [ 0 ; 1 ]. On a
λ xkjℓ +1 + (1 − λ) xkjℓ = xkjℓ + λ δjℓm sℓm ∈ C1
m m m

Par convexité et optimalité, on en déduit que

fm xkjℓ + λ δjℓm sℓm ≤ λ fm xkjℓ +1 + (1 − λ) fm xkjℓ
m m m



≤ λ fm xkjℓ + (1 − λ) fm xkjℓ
m m

On a donc l’encadrement




fm xkjℓ +1 ≤ fm xkjℓ + λ δjℓm sℓm ≤ fm xkjℓ
m m m

En revenant à la définition de fm , et en vertu de la proposition 1, on a

= J(x∗ )



lim fm xkjℓ +1 = lim fm xkjℓ
m→+∞ m m→+∞ m

Ainsi, par encadrement, on a démontré que, pour tout λ ∈ [ 0 ; 1 ],

lim fm xkjℓ + λ δjℓm sℓm = J(x∗ )


m→+∞ m

Or, par continuité de J, on a

J(x∗ , z ∗ ) = + λ δjℓm sℓm = J x∗ + λ α s∗ , z ∗



lim fm xkjℓ
m→+∞ m

Comme cette égalité est vraie pour tout λ ∈ [ 0 ; 1 ], et que α s∗ ̸= 0, elle contre-
dit la stricte convexité de x 7→ J(x, x∗(2) ). On en déduit donc que l’hypothèse
initiale, à savoir que la suite (δj )j∈N ne converge pas vers 0, est fausse.
• (x∗ , z ∗ ) est un point critique partiel de J. Une conséquence directe du
point précédent est que
lim xkj +1 , zkj = (x∗ , z ∗ ) = lim xkj , zkj



j→+∞ j→+∞

Par continuité et biconvexité de J, on peut alors utiliser la fermeture des sous-

différentiels pour obtenir que
0 ∈ ∂x J(x∗ , z ∗ ) et 0 ∈ ∂z J(x∗ , z ∗ )
Le point (x∗ , z ∗ ) est par ailleurs un point critique de J si
∂x J(x∗ , z ∗ ) × ∂z J(x∗ , z ∗ ) ⊂ ∂J(x∗ , z ∗ )
ce qui est le cas sous les conditions additionnelles introduites dans l’énoncé de
la proposition. ■

Pauline Tan 6 V2.9.2023

5mm71 : Méthodes du premier ordre pour l’optimisation... Sorbonne Université

2.4 Exemples d’applications

Une application historique, qui donne le nom alternatif de méthode Gauss–Seidel
non linéaire à l’algorithme BCD, est la résolution itérative d’un système linéaire
Ax = b (S)
n
où A ∈ Mn,n (R) est une matrice symétrique définie positive et b ∈ R \ {0}. L’idée est
de réécrire ce problème sous la forme d’un problème d’optimisation équivalent :
 
1
min ⟨A x, x⟩ − ⟨b, x⟩ (PGS )
x∈Rn 2
Le système linéaire (S) et le problème (PGS ) partagent le même ensemble de solutions.
En effet, il est aisé 2 de vérifier que la fonction objectif de (PGS ) est une fonction quadra-
tique généralisée, qu’elle est fortement convexe si et seulement si A est définie positive,
et que, par ailleurs, si A est symétrique, alors la règle de Fermat (qui est une condition
nécessaire et suffisante d’optimalité ici) s’écrit
Ax = b
n
La fonction objectif est définie sur R , et on peut naturellement décomposer la va-
riable x ∈ Rn en n blocs, correspondant aux n coordonnées de x. Intéressons-nous à
l’expression des fonctions partielles de la fonction objectif J. Soit i ∈ [[ 1 ; n ]]. La i-ème
fonction partielle fi : x(i) 7→ J(x) est de la forme
n
1 X
∀ t ∈ R, fi (t) = Ai,i t2 + Aj,i x(j) t − bi t + constante
2 j=1
j̸=i

Puisque les Ai,i sont strictement positifs (car A est définie positive), il s’ensuit que la
i-ème fonction partielle est une parabole strictement convexe, donc admet un unique
minimiseur t∗i donné par
   
n n n
1  X
 = 1 bi −
X X
t∗i =
  
bi − A j,i x (j) A j,i x (j) − Aj,i x(j) 
Ai,i 
j=1
 Ai,i 
j=1 j=1

j̸=i j<i j>i

Nous pouvons donc maintenant écrire les itérations de l’algorithme BCD appliqué au
problème (PGS ) : pour x0 = ((x(i) )0 )1≤i≤n ∈ Rn , on a pour tout k ∈ N
∀ i ∈ [[ 1 ; n ]] , (x(i) )k+1 = argmin f (xk+1 , . . . , (x(i−1) )k+1 , t, (x(i+1) )k , . . . , (x(n) )k )
t∈R

D’après ce qui précède, on a

 
n n
1  bi −
X X 
(x(i) )k+1 = Aj,i (x(j) )k+1 − Aj,i (x(j) )k 
Ai,i 
j=1 j=1

j<i j>i

En particulier, chacun de ces points satisfait l’équation linéaire suivante :

n
X n
X
Ai,j (x(j) )k+1 + Ai,i (x(i) )k+1 + Ai,j (x(j) )k = bi
j=1 j=1
j<i j>i

Autrement dit, pour déterminer la i-ème coordonnée du nouveau vecteur xk+1 , on consi-
dère la i-ème équation du système linéaire étudié et on y fixe la valeur des autres coor-
données x(j) à leur valeur courante (c’est-à-dire x(j) = (x(j) )k+1 si j < i et x(j) = (x(j) )k
2. Cf. b2 : Introduction à la méthode des moindres carrés (3ma261)

Pauline Tan 7 V2.9.2023

5mm71 : Méthodes du premier ordre pour l’optimisation... Sorbonne Université

si j > i), puis on résout cette équation affine. On met ainsi à jour la valeur de x(i) et
on réitère le processus pour la coordonnée suivante x(i+1) . On reconnaît l’algorithme de
Gauss-Seidel pour la résolution d’un système linéaire.
La fonction objectif J du problème (Pgs ) est continûment différentiable (car poly-
nomiale), et multiconvexe (car convexe) lorsque que A est (semi-)définie positive. Par
ailleurs, chaque fonction partielle est strictement convexe (car les Ai,i sont strictement
positifs), donc on peut appliquer une généralisation multiconvexe de la proposition 2,
qui assure que toute valeur d’adhérence de la suite générée par cet algorithme est un
point critique de J. Puisque J est dans ce cas strictement convexe, l’ensemble des points
critiques de J est réduit à l’unique minimiseur de J, ce qui assure par ailleurs la conver-
gence forte de la suite des itérées vers ce point, qui n’est autre que la solution du système
linéaire (S).

L’algorithme de Gauss-Seidel n’est a priori pas un algorithme très effi-

cace pour résoudre un système linéaire de manière exacte, puisqu’il faut en
général une infinité d’itérations pour atteindre la solution (contrairement
à la méthode du pivot de Gauss, par exemple, qui donne une solution en
un nombre fini d’itérations). Or, en pratique, on interrompt nécessairement
la suite prématurément (donc au bout de N itérations), ce qui ne donne
qu’une approximation de la solution recherchée. L’intérêt de cet algorithme
se révèle donc dans les cas où la mise en œuvre d’une résolution exacte n’est
pas possible ou déraisonnable, soit parce que le système est trop grand, ou
encore parce que la matrice A est mal conditionnée.
Notons enfin que, pour résoudre de manière approchée le système linéaire
A x = b, on peut également appliquer la méthode du gradient explicite
au problème (Pgs ), car la fonction objectif J est |||A|||-régulière (cf. b2
: Méthodes du gradient explicite). Cependant, la convergence de cet
algorithme est conditionnée par le choix du pas de temps, qui lui-même
dépend du calcul de la norme de A.

Un second exemple, plus générique, d’application de l’algorithme BCD est celui des
estimations jointes. Pour illustrer notre propos, prenons l’exemple de la restauration
d’une image numérique g. Cette image est supposée bruitée et floue ; on peut la modéliser
comme la dégradation d’une image idéale u de la manière suivante :
g =K ⋆u+n
où K est un noyau de convolution modélisant le flou et n un bruit blanc gaussien. Parmi
les méthodes permettant de débruiter ou de rendre nette une image, on a les méthodes
dites variationnelles qui écrivent ces problèmes comme ceux de la minimisation d’une
fonction objectif. Par exemple, pour la restauration de l’image dégradée g, on peut
considérer le problème de la forme
nµ o
min ∥v − K ⋆ u∥2 + ∥∇u∥ + α ∥K∥2
(u,K)∈X ×Σ 2

(on n’entre pas ici dans les détails quant à la pertinence du choix de cette fonction). De
manière générale, ce problème est difficile à résoudre ; si on applique l’algorithme BCD,
on est amené à résoudre successivement les deux problèmes
nµ o
min ∥v − K ⋆ u∥2 + ∥∇u∥
u∈X 2
nµ o
et min ∥v − K ⋆ u∥2 + α ∥K∥2
K∈Σ 2

Pauline Tan 8 V2.9.2023

5mm71 : Méthodes du premier ordre pour l’optimisation... Sorbonne Université

Le premier problème peut être vu comme le débruitage de l’image g connaissant l’opéra-

teur de flou K, tandis que le second problème comme la détermination de cet opérateur
de flou connaissant l’image nette u. On a donc scindé la tâche en deux sous-tâches plus
abordables. Il est clair qu’une telle procédure est très peu robuste, car dépendant très
fortement de l’initialisation (que ce soit de K ou de u, à partir de la donnée g). Ainsi, la
convergence éventuelle de la suite des itérées est très sensible à l’initialisation, avec un
risque non négligeable de converger vers un point critique non minimiseur.
De manière générale, en dépit de son apparente simplicité, la convergence de l’algo-
rithme BCD est difficile à établir, d’une part car la stricte convexité d’une des fonctions
partielles n’est pas toujours assurée dans les problèmes considérés, et d’autre part car
l’ensemble des points critiques n’est pas toujours réduite à un point.

3 Descente proximale linéarisée alternée

3.1 Position du problème
On considère le problème (P2 blocs ), dans le cas où la fonction objectif peut être
décomposée de la manière suivante :
∀ (x, z) ∈ X × Z, J(x, z) = f (x) + g(z) + h(x, z)
avec f : X → R ∪ {+∞} et g : Z → R ∪ {+∞} deux fonctions minorées et simples
et h : X × Z → R une fonction continûment différentiable, telles que, pour tout (x, z) ∈
X × Z, les fonctions partielles x′ 7→ J(x′ , z) et z ′ 7→ J(x, z ′ ) sont respectivement Lz
et L̃x -régulières. Cette décomposition n’est pas nécessairement unique.
Notons d’ores-et-déjà que, sous ces hypothèses, on a la décomposition suivante du
sous-différentiel de J en (x, z) ∈ X × Z :
   
∂h ∂h
∂J(x, z) = ∂f (x) + (x, z) × ∂g(z) + (x, z)
∂x ∂z
En particulier, si (x∗ , z ∗ ) satisfait les inclusions
∂h ∗ ∗ ∂h ∗ ∗
0 ∈ ∂f (x∗ ) + (x , z ) et 0 ∈ ∂g(z ∗ ) + (x , z )
∂x ∂z
alors (x∗ , z ∗ ) est un point critique de J.

3.2 Algorithme PALM

On a vu que, sous certaines conditions, il est possible de résoudre le problème (P)2 blocs
en alternant des minimisations partielles. Cependant, les conditions d’application sont
très restrictives, et les résultats de convergence relativement faibles. L’idée est donc de
remplacer les minimisations partielles par des pas de descentes, appliqués aux fonctions
partielles de J.
Dans l’algorithme PALM (pour Proximal Alternating Linearized Minimization), on
choisit d’utiliser des pas de descente de gradient explicite-implicite, c’est-à-dire d’appli-
quer une itération de l’algorithme FBS à la fonction partielle courante. Plus précisément,
on considère les itérations suivantes
 
∂h


xk+1 ∈ proxτk f xk − τk ∂x xk , zk


 
 ∂h

zk+1 ∈ proxσk g zk − σk
 xk+1 , zk
∂z
Notons que les itérées sont définies de manière unique dès que f et g sont convexes.

Pauline Tan 9 V2.9.2023

5mm71 : Méthodes du premier ordre pour l’optimisation... Sorbonne Université

De la même manière que pour l’algorithme FBS, ces itérations peuvent être vues
comme des minimisations de fonctions approchées ; ici, la première mise-à-jour comme
la minimisation de la fonction
 
∂h 1
∥x − xk ∥2


x 7→ f (x) + g(zk ) + h(xk , zk ) + xk , zk , x − xk +
∂x 2 τk
qui est une approximation autour du point xk de la fonction x 7→ J(x, zk ), tandis que
la seconde mise-à-jour s’écrit comme la minimisation de la fonction
 
∂h 1
∥z − zk ∥2


z 7→ f (xk+1 ) + g(z) + h(xk+1 , zk ) + σk xk+1 , zk , z − zk +
∂z 2 σk
qui est une approximation autour du point zk de la fonction z 7→ J(xk+1 , z).

Il existe évidemment d’autres manières de remplacer les minimisations par-

tielles. On peut les remplacer par des pas de descentes de gradient explicite,
par une itérations de l’algorithme du point proximal, ou encore ne pas ap-
pliquer le même traitement (minimisation / descente) aux deux variables.

3.3 Propriétés de convergence

Puisque chaque mise-à-jour est un pas de FBS, on peut montrer un premier résultat :

Proposition 3 (Convergence du critère)

Soit f : X → R ∪ {+∞} et g : Z → R ∪ {+∞} deux fonctions minorées et

simples et h : X × Z → R une fonction continûment différentiable, telles que,
pour tout (x, z) ∈ X × Z, les fonctions partielles x′ 7→ J(x′ , z) et z ′ 7→ J(x, z ′ )
sont respectivement Lz et L̃x -régulières. Posons
∀ (x, z) ∈ X × Z, J(x, z) = f (x) + g(z) + h(x, z)
et considérons la suite générée par l’algorithme suivant : soit x0 ∈ X × Z et
 
∂h


 x
 k+1
 ∈ prox τk f x k − τk x ,
k kz
∂x
∀ k ∈ N,  
 ∂h

zk+1 ∈ proxσk g zk − σk
 xk+1 , zk
∂z
On pose Q = 2 (resp. Q̃ = 2) si f (resp. g) est convexe, et Q = 1 (resp. Q̃ = 1)
sinon. Si τk ∈ ] 0 ; Q/Lzk [ et σk ∈] 0 ; Q̃/L̃xk+1 [ pour tout k ∈ N, alors les
suites (J(xk , zk ))k∈N et (J(xk+1 , zk ))k∈N sont décroissantes et convergent vers
la même limite. De plus, on a pour tout k ∈ N
 
1 Q
− Lzk ∥xk+1 − xk ∥2


J xk+1 , zk ≤ J(xk ) −
2 τk
!

1 Q̃
et J(xk+1 ) ≤ J xk+1 , zk − − Lxk+1 ∥zk+1 − zk ∥2
2 σk

Remarque : On voit se profiler dans cette proposition l’un des désavantages de la

méthode PALM, à savoir le coûteux calcul des constantes de Lipschitz des dérivées

Pauline Tan 10 V2.9.2023

5mm71 : Méthodes du premier ordre pour l’optimisation... Sorbonne Université

partielles de h au point courant. En effet, ce calcul est nécessaire pour choisir correcte-
ment les pas de temps (τk , σk ).

Démonstration : Laissée au lecteur. Il suffit de suivre la démarche des preuves des

corollaires 1 et 2 du module b4 : Éclatement primal d’opérateurs.

Notons qu’en particulier, sous les hypothèses de la proposition précédente, on a

 
Q
lim − Lzk ∥xk+1 − xk ∥2 = 0
k→+∞ τk
!
Q̃
et lim − Lxk+1 ∥zk+1 − zk ∥2 = 0
k→+∞ σk
Pour avoir les convergences des quantités ∥xk+1 − xk ∥ et ∥zk+1 − zk ∥ vers 0 (et donc, de
la quantité ∥xk+1 − xk ∥), il faut que les quantités positives
Q Q̃
− Lzk et − Lxk+1
τk σk
soient minorées par une quantité strictement négatives. Autrement dit, il faut choisir les
pas de temps τk et σk de sorte que
Q Q̃
> τk et > σk
Lzk + ε Lxk+1 + ε̃
avec ε > 0 et ε̃ > 0 deux réels fixés. Notons que, si les constantes de Lipschitz soient
majorées (par L et L̃ respectivement), alors il est possible de considérer des pas constants
  # "
Q Q̃
τ ∈ 0; et σ ∈ 0;
L L̃
Un tel choix réduit la complexité de l’algorithme (puisque les pas de temps ne sont
calculés qu’une seule fois, avant le début des itérations), mais ne permet plus de tirer
avantage, le cas échéant, de propriétés localement plus intéressantes, à savoir une petite
constante de Lipschitz, c’est-à-dire un pas de temps adaptatif.
Intéressons-nous maintenant à la convergence des sous-gradients. Commençons par
écrire, pour tout k ∈ N, la règle de Fermat associée aux sous-problèmes d’optimisation :

1
∂h

0 ∈ ∂f xk+1 + xk+1 − xk + xk , zk
τk ∂x

1
∂h

et 0 ∈ ∂g zk+1 + zk+1 − zk + xk+1 , zk
σk ∂z
En utilisant la continuité des dérivées partielles de h, on peut réécrire ces deux inclusions
à l’aide des sous-différentiels partiels de J : on a d’une part
xk − xk+1 ∂h
∂h


+ xk+1 , zk − xk , zk ∈ ∂x J xk+1 , zk
τk ∂x ∂x
et d’autre part
zk − zk+1 ∂h
∂h


+ xk+1 , zk+1 − xk+1 , zk ∈ ∂z J xk+1 , zk+1
σk ∂z ∂z
En utilisant le caractère lipschitzien des dérivées partielles de h et le fait que les quan-
tités ∥xk+1 − xk ∥ et ∥zk+1 − zk ∥ tendent vers zéro si les pas de temps sont choisis
correctement, on en déduit le résultat suivant :

Pauline Tan 11 V2.9.2023

5mm71 : Méthodes du premier ordre pour l’optimisation... Sorbonne Université

Proposition 4 (Convergence des sous-gradients)

Soit f : X → R ∪ {+∞} et g : Z → R ∪ {+∞} deux fonctions minorées et

simples et h : X × Z → R une fonction continûment différentiable, telles que,
pour tout (x, z) ∈ X × Z, les fonctions partielles x′ 7→ J(x′ , z) et z ′ 7→ J(x, z ′ )
sont respectivement Lz et L̃x -régulières. Posons
∀ (x, z) ∈ X × Z, J(x, z) = f (x) + g(z) + h(x, z)
et considérons la suite générée par l’algorithme suivant : soit x0 ∈ X × Z et
 
∂h


 x
 k+1
 ∈ prox τk f x k − τk x ,
k kz
∂x
∀ k ∈ N,  
 ∂h

zk+1 ∈ proxσk g zk − σk
 xk+1 , zk
∂z
On pose Q = 2 (resp. Q̃ = 2) si f (resp. g) est convexe, et Q = 1 (resp. Q̃ = 1)
sinon. On définit également les vecteurs suivants :
xk − xk+1 ∂h
∂h

pk+1 = + xk+1 , zk − xk , zk
τk ∂x ∂x
zk − zk+1 ∂h
∂h

et qk+1 = + xk+1 , zk+1 − xk+1 , zk
τk ∂z ∂z
Ces vecteurs vérifient



pk+1 ∈ ∂x J xk+1 , zk et qk+1 ∈ ∂z J xk+1 , zk+1
Si τk ∈ ] 0 ; Q/(Lzk + ε) [ et σk ∈ ] 0 ; Q̃/(L̃xk+1 + ε̃) [ pour tout k ∈ N pour ε > 0
et ε̃ > 0 donnés, alors les suites (pk )k∈N∗ et (qk )k∈N∗ convergent vers 0. Par
ailleurs, on a pour tout k ∈ N
   
1 1
∥pk+1 ∥ ≤ + Lzk ∥xk − xk+1 ∥ et ∥qk+1 ∥ ≤ + L̃xk+1 ∥zk − zk+1 ∥
τk σk

Démonstration : Laissée au lecteur.

Notons que les sous-différentiels partiels de J sont fermés (proposition 22 du module a2

: Sous-différentiabilité). Par ailleurs, on a


∂h
∂h

∂x J xk+1 , zk+1 = ∂x J xk+1 , zk + xk+1 , zk+1 − xk+1 , zk
∂x ∂x
de sorte que, si on pose
∂h
∂h

p̃k+1 = pk+1 + xk+1 , zk+1 − xk+1 , zk

∂x ∂x
alors on a p̃k+1 ∈ ∂x J xk+1 , zk+1 . Ainsi, sous les hypothèses de la proposition précé-
dente, on a
 
1
∥p̃k+1 ∥ ≤ + Lzk ∥xk − xk+1 ∥ + L̃xk+1 ∥zk − zk+1 ∥
τk
Ainsi, puisque les hypothèses de régularité sur J impliquent que
∀ k ∈ N∗ , Pk = (p̃k , qk ) ∈ ∂J(xk , yk )
et que l’on a (a + b) ≤ (a + b) + (a − b)2 = 2 (a2 + b2 ) pour tout (a, b) ∈ R2 , alors
2 2

Pauline Tan 12 V2.9.2023

5mm71 : Méthodes du premier ordre pour l’optimisation... Sorbonne Université

∥Pk ∥2 = ∥p̃k ∥2 + ∥qk ∥2

  2  2
1 1
≤ + Lzk ∥xk − xk+1 ∥ + L̃xk+1 ∥zk − zk+1 ∥ + + L̃xk+1 ∥zk − zk+1 ∥2
τk σk
 2  2 !
1 2 1
≤2 + Lzk ∥xk − xk+1 ∥ + + L̃xk+1 + 2 L̃xk+1 ∥zk − zk+1 ∥2
2
τk σk
Si on suppose que les constantes de Lipschitz Lx et L̃z sont majorées respectivement
par L et L̃, alors on a pour tout k ∈ N,
Q Q Q̃ Q̃
≤ et ≤
L+ε Lzk + ε L̃ + ε̃ L̃xk+1 + ε̃
En particulier, on voit qu’il est possible d’imposer le choix de deux bornes inférieures τ >
0 et σ > 0 tels que
∀ k ∈ N, τ ≤ τk et σ ≤ σk
Par conséquent, on peut obtenir la majoration suivante
∀ k ∈ N∗ , ∥Pk ∥ ≤ b ∥xk+1 − xk ∥
(  2  2 !)
1 1
avec b = max 2 +L , + L̃ + 2 L̃2
τ σ
Ainsi, grâce à la proposition 19 du module a2 : Sous-différentiabilité, on en déduit
que si la suite (xk )k∈N admet une sous-suite convergente, celle-ci converge vers un point
critique de J. Par ailleurs, on a le résultat général dans le cas d’une fonction KŁ :
Proposition 5 (Convergence vers un point critique)

Soit f : X → R ∪ {+∞} et g : Z → R ∪ {+∞} deux fonctions minorées et

simples et h : X × Z → R une fonction continûment différentiable, telles que,
pour tout (x, z) ∈ X × Z, les fonctions partielles x′ 7→ J(x′ , z) et z ′ 7→ J(x, z ′ )
sont respectivement Lz et L̃x -régulières. Posons
∀ (x, z) ∈ X × Z, J(x, z) = f (x) + g(z) + h(x, z)
On suppose que J est continue sur son domaine, supposé fermé. Considérons la
suite générée par l’algorithme suivant : soit x0 ∈ X × Z et
 
∂h


 x
 k+1
 ∈ prox τk f x k − τk x ,
k kz
∂x
∀ k ∈ N,  
 ∂h

zk+1 ∈ proxσk g zk − σk
 xk+1 , zk
∂z
On pose Q = 2 (resp. Q̃ = 2) si f (resp. g) est convexe, et Q = 1 (resp. Q̃ = 1)
sinon. Soit x∗ un point d’adhérence de la suite (xk )k∈N . On suppose que J
satisfait la propriété KŁ en x∗ . On suppose que
∀ (x, z) ∈ X × Z, Lz ≤ L et L̃x ≤ L̃
Q Q̃
Soit 0<τ ≤ et 0<σ≤
L+ε L̃ + ε̃
Si τk ∈ ] τ ; Q/(Lzk + ε) [ et σk ∈ ] σ ; Q̃/(L̃xk+1 + ε̃) [ pour tout k ∈ N pour ε > 0
et ε̃ > 0 donnés, alors la suite (xk )k∈N converge vers x∗ . De plus, x∗ est un point
critique de J.

Pauline Tan 13 V2.9.2023

5mm71 : Méthodes du premier ordre pour l’optimisation... Sorbonne Université

Démonstration : Laissée au lecteur. Il s’agit d’une application du théorème d’Attouch,

Bolte & Svaiter (théorème 2 du module a1 : Éléments de topologie).

3.4 Exemple d’applications

On considère ici un problème bien connu, qui est celui de la factorisation de matrices
positives. Il s’agit de déterminer une factorisation de la matrice A à coefficients positifs
A=XY
+ +
où X ∈ Mm,r (R ) et Y ∈ Mr,n (R ). La connaissance de cette factorisation peut
être utile dans de nombreuses applications. En particulier, on peut parfois supposer
que, parmi les factorisations possibles de ce type, l’une d’elles implique une matrice
parcimonieuse, c’est-à-dire avec un petit nombre de coefficients non nuls. Le problème
de la factorisation peut alors s’exprimer comme un problème d’optimisation :
 
1 2
min ∥A − X Y ∥F + χ{X∈Mm,r (R+ )|∥X∥0 ≤s} (X) + χMm,r (R+ ) (Y )
X∈Mm,r (R) 2
Y ∈Mr,n (R)

Ici, la norme de Frobenius est définie pour toute matrice A = (ai,j )1≤i≤m par
1≤j≤n
v
n
um X
uX
∥A∥F = t a2i,j
i=1 j=1

tandis que la norme ℓ0 est la norme de comptage, définit par

∥A∥0 = card {ai,j ̸= 0}
Ainsi, les matrices X satisfaisant ∥X∥0 ≤ s sont celles qui possèdent au plus s ∈ N
coefficients non nuls.
On peut aisément vérifier que, si on pose pour tout X, Y
1
h(X, Y ) = ∥A − X Y ∥2F
2
alors la fonction h est différentiable, et ses dérivées partielles sont lipschitziennes ; plus
précisément, en adaptant les notations de la section précédente, on a
LY = ∥Y tY ∥F et L̃X = ∥X tX∥F
De plus, si on pose
f (X) = χ{X∈Mm,r (R+ )|∥X∥0 ≤s} (X) et g(Y ) = χMm,r (R+ ) (Y )
alors les fonctions f et g sont simples ; en effet, l’opérateur proximal d’une indicatrice
d’ensemble étant la projection orthogonale sur cet ensemble, il est immédiat que proxg
est calculable (il suffit de remplacer tous les coefficients négatifs de la matrice Y par
zéro). L’autre projection (sur les matrices à au plus s coefficients non nuls et positifs)
est également facilement calculables. Il suffit d’appliquer la projection sur les matrices
à coefficients positifs puis de retenir les s coefficients les plus grands parmi ceux qui
restent, les autres étant ramenés à 0. On voit donc que cette projection n’est pas unique
(il suffit de songer à la matrice avec 1 pour tous les coefficients).

Pauline Tan 14 V2.9.2023

5mm71 : Méthodes du premier ordre pour l’optimisation... Sorbonne Université

Pour aller plus loin

Minimisation et descentes alternées. Les stratégies de minimisation par-
tielle (alternée) ou de descentes alternées (et leurs équivalents en maximisation)
sont utilisées massivement dans la conception des algorithmes en optimisation
numérique. On peut citer les exemples déjà vus de l’éclatement de Dykstra
(étudié dans le module b4 : Éclatement primal d’opérateurs), de l’algo-
rithme de Chambolle–Pock et l’ADMM (introduits dans le module b5 :
Éclatement primal-dual).
Méthode de Gauss–Seidel L’étude de la convergence de cette méthode
est à retrouver dans le Problème 1 : Optimisation convexe et systèmes
linéaires (3ma261). La théorie sur les fonctions quadratiques généralisées est
développée quant à elle dans B3 : Introduction à la méthode des moindres
carrées (3ma261).

Pauline Tan 15 V2.9.2023