2.2 Quelques illustrations
47
Description du mod` ele
Supposons d´ esormais qu’il n’existe qu’un seul point x a ∈ R
d prenant la
valeur U (x a ) = a, et pour chaque x = x a , on a
x − x a , U(x) − U (x a ) > 0.
(2.8)
Lorsque d = 1, l’in´ egalit´ e (2.8) indique que les nombres
(x − x a ) & (U (x) − U (x a ))
ont les mˆ emes signes. Dans cette situation, la relation (2.8) se traduit par
l’une des ´ equivalences suivantes
x < x a ⇐⇒ U (x) − U (x a ) < 0
x > x a ⇐⇒ U (x) − U (x a ) > 0.
Un algorithme d´ eterministe naturel de recherche du point x a ∈ R
d est donc
d´ efini en posant
X n+1 − X n = γ n (U (x a ) − U (X n )) = γ n (a − U (X n ))
On choisit X 0 ∈ R
d , et on utilise une suite de pas positifs γ n ↓ 0 afin de
stopper l’´ evolution de la suite X n . Les sch´ emas de d´ ecroissances de γ n pour
lesquels lim n→∞ X n = x a doivent satisfaire les deux conditions suivantes
n
γ n = ∞ et
n
γ
2
n < ∞
La figure 2.6 repr´ esente l’´ evolution d’un algorithme de Robbins-Monro
“d´ eterministe” sur 4 it´ erations pour le calcul de quantiles.
Dans le cas de probl` emes pos´ es sous contraintes, on recherche des points
dans des lignes de niveaux `
a l’intersection d’un espace ferm´ e repr´ esentant les
contraintes :
U a := U a ∩ F = {x ∈ F : U (x) = a}, a ∈ R
d
(2.9)
Dans ce registre, il est courant de projeter s´ equentiellement les ´ etats visit´ es sur
la projection euclidienne proj F sur l’espace F ; plus formellement, l’algorithme
prend la forme suivante
X n+1 = proj F (X n + γ n (U (x a ) − U (X n )))
47
Description du mod` ele
Supposons d´ esormais qu’il n’existe qu’un seul point x a ∈ R
d prenant la
valeur U (x a ) = a, et pour chaque x = x a , on a
x − x a , U(x) − U (x a ) > 0.
(2.8)
Lorsque d = 1, l’in´ egalit´ e (2.8) indique que les nombres
(x − x a ) & (U (x) − U (x a ))
ont les mˆ emes signes. Dans cette situation, la relation (2.8) se traduit par
l’une des ´ equivalences suivantes
x < x a ⇐⇒ U (x) − U (x a ) < 0
x > x a ⇐⇒ U (x) − U (x a ) > 0.
Un algorithme d´ eterministe naturel de recherche du point x a ∈ R
d est donc
d´ efini en posant
X n+1 − X n = γ n (U (x a ) − U (X n )) = γ n (a − U (X n ))
On choisit X 0 ∈ R
d , et on utilise une suite de pas positifs γ n ↓ 0 afin de
stopper l’´ evolution de la suite X n . Les sch´ emas de d´ ecroissances de γ n pour
lesquels lim n→∞ X n = x a doivent satisfaire les deux conditions suivantes
n
γ n = ∞ et
n
γ
2
n < ∞
La figure 2.6 repr´ esente l’´ evolution d’un algorithme de Robbins-Monro
“d´ eterministe” sur 4 it´ erations pour le calcul de quantiles.
Dans le cas de probl` emes pos´ es sous contraintes, on recherche des points
dans des lignes de niveaux `
a l’intersection d’un espace ferm´ e repr´ esentant les
contraintes :
U a := U a ∩ F = {x ∈ F : U (x) = a}, a ∈ R
d
(2.9)
Dans ce registre, il est courant de projeter s´ equentiellement les ´ etats visit´ es sur
la projection euclidienne proj F sur l’espace F ; plus formellement, l’algorithme
prend la forme suivante
X n+1 = proj F (X n + γ n (U (x a ) − U (X n )))