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 régularisation par l'élément de plus petite norme

3.2.1 première méthode

Si la fonction objectif du leader F ne possède pas toutes les propriétés requises pour que puisse être appliquée la régularisation de Tykhonov, une autre méthode dénommée régularisation par l'élément de plus petite norme peut être appliquée.

Cette méthode consiste à prendre comme approximation de la solution du problème du suiveur

{x(y)} = Ø⁰(y) ; (sous réserve que Ø⁰(y) est un singleton)

Où pour tout y ? 1[8^m

Ø^0(y) = Argmin x

{kxk : x ? Ø(y)}

Cette technique de régularisation à été utilisée pour la première fois par P.Loridan et J.Morgan en 1992 dans [28] en appliquant une idée de V.F.Solohovic émise en 1970 dans [29].

Mais il se trouve malheureusement que l'utilisation de cette approche ne permet pas de contourner toutes les difficultés rencontrées dans les approches optimiste et péssimiste respec-

tivement. En effet, la fonction Ø^0(.) : y 7? Argmin x

{kxk : x ? Ø(y)} n'est pas en général

semi-continue inférieurement. Ceci peut être observé dans l'exemple suivant :

Exemple 3.2.1. [28] On considère le PBN :

min

y

{ - xy : x ? Ø(y)}

Où

Ø(y) = Argmin {(y - 0.5)x : 0 = x = 1}

x

Ø(y) =

{

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

On a

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

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

°(y) ={{0}

si y = 0.5

{1} si y < 0.5

d'où

(

0 si y = 0.5

F(x(y), y) =

-y si y < 0.5

Où {x_á(y)} = Ø^°(y)

L'infimum de F sur [0,1] est égal à -0.5 Pourtant, il n'existe pas de y appartenant à [0,1] tel que F(x(y),y) = -0.5

donc Ø^°(.) n'est pas semi-continue inférieurement.

Il est tout de même possible de contourner cette difficulté. Ceci se fait en utilisant à nouveau le concept de solution å-optimale.

On pose :

Ø^°E(y) = Argmin x

n o kxk : x ? ØE(y)

Où

_{n o}

Ø_E(y) = x ? M(y) : f(x, y) = ?(y) + å

Si le problème (3.4) est convexe, alors Ø_E(y) est réduit à un singleton sous réserve que Ø(y) =6 Ø [11]. On alors note x_E(y) l'unique élément de Ø_E(y).

On a le théorème suivant :

Théorème 3.2.1. [28]

On considère le problème d'optimisation paramétrique convexe (3.3) en y = y^°.

Si les assertions (C) et (MFCQ) sont satisfaites en tout point (x, y^°) avec x ? M(y^°), alors

E?°+

lim x_E(y) = x°(y)

preuve : On a

_{n o n o}

x ? M(y) : f(x,y) = ?(y) ? x ? M(y) : f(x,y) = ?(y) + å ?å > 0

i.e

Ø°(y) ? Ø_E(y) ? å > 0

ainsi

x°(y) ? Ø_E(y)

d'où

x_E(y) = min kxk, x ? Ø_E(y) = x°(y) < +8, ? å > 0

x _{n o}

Donc la suite {x_E(y)}_E est borné et par conséquent admet un point d'accumulation x.

Ainsi, la suite {x_E(y)}_E admet une sous suite que nous notons encore {x_E(y)}_E qui converge vers x

Or

x_E(y) ? M(y) et f(xE(y), y) = ?(y) + å ?å > 0

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

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

d'où lorsque å ? 0⁺, x ? M(y) et f(x, y) = ?(y) i.e

x ? Ø0(y) = Ø(y)

Par ailleur, on a i.e

kxk = lô å

Ilxå(y) Ilx0(y) Il

kxk = Ilx0(y) avec x, x0(y) ? Ø(y)

d'où x = x0(y) par unicité de l'élément de plus petite norme de Ø(y) = Ø0(y) (grace à la convexité du problème (3.3))
·

Ainsi, le PBN régularisé par la méthode de la plus petite norme s'écrit :

_{n o}

min F (x_å(y), y) : y ? Y

y

Où {xå(y)} = Argmin x		n o kxk : x ? Øå(y) ,å > 0
Posons	S = {(x,y) : y ? Y, x ? Ø(y), F(x, y) = inf ?p(z) }

Où

_{n o}

?_p(z) = max F (x, z) : x ? Ø(z)

x

S est l'ensemble des solutions admissibles du problème du leader qui sont plus bonnes que la solution péssimistique du PBN (3.1)-(3.2). On l'appelle ensemble des sous-solutions optimales de (3.1)-(3.2).

On a le résultat suivant :

Théorème 3.2.2. [28]

On suppose que le problème du suiveur (3.3) est convexe et que les assertions (C) et (MFCQ) sont satisfaites en tout point (x, y), x ? M(y) et y ? Y .

Pour toute suite (å^k)_k (å^k > 0 ?k) convergeant vers 0⁺, on considère la suite (y^k)_k tel que

yk ? Argmin y

n o F(x, y) : x ? Ø^0åk(y), y ? Y ?k.

Tout point d'accumulation (x, y) de la suite {xåk(yk), yk}8k=1 est une sous-solution optimale du PBN (3.1)-(3.2) ; i.e (x, y) ? S.

Preuve :

_{n o}

Posons K = (x, y) ? Rⁿ × Y : x ? M(y) ; d'après (C), K est compact.

Soit (x, y) un point d'accumulation de {xåk(yk), yk}k=1 ( qui existe car (xåk(yk), y^k) ? K ?O ;

On veut montrer que (x, y) ? S, i.e F(x, y) = inf z		?p(z).
Supposons que F(x, y) > v = inf z	?p(z).

{x_åk(y^k),y^k}⁸_k=1 admet une sous-suite que nous notons encore {x_åk(y^k),y^k}⁸_k=1 qui converge

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

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

vers (x, y). Soit

(F (x, y) - v)

0 < ä <

3

Puisque F est continue,

F (xåk(yk), y^k) -?

k--00 F(x, y)

d'où

~~ < ä

?K1 ? N : k > K1 = ~~F(xåk(yk), y^k) - F(x, y)

= -F(xåk(yk), y^k) + F(x, y) < ä

= F (xåk(yk), y^k) > F(x, y) - ä > 3ä + v - ä

= F(xåk(yk), y^k) > v + 2ä

Puisque K est compact et ?_p semi-continue inférieurement, v est fini et ?z ? P2(K) : v = ?_p(z)

z

z ? P2(K) = ?(z^t) ? P2(K) : z^t -?

t--00

= ?(z^t) ? P2(K) : ?_p(z^t) -??_p(z) = v

t--00

d'où ?t1 ? N : t > t1 = ?_p(z^t) = v + ä.

z^t.

Soit t > t1 fixé. Puisque z^t ? P2(K),

?(v^k)k ? P2(K) : v^k -?

k--00

Soit la suite (u^k)k définie par u^k ? Ø_åk(v^k) ?k

{ }

F(x, z^t) : x ? Ø(z^t)

Soit u un point d'accumulation de (u^k)k (qui existe car (u^k)k ? P2(K)) ; d'après le theorème 3.2.1, u ? Ø(z^t) ;

d'où

F(u, z^t) = ?_p(z^t) = max

x

(u^k)k admet une sous-suite que nous notons encore (u^k)k qui converge vers u ; étant donné que F est continue, on a :

d'où

F(u^k, v^k) -? k--00

F(u, z^t)

?K2 ? N : k > K2 = F(u^k, v^k) = F (u, z^t) + ä = F(u^k, v^k) = ?_p(z^t) + ä

Ainsi pour t > t1 et k > max (K1, K2), on a

F(u^k, v^k) = ?_p(z^t) + ä = v + 2ä < F(x_åk(y^k), y^k)

Ce qui contredit le fait que y^k? Argmin y		{ } F(x, y) : x ? Ø^0åk(y^k), y ? Y .
donc F(x, y) = inf z	?p(z). ·

Ce théorème montre qu'en résolvant le PBN (3.1)-(3.2) en utilisant cette méthode, on aboutit à une solution qui est meilleure que la solution pessimiste.

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