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.2.2 Deuxième méthode

Si la fonction objectif du leader ne possède pas les propriétés nécessaires pour l'application de la régularisation de Tykhonov, une autre méthode de régularisation de(3.1)-(3.2) consiste à remplacer le problème du suiveur par :

{ }

min f(x, y) + á11x11² : x E M(y) pour á > 0 (3.8)

x

Soit W_á l'ensemble des solutions de (3.8)pour y fixé; Le PBN régularisé s'écrit alors :

{ }

min F(x, y) : y E Y, x E W_á(y) (3.9)

y

Où

Wá(y) = Argmin x

{ } f(x, y) + á11x11^2: x E M(y) (3.10)

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

Des relations entre le problème régularisé (3.9)-(3.10) et le problème original (3.1)-(3.2) sont présentées dans [28].

On a le théorème suivant :

Théorème 3.2.3. Considérons les problèmes (3.3) et (3.8). Si les assertions (C) et (MFCQ) sont satisfaites, alors :

1) Pour toute suite (y^k)k avec y^k E Y Vk et (á^k)k C 1[8+ convergeant vers y et á respectivement, toute suite (x^k)k satisfaisant x^k E W_ák(y^k) V k, admet un point d'accumulation x tel que x E W_á(y)

2)

lim

yk?y ák&0

Pour á = 0, on a :

x_ák(y^k) = x(y)

Sous réserve que W(y) = {x(y)}

Preuve :

1)

xk E W_ák(y^k) Vk = g(x^k, y^k) < 0 et h(xk, y^k) = 0

{ }

= (x^k, y^k)_k C K := (x,y) E 1[8ⁿ X 1[8^m : g(x,y) < 0, h(x, y) = 0

d'après l'assertion (C), K est compact.

Si on note P1(K) la première projection de K sur 1[8ⁿ, puisque P1 est continue, P1(K) est compacte.

(x^k)_k C P1(K) = (x^k)_k admet un point d'accumulation x

montrons que x E W_á(y)

D'après le théorème 1.4.2, W_.(.) est semi-continue supérieurement. (x^k)k admet x comme point d'accumulation implique que (x^k)k admet une sous-suite que nous notons encore (x^k)k qui converge vers x.

xk E W_ák(y^k) Vk = x E W_á(y) (car W_.(.) est semi-continue sup)

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

D'après le théorème 1.4.2, x_.(.) est continue d'où

lim

yk?y ákN0

x_ák(y^k) = x(y)
·

Notons qu'en général, sans l'hypothèse Ø(y) = {x(y)} ; on n'a pas

lim yk?y ák&0

xák(y^k) = x(y) ? Argmin x

{ } kxk : x ? Ø(y)

L'exemple suivant illustre ce fait :

Exemple 3.2.2. On considère le problème :

{ }

min xy : x ? [-1, 1]

x

on a

Ø(y) =

{ [-1,1] si y = 0 {-1} si y > 0 {1} si y < 0

Le problème régularisé est

{ }

min xy + áx² : x ? [-1, 1]

x

On a ?_x(xy + áx²) = y + 2áx ?_x(xy + áx²) = 0 ? x = -y2á en plus, ?2 xx(xy + áx²) = 2á > 0

-1 = x = 1 ? -1 = - y = 1

2á

?-2á = y = 2á

donc

{

Ø_á(y) =

{-^y_2á} si y ? [-2á, 2á]

{1} si y = -2á
{-1} si y = 2á

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

la suite (x_ák(y^k))k = (-k) n'admet pas de limite dans [-1,1] lorsque y^k ? 0 et á^k ? 0

{ }

alors que Argmin _x |x| : x ? Ø(0) = {0}

On montre que si (3.3) est convexe, alors pour á > 0 fixé, le problème (3.8) admet une solution unique et le fonction x_á(.) est continue [28]

pour á > 0 fixé et Sous certaines conditions (que nous mentionnerons par la suite) l'unique solution optimale de (3.8) est Lipschitz-continue par rapport à á et y.

Il s'ensuit que le PBN régularisé

min

y

{F_á(y) := F(xá(y), y) : y ? Y} (3.11)

est un problème de minimisation d'une fonction Lipschitz-continue, et par conséquent peut être résolu par un algorithme du paquet.

Nous allons dans la paragraphe qui suit présenter un algorithme développé par S.Dempe [12] qui résoud les PBN dans le cas de la non unicité en se basant sur cette méthode de régularisation.

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

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