3.4 Convergence de l'algorithme du paquet
modifié
Définition 3.4.1. Soit ë0 E
Ëá(xá(y0),
y0)
On dit que l'assertion (NE) est satisfaite si la matrice
~
V2xxL(xá(y0), y0,
ë0) + 2áE VTxgJ0(xá(y0), y0) ~
VxgI0(xá(y0), y0) 0
VygI0(xá(y0), y0)
est de rang maximal : n +
I(xá(y0), y0)
}où J0 = j : ë0 j > 0 et I0
= I(xá(y0), y0) = { j : gj (xá(y0),
y0) = 0 , E est la matrice
identité.
On suppose que les assertions (C), (MFCQ), (CRCQ) et (NE) sont
satisfaites pour le problème (3.12). Alors [11] la différentielle
au sens de Clarke Fá en y0 E Y
est donné par
{VxF(xá(y0),
y0)?yxá(y0) +
VyF(xá(y0), y0)}
?Fá(y0) =
posons Y = 1[8m, et supposons également que
la suite (zs)s généré par
l'algorithme est infini et borné.
Si le seuil d'optimalité å = 0 est choisi, alors
[30] le critère d'arrêt de l'algorithme est
{VxF(xás(zs), zs)d
+ VyF(xás(zs), zs) : d E
?yxás(zs)}
0 E .
i.e dès que zs est stationnaire au sens de
Clarke.
Montrer que l'algorithme converge revient à montrer que la
suite (zs)s converge vers un
point stationnaire au sens de Clarke. C'est-à-dire qu'il
faut montrer que :
{VxF (xá(y), y)d +
VyF(xá(y), y) : d E
?yxá(y)}
0 E .
où (xá(y), y, á) est un
point d'accumulation de la suite
{xás(zs), zs, ás}8s=1 .
On a le résultat suivant :
Approche de résolution par régularisation des
PBN dans le cas de la non unicité. 48
Théorème 3.4.1. Soit
{xás(zs), zs,
ás}00s=1 la suite généré par l'algorithme du
paquet modifié pour å = 0. Supposons que la suite
(ás)s est borné par
á0 > 0, alors tout point d'accumulation
(xá(y), y, á) de cette suite
satisfait
}.
{ ?xF
(xá(y), y)d
+ ?yF (xá(y),
y) : d ? ?yxá(y)
0 ?
preuve :
Rappelons que dans l'algorithme du paquet modifié, la
modification apporté à l'algorithme de Kiwiel consiste à
contrôler le renouvellement de la région de confiance à
chaque itération ; ainsi certains résultats de [30] reste vraies
pour l'algorithme modifié.
Soit y un point d'accumulation de la suite
(zs)s. La solution optimale ds
du problème de minimisation de (3.13) vérifie [30] :
|
ds ? ?Fás (zs; max
{kyj - zjk +
\
jEJs,çsj
0
|
Es - 1 k=1
|
}~kzk+1 - zkk
|
Si l'assertion (SSOC) est satisfaite en
(x0(y), y),
alors
{?xF(x0(y),
y)d +
?yF(x0(y), y) : d
? ?yx0(y) }
0 ?
Où ?Fá(z; å)
est l'å-sous différentielle de Goldstein définie
par
{ }
?Fá(z; å) =
conv ?Fá(y) : kz - yk = å
?Fá(z; å) est
semi-continue supérieurement et localement borné [31].
D'où si (á, y, 0,0) est un
point d'accumulation de la suite
s- 1 00
{ás, zs, ds,
max {yj -- z'k + E kzk+1 _ zkk }
,
jEJs,çs j
k=1 s=1
alors 0 ? ?Fá(y) et
le théorème 3.9 de [30] nous permet de conclure que
{ ?xF
(xá(y), y)d
+ ?yF (xá(y),
y) : d ? ?yxá(y) }
0 ? .
·
Si la suite (ás)s
converge vers zero, alors la condition suffisante d'optimalité
forte (SSOC) aux points d'accumulations de
{xás(zs), zs}00s=1 est
nécessaire pour garantir que l'algorithme du paquet modifié sera
à mesure de calculer toutes les données nécessaire a la
résolution du PBN.
Si cette condition d'optimalité (SSOC) est satisfaite,
le théorème précédent montre que les points
d'accumulations de la suite
{xás(zs),
zs}:1 sont des points stationnaires au sens de
Clarke.
Notons que la suite (zs)s
converge grace à la modification apporté par l'algorithme
du paquet modifié.
Le corollaire suivant découle du théorème
précédent.
Corollaire 3.4.1. Soit
{xás(zs), zs,
ás}00s=1 la suite générée par l'algorithme
du paquet modifié, où {ás}00s=1 converge vers zero. Soit
y = lim zs et x0(y) ?
Ø(y)
s?00
Mémoire de DEA * Laboratoire d'analyse
numérique * UYI Francisque.D.Fouodji (c)UYI 2007-2008
Approche de résolution par régularisation des
PBN dans le cas de la non unicité. 49
Mémoire de DEA * Laboratoire
d'analyse numérique * UYI Francisque.D.Fouodji
c~UYI 2007-2008
Ce résultat nous garanti que en résolvant le PBN
(3.1)-(3.2) par régularisation (utilisant l'algorithme du paquet
modifié), on aboutit à une approximation de la solution de la
solution du problème original qui est stationnaire au sens de Clarke
(par consequent fortement stable). Donc plus régulière que les
solutions optimiste et péssimiste respectivement qui sont le plus
souvent instables.
Mémoire de DEA * Laboratoire d'analyse
numérique * UYI Francisque.D.Fouodji
c~UYI 2007-2008
| 
