1.5.2 L'algorithme du paquet
On considère le problème (1.8) en y =
y0 et on suppose que les assertions (MFCQ), (SSOC) et (CRCQ) sont
satisfaites en x0 E SP(y0) . Alors (1.12) est un
problème de minimisation d'une fonction Lipschtz-continue.
Nous présentons l'algorithme dans le cas où la
contrainte G(y) < 0 est absente.
Soit v(y) le gradient
généralisé au sens de Clarke de F ; la méthode du
paquet s'inspire de la méthode dite de découpage de plan (cutting
plane method) pour la minimisation de fonctions convexes.
Soit {yi}ki=1 ; {zi}ki=1
des points d'essaie et des itérées déjà
évalués. La méthode de découpage du plan consiste
à minimiser la fonction :
mia k nv(yi)d +
v(yi)(zk - yi) + F(yi)o (1.13)
La direction d qui minimise ce modèle est une
direction de descente si y n'est pas un point stationnaire. Mais il
s'avère que l'utilisation du modèle (1.13) pour trouver une
direction de descente à une vitesse de convergence très lente;
c'est pourquoi à (1.13) on ajoute le terme de
régularisation quadratique (2tkjdT
d pour obtenir le modèle
e1<rm
1
nv(yi)d - áik > +
F(zk) + (2t )dTd (1.14)
-- = J k
Avec áik = F(zk) -
v(yi)(zk - yi) -
F(yi)
La solution optimale d de (1.14) est une direction de
descente pour F(y) en y = zk sous réserve que
le modèle donne une approximation suffisamment bonne de F(y)
dans un voisinage du point non stationnaire zk. Une nouvelle
itérée est zk+1 = zk + d est
calculée de manière à faire décroître de
façon considérable la fonction modèle ; i.e F(zk
+ d) < F(zk).
Genéralités sur la programmation
mathématique à deux niveaux 16
Mémoire de DEA *
Laboratoire d'analyse numérique *
UYI Francisque.D.Fouodji c~UYI 2007-2008
Si dans le voisinage de zk la direction de descente
n'est pas assez bonne, alors aucune nouvelle itérée n'est
calculée mais les nouveaux points d'essaie yk+1 et zk
seront utilisés pour rechercher une nouvelle direction de descente
dans (1.14) après ajout d'un gradient généralisé
?..F(yk+1).
Algorithme du paquet
|
Entrée : Suite d'itérée
{zi}k i=1 et des points d'essaie
{yi}k i=1, le paramètre de
régularisation tk
Sortie : Une meilleure itérée
zk+1 ou un modèle amélioré.
1. Calculer une solution optimale dk de (1.14);
initialiser : yk+1 := zk + dk
2. Si ..F(yk+1) est suffisamment petit comparé
à ..F(zk) alors :
a) Agrandir tk et retourner à 1 ou
b) Poser zk = yk+1 . Si ..F(yk+1)
n'est pas suffisamment petit comparé à ..F(zk) alors
c) réduire tk et retourner à 1 ou
d) poser zk+1 = zk calculer
v(yk+1) E ?..F(yk+1)
|
Il existent plusieurs critères pour le choix de tk
à l'étape 2; ils peuvent être trouvés dans
[11].
Pour terminer ce chapitre , nous allons présenter
quelques unes des nombreuses applications de la PBN.
| 
