Approche de résolution par régularisation des problèmes de programmation mathématique à deux niveaux dans le cas de la non unicité de la solution du problème du suiveur

3.3.2 Présentation de l'algorithme

Le principe de l'algorithme est le suivant : pour la valeur fixée á0 du paramètre de régularisation et pour å0 > 0, utiliser l'algorithme du paquet que nous avons présenté au chapitre un pour calculer la solution å0-optimale z⁰ du problème régularisé de paramètre á0 ; ensuite considerer un nouveau paramètre á1 < á0 et å1 < å0 et calculer la solution å1-optimale z¹. Si z1 est meilleure que z⁰, alors z¹ est une itérée; sinon y¹ = z¹ est un point d'éssaie (ce point sera utilisé pour le calcul d'une nouvelle direction de descente en z⁰). Ainsi de suite jusqu'à ce que soit satisfait un certain critère d'arrêt (qui ici portera sur å).

le prototype de cet algorithme est le suivant :

Approche de résolution par régularisation des PBN dans le cas de la non unicité. 45

Mémoire de DEA * Laboratoire d'analyse numérique * UYI Francisque.D.Fouodji (c)UYI 2007-2008

étape1 : Choisir å0, á⁰ et un point de départ z0

initialiser s := 0

étape2 : Avec comme point de départ z^s, calculer en utilisant l'algorithme du paquet une solution ås-optimale z^s+1 du problème (3.11)

étape3 : Poser å^s+1 := ås2 , á^s+1 := ás2 , s := s + 1 et répéter l'étape 1 jusqu'à ce qu'un critère d'arrêt soit satisfait.

On montre [30] que si la valeur de á^s n'est pas très petite, l'étape 2 peut s'effectuer en un nombre fini d'itérations ; ceci est également garanti si la suite _(zs)sEN obtenue en appliquant l'algorithme converge vers un point z où l'unique solution x0(z) du problème du suiveur est fortement stable.

Utilisant ce prototype, K.C.Kiwiel dans [30] construit un algorithme qui consiste en une suite d'applications de l'algorithme du paquet à différents problèmes. Lors de l'utilisation de cet algorithme, les itérées z^s calculées sont réutilisées même lorsqu'elles ne permettent pas d'avoir une décroissance significative de F_á par rapport aux itérées calculées précédemment ; ce qui peut conduire au pire des cas à un recommencement infini de l'algorithme(on dit que l'algorithme boucle).

C'est face à ce défaut de l'algorithme de K.C.Kiwiel que S.Dempe dans [12] a proposé un nouvel algorithme : l'algorithme du paquet modifié.

Cet algorithme consiste à : étant donné le paramètre á^s à la s^me itération, déterminer l'itérée z^s qui permet à F_ás(z^s) = F(x_ás(z^s), z^s) d'approximer au mieux F(x(z^s), z^s) ; ensuite faire décroître á^s et ne considérer que les z^s significatifs.

On note v(y) le gradient généralisé de F_ás(y). D'après [30] ; on a

{?_xF~x_á(y), y~d + ?yF~xá(y), y : d E ?_yx_á(y)}

v(y) E

Soit {yk}sk=1 une suite de points d'essaie; {z^k}^s_k=1la suite d'itérées calculées jusqu'à l'étape s. On considère le modèle suivant :

{ } + F_á(z^s) + u^sd^T d

max v(y^k)^Td - âk,s

2 (3.14)

kEJs

Où J_s ? {1,...,s};u^s > 0 et

âk,s = F_á(z^s) - v₍y^k)(z^s - y^k) - F_á(y^k)

Comme nous l'avons déjà mentionné au chapitre un, le réel d qui minimise le modèle (3.14) est une direction de descente pour F_á(y) en y = z^s.

Soit å > 0 le réel positif tel que ?å^' = å , (3.12) n'admet pas de solution å^'-optimale. å est appelé seuil d'optimalité. Soit %^s > 0 le rayon de la région de confiance (c'est le rayon de la plus petite boule dans laquelle on est sûr de trouver une solution). Soit mL un paramètre positif (paramètre de recherche en ligne [12]). Soit u^s = umin > 0 , á^s le coefficient de régularisation et d^s le réel qui minimise (3.14).

On pose

s - 1

ås := max m_p(IIu^sd^sII _+Eçsjâj,s) , _jEmax₀{IIy^j - z^jII+EIIz^k+1 - z^kII}

jEJ_s k=j

Approche de résolution par régularisation des PBN dans le cas de la non unicité. 46

Où (7^s_j)j sont les multiplicateurs de lagrange du problème de minimisation de (3.14) et

J_s ? {j : 7s j =6 0}

Es est utilisé pour mesurer la qualité de l'approximation z^s de la solution du PBN calculé à la s^eme iteration. Durant la procédure E^s doit tendre vers 0 ; mais pour des raisons pratiques, (impossibilité de trouver des solutions E^'-optimale pour les valeurs de E^' plus petite qu'une certaine valeur seuil) on arrête l'algorithme si E^s < E.

Soit k = 1 une certaine constante utilisée pour borner le changement de la région de confiance. 81 un paramètre donné.

Les principales étapes de l'algorithme sont les suivantes :

Algorithme du paquet modifié

Entrée : Suite d'itérée {zk}sk=1, les points d'essaie {yk}sk=1, les paramètres ás > 0, E^s > 0, us, Ss

Sortie : Une meilleure itérée z^s+1. Etape1 :

a) Calculer en augmentant si nécessaire la valeur de u^s, le réel d^s qui minimise le modèle (3.13) ainsi que les multiplicateurs de Lagrange ç^s_j, j E J_s tel que M^sII < Os

b) Tester le critère d'arrêt E^s < E, réduire E^s et J_s si nécessaire. Si E^s < S^s alors

Ss := ùS^s

Etape2 :

_{n o}

Si F_ás(z^s + d^s) < F_ás(z^s) + mL max v(yk)T d^s - âk,s alors

k?J_s

zs+1 := z^s + d^s, t_s := 1

Sinon

a) Rechercher t_s > 0 tel que

F_ás(z^s + t_sd^s) < F_ás(z^s) + _mLts max {v(y^k)^Td^s ? âk,s}

k?J l

et faire z^s+¹ := z^s + t_sd^s

b)Ou considerer que l'étape est nulle et calculer un nouveau point d'essaie yk+1 := z^s + td^s avec t > 0

t_s := 0

Si t > 0, calculer un nouveau coefficient de régularisation á^s+1 E]0, á^s] tel que

F_ás+1(z^s+1) - F_ás(z^s) < 0.5 (F_ás(z^s+¹) - F_ás(z^s)~ , ys+1 := zs+1

Sinon

ás+1 := ás

Etape3 : Choisir un nouveau rayon de la région de confiance O^s < êS^s Réactualiser l'ensemble J_s et les autres paramètres. Calculer le gradient généralisé de la fonction F_ás+1(y) au point y = ys+1 Faire S^s+¹ := S^s,s := s + 1 et répéter l'étape 1.

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é. 47

Mémoire de DEA * Laboratoire d'analyse numérique * UYI Francisque.D.Fouodji (c)UYI 2007-2008

La méthode pour la recherche de t_s à l'étape 2 et la méthode utilisé pour le choix de la région de confiance peuvent être trouvées dans [30].

Pour l'étude théorique, on choisi le seuil d'optimalité å = 0. L'algorithme précédent génère une suite (á^s, x_ás(z^s))_s qui théoriquement est infinie. Si (á^s)_s converge vers zero, alors le problème est résolu avec succès.

La modification apporté par ce nouvel algorithme réside dans le contrôle de la région de confiance, en posant que %^s < êä^s ave ê > 1. L'ajout de ce contrôle garanti que que toutes les itérées et points d'essaie générés durant l'exécution de l'algorithme ont toujours un intérêt.

Étant donné que l'algorithme génère une suite (z^s)_s ayant une infinité de termes (du point de vu théorique), il est impossible de le dérouler manuellement sur un exemple de PBN donné. Néanmoins, dans le paragraphe qui suit, nous allons étudier la convergence théorique de l'algorithme du paquet modifié afin de montrer que la suite (z^s)_s calculée converge vers une approximation de la solution du PBN original qui est stationnaire au sens de clarke. Ce qui permettra de conclure puisque la solution du problème du suiveur est fortement stable, que l'approximation de la solution du problème original calculée via l'algorithme est également fortement stable [11].