L'Optimisation Multiobjectif et

Partage de variables d'optimisation

Pr. EL MOUMEN

Faculté des Sciences Aïn Chock

Automne 2024
 Introduction

L'optimisation multiobjectif

Dénition
L'optimisation multiobjectif est un domaine fondamental de l'aide à la
décision multicritere, auquel de nombreux milieux scientiques et industriels
se doivent de faire face.
La résolution d'un probleme d'optimisation multiobjectif consiste à
déterminer la solution correspondante au mieux aux préférences du
décideur.
L'une des questions les plus diciles est donc liée à l'identication de
l'ensemble Pareto optimal, ou d'une approximation de celui-ci pour des
problemes complexes.

(EL MOUMEN ) Master MNSA S3 FSAC - MNSA S3 2 / 53

 Formulation d'un probleme multiobjectif

Formulation d'un probleme multiobjectif

Dénition
Un probleme multiobjectif ou multicritere peut etre déni comme un
probleme où on cherche à optimiser plusieurs composantes d'un vecteur de
fonction objectif toute en satisfaisant un ensemble de contraintes.
Contrairement à un probleme mono-objectif, la solution n'est pas unique
mais constituée d'un ensemble de solutions dites de Pareto optimales.

La formulation mathématique d'un probleme d'optimisation multiobjectif

est donnée comme suit :

min F (x) = (f1 (x), ..., f` (x))T



s. t. hi (x) = 0 , i = 1, ...., m,


POM (1)

 gj (x) ≥ 0 , j = 1, ...., k,
xL ≤ x ≤ xU


avec x ∈ Rd est le vecteur des variables de décision, {f1 , ..., f` } est

l'ensemble des fonctions objectif.
(EL MOUMEN ) Master MNSA S3 FSAC - MNSA S3 3 / 53
 Formulation d'un probleme multiobjectif

Formulation d'un probleme multiobjectif

Notons par S = {x ∈ Rn hi (x) = 0, gj (x) ≥ 0 et xL ≤ x ≤ xU }

l'ensemble de décision.
Considérons l'application

F : S → Rp
(2)
x → F (x)

L'ensemble Z = F (S) s'appelle espace des critères ou espace des objectifs.

(EL MOUMEN ) Master MNSA S3 FSAC - MNSA S3 4 / 53

 Formulation d'un probleme multiobjectif

La gure suivante montre l'espace de décision S avec 3 variables de

décisions et l'espace des objectif à 2 objectifs.

(EL MOUMEN ) Master MNSA S3 FSAC - MNSA S3 5 / 53

 Formulation d'un probleme multiobjectif

Remarques

1 Si toutes les fonctions fi , gj et hl sont linéaires on parle

d'optimisation multiobjectifs linéaire qu'on note par (MOLP).
2 Si l'une de ces fonctions n'est pas linéaire, dans ce cas nous parlerons
d'optimisation multiobjectifs non linéaire qu'on note par (MONLP).
3 Si une ou plusieurs variables de décision est discrète (entière), on parle
d'optimisation multiobjectifs en nombres entiers et les fonctions sont
linéaires, on parle ainsi d'optimisation multiobjectifs linéaire en
nombres entiers qu'on note (MOILP)

(EL MOUMEN ) Master MNSA S3 FSAC - MNSA S3 6 / 53

 Formulation d'un probleme multiobjectif

Exemple de Problème d'optimisation multiobjectifs linéaire

Un artisan menuisier fabrique des portes et fenêtres en aluminium pour le

compte d'un promoteur immobilier. L'artisan et ses deux stagiaires travaille
8 heures par jours.
Sachant que toutes les portes et toutes les fenêtres sont de la même
dimension et la fabrication d'une porte nécessite une heure et une fenêtre
nécessite 90 minutes.
L'artisan devrait fabriquer au moins deux articles par jours et il pourrait
fabriquer au plus 5 portes et 4 fenêtres par jour. Les bénéces nets sont de
3000 Dhs pour une porte et 2000 Dhs pour une fenêtre. La fabrication
d'une porte cause une perte (déchet) 60 cm et 50 cm pour une fenêtre.
L'artisan souhaite maximiser ses bénéces et minimiser ses déchets,
modéliser ce problème sous forme d'un MOLP.

(EL MOUMEN ) Master MNSA S3 FSAC - MNSA S3 7 / 53

 Formulation d'un probleme multiobjectif

Notons par x1 le nombre de portes et x2 le nombre de fenêtres a fabriquer

par jour.
les contraintes sont :
1 x1 + 32 x2 ≤ 8 :temps de travail.
2 x1 + x2 ≥ 2 :la commande minimale.
3 x1 ≤ 5 et x2 ≤ 4 commande maximale.
Et les fonctions objectifs sont :
1 max f1 (x) = 3000x1 + 2000x2 (maximiser le prot total en Dirhams).
2 min f2 (x) = 0.6x1 + 0.5x2 (minimiser le déchet total en mettre).

(EL MOUMEN ) Master MNSA S3 FSAC - MNSA S3 8 / 53

 Formulation d'un probleme multiobjectif

Le problème multiobjectifs (MOLP) qui modélise ce problème peut s'écrire

comme suit :

(EL MOUMEN ) Master MNSA S3 FSAC - MNSA S3 9 / 53

 Formulation d'un probleme multiobjectif

La gure suivante montre l'ensemble réalisable de l'exemple :

(EL MOUMEN ) Master MNSA S3 FSAC - MNSA S3 10 / 53

 Formulation d'un probleme multiobjectif

(EL MOUMEN ) Master MNSA S3 FSAC - MNSA S3 11 / 53

 Formulation d'un probleme multiobjectif

La diculté principale

il n'existe pas de dénition de la solution optimale.

→ Le décideur peut simplement exprimer le fait qu'une solution est
préférable à une autre
il n'existe pas une solution meilleure que toutes les autres solutions.
Résoudre un problème multiobjectif ne consiste pas à rechercher la solution
optimale mais l'ensemble des solutions satisfaisantes pour lesquelles on ne
pourra pas eectuer une opération de classement.
Les méthodes de résolution des problèmes multiobjectif sont donc des
méthodes d'aide à la décision car le choix nal sera laissé au décideur.

(EL MOUMEN ) Master MNSA S3 FSAC - MNSA S3 12 / 53

 Formulation d'un probleme multiobjectif

Pour rèpondre à ce problème, la communauté scientique a adopté deux

types de comportement.
⇒ Ramener un problème multiobjectif à un problème mono-objectif en
utilisant des pondérations ;
⇒ Tenter d'apporter des réponses au problème en prenant en considération
l'ensemble des fonctions objectifs.

(EL MOUMEN ) Master MNSA S3 FSAC - MNSA S3 13 / 53

 Formulation d'un probleme multiobjectif

(EL MOUMEN ) Master MNSA S3 FSAC - MNSA S3 14 / 53

 Notions d'optimalité et de dominance

Lorsque nous voulons résoudre un problème d'optimisation multiobjectifs,

il s'agit de déterminer un ensemble de solutions ecaces ou l'ensemble
optimale au sens de Pareto ou l'ensemble de solution non dominées.
Sans perte de généralités, considérons le problème d'optimisation
multiobjectifs de type minimisation qui s'écrit comme suit

min F (x) = (f1 (x), ..., f` (x))T


POM (3)
s. t. x ∈ S

(EL MOUMEN ) Master MNSA S3 FSAC - MNSA S3 15 / 53

 Notions d'optimalité et de dominance

Solution ecace

Dénition
1 x̂ ∈ S est dite solution ecace ou optimale au sens de Pareto si
et seulement s'il n'existe pas une autre solution x ∈ S tel que
fi(x) ≤ fi (x̂)∀i = 1, 2, ..., l avec au moins une inégalité stricte. Le
vecteur critère ẑ = F (x̂) est dit vecteur où solution non dominé.
2 x̂ ∈ S est dite solution faiblement ecace ou faiblement
optimale au sens de Pareto si et seulement s'il n'existe pas une
autre solution x ∈ S tel que fi(x) ≤ fi (x̂)∀i = 1, 2, ..., l . Le vecteur
critère ẑ = F (x̂) est dit vecteur où solution faiblement non dominé.
3 x̂ ∈ S est dite fortement ecace si et seulement s'il n'existe pas une
autre solution x ∈ S tels que x 6= x̂ et fi (x) < fi (x̂)∀i = 1, 2, ..., l . Le
vecteur critère ẑ = F (x̂) est dit fortement non dominé.

(EL MOUMEN ) Master MNSA S3 FSAC - MNSA S3 16 / 53

 Notions d'optimalité et de dominance

La notion de dominance

Dénition
Soient z1 , z2 ∈ Rl , on dit que le vecteur z1 domine le vecteur z2 si :
 Dominance faible :∀i, i = 1, 2, ..., l z1 (i) ≤ z2 (i), et
 Dominance forte ∀i, i = 1, 2, ..., l z1 (i) < z2 (i).

Proposition
Les solution qui dominent les autres mais ne se dominent pas entre elles
sont appelées solutions non dominées ou solutions optimales au sens de
Pareto.
En d'autres termes, une solution réalisable x̂ ∈ S est dite ecace si son
image ẑ par l'application F (x) où ẑ = F (x̂) n'est pas dominée par aucune
autre solution.
Notons par XE l'ensemble de solutions ecaces et ZND l'ensemble de
solutions non dominées ainsi que ZND = F (XE ).
(EL MOUMEN ) Master MNSA S3 FSAC - MNSA S3 17 / 53
 Notions d'optimalité et de dominance

Exemple
Dans l'exemple ci-dessous, les points 1, 3 et 5 ne sont dominés par aucun
autre. Alors que le point 2 est dominé par le point 3, et que le point 4 est
dominé par les points 3 et 5.

(EL MOUMEN ) Master MNSA S3 FSAC - MNSA S3 18 / 53

 Notions d'optimalité et de dominance

Front de Pareto

Dénition
le front de Pareto est l'ensemble généralement non convexe constitué par
l'image des solutions ecaces dans l'espace des critères . En eet, le front
de Pareto est l'ensemble ZND = F (XE ).

La gure suivante montre le front de Pareto pour les diérentes situations

envisageables pour un problème de deux critères. Notons que, le front de
Pareto de chaque cas et la partie en gras de l'ensemble.

(EL MOUMEN ) Master MNSA S3 FSAC - MNSA S3 19 / 53

 Notions d'optimalité et de dominance

(EL MOUMEN ) Master MNSA S3 FSAC - MNSA S3 20 / 53

 Notions d'optimalité et de dominance

Les points caractéristiques

Dénition : (Point idéal)

le point idéal pour le cas de minimisation est le point z ∗ = (z1∗ , z2∗ , ..., zl∗ )
est le vecteur qui minimise chacune des fonctions objectifs fi
zi∗ = min fi (x), x ∈ S, i = 1, ..., l

Dénition : (Point Nadir)

Les coordonnées du point nadir correspondent aux pires valeurs obtenues
par chaque fonction objectif sur l'ensemble de solutions non dominées.

(EL MOUMEN ) Master MNSA S3 FSAC - MNSA S3 21 / 53

 Notions d'optimalité et de dominance

Dénition : (Matrice des gains)

Soit x̂j une solution optimale du critère fj . La matrice des gains l × l est
formée des éléments zji = fi (x̂j ) tels que

z11 · · · zi1 · · · zl1

 
 .. . . .. . . .. 
 . . . . . 
(4)
 i i

G =  z1 · · ·
 zi · · · zli 
 .. . . .. . . .. 

 . . . . . 
z1l ··· zil ··· zll

Avec zi∗ = zii où i = 1, ..., l

(EL MOUMEN ) Master MNSA S3 FSAC - MNSA S3 22 / 53

 Notions d'optimalité et de dominance

Exemple d'illustration

Pour bien illustrer tous ces points, nous introduisons le problème bi-objectifs
linéaire (MOLP) pour un cas de maximisation des fonctions objectif.

max f1 (x) = −3x1 + x2 ;



max f2 (x) = x1 − 2x2




x1 + x2 ≤ 15




2x1 + x2 ≥ 4


(MOLP)

 x1 − x2 ≤ 5
x1 ≤8




x2 ≤ 10




x1 , x2 ≥ 0


(EL MOUMEN ) Master MNSA S3 FSAC - MNSA S3 23 / 53

 Notions d'optimalité et de dominance

Exemple d'illustration

(EL MOUMEN ) Master MNSA S3 FSAC - MNSA S3 24 / 53

 Notions d'optimalité et de dominance

Exemple d'illustration

Représentation graphique de l'espace de décision S :

La gure montre l'ensemble réalisable S dans l'espace de décision .
L'ensemble S est un polyèdre convexe délimité par les 7 points extrêmes
a = (2; 0), b = (0; 4), c = (0; 10), d = (5; 10), e = (8; 7) ; f = (8; 3),
g = (5; 0).
On pose Xex = {a, b, c, d, e, f , g } l'ensemble des points extrêmes de S.
Représentation graphique de l'espace des critères Y :
Dans le cas linéaire pour avoir l'ensemble réalisable Y dans l'espace des
critères, il sut de calculer l'image de chaque point extrême de l'ensemble
de décision S pour avoir tout l'ensemble Y.

(EL MOUMEN ) Master MNSA S3 FSAC - MNSA S3 25 / 53

 Notions d'optimalité et de dominance

Exemple d'illustration

(EL MOUMEN ) Master MNSA S3 FSAC - MNSA S3 26 / 53

 Notions d'optimalité et de dominance

Exemple d'illustration

Représentation graphique de l'espace des critères Y :

La gure montre L'ensemble Y qui est un polyèdre convexe délimité par les
7 points extrêmes :
F (a) = (−6; 2), F (b) = (4; 8), F (c) = (10; −20), F (d) = (−5; −15),
F (e) = (−17; −6) ; F (f ) = (−21; 2), F (g ) = (−15; 5).
le point idéal, le point Nadir,et la matrice des gains :
Le point idéal z ∗ = (z1∗ , z2∗ ) est le point qui maximise les deux critères
séparément :

z1∗ = max f1 (x)

x∈S
et
z2∗ = max f2 (x).
x∈S

(EL MOUMEN ) Master MNSA S3 FSAC - MNSA S3 27 / 53

 Notions d'optimalité et de dominance

Exemple d'illustration
Graphiquement,la gure de l'espace de décision S, montre que :
La solution de (max f1 (x)) est le point c = (0; 10) et son image est
x∈S
F (c) = (10; −20).
La solution de (max f2 (x)) est le point g = (5; 0) et son image est
x∈S
F (g ) = (−15; 5).
Le point idéal est le point : z ∗ = (10; 5).
les coordonnées du point Nadir est Znad = (−15; −20), elles
correspondent aux pires valeurs des fonctions objectif sur le front de
Pareto.
La matrice des gains est
10 −15
 
M=
−20 5

(EL MOUMEN ) Master MNSA S3 FSAC - MNSA S3 28 / 53

 Transformation en un problème mono-objectif

Transformation en un problème mono-objectif

Cette approche, qualiée d'approche naive de l'optimisation multiobjectif

(MO), consiste tout simplement à transformer un problème multi-objectif
en un problème mono-objectif, qu'on peut résoudre par de nombreuses
méthodes de résolution.
Parmi les méthodes qui utilisent cette approche, nous pouvons citer :
les méthodes d'agrégation
les méthodes ε-contraintes
les méthodes de programmation par but et min-max

(EL MOUMEN ) Master MNSA S3 FSAC - MNSA S3 29 / 53

 Transformation en un problème mono-objectif Technique de pondération des fonctions objectifs

Méthode d'agrégation

Cette technique consiste à transformer le problème multiobjectifs en un

problème mono-objectif en attribuant des coecients (paramètres) de
pondération notée αi à chaque fonction objectif fi . On obtient alors un
problème d'optimisation mono-objectif à une seul fonction objectif qu'on
appelle problème paramétrique.
Le problème paramétrique noté par (Pα ) en question est dénis comme
somme pondérée des l fonctions objectifs tel que :
 Pl
min i=1 αi fi (x);
(Pα )
x ∈S

où
αi ≥ 0 représentent les poids aectés aux critères,
l
i=1 αi = 1 et l désigne le nombre de critères.
P

(EL MOUMEN ) Master MNSA S3 FSAC - MNSA S3 30 / 53

 Transformation en un problème mono-objectif Technique de pondération des fonctions objectifs

Remarque

Si le problème multiobjectifs (MOP) est linéaire et pour une certaine valeur

de vecteur α le problème paramétrique (Pα ) est aussi linéaire et sa
résolution peut se faire avec la méthode simplexe et sa solution optimale
est toujours un point extrême de l'ensemble réalisable.

(EL MOUMEN ) Master MNSA S3 FSAC - MNSA S3 31 / 53

 Transformation en un problème mono-objectif Technique de pondération des fonctions objectifs

Les théorèmes suivants nous montre les diérents aspects théoriques pour
caractériser une solution ecace du problème (MOP) en utilisant le
problème paramétrique α.
Théorème(Georion ,1968)
Soit x̂ ∈ S , x̂ est une solution ecace si et seulement si x̂ ∈ S est une
solution optimale du problème paramétrique (Pα ) pour un certain α ≥ 0.

Théorème(Iserman ,1974)
x̂ ∈ S est une solution optimale du problème paramétrique (Pα )
1 Si α ≥ 0 alors x̂ est faiblement ecace.
2 Si α > 0 alors x̂ est ecace.
3 Si α ≥ 0 et x̂ est l'unique solution optimale de (Pα ) alors x̂ est ecace.
En autre, si S est convexe alors :
1 Si x̂ est ecace alors il existe α > 0 tel que x̂ est une solution optimale
de (Pα ).
2 Si x̂ est faiblement ecace alors il existe α ≥ 0 tel que x̂ est une
solution optimale de (Pα ).
(EL MOUMEN ) Master MNSA S3 FSAC - MNSA S3 32 / 53
 Transformation en un problème mono-objectif Technique de pondération des fonctions objectifs

Exemple pour la méthode de pondération

Pour illustrer la méthode de pondération des objectifs, considérons le

problème multiobjectifs non linéaire (MONLP) suivant :

min f1 (x) = x12 + x22 ;



min f2 (x) = (x1 − 5)2 − (x2 − 5)2


(MONLP)

 −5 ≤ x1 ≤ 10
−5 ≤ x2 ≤ 10


(EL MOUMEN ) Master MNSA S3 FSAC - MNSA S3 33 / 53

 Transformation en un problème mono-objectif Technique de pondération des fonctions objectifs

Exemple pour la méthode de pondération

La fonction objectif du problème paramétrique (Pα ) peut s'écrire comme

suit :
min ϕ = α1 f1 (x) + α2 f2 (x);
= α1 (x12 + x22 ) + α2 ((x1 − 5)2 − (x2 − 5)2 )
Avec α1 , α2 ≥ 0 et α1 + α2 = 1.
Si on pose α1 = 1 − α2 d'où 0 ≤ α1 ≤ 1 alors la fonction objectif ϕ
devient :

ϕ = x12 + x22 − 10α2 (x1 + x2 ) + 50α2

(EL MOUMEN ) Master MNSA S3 FSAC - MNSA S3 34 / 53

 Transformation en un problème mono-objectif Technique de pondération des fonctions objectifs

Exemple pour la méthode de pondération

On cherche maintenant l'optimum de cette nouvelle fonction objectif ϕ :
Le gradient de la fonction ϕ est le vecteur
δϕ δϕ
∇ϕ = ( δx ; δx )1 2

= (2x1 − 10α2 ; 2x2 − 10α2 )

Le Hessien de la fonction ϕ est la matrice

2 0
 

0 2

Comme on peut le vérier facilement, le Hessien ϕ est une matrice dénie

positif alors le minimum de la fonction ϕ est donné par la résolution du
système :
2x1 − 10α2 = 0; x1 = 5α2 ;
  ∗
⇒
2x2 − 10α2 = 0 x2∗ = 5α2

(EL MOUMEN ) Master MNSA S3 FSAC - MNSA S3 35 / 53

 Transformation en un problème mono-objectif Technique de pondération des fonctions objectifs

Exemple pour la méthode de pondération

Cependant, toutes les solutions ecaces de problème multiobjectif peuvent
s'écrire :
x ∗ = 5α2 (1; 1), avec 0 ≤ α2 ≤ 1
On obtient alors les fonctions objectif suivantes :
f1 = 50α22
f2 = 50(1 − α2 )2
On peut alors calculer quelques solutions du front de Pareto pour un
certain nombre de valeurs du coecient α2 .

(EL MOUMEN ) Master MNSA S3 FSAC - MNSA S3 36 / 53

Transformation en un problème mono-objectif Technique de pondération des fonctions objectifs

(EL MOUMEN ) Master MNSA S3 FSAC - MNSA S3 37 / 53

 Normal boundary intersection (NBI)

La méthode NBI
Une méthode développée en 1998 par Das et Dennis.
Elle donne une bonne répartition des points sur le front de Pareto, et cela
donne un avantage à NBI par rapport aux autres méthodes, à savoir la
méthode de pondération (weighting method) et la méthode de
-contraintes (-constrain method).
Considérons le problème biobjectif suivant :
tel que

 min (f1 (x), f2 (x))




f1 (x) = x12 + x22 + x32 + x42 + x52








f2 (x) = 3x1 + 2x2 − 13 x3 + 0.01(x4 − x5 )3 (5)




s.t. x1 + 2x2 − x3 − 0.5x4 + x5 = 2,



4x − 2x + 0.8x3 + 0.6x4 + 0.5x52 = 0,


 21 2 2 2


x1 + x2 + x3 + x42 + x52 ≤ 10.


(EL MOUMEN ) Master MNSA S3 FSAC - MNSA S3 38 / 53

 Normal boundary intersection (NBI)

(a) (b)
Figure  La frontière de Pareto dans l'espace objectif en minimisant les
combinaisons convexes des objectifs (b), La frontière de Pareto dans l'espace
objectif en utilisant la méthode NBI (a).

(EL MOUMEN ) Master MNSA S3 FSAC - MNSA S3 39 / 53

 Normal boundary intersection (NBI)

− Soit xi∗ = (x1i , x2i , ......, xdi ) le minimum global de la fonction

fi (x), i = 1, 2, ..., l sur x ∈ C . Autrement dit, la i ème fonction objectif
admet un minimum global au point xi∗ .
− Soit Fi∗ = F (xi∗ ) le vecteur des fonctions objectifs évaluées au point xi∗ ,
i.e., Fi∗ = [f1 (xi∗ ), f2 (xi∗ ), ......, fl (xi∗ )]T .
− On dénit minimum individuel tout vecteur xi∗ = (x1i , x2i , ......, xdi )
obtenu en considérant la résolution de chaque fonction objectif fi (x)
séparément.
− Soit F ∗ le vecteur contenant les fonctions objectifs des minimum
individuel, i.e., F ∗ = [f1∗ , f2∗ , ......, fl∗ ]T = [f1∗ (x1∗ ), f2∗ (x2∗ ), ......, fl∗ (xl∗ )]T .
On dit que F ∗ est un point Utopie.
− Soit φ la matrice d'ordre l × l dont la i ème colonne composée du vecteur
F (xi∗ ) − F ∗ . φ est appelée matrice pay-o.
− Soit h l'ensemble des vecteurs objectif réalisable, {F (x) : x ∈ C }, tel
que F : C −→ h et ∂h est la frontière de h.

(EL MOUMEN ) Master MNSA S3 FSAC - MNSA S3 40 / 53

 Normal boundary intersection (NBI)

Soit l'Enveloppe Convexe des Minimums Individuels (CHIM) dénit comme

étant l'ensemble des points dans IR l qui sont une combinaison convexe des
Fi∗ − F ∗ , i = 1, 2, ..., l .
il est déni par
`
X
{φ βj : βj = [β1j , β2j , ......, βlj ]T ∈ IR l , βij = 1, βij ≥ 0 ∀ j = 1, 2, ....., Nj }.
i=1

Avec Nj le nombre total de points φ βj .

Étant donné un β particulier, φ β représente un point de CHIM.

(EL MOUMEN ) Master MNSA S3 FSAC - MNSA S3 41 / 53

 Normal boundary intersection (NBI)

La gure suivante montre le concept clé ainsi que les notations de la

méthode NBI pour l = 2.
Le CHIM est alors le segment reliant F1∗ − F ∗ avec F2∗ − F ∗ .

(EL MOUMEN ) Master MNSA S3 FSAC - MNSA S3 42 / 53

 Normal boundary intersection (NBI)

L'idée centrale de la méthode NBI est que le point d'intersection entre la

frontière ∂h et la normale n, émanant de n'importe quel point dans le
CHIM et pointant vers l'origine est un point situé sur la partie de ∂h
contenant les points ecients. Par exemple, les points P1 , P2 , et P3 sont
Pareto optimal.
Remarque : pour l = 2
0 f1 (x2∗ ) − f1 (x1∗ ) 1−α
   
φ= et β =
f2 (x1∗ ) − f2 (x2∗ ) 0 α

(EL MOUMEN ) Master MNSA S3 FSAC - MNSA S3 43 / 53

 Normal boundary intersection (NBI)

Soit n le vecteur unitaire normale à CHIM pointant vers l'origine,

φ β + t n, t ∈ IR représente l'ensemble des points appartenant à cette
normale. Le point d'intersection de la normale avec la frontière de h la plus
proche de l'origine est maximum globale du sous-problème d'optimisation
suivant :

 max t

 x,t
 s. t. Φβ + t n = F (x)


(NBIβ ) h(x) = 0 (6)
g (x) ≥ 0





xl ≤ x ≤ xu


Remarque : si l'origine n'est pas prise en F ∗ , la première contrainte doit

s'écrire sous la forme Φβ + t n = F (x) − F ∗ (x)

(EL MOUMEN ) Master MNSA S3 FSAC - MNSA S3 44 / 53

 Normal boundary intersection (NBI)

Algorithme pour générer les β :

Soit δ > 0 un pas uniforme entre deux valeurs consécutives de βi ,
pour i = 1, ..., n.
Pour simplier, on prend p = 1δ un entier donné, les valeurs possibles
qui peuvent être prises par β1 sont [0, δ, 2δ, ..., 1].
Pour βi donné, on dénie m1 = βδ , alors les valeurs possibles de β2
1

sont [0, δ, 2δ, ..., k2 δ] avec k2 = 1−β

δ = 1−m
δ
δ
= p − m1 .
1 1

β2
On dénit de même m2 = δ , alors les valeurs possibles de β3 sont
[0, δ, 2δ, ..., k3 δ]
avec k3 = 1−βδ −β = 1−m
1 2 1 δ−m2 δ
δ = p − m1 − m2 .
Et par récurrence, pour βj , j = 2, .., n − 1, il prend les valeurs parmi
P1
j−
[0, δ, 2δ, ..., kj δ] avec kj = p − mi .
i=1
P1
n−
Finalement : βn = 1 − βi .
i=1

(EL MOUMEN ) Master MNSA S3 FSAC - MNSA S3 45 / 53

 Normal boundary intersection (NBI)

(EL MOUMEN ) Master MNSA S3 FSAC - MNSA S3 46 / 53

 Approche par partage des variables

L'optimisation multiobjectif

On considère le problème de minimisation multi-objectif suivant :



 Trouver y solution de :

min f1 (y ), (7)
y
 min f2 (y ),


y

Si on souhaite aborder ce problème via la théorie des jeux, sans qu'on

puisse partager y entre les deux intérêts naturellement

(EL MOUMEN ) Master MNSA S3 FSAC - MNSA S3 47 / 53

 Approche par partage des variables

Tableaux d'allocations binaires

Le partage de la variable y est de construire deux tableaux d'allocation P

et Q de {0, 1}n avec Pi + Qi = 1 pour 1 ≤ i ≤ n.
Soit :
I12 = {1, ..., n} un ensemble d'indices de cardinal n,
I1 un sous ensemble de I12 de cardinal n − p , et
I2 son complémentaire de cardinal p , c'est-à-dire

I12 = I1 ∪ I2 .

Supposons que :
U = (yi ), pour i ∈ I1 ,

(8)
V = (yi ), pour i ∈ I2 .

(EL MOUMEN ) Master MNSA S3 FSAC - MNSA S3 48 / 53

 Approche par partage des variables

Tableaux d'allocations binaires

On pose dans ce cas le tableau d'entiers d'allocation P de taille n :

Pi = 1, ∀i ∈ I1 , Pi = 0, ∀i ∈ I2 ,
de sorte que

y = P.y + (I − P).y = (U, V ) avec I = (1, · · · , 1) (9)

Désignons par ”.” le produit d'Hadamard, c'est-à-dire

(P.y )i = Pi yi et P.y ∈ Rn .
Le vecteur (U, V ) est déni dans l'équation (8).

(EL MOUMEN ) Master MNSA S3 FSAC - MNSA S3 49 / 53

 Approche par partage des variables

Tableaux d'allocations binaires

Le but d'un tel partage est :

minimiser f1 (U, V ) par rapport à U en xant V et
minimiser f2 (U, V ) par rapport à V en xant U .
par une méthode d'optimisation concourante utilisant un algorithme
simulant un jeu de Nash entre des joueurs associés aux deux fonctionnelles
respectivement.

(EL MOUMEN ) Master MNSA S3 FSAC - MNSA S3 50 / 53

 Approche par partage des variables

Tableaux d'allocations binaires

Considérons deux fonctions convexes f1 et f2 , et le jeu de Nash qui s'écrit

sous la forme suivante :

 Trouver yEN solution de :



min f1 (P.y + (I − P).yEN ), (10)
U
 min f2 ((I − P).y + P.yEN ),

V

On considère le problème (N 0 ) suivant :

Trouver yEN solution de :

(

min f1 (P.y + (I − P).yEN ) + f2 ((I − P).y + P.yEN ). (11)

y

Si yEN est un point xe de (11), alors yEN est un équilibre de Nash de (10).

(EL MOUMEN ) Master MNSA S3 FSAC - MNSA S3 51 / 53

 Approche par partage des variables

Tableaux d'allocations convexiés

Nous considérons le même problème (10), avec P ∈ [0, 1]N , donc notre
nouveau problème s'écrit sous la forme suivante :


 Trouver yEN solution de :
min f1 (P.y + (I − P).yEN )

y (12)
 min f2 ((I − P).y + P.yEN )


y

(EL MOUMEN ) Master MNSA S3 FSAC - MNSA S3 52 / 53

 Approche par partage des variables

(0) (0) (0) (0) (0)

1 Initialisation : yopt 1 , yopt 2 posons, yEN = P.yopt 1 + (I − P).yopt 2
2 pour k ≥ 1 :
1 résoudre le problème :
(k−1) (k)
min f1 (P.y + (I − P).yEN ) ⇒ yopt 1
y

2 résoudre le problème :
(k−1) (k)
min f2 ((I − P).y + P.yEN ) ⇒ yopt 2
y

(k) (k) (k)

3 mise à jour : yEN = P.yopt 1 + (I − P).yopt 2 , mise à jour de yEN

(k) (k) (k−1)

yEN = tyEN + (1 − t)yEN , avec t ∈]0, 1], relaxation de yEN

(k) (k−1)
3 tant que ||yEN − yEN || > ε, poser k = k + 1, et répéter 2
où ε est un petit paramètre positif

(EL MOUMEN ) Master MNSA S3 FSAC - MNSA S3 53 / 53