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.5 Algorithmes et méthodes de résolution des PBN

La littérature nous propose dans le cas de l'unicité de la solution du problème du suiveur, plusieurs algorithmes permettant le calcul de la (ou des) solution(s) de (1.7) - (1.8). Nous présentons dans ce paragraphe un algorithme inspiré de la méthode de descente connue en optimisation à un niveau et un algorithme dit du paquet.

1.5.1 Algorithme de descente

Si le problème du suiveur admet une solution unique pour tout paramètre y alors (1.7) - (1.8) est equivalent à (1.12).

Supposons que (1.8) est un problème d'optimisation paramétrique convexe et que les assertions (MFCQ), (CRCQ) et (SSOC) sont satisfaites en tout point (x, y) tel que

x E Ø(y), G(y) < 0. Alors, d'après le théorème 1.3.1 l'unique solution optimale de ce problème est fortement stable. Par le théorème 1.3.5 elle est une PC-function et par conséquent la dite solution est localement Lipschtz-continue . Il s'ensuit que la fonction objectif de (1.12) est di-rectionnellement différentiable.

Ce qui motive à envisager un algorithme de descente[11]. La méthode consiste en : étant donné un point réalisable x chercher une direction de descente d E Rⁿ suivant laquelle F(.) décroît. Un nouveau point x + Ed (E > 0) est déterminé de façon à assurer une décroissance raisonnable de F(.) tout en demeurant réalisable pour le PBN. On construit ainsi une suite qui converge vers une solution stationnaire au sens de Clarke.

Définition 1.5.1. Soient f E C(Rp, R) et x E Rp.

1. On dit que d E Rp\{0} est une direction de descente en x s'il existe E_o > 0 tel que

f(x + Ed) < f(x) VE E [0, E0].

2. On dit que d E Rp\{0} est une direction de descente stricte en x s'il existe E_o > 0 tel que f(x + Ed) < f(x) VE E [0, E_o].

Définition 1.5.2. Soit f : Rp -> R une fonction et z E Rp. Si f est localement Lipschtz-continue, z est dit stationnaire au sens de Clarke si 0 E ?f(z) ; si f est pseudodifférentiable, le point z est dit pseudostationnaire si 0 E (z).

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

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

Algorithme de descente

Entrée : Les paramètres du PBN (1.7) - (1.8). Sortie : Une solution stationnaire au sens de Clarke.

1. Choisir y⁰ satisfaisant G(y⁰) < 0;

2. Initialiser k := 1

3. Déterminer une direction r^k, 1r^k1 > 1 satisfaisant F(y^k, x^k) < s^k V_yGi(y^k)r^k < -Gi(y^k) + s^k, Z = 1, ..., l et s^k < 0;

4. Choisir un pas de longueur t^k tel que F(y^k + t^kr^k) < F(y^k) + Et^ks^k, G(y^k + t^kr^k) < 0

5. Initialiser x^k+1 := x^k + t^kr^k , déterminer x^k E ø(y^k) ; incrementer k := k + 1;

6. Si un critère d'arrêt est satisfait, arrêter ; sinon aller à l'étape 2.

On se donne en général un critère d'arrêt de la forme x^k+1 - _xk ~< E. De plus, puisque la convergence n'est pas toujours assuré, une règle de base est de fixer le nombre d'itérations maximale K^max.

Sous certaines conditions de régularité, on montre [11] que chaque point d'accumulation de la suite (x^k, y^k) obtenue au moyen de l'algorithme est un point stationnaire de (1.7) - (1.8) au sens de Clarke.