3.3 Algorithme de résolution d'un PBN dans le
cas de la non unicité
Nous allons présenter l'algorithme lorsque le
problème du suiveur n'est pas soumis à la contrainte
h(x, y) = 0. Le problème du suiveur
régularisé est alors donné par
{ }
min f(x, y) +
ákxk2 : g(x, y) = 0
(3.12)
x
On suppose que les assertions (C), (MFCQ) et (CRCQ) sont
satisfaites. Ceci nous garanti que la fonction
x.(.) qui à
(á,y) associe la solution de (3.10) pour le paramètre
á > 0 et y fixé est une PC-function; et par
conséquent est Lipschitz-continue. Le problème consiste donc
à minimiser la fonction Lipschitz-continue
Fá(y).
3.3.1 La methde du paquet
L'algorithme que nous présentons dans cette section est
un algorithme du paquet. Cet algorithme se construit à partir de la
méthode du paquet, qui est une généralisation de la
méthode de descente (connue en optimisation diérentiable)
à des fonctions qui ne sont pas diérentiables, mais au moins
Lipschitz-continue.
F(y)
Rappelons qu'une méthode de descente pour la recherche de
y telle que F(y) = min
y
consiste à construire la suite
(yn)n
vérifiant :
1. initialisation : y0 donné;
2. nime itération :
on suppose y1, y2, ..., yn
connus;
a) chercher dn une
direction de descente stricte en yn ; i.e
chercher dn tel que ? p0 >
0 avec
F(yn +
pdn) <
F(yn) ?p ?]0,
p0]
b) prendre yn+1 = yn
+ pdn (avec p
bien choisi). On a le Lemme suivant :
Lemme 3.3.1. Soit y ?
Rm.
Si F ?
C1(Rm, R) et
si ?F(y) =6 0; alors w = -?F(y) est une direction de
descente stricte en
y.
Preuve :
Soit ? la fonction de R dans R définie par
?(p) = F(y + pw)
Puisque F est C1,
? ? C1(R,R) et
?'(p) = w.?F(y + pw)
.
Supposons que ?F(y) =6 0.
On veut montrer que ?p0 > 0 tel que si
p ?]0, p0] alors F(y + pw) <
F(y); ou encore que ?(p) <
?(0).
On a
?'(0) = w.?F(y) = -
|?F(y)|2 < 0
Approche de résolution par régularisation des
PBN dans le cas de la non unicité. 44
Mémoire de DEA * Laboratoire d'analyse
numérique * UYI Francisque.D.Fouodji (c)UYI 2007-2008
d'où comme ?' est continue, il existe
ä0 > 0 tel que si ñ E [0,ä0]
alors ?'(ñ) <
0.
Soit ñ E]0, ä0]. Alors
f
?(ñ) - ?(0) = J
cp'(t)dt < 0
(car Vt E]0, ñ],
?'(t) < 0)
o
donc on a
?(ñ) < ?(0) Vñ
E]0, ä0]
Il suffit donc de prendre ñ0 = ä0 pour
conclure.
·
Ce lemme nous montre que lors de la minimisation d'une fonction
différentiable F, pour trouver une direction de descente stricte en un
point y il suffit de considerer la direction
d = -VF(y). Le prototype de
l'algorithme de descente pour la minimisation des fonctions
différentiables est donc :
Entrée : y0 donné ;
Sortie : la suite (yn)n
On suppose y1, y2, ..., yn connus ;
a) calculer dn =
-VF(yn)
b) prendre yn+1 = yn +
ñdn (avec ñ bien choisi).
Supposons à présent que F est juste
Lipschitz-continue ; alors le gradient de F n'existe pas en tous points
y, mais on peut calculer en ces points un gradient
généralisé (par exemple le gradient
généralisé au sens de Clarke). On montre [30] que si
v(y) est le gradient généralisé au sens
de Clarke de F en y, alors d = -v(y) n'est
pas forcément une direction de descente stricte de F en y.
Dans la méthode du paquet, on commence par calculer le
gradient généralisé de F en y; si la direction
opposée à celle de ce gradient (d =
-v(y)) est une direction de descente stricte, on
construit un nouveau point z = y + ñd qui
améliore la fonction F.
Sinon on cherche une autre direction de descente. On montre
[11] qu'en général, si {yi}ki=1 et {zi}ki=1 sont des points
d'éssaie et des itérées déjà
évalués, la direction d qui minimise le modèle
max1
ik {v(yi)d -
áik} + F(zk) + (2t )dT d
(3.13)
1< k
Avec áik = F(zk) -
v(yi)(zk - yi) - F(yi) est une
direction de descente stricte de F en zk. Nous avons déjà
présenté le prototype de l'algorithme du paquet à la
section 1.5.1 du chapitre un.
| 
