78
4 D´ ebruitage par m´ ethodes non lin´ eaires
Algorithme 3 Algorithme de Nesterov
Initialisation : k “ 0 ; G 0 “ 0 ; x k P Q et L est la constante de Lipschitz de ∇E.
It´ eration k :
for 0 ď k ď J do
(a) On pose η k “ ∇E px k q.
(b) Calcul de la solution y k de
min
yPQ
"
xη k , y ´ x k y X `
1
2
L }y ´ x k }
2
X
*
.
(c) G k “ G k´1 `
k ` 1
2
η
k .
(d) Calcul de la solution z k de
min
zPQ
"
L
σ
dpzq ` xG k , zy X
*
.
(e) On pose x k “
2
k ` 3
z k `
k ` 1
k ` 2
y k .
end for
Nesterov a montr´ e que si ¯
u est la solution de (4.13) alors
0 ď E py k q ´ E puq ď
4Ld puq
σ pk ` 1q pk ` 2q
.
Dans le cas qui nous int´ eresse, on va utiliser cet algorithme pour r´ esoudre
le probl` eme dual de (4.9) grˆ ace au th´ eor` eme 1.4.6 qui indique que
min
uPX
Jpuq `
1
2ε
}u ´ u d }
2
X “ max
vPX
p´J
˚
p´vq ´ N
˚
0 pvqq
“ ´ min
qPX
pJ
˚
p´vq ` N
˚
0 pvqq ,
o` u on a pos´ e
N 0 puq “
1
2ε
}u ´ u d }
2
X .
On a d´ ej` a remarqu´ e que J
˚ est l’indicatrice de l’ensemble K d´ efini par (4.10).
Calculons maintenant N
˚
0 :
N
˚
0 pvq “ sup
uPX
p xu, vqy X ´ N 0 puqq “ sup
uPX
p xu, vy X ´
1
2ε
}u ´ u d }
2
X q .
Le supremum est atteint pour
u “ εv ` u d
(4.14)
et donc
N
˚
0 pvq “
ε
2
}v}
2
X ` vu d “
1
2ε
}εv ` u d }
2
X ´
}u d }
2
2ε
.