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

CHAPITRE TRIS

Approche de résolution par régularisation

des PBN dans le cas de la non unicité.

Où

(y) = Argmin

x

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

Soit le PBN :

\ min y

{ } » F (x, y) : y ? Y, x ? (y) (3.1)

{ }

f(x, y) : g(x, y) = 0, h(x, y) = 0 (3.2)

Y est un fermé deR^m

F : Rⁿ × R^m -? R, f : Rⁿ × R^m -? R
g : Rⁿ × R^m -? R^q, h : Rⁿ × R^m -? Rk

Nous voulons résoudre (3.1 - 3.2) dans le cas où le problème du suiveur

{ }

min f(x, y) : g(x, y) = 0, h(x, y) = 0 (3.3)

x

n'admet pas une solution unique.

Au chapitre deux, nous avons vu qu'on peut pour ce faire utiliser l'approche optimiste ou l'approche pessimiste; mais il nous a été donné de constater que ces deux approches présentent de graves défauts dont certains (par exemple le problème d'instabilité de la solution) peuvent être contournés tandis que d'autres, (par exemple le problème d'éloignement de la solution optimiste ou péssimiste de la solution optimale du PBN) n'ont pas encore pu être résolus.

Pour éviter ces défauts, une autre approche a été développée dans la littérature et fait actuellement l'objet de nombreuses recherches : c'est l'approche par régularisation. A ce jour on distingue deux techniques de régularisation : la régularisation de Tykhonov et la régularisation par l'élément de plus petite norme.

3.1 La régularisation de Tykhonov

Cette technique consiste à introduire un paramètre (dit de régularisation) dans le problème du suiveur de façon à ce que le nouveau problème (le problème du suiveur régularisé) admette pour chaque paramètre de régularisation une solution unique fortement stable. Cette solution unique converge vers une solution du problème du suiveur original lorsque le paramètre de régularisation tend vers zéro (sous l'hypothèse que les fonctions qui définissent le problème

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

satisfont certaines conditions de régularité).

Par cette technique, la solution obtenue est une approximation de la solution du PBN original, mais qui a l'avantage d'être stable et qui parfois est même meilleure que la solution optimiste ou péssimiste.

Lemme 3.1.1. Si le problème du suiveur (3.3) est convexe, (i.e les fonctions f(. , y), gi(. , y) i = 1, ... ,p sont convexes et les fonctions hj(. , y) j = 1, ... ,q sont affines linéaires sur Rⁿ pour y fixé dans R^m.)

Si en plus F(., y) est strictement convexe pour y fixé dans R^m, alors :

(i) la fonction f(. , y) + áF(. , y) est strictement convexe Vá > 0 Vy E R^m ;

(ii) le problème

{ }

min f(x, y) + áF(x, y) : g(x, y) < 0, h(x, y) = 0 (3.4)

x

admet une solution unique pour tout á > 0 tel que l'ensemble des solutions admissibles de (3.4) est non vide.

preuve :

(i) Montrons que f(. , y) + áF(. , y) est strictement convexe Vá > 0 Vy E R^m. Soient y E R^m , á > 0, x, z E Rⁿ, t E [0, 1]

on a :

f(tx + (1 - t)z, y) < tf(x, y) + (1 - t)f(z, y) (car f(. ,y) est convexe)

~áF(tx + (1 - t)z, y) < á~tF(x, y) + (1 - t)F(z, y) (car F(. ,y) est strictement convexe ) < átF(x, y) + á(1 - t)F(z, y).

d'où

f(tx+(1-t)z, y)+áF(tx+(1-t)z, y) < t(f(x, y)+áF(x, y))+(1-t)(f(z, y)+áF(z, y)) Donc f(., y) + F(., y) est strictement convexe.

(ii) Soit á > 0 tel que l'ensemble des solutions admissibles de (3.4) est non vide.

Montrons que (3.4) admet une solution unique ;

Supposons que (3.4) admet deux solutions distinctes {x(y)}et{z(y)}. g étant convexe et h affine linéaire, pour y fixé dans R^m, 2x(y) + 2z(y) est une solution admissible de (3.4). En effet,

g (¹x(y) + ₂z(y),y) ~ ₂g(x(y),y) +¹₂g(z(y),y) ~ ₂.₀+ ¹₂.0 = 0

h (x(y) + ₂z(y),y) = ₂h(x(y),y) + ₂h(z(y),y) = ₂.0+ ¹₂.0 = 0

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

Puisque f(. , y) + áF(. , y) est strictement convexe,

f (x(y) + ₂z(y), y + áF (2x₍y) + 2z(y), y) < 2 (f(x(y), y) + áF(x(y), y))+

1 ~f(z(y), y) + áF(z(y), y)

2

<

2min { f(x, y) + áF(x, y) : x E M(y)}+

x

1

2

{ }

min f(x, y) + áF (x, y) : x E M(y)

x

{ }

< min f(x, y) + áF (x, y) : x E M(y)

x

ce qui est absurde.

Si les assertion du theorème1.3.1 sont satisfaites, alors

Øá(y) = Argmin x

{ } f(x, y)+áF(x, y) : g(x, y) < 0 , h(x, y) = 0 est semi-continue supérieurement.

La régularisation de Tykhonov consiste à remplacer le problème (3.1)-(3.2) par :

{ }

min F(x, y) : y E Y, x E Ø_á(y) (3.5)

y

Où

Øá(y) = Argmin x

{ } f(x,y) + áF(x,y) : g(x,y) < 0 ,h(x,y) = 0 (3.6)

F : 1[8ⁿ x 1[8^m -? 1[8 est strictement convexe par rapport à la première variable; f : 1[8ⁿ x 1[8^m -? 1[8 ainsi que toutes les fonctions composantes de g : 1[8ⁿ x 1[8^m -? 1[8^p sont convexes par rapport à la première variable; h : 1[8ⁿ x 1[8^m -? 1[8^kest affine linéaire sur 1[8ⁿ par rapport à la première variable. Le problème du suiveur régularisé est défini par :

min

x

{ }

f(x,y) + áF(x,y) : g(x, y) < 0, h(x, y) = 0 (3.7)

L'idée d'utiliser cette méthode est due à A.N.Tykhonov [25]. On a le résultat suivant :

Théorème 3.1.1. Si les assertions (C), (MFCQ) sont satisfaites pour (3.5)-(3.6) en y = y° et si V _xxF(x, y) est définie positive en tout point (x, y), alors :

(i) l'unique solution optimale x_á(y) E Ø_á(y) est fortement stable pour tout á > 0 et est directionnellement différentiable.

(ii) Pour tout á > 0, on a les inégalités suivantes :

F(xá(y), y) < min { }

F (x, y) : x E Ø(y)

x

f(xá(y), y) > ?(y) = min { }

f(x, y) : g(x, y) < 0, h(x, y) = 0

x

(iii) Pour y fixé dans 1[8^m ,

{ }

lim ~x_á(y)~ = Argmin F(x, y) : x E Ø(y)

á?)+ x

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

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

Preuve :

On se place sous les hypothèses du théorème.

(i) Puisque (3.4) est un problème d'optimisation paramétrique convexe et que V _xxF(x, y) est définie positive, les conditions du théorème 1.3.1 sont satisfaites [26] ; d'où x_á(y) est fortement stable pour tout á > 0 et est directionnellement différentiable.

(ii) On a g(xá(y), y) < 0 et h(xá(y), y) = 0

d'où

f(xá(y), y) >_ min {f(x,y) : g(x, y) < 0, h(x, y) = 0} = ?(y).

Montrons que F(xá(y), y) < min { }

F (x, y) : x E Ø(y)

x

Supposons que

F(xá(y), y) > min { }

F (x, y) : x E Ø(y)

x

alors

x E Ø(y) = {?(y), y E R^m} : F(xá(y), y) > F(x, y)

d'où

?y0 E IIB^m : áF (x_á(y0), y0) > áF (?(y0), y0) (car á > 0)

Or on a

f(xá(y), y) >_ ?(y) Vy E 118^m

donc

f(x_á(y0), y0) + áF(x_á(y0), y0) > ?(y0) + áF(x, y0) ce qui contredit le fait que x_á(y) E Ø_á(y).

(iii) D'après (ii), on a F(xá(y), y) < min { }

F (x, y) : x E Ø(y)

x

Puisque F est continue, on a :

lim

á?0+

d'où

F(xá(y), y) = F (áli _ô+ xa(y), y) = min {F(x, y) : x E Ø(y)}

x

{ }

lim ~x_á(y)~ = Argmin F (x, y) : x E Ø(y)
·

á?0+ x

L'assertion (iii) de ce théorème peut être interprétée comme suit : pour y fixé dans R^m, lorsque á tend vers 0⁺, l'unique solution du problème du suiveur régularisé par la méthode de Tykhonov converge vers la solution du problème original du suiveur, qui permet au leader de minimiser sa fonction objectif.

Ainsi, {x_á(y)} tend (lorsque á --* 0⁺) vers la solution du problème du suiveur recherchée dans l'approche optimiste. L'avantage ici est que x_á(y) est fortement stable et même lorsque l'approche optimiste n'est pas envisageable, cette approximation de la solution du PBN pourra être atteinte.

En utilisant le concept de å-optimalité, S.Addoune dans [27] énonce une autre version du théorème précédent. Avant d'y arriver, Commençons par définir la notion de solution å-optimale.

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

Définition 3.1.1. Soit e > 0

Une solution e-optimale du problème du suiveur (3.7) est un élément de l'ensemble

{ }
Tá,E(y) := x E M(y) : f(x, y) + áF(x, y) < ?_á(y) + e

Où M(y) est l'ensemble des solutions admissible de (3.7) et

{ }

?_á(y) := min f(x, y) + áF (x, y) : x E M(y)

x

Théorème 3.1.2. Soit á > 0 , e > 0

Si l'assertion (C) est satisfaites pour le problème du suiveur (3.4), alors il existe une constante c telle que

Tá,E(y) C _T0,E+ác(y) pour tout y E Y

Preuve :

{ }

D'après (C) K = (x, y) E Rⁿ x Y : x E M(y) est compact. Puisque F est continue, il existe des réels b et c tels que

b < F(x, y) < b + c V(x, y) tels que y E Y et x E M(y)

Ceci implique que

f(x, y) + áF(x, y) > ?(y) + áb V(x, y) tels que y E Y et x E M(y)

{ }

Où ?(y) = ?0(y) = min f(x, y) : x E M(y) .

x

Soit x E _Tá,E(y) alors,

f(x, y) + áb < f(x, y) + áF(x, y) < ?á(y) + e (par definition de Tá,E(y))

i.e

f(x,y) + áb < min

x

< min

x

{ }

= min f(x, y) : x E M(y) + á(b + c) + e

x

{ }

f(x,y) + áF(x,y) : x E M(y) + e

{ }

f(x,y) + á(b + c) : x E M(y) + e

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

d'où

f(x, y) < ?(y) + ác + e

i.e x E T0,E+ác(y) donc

Tá,E(y) C _T0,E+ác(y) pour tout y E Y

Dans le théorème précédent, _T0,E+ác(y) représente l'ensemble des solutions (e+ác)-optimale du problème du suiveur original pour le paramètre fixé y, donc plus rigoureusement, on devrait écrire _TE+ác(y) au lieu de T0,E+ác(y).

Le théorème que nous allons à présent énoncer permet de comparer la solution du problème régularisé et celle du problème original.

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

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

Théorème 3.1.3. Si les hypothèses du théorème 3.1.2 sont satisfaites, alors pour tout x ? Wá,å(y), y ? Y on a :

min {F(x, y) : x ? W(y)} + a = F(x, y) = min {F(x, y) : x ? W0,å+ác(y)}

x x

Ceci implique que :

et

x,y

min {F(x, y) : x ? W(y)} + á = min {F(xá,å(y), y) : x ? W(y)} y
min {F(x_á,å(y),y) : x ? W(y)} = min {F(x, y) : x ? W0,å+ác(y), y ? Y}

y x,y
Où xá,å(y) ? W0,å+ác(y) ?y

Preuve :

Soit y ? Y, x ? Wá,å(y) alors,

{ } {F(x(y), y) : x ? W0,å+ác(y)}

F(x, y) = min F(x, y) : x ? Wá,å(y) = min

x y

(car Wá,å(y) ? W0,å+ác(y) pour tout y ? Y )

D'autre part, on a par définition :

{ }

f(x, y) + áF(x, y) = ?_á(y) + å = min f(x, y) + áF(x, y) : x ? M(y) + å

x

= min

{} + å (carW(y) ? M(y)) f(x,y) + áF(x, y) : x ? W(y) { }

x

= min

x

= ?(y) + min

x

= f(x, y) + á min

?(y) + áF(x,y) : x ? W(y) + å

{ }

áF(x,y) : x ? W(y) + å

{ }

x

d'où donc

F(x, y) : x ? W(y) + å

F(x, y) = min {F (x, y) : x ?Ø(y)} + a

min {F(x, y) : x ? W(y)} + a = F(x, y) = min {F(x, y) : x ? W0,å+ác(y)}

x x

En prenant le minimum de chaque membre de ces inégalités, on obtient la dernière implication du théorème.
·

Le corollaire suivant découle de la dernière implication du théorème 3.1.3 :

Corollaire 3.1.1. Sous les hypothèses du théorème 3.1.2, si á?0⁺å?0⁺tel que ^å_á?0, alors

{ } { }

min F(x, y) : x ? Wá,å(y) -? min F(x,y) : x ? Ø(y)

x x

et	{ } { } min F(x, y) : x ? Wá,å(y), y ? Y -? min F(x,y) : x ? W(y), y ? Y x,y x,y

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

Notons que les assertions du théorème 3.1.1 ne sont pas toujours vérifiés lorsque simultanément on fait tendre á vers 0⁺ et y vers y⁰. L'exemple 3.1.1 illustre ce fait :

Exemple 3.1.1. Soit le PBN

_{n o}

y

min (x - y)² + y² : -20 < y < 20, x E Ø(y)

Où	Ø(y) = Argmin nxy : -y - 1 < x < -y + 1o x

Le problème régularisé correspondant par la méthode de Tykhonov est :

_{n o}

min (x - y)² + y² : -20 < y < 20, x E Ø_á(y)

y

où

Øá(y) = Argmin x

n o xy + á(x - y)^2+ áy^2: -y - 1 < x < -y + 1

Posons

F(x, y) = (x - y)²
f(x, y) = xy

f_á(x, y) = xy + á(x - y)² + áy²

On a

V2 _xxF(x, y) = 2 > 0 d'où F est strictement convexe.

V²_xxf(x, y) = 0 d'où f est convexe.

Donc le problème régularisé admet une solution unique pour chaque paramètre de régularisation.

On a

V_xf_á(x, y) = y + 2á(x - y) = 2áx + y(1 - 2á) V_xf_á(x,y) = 0 ~x = y(1 - 2a)

Dont le seul point critique est x = y(1 - 12á), pour á fixé. posons 0 < á < 41

-y - 1 < x < -y + 1 ~-y - 1 < y(1 -21á) < -y + 1

?	2á	< y <	2á
	4á - 1		4á - 1

Si y > - 2á

4á-1^,

alors puisque 0 < á < ¹₄, y>0

on a

Argmin

x

nxy + á(x - y)² + áy² : -y - 1 < x < -Y+11=--Y-- 1

y+1}=--y-1

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

Si y < 2á

4á-1 alors y < 0 d'où

Argmin x

n o xy + á(x - y)^2+ áy^2: -y - 1 < x < -y + 1 = -y + 1

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

donc pour 0 < á < ^14, Pour y = 2á, on a

xá(y) =

{

- y - 1 si y > - 2á 4á-1 y(1 - 1 2á) si ^2á 4á-1 = y = - 2á 4á-1 - y + 1 si y < 2á 4á-1

2á

= y =

2á

4á - 1

4á - 1

d'où x_á(y) = y - y2á = y - 1 Or on a

lim

á?0+

x_á(y) = lim y - 1 = -1 =6 0 = Argmin {x² : x ? Ø(0)}

x

y?0

Malgré ce défaut, la solution du problème du suiveur régularisé est plus régulière que les solutions du problème du suiveur original. En plus {x_á(y)} étant directionnellement différen-tiable, on peut envisager l'application de l'algorithme de descente pour la détermination de la solution du PBN [11].