32
CHAPITRE 2. CONDITIONS D’OPTIMALITÉ APPROCHÉE
(il n’est pas exclu que x k+1 puisse être pris égal à x k si f (x k ) = m k ).
Puis on définit S k+1 comme plus haut, et ainsi de suite.
Analysons les propriétés des suites (de points) (x k ) et de fermés (S k ) que
l’on vient de définir. Les choses ne sont pas difficiles, mais il faut y aller
progressivement.
(P 1 ) (S k ) est décroissante : ∀ k, S k+1 ⊂ S k .
Soit en effet x ∈ S k+1 . Cela signifie, par définition même de S k+1 ,
f (x) +
ε
λ
x − x k+1 ≤ f (x k+1 ).
(2.4)
De par l’inégalité triangulaire, on en déduit :
f (x) +
ε
λ
x − x k ≤ f (x) +
ε
λ
x − x k+1 +
ε
λ
x k+1 − x k
≤ f (x k+1 ) +
ε
λ
x k+1 − x k (grˆ ace ´
a (2.4)),
≤ f (x k ) (puisque x k+1 ∈ S k par construction) .
D’où, finalement,
f (x) +
ε
λ
x − x k ≤ f (x k ),
qui traduit bien le fait que x ∈ S k .
(P 2 ) (m k ) est croissante.
Comme S k+1 ⊂ S k ,
m k+1 := inf
S k+1
f ≥ inf
S k
f =: m k .
(P 3 ) Décroissance géométrique de ( f (x k ) − m k ) k :
f (x k+1 ) − m k+1 ≤
1
2
[ f (x k ) − m k ] .
(2.5)
En effet,
f (x k+1 ) ≤
1
2
[ f (x k ) + m k ] (par construction de x k+1 ) ,
m k ≤ m k+1
d´ emontr´ e au point(P 2 )
;
cela implique