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

1.3 Quelques résultats d'optimisation paramétrique

On considère le problème (1.8) pour y fixé dans 1[8^m ; avec les fonctions f, g et h suffisamment régulières.

On considère l'application M : 1[8^m -> 2' définie par :

{ }

M(y) := x E 1[8ⁿ : g(x, y) < 0 et h(x, y) = 0 pour tout y E 1[8^m.

M(y) est l'ensemble réalisable de (1.8) pour le paramètre fixé y. On défini l'ensemble des minimaux locaux de (1.8) par

{ }

Øloc(y) = x E M(y) : ?E > 0 avec f(x, y) < f(z, y) Vz E M(y) n V_å(x) ;

{ }

où V_å := z E Rⁿ : 11x - z11 < E est la boule ouverte centré en x et de rayon E.

Soit L(x, y, À, u) := f(x, y) + À^Tg(x, y) + u^Th(x, y) , le lagrangien du problème (1.8).

Genéralités sur la programmation mathématique à deux niveaux 7

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

On pose :

{ }

A(x, y) := (À, u) E 1[8^p x 1[8^q : À > 0, À^Tg(x, y) = 0, V_xL(x, y, À, u) = 0

{ }

L'ensemble SP(y) = x E M(y) : A(x, y) =6 0 est appelé l'ensemble des points station-

naires du problème (1.8)

Dans la suite, nous utiliserons abondamment l'assertion suivante :

{ }

(C) : l'ensemble (x,y) E 1[8ⁿ x 1[8^m : g(x, y) < 0, h(x, y) = 0 est non vide et compact

Définition 1.3.1. Soit y0 E 1[8^m, x0 E M(y0)

On dit que lescontraintes de qualification de Mangasarian-Fromowitz (MFCQ) sont satisfaites au point (x0, y0) s'il existe une direction d E 1[8ⁿ satisfaisant :

Vxgi(x0, y0)d < 0 pour tout i E I(x0.y0) := {j : gj(x0, y0) = 0}

Vxhj(x0, y0) = 0 pour tout j = 1, ...., q

}, , q sont linéairement indépendants.

{et les gradients Vxhj(x0,y0) : j = 1

Définition 1.3.2. soit y0 E 1[8^m et x0 E SP(y0)

On dit que les conditions suffisantes d'optimalités forte (SSOC) sont satisfaites au point (x0, y0) si pour tout (À, u) E A(x0, y0) et pour tout d =6 0 satisfaisant :

(i) Vxgi(x0, y0)d = 0 pour tout i E J(À) := {j : Àj > 0}

(ii) Vxhj(x0, y0) = 0 pour tout j = 1, ..., q on a dTV _xxL(x0, y0, À, u)d > 0.

Définition 1.3.3. On dit que les contraintes de constance de rang (CRCQ) sont satisfaites au point (x0, y0) si il existe une boule ouverte centrée en (x0, y0) de rayon e > 0 W_å(x0, y0)

tel que pour tout sous ensembles I Ç I(x0, y0) := {i : gi(x0, y0) = 0} ; J Ç {1, ...., q} , la

{ } { }

famille de gradients V_xgi(x,y) : i E I U Vxhj(x0,y0) : j E J ait le même rang pour tout (x, y) E W_å(x0, y0).

Définition 1.3.4. Une fonction f : 1[8^k -- 1[8 est dite semi-continue inférieurement au point

zn = z on a lim inf n?oo

f(zn) > f(z) .

z E 1[8^k si pour toute suite {zn}^oon°1 Ç 1[8^k avec lim

n?oo

f est dite semi-continue supérieurement au point z E 1[8^k si pour toute suite {zn}oon°1 Ç 1[8^k

avec lim n?oo

zn = z on a lim sup n?oo

f(zn) < f(z) .

Genéralités sur la programmation mathématique à deux niveaux 8

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

Définition 1.3.5. Une fonction F : R^k -? 2^Rl est dite semi-continue supérieurement au point z ? R^k si pour tout ensemble ouvert Z avec F(z) ? Z , il existe une boule ouverte centrée en z, Uä(z); 8 > 0 telle que F(z^') ? Z pour tout z^' ? Uä(z).

F est dite semi-continue inférieurement au point z ? R^k si pour tout ensemble ouvert Z avec F(z) n Z =6 Ø , il existe une boule ouverte centrée en z, Uä(z); 8 > 0 telle que F(z^') n Z =6 Ø pour tout z^' ? Uä(z).

Définition 1.3.6. Une fonction F : R^k -? 2^R1 telle que F(y) est non vide et compact pour tout y ? R^k est dite Lipchitz-continue supérieurement en un point z ? R^k si il existe une boule ouverte centrée en z, (Uä(z); 8 > 0) et une constante K < 8 telle qu'on a pour tout z^' ? Uä(z), l'inclusion F(z^') ? F(z) + Kkz - z^'kB^l ; où B^l désigne la boule unité de R^l.

F est dite Lipschtz-continue inférieurement en un point z ? R^k si il existe une boule ouverte centrée en z,( Uä(z); 8 > 0) et une constante L < 8 telles que pour tout z', z^'' ? Uä(z), on a l'inclusion F(z^') ? F(z^'') + Kkz^'' - z^'kB^l.

Définition 1.3.7. L'optimum local x0 ? Øloc(y0) est dit fortement stable s'il existe une boule ouverte centré en y0 (Uä(y0), 8 > 0) , une boule ouverte centré en x0 (V_å(x0), å > 0) et une fonction continue

x : Uä(y0) -? V_å(x0) tel que x(y) soit l'unique optimum local du problème (1.8) dans V_å(x0) pour tout y ? Uä(y0).

Théorème 1.3.1. [16] Soit y0 ? R^m. On suppose que les assertions (MFCQ) et (SSOC) sont satisfaites pour (1.8) en (x0, y0) avec x0 ? Øloc(y0). Alors l'optimum local x0 est fortement stable.

La preuve originale de ce théorème dans [16] utilise une théorie que nous n'avons pas abordé dans ce travail : la théorie du degré. Dans [11], ce résultat est démontré autrement en supposant qu'en plus, ( 1.8) satisfait les contraintes d'indépendance linéaire (LICQ) en (x0, y0).

Définition 1.3.8. On dit que (1.8) satisfait les contraintes d'indépendance linéaire (LICQ) en (x0, y0) si la famille de gradients :

_{n o} [ _{n o}

?xgi(x0, y0), i ? I(x0, y0) ?xhj(x0,y0),j = 1, ..., q est linairement independante.

Où I(x0, y0) := i : gi(x0, y0) = 0

Définition 1.3.9. Une fonction f : Rp -? Rq est dite localement Lipschitz-continue au point x0 ? Rp s'il existe une boule ouverte centré en x0, (V_å(x0), å > 0) et une constante K < 8 tel que

f(x) - f(x^') . = Kkx - x0k pour tout x, x^' ? V_å(x0)

F est dit localement Lipschitz-continue supérieurement en x0 si pour toute boule ouverte centrée en x0 ? V_å(x0), å > 0 et pour une certaine constante K < 8, on a l'égalité :

f(x) - f(x0) = Kkx - x^'k pour tout x ? V_å(x0)

Genéralités sur la programmation mathématique à deux niveaux 9

Définition 1.3.10. Une fonction f : 1[8p -? 1[8q est appelé PC-function (piecewise continuously differentiable function) en x0 s'il existe une boule ouverte centrée en x0 (V_å(x0) , e > 0) et un nombre finie de fonctions continûment différentiables

fi :V_å(x0) -? 1[8^q, i = 1, ..., t

tel que f est continue sur V_å(x0) et f(w) ? {f1(w), ..., ft(w)}. pour tout w ? V_å(x0).

Théorème 1.3.2. [17] Les PC-functions sont localement Lipschitz-continues avec pour constante de Lipschitz la plus grande constante de Lipschitz de la famille de fonction qui définit la PC-function.

La preuve de ce théorème nécessite le lemme suivant :

Lemme 1.3.1. [24]

Soit g : [0,1] -? 1[8p une fonction continue et soit la famille d'ensemble non vide fermé {Ai}qi=1 ? 1[8^m telles que

[ g([0,1]) := x?[0,1]

{g(x)} ?

[ ^qi=1

Ai

alors, il existe une suite de réels {ti}^r+1

i=0 avec t0 = 0, tr+1 = 1, ti < ti+1 ?i et la suite {ji}ri=0

i = 0, ...,r telle que

{g(ti), g(ti+1)} ? Aji i = 0, ..., r.

La preuve de ce lemme ce fait par induction sur le nombre r des différents ensembles Ai pour lesquels il existe des points t tels que g(t) ? Ai. On peut la trouver dans [11].

Preuve (du théorème) :

Soit f : 1[8p -? 1[8q une PC-function. Soit x0 ? 1[8p ; f est une PC-function en x0.

Par définition, il existe une boule ouverte V_å(x0) centrée en x0 de rayon e > 0 et un nombre finie de fonctions continûment différentiables

fi : V_å(x0) -? 1[8^q, i = 1, ..., k

telles que f est continue sur Vå(x0 et

f(u) = {f1(u), ..., fk(u)} ?u ? V_å(x0)

soit x, y ? V_å(x0) Posons :

w(t) = f(x + t(y - x)), t ? [0, 1]

wi(t) := w(t) si fi (x + t(y - x)) = f(x + t(y - x))

x.

_{n o}

Ai = x ? V_å(x0) : fi(x) = f(x) .

Puisque f est continue sur V_å(x0), Ai est fermé.

En effet, soit {xk}k ? Ai une suite de points telle que xk ?

k?+8

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

Genéralités sur la programmation mathématique à deux niveaux 10

Il suffit de montrer que x ? Ai. On a :

(xk ? k?+8

x) =f(xk) ? f(x) (car f est continue sur Vå(x0)) k?+8

De même, puisque fi est continue sur V_å(x0), on a

(xk ? k?+8

x) fi(xk) k?+8 fi(x)

Étant donné que xk ? Ai ?k ? N, on a fi(xk) = f(xk) ?k ? N d'où

f(xk) ? f(x) et f(xk) ? fi(x)

k?+8 k?+8

et par unicité de la limite, on a f(x) = fi(x)

d'où x ? Ai. et par suite, Ai est fermé.

D'après le lemme 1.3.1, il existe des points t0 = 0 < t1 < ... < t_r < tr+1 = 1 tels que :

w(ti), w(ti+1) ? Ajz, i = 0, ..., r (i)

on a

f(y) - f(x) 1 1 = 1 lw(1) - w(0)Il=

r i=0

w(ti+1) - w(ti)

=

r i=0

wjz(ti+1) - wjz(ti)

(d'après (i))

r = E i=0 r = E i=0

wjz(ti+1) - wjz(ti)11 fjz (x + ti+1(y - x) - fjz(x + ti(y - x) 11

r = E i=0

Kjz x - ti+1(y - x) - ti(y - x) (car fjz est lip sur Vå(x0))

r = E i=0

Kji (ti+1 - ti)(y - x)

= max 1=j=k

Kjzky - xk

r i=0

|ti+1 - ti|

= Kky - xk

Où K = max j

Kjz est la plus grande constante de lipschitz des fonctions fi, i = 1, ... , k

Donc f est localement lipschitzienne.
·

L'intérêt des PC-function est qu'elles possèdent un grand nombre de propriétés qui sont d'une grande utilité dans l'optimisation paramétrique. Nous allons maintenant définir la notion de gradient généralisé au sens de Clarke.

Définition 1.3.11. Soit f : Rp -? R une fonction localement Lipschitz- continue. Le gradient généralisé au sens de Clarke de f en x0 est défini par :

?f(x0) = convn lim _k?8 ?f(xk) : k J

xk = xo, V f (xk) existeVk ?

00

où conv désigne l'enveloppe convexe.

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

Genéralités sur la programmation mathématique à deux niveaux 11

Théorème 1.3.3. [11] Soit f : 118p -> 118 une PC-function alors

_{n o}

?f(x0) = conv ?fi(x0) : x0 E cl int supp(f, fi)

où supp(f, fi) = {x : f(x) = fi(x)} ; cl int supp(f, fi) est l'adhérence de l'intérieur de l'ensemble supp(f, fi).

La preuve de ce théorème peut être trouvé dans [11]

Définition 1.3.12. Une fonction f : 118p -> 118 est dite différentiable en x0 dans la direction r E 118p si la quantité suivante existe et est finie :

f^0(x0, r) := lim t?o+

[f(x0 + tr) - f(x0)] t

f⁰(x0, r) est la dérivé de f dans la direction r en x0.

Définition 1.3.13. Une fonction directionnellement différentiable f : 118p -> 118 est dite Bouligand-différentiable (B-différentiable) en x0 si la dérivée directionnelle d'ordre 1 de f en x0 ; i.e

lim

x?x0

= 0

f(x) - f(x0) - f⁰(x0, x - x0)

kx - x0k

. Une fonction f localement Lipschitz-continue, directionnellement différentiable est B-différentiable

[20] et f⁰(x0, .) est une sélection continue de fonction linéaires :

_{n o}

f⁰(x0, r) E ?fi(x0)r : i E Io f(x0)

_{n o}

où Io f(x0) = i : x0 E supp(f, fi)

Définition 1.3.14. Une fonction f : 118p -> 118 est dite pseudodifférentiable en x0 si il existe une boule ouverte centrée en x0, (V_å(x0), å > 0) et une fonction semi-continue supérieurement Pf : V_å -> 2^Rp avec Pf(y) non vide, convexe et compact pour tout y E V_å(x0) telles que

f(x) = f(x0) + g(x - x0) + o(x, x0, g) Vx E V_å(x0)

où g E Pf(x) et lim ^o(xk,x0,gk)= 0 Pour toute suite {xk}k _i , {gk}k ₁ avec lim xk = 0, gk E

k?0 kxk-x_ok -- _k--

Tf(xk)

.

Le théorème suivant est fondamental en ce sens qu'il permet de transformer (1.7)-(1.8) en un problème d'optimisation à un niveau.

Théorème 1.3.4. Considèrons le problème (1.8) en y = y0 et supposons que les assertions (MFCQ), (SSOC), et (CRCQ) sont satisfaites en un point stationnaire x0 E sp(y0). alors x0 est fortement stable et l'unique fonction x(y) avec {x(y)} = Øloc(y) n V_å(x0) est une PC-function.

La preuve de ce théorème nécessite des notions que nous n'avons pas jusqu'ici abordées ; elle peut être néanmoins trouvée dans [11].

Le corollaire suivant découle des propriétés des PC-functions.

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

Genéralités sur la programmation mathématique à deux niveaux 12

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

Corollaire

Sous les hypothèses du Théorème 1.3.4 on a que la solution optimale locale x(y) est

? Localement Lipschitz-continue de jacobien généralisé au sens de Clarke donné par :

{ }

Ox(y0) = conv Vxi(y0) : i E Io x(y0)

? Directionnellement différentiable avec

{ }

x^'(y0, r) = Vxi(y0)r : i E Io x(y0)

? B-différentiable

? Pseudodifférentiable de différentielle

{ }

_x(y0) = conv Vxi(y0) : i E I_x(y0)

Nous allons maintenant présenter quelques conditions sous lesquelles le problème (1.7)-(1.8) admet une solution locale ou globale. Nous ne traiterons dans le paragraphe suivant par soucis de clarté de notre exposé , que le cas où le problème du suiveur (1.8) admet une solution pour chaque paramètre y ; le cas de la non unicité qui constitue le coeur de notre travail sera traité au chapitre suivant.