4.3 M´ ethodes variationnelles
81
Algorithme 5 Algorithme de Chambolle-Pock g´ en´ erique [29]
Entr´ ee : on se donne des param` etres τ, σ ą 0, θ P r0, 1s
Initialisation : on se donne un point initial px 0 , y 0 q P X ˆ Y et on pose ¯
x 0 “ x 0 .
It´ eration n : on actualise x n , y n et ¯
x n avec
y
n`1 “ argmin yPY
#
F
˚ pyq `
}y ´ y n ´ σLp¯ x n q} 2
Y
2σ
+
,
x
n`1 “ argmin xPX
#
Gpxq `
}x ´ x n ` τ L ˚ py n`1 q} 2
X
2τ
+
,
¯
x
n`1 “ x
n`1 ` θpx
n`1 ´ x
n q.
L’algorithme fournit un point selle comme le montre le th´ eor` eme suivant :
Th´ eor` eme 4.3.6 Supposons que le probl` eme (4.18) poss` ede au moins une
solution. Soit L “ }L} (la norme de l’op´ erateur L). Si θ “ 1 et τ σL
2
ă 1,
alors px
n , y
n
q converge vers un point-selle solution de (4.18). En particulier
px
n
q converge vers une solution du probl` eme (4.19).
Nous pouvons alors appliquer cette m´ ethode au mod` ele discret de RudinOsher-Fatemi. Dans ce cas
Lpuq “ ∇u, L
˚
ppq “ ´div p, F p∇uq “ Jpuq et Gpuq “
1
2ε
}u´u d }
2
X , L
2
“ 8.
En utilisant une version acc´ el´ er´ ee de l’algorithme g´ en´ erique (pr´ esent´ ee aussi
dans [29]) on obtient :
Algorithme 6 Algorithme de Chambolle-Pock pour le mod` ele ROF
Entr´ ee : on se donne γ en fonction de ε (par exemple γ “ 1{ε).
Initialisation : on se donne
– τ 0 , σ 0 ą 0 tels que τ 0 σ 0 ă 1{8,
– un point initial pu 0 , p 0 q P X ˆ Y et on pose ¯
u 0 “ u 0 .
It´ eration n : on actualise u n , p n , ¯
u n , θ n , τ n et σ n avec
– p
n`1
i,j “
q n
i,j
maxp1, |q n
i,j |q
o` u q n “ p n ` σ n ∇¯ u n P Y ,
– u
n`1
i,j “
εv n
i,j ` τ n pu d q i,j
ε ` τ n
o` u v n “ u n ` τ n div p n`1 P Y ,
, τ n`1 “ θ n τ n , σ n`1 “
σ n
θ n
.
– ¯
u n`1 “ u n`1 ` θ n pu n`1 ´ u n q.
✓ n =
r
1
1 + 2⌧ n