0% ont trouvé ce document utile (0 vote)

12 vues65 pages

Problèmes d'optimisation : Concepts clés

Le chapitre présente les problèmes d'optimisation, qui sont essentiels dans la recherche scientifique, en détaillant leurs caractéristiques, types et définitions. Il aborde la notion d'optimisation, les éléments constitutifs d'un problème d'optimisation, ainsi que les classifications des méthodes de résolution, en mettant l'accent sur les problèmes mono-objectifs et combinatoires. Les défis liés à la résolution optimale et les approches heuristiques et métaheuristiques sont également discutés.

Transféré par

HAFIDA BAAZIZI

Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.

Formats disponibles

Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

0% ont trouvé ce document utile (0 vote)

12 vues65 pages

Problèmes d'optimisation : Concepts clés

Transféré par

HAFIDA BAAZIZI

Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.

Formats disponibles

Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Chapitre 2

Problèmes d’optimisation

2.1 Généralités

Les problèmes d’optimisation occupent actuellement une place de choix dans la communauté
scientifique. L’évolution des techniques informatiques a permis de dynamiser les recherches
dans ce domaine. Le monde réel offre un ensemble de problèmes d’optimisation de nature très
diverse :

• problèmes statiques ou dynamiques,

• problèmes combinatoires ou à variables continues,

• problèmes dans l’incertain,

• problèmes à un ou plusieurs objectifs.

2.1.1 Notion de l’optimisation

Dans toute sa généralité, le problème d’optimisation consiste à déterminer la plus petite (grande)
valeur possible qu’une fonction réelle f : E → R nommée fonction objectif puisse prendre dans
l’ensemble E nommé ensemble réalisable. Sous forme mathématique, ceci s’exprime (pour le cas
de la minimisation) par l’équation :

f ∗ = inf f (x) avec x ∈ E

19
CHAPITRE 2. PROBLÈMES D’OPTIMISATION 20

et signifie la relation :

∀x ∈ E f (x) > f ∗ et ∀ > 0 ∃x ∈ E tel que f (x ) < f ∗ +

Sans ajouter d’hypothèse sur la fonction f et l’ensemble E, il n’est pas certain que l’on puisse
trouver un élément x∗ de l’ensemble E pour lequel f (x∗ ) = f ∗ . Lorsque cela s’avère le cas, la
formulation mathématique devient (toujours pour le cas de la minimisation):

f (x∗ ) = f ∗ = min f (x) avec x ∈ E

Un problème d’optimisation se définit comme la recherche du minimum ou du maximum

(l’optimum) d’une fonction donnée. On peut aussi trouver des problèmes d’optimisation pour
lesquels les variables de la fonction à optimiser sont contraintes d’évoluer dans une certaine
partie de l’espace de recherche. Dans ce cas, on a une forme particulière de ce que l’on appelle
un problème d’optimisation sous contraintes. Ce besoin d’optimisation vient de la nécessité de
l’ingénieur de fournir à l’utilisateur un système qui répond au mieux au cahier des charges. Ce
système devra être calibré de manière à :

• occuper le volume minimum nécessaire à son bon fonctionnement (coût des matières
premières),

• consommer le minimum d’énergie (coût de fonctionnement),

• répondre à la demande de l’utilisateur (cahier des charges).

Un problème d’optimisation est défini par les éléments suivants :

• un espace de recherche (de décision) c-à-d un ensemble de solutions ou de configurations

constitué des différentes valeurs prises par les variables de décision,

• une ou plusieurs fonction(s) dite(s) objectif(s), à optimiser (minimiser ou maximiser),

• un ensemble de contraintes à respecter.

Dans la plupart des problèmes, l’espace d’état (décision) est fini ou dénombrable. Les variables
du problème peuvent être de nature diverse (réelle, entière, booléenne, etc.) et exprimer des
données qualitatives ou quantitatives. La fonction objectif représente le but à atteindre pour le
CHAPITRE 2. PROBLÈMES D’OPTIMISATION 21

décideur. L’ensemble des contraintes définit des conditions sur l’espace d’état que les variables
doivent satisfaire. Ces contraintes sont souvent des contraintes d’inégalité ou d’égalité et
permettent, en général, de limiter l’espace de recherche (solutions réalisables). La résolution
optimale du problème consiste à trouver le point ou un ensemble de points de l’espace de
recherche qui satisfait au mieux la fonction objectif. Le résultat est appelé valeur optimale ou
optimum. Néanmoins en raison de la taille des problèmes réels, la résolution optimale s’est
souvent montrée impossible dans un temps raisonnable. Cette impossibilité technique impose la
résolution approchée du problème et consiste à trouver une solution de bonne qualité (la plus
proche possible de l’optimum). Il est vital pour déterminer si une solution est meilleure qu’une
autre, que le problème introduise un critère de comparaison (une relation d’ordre). La plupart
des problèmes d’optimisation appartiennent à la classe des problèmes NP-difficile : classe où il
n’existe pas d’algorithme qui fournit la solution optimale en un temps polynomial en fonction
de la taille du problème et du nombre d’objectifs à optimiser. Dans la littérature, il existe des
problèmes académiques utilisés comme des benchmarks : sac à dos, les fonctions de schaffer,
voyageur de commerce, Flowshop,... et des problèmes réels correspondant à des applications
industrielles dans les domaines de télécommunications, transport, environnement, etc.

2.1.2 Vocabulaire et définitions

D’un point de vue mathématique, un problème d’optimisation se présentera sous la forme

suivante :
min f (x) (fonction à optimiser)
avec g(x) 6 0 (m contraintes d’inégalité)
et h(x) = 0 (p contraintes d’égalité)

Les vecteurs g(x) et h(x) représentent respectivement m contraintes d’inégalité et p contraintes

d’égalité. Cet ensemble de contraintes délimite un espace restreint de recherche de la solution
optimale. En général, on peut rencontrer deux types de contraintes d’inégalité :

• des contraintes du type Biinf ≤ xi ≤ Bisup où les valeurs de x qui vérifient ces contraintes
définissent l’espace de recherche. Cet espace est représenté à la figure 2.1 pour n = 2,

• des contraintes du type c(x) ≤ 0 ou c(x) ≥ 0 où les valeurs de x qui vérifient ces contraintes
définissent l’espace des valeurs réalisables. Cet espace est représenté à la figure 2.1
pour n = 2.
CHAPITRE 2. PROBLÈMES D’OPTIMISATION 22

Figure 2.1: Les différents espaces de recherche.

Fonction objectif : c’est le nom donné à la fonction f (que l’on appelle aussi fonction de coût
ou critère d’optimisation). Il s’agit de la fonction que l’algorithme d’optimisation va devoir
optimiser (trouver un optimum).
Variables de décision : elles sont regroupées dans le vecteur x. C’est en faisant varier ce
vecteur que l’on recherche un optimum de la fonction objectif f .
Minimum global : un point x∗ est un minimum global de la fonction f si l’on a f (x∗ ) < f (x)
quel que soit x tel que x 6= x∗ . Cette définition correspond au point M3 de la figure 2.2.
Minimum local fort : un point x∗ est un minimum local fort de la fonction f si l’on a
f (x∗ ) < f (x) quel que soit x ∈ V (x∗ ) où x 6= x∗ et V (x∗ ) définit un voisinage de x∗ . Cette
définition est illustrée par les points M2 et M4 de la figure 2.2.
Minimum local faible : un point x∗ est un minimum local faible de la fonction f si l’on a
f (x∗ ) 6 f (x) quel que soit x ∈ V (x∗ ) où x 6= x∗ et V (x∗ ) définit un voisinage de x∗ . Cette
situation correspond au point M1 de la figure 2.2.

Figure 2.2: Les différents minima.

CHAPITRE 2. PROBLÈMES D’OPTIMISATION 23

2.1.3 Classification des problèmes d’optimisation

On peut classer les différents problèmes d’optimisation, rencontrés dans la vie courante, en
fonction de leurs caractéristiques (voir figure 2.3). Face à un problème d’optimisation, il faut :

• Élaborer un modèle mathématique fournissant l’expression de l’objectif à optimiser et

précisant les contraintes à respecter ;

• Développer un algorithme de résolution ;

• Évaluer la qualité des solutions produites.

Figure 2.3: Classification d’un problème d’optimisation.

Dans la suite de ce chapitre, nous allons aborder l’optimisation mono-objectif alors que
l’optimisation multiobjectif fera le sujet du chapitre suivant.

2.2 Optimisation mono-objectif

Lorsqu’un seul objectif (critère) est donné, le problème d’optimisation est dit mono-objectif.
Dans un tel cas, la solution optimale est clairement définie et elle correspond à celle qui a le coût
optimal (minimal ou maximal). De manière formelle, à chaque instance d’un tel problème est
associé un ensemble E de solutions potentielles respectant certaines contraintes et une fonction
d’objectif f : E → R qui associe à chaque solution admissible x ∈ E une valeur f (x). Résoudre
l’instance (E, f ) du problème d’optimisation consiste à trouver la solution optimale x∗ ∈ E
qui optimise (minimise ou maximise) la valeur de la fonction objectif f . Pour le cas de la
minimisation, le but consiste à trouver x∗ ∈ E tel que f (x∗ ) 6 f (x) pour tout élément x ∈ E.
CHAPITRE 2. PROBLÈMES D’OPTIMISATION 24

• Variables de décision
Les variables de décision sont des quantités numériques pour lesquelles des valeurs sont à
choisir. Cet ensemble de n variables est appelé vecteur de décision : (x1 , x2 , ..., xn ). Les
différentes valeurs possibles prises par les variables de décision xi constituent l’ensemble
des solutions potentielles.

• Espace décisionnel et espace objectif

En optimisation, deux espaces Euclidiens sont à considérer à savoir :

• l’espace décisionnel, de dimension n, où n désigne le nombre de variables de décision.

Cet espace est constitué par l’ensemble des valeurs pouvant être prises par le vecteur
de décision,

• l’espace objectif correspondant à l’ensemble de définition de la fonction objectif et

généralement défini comme étant un sous-ensemble de R. La valeur dans l’espace
objectif d’une solution est appelée coût.

• Contraintes
Dans la plupart des problèmes d’optimisation, des restrictions sont imposées par les
caractéristiques du problème. Ces restrictions doivent être satisfaites afin de considérer
une solution comme étant acceptable. Cet ensemble de restrictions, appelées contraintes,
décrit les dépendances entre les variables de décision et les paramètres du problème. On
formule, usuellement, ces contraintes cj par un ensemble d’inégalités ou d’égalités de la
forme cj (x1 , x2 , ..., xn ) 6 0 ou cj (x1 , x2 , ..., xn ) = 0.

2.2.1 Classification générale des méthodes de type mono-objectif

Pour tenter de récapituler les considérations précédentes, On se réfère, à la figure 2.4 pour une
classification générale des méthodes d’optimisation de type mono-objectif. On distingue deux
types de problèmes d’optimisation : les problèmes combinatoires (ou problèmes “discrets”) et
les problèmes à variables continues. Cette différenciation est nécessaire pour cerner le domaine
de l’optimisation difficile. Certains problèmes d’optimisation combinatoire ne possèdent pas
un algotithme de résolution exact qui soit rapide. Il s’agit, en particulier, des problèmes “NP-
difficiles”dont la résolution exacte n’est pas possible en un temps de calcul proportionnel à nr
où n désigne le nombre de paramètres inconnus du problème et r est un entier. Pour certains
CHAPITRE 2. PROBLÈMES D’OPTIMISATION 25

problèmes d’optimisation continue, il n’est pas possible de disposer d’algorithme permettant de

repérer un optimum global à coup sûr et en un nombre fini de calculs.

Des efforts ont longtemps été fournis, séparément, pour la résolution de ces deux types de
problèmes d’optimisation “difficiles”. Il est à noter que pour l’optimisation continue, il existe
un arsenal important de méthodes classiques dites d’optimisation globale, sauf que de telles
techniques s’avèrent souvent inefficaces si la fonction objectif ne possède pas une propriété
structurelle particulière, telle que la convexité. Dans le domaine de l’optimisation combinatoire,
un grand nombre d’heuristiques, qui produisent des solutions proches de l’optimum, ont été
développées ; mais la plupart d’entre elles ont été conçues spécifiquement pour des problèmes
particuliers.

Pour l’optimisation combinatoire, on se fie aux méthodes exactes ou aux méthodes approchées.
Ainsi, les méthodes exactes sont généralement utilisées pour des problèmes de petite taille
et elles cherchent l’optimum global en effectuant, en général, une énumération des solutions
de l’espace de recherche (exemple : méthode Branch and Bound). Les méthodes approchées
sont utilisées lorsqu’il s’agit d’un problème difficile. Dans une telle situation, on peut se servir
d’heuristiques ou de métaheuristiques. Une heuristique “spécialisée”est dédiée entièrement au
problème considéré et elle est, plutôt, conçue pour résourde un type de problème en particulier.
Elle ne fonctionne que sur le type de problème pour lequel elle a été développée (exemple:
l’algorithme de type “First Fit”du problème de rangement “Binpaking”). Une métaheuristique
est fondée sur un concept général et elle peut s’adapter à n’importe quel type de problème avec
de bons résultats fournis (exemple : le recuit simulé). On peut différencier les métaheuristiques
“de voisinage”faisant progresser une seule solution à la fois (recuit simulé, recherche tabou, etc.)
et les métaheuristiques “distribuées”manipulant en parallèle toute une population de solutions
(algorithmes génétiques, etc.).

Pour l’optimisation continue, le cas linéaire (programmation linéaire) est séparé du cas
non linéaire, où l’on retrouve le cadre de l’optimisation difficile ; dans ce cas, une solution
pragmatique peut consister à recourir à l’application répétée d’une méthode locale qui exploite,
ou non, les gradients de la fonction objectif. Si le nombre de minima locaux est très élevé, le
recours à une méthode globale s’impose : on retrouve alors les métaheuristiques, qui offrent une
alternative aux méthodes classiques d’optimisation globale, celles-ci requérant des propriétés
mathématiques restrictives de la fonction objectif. Deux types de méthodes de programmation
non linéaire sont à distinguer :
CHAPITRE 2. PROBLÈMES D’OPTIMISATION 26

Figure 2.4: Classification d’un problème d’optimisation mono-objectif.

Les méthodes globales

Méthodes globales classiques : De telles méthodes peuvent être considérées comme

les méthodes de base de l’optimisation. Dans cette famille, on trouve la méthode
de descente du gradient qui permet de trouver un optimum global lorsqu’elle est
appliquée à une fonction convexe.

Métaheuristiques : L’idée directrice sur laquelle repose une métaheuristique est

suffisamment générale pour être transposable facilement aux problèmes d’optimisation
continus.

Les méthodes locales

Avec gradient : ces méthodes exploitent le gradient d’une fonction pour effectuer
la recherche de l’optimum. Quand cette technique est appliquée à un problème
d’optimisation continue de forme générale, il n’est en général pas possible de trouver
l’optimum global du problème. On obtient alors un optimum local.
CHAPITRE 2. PROBLÈMES D’OPTIMISATION 27

Sans gradient : cette famille regroupe une grande diversité de méthodes et entre
autre les méthodes constructives basées sur la détermination de la solution variable
après variable, en interdisant la modification d’une variable déjà affectée. La méthode
glouton fait partie des méthodes constructives. Dans cette catégorie, on retrouve
aussi les méthodes stochastiques qui reposent sur un processus aléatoire.

Finalement, il y a les méthodes hybrides qui correspondent souvent à une association entre une
métaheuristique et une méthode locale. Cette coopération peut prendre la simple forme d’un
passage de relais entre la métaheuristique et la technique locale, chargée d’affiner la solution.
Mais, les deux approches peuvent aussi être entremêlées de manière plus complexe.

2.3 Optimisation continue

2.3.1 Formulation et concepts de base

Comme déjà mentionné, l’optimisation se divise essentiellement en deux catégories dont les
outils et les méthodes de résolution sont distincts.

Si l’espace décisionnel E est discret (E ⊂ Z n , un ensemble fini ou dénombrable), il s’agit de

l’optimisation combinatoire. Les outils de résolution proviennent des mathématiques discrètes.

Par contre, si l’espace E est continu et la fonction objectif f est continue alors cela correspond
à l’optimisation continue. Les outils de résolution relatifs proviennent essentiellement de l’analyse
(calcul différentiel, convexité) et de l’algèbre linéaire.

Généralement, le traitement et l’étude dans le domaine de l’optimisation continue est

considéré comme relativement plus simple que dans le cadre de l’optimisation combinatoire.
En effet, les outils d’analyse dans le cas continu contribuent considérablement à effectuer les
études avec un effort raisonnable et adéquat tant du point de vue théorique que de point de
vue algorithmique. Il est certain que la classe des problèmes d’optimisation continue est bien
trop large pour pouvoir espérer l’obtention de méthodes de résolution générales efficientes. Pour
contourner cet obstacle, on impose certaines hypothèses “restrictives”permettant d’établir des
méthodes de résolution spécifiques. De telles hypothèses doivent être suffisamment fortes pour
pouvoir établir des méthodes utilisables en pratique, et suffisamment faibles pour être capable
d’englober une large classe de problèmes. À titre indicatif en imposant certaines hypothèses, on
CHAPITRE 2. PROBLÈMES D’OPTIMISATION 28

peut se ramener à restreindre notre étude à des sous-classes de problèmes telles que :
Programmation linéaire lorsque la fonction objectif et les fonctions contraintes sont toutes
des fonctions affines.
Programmation quadratique lorsque la fonction objectif est quadratique et les fonctions
contraintes sont des fonctions affines.
Programmation convexe lorsque la fonction objectif est convexe et les fonctions contraintes
sont des fonctions affines.
Tout problème d’optimisation que nous considérerons peut être exprimé de la façon suivante :

min f (x) avec x ∈ Rn sous la contrainte x ∈ X et X ⊂ Rn . (2.1)

Résoudre le problème (2.1) revient à chercher des points minimums locaux au sens de la définition
suivante.

Définition [Link]. (Minimum local/Minimum global)

On considère une fonction f : X ⊂ Rn → R.
• x ∈ Rn est un point de minimum local de la fonction f sur l’ensemble X si

x ∈ X et ∃r > 0 | ∀y ∈ X ∩ B(x, r), f (x) 6 f (y) (2.2)

On dit alors que f (x) est un minimum local de f sur X.

• x ∈ Rn est un point de minimum global de la fonction f sur l’ensemble X si

x ∈ X et ∀y ∈ X, f (x) 6 f (y) (2.3)

On dit alors que f (x) est un minimum global de f sur X.

Les notions de maximum local et global sont définies de façon tout à fait similaire. En fait,
on peut facilement vérifier les relations suivantes :

min f (x) = − max −f (x) ou encore max f (x) = − min −f (x) avec x ∈ X

Ainsi et étant donné que la recherche d’un maximum pouvant se ramener à la recherche d’un
minimum, nous ne nous intéresserons qu’à la recherche de minimums.
CHAPITRE 2. PROBLÈMES D’OPTIMISATION 29

Figure 2.5: Exemple de minimums ou maximums globaux et locaux.

2.3.2 Convexité et optimisation

La notion de convexité permet de garantir que les minimums locaux sont en fait des minimums
globaux. La notion de convexité est suffisante pour garantir que nous avons trouvé un minimum
global mais aucunement nécessaire. Les problèmes dont les données sont convexes, constituent
une classe importante en optimisation, car ils sont fréquemment rencontrés dans les applications
et ils sont à la base de nombreuses méthodes développées pour des problèmes plus généraux.

Définition [Link]. On se donne un ensemble X ⊂ Rn .

L’ensemble X est convexe si ∀(x, y) ∈ X 2 , ∀λ ∈]0, 1[, λx + (1 − λ)y ∈ X c’est-à-dire, si x et y
sont deux élèments de X alors le segment qui relie x à y est inclus dans X.

Définition [Link]. On se donne un ensemble convexe X ⊂ Rn et une fonction f : X → R.

• La fonction f est convexe ssi ∀(x, y) ∈ X 2 , ∀λ ∈]0, 1[, λf (x+(1−λ)y) 6 λf (x)+(1−λ)f (y))
• f est strictement convexe ssi ∀(x, y) ∈ X 2 , ∀λ ∈]0, 1[, λf (x+(1−λ)y) < λf (x)+(1−λ)f (y))
CHAPITRE 2. PROBLÈMES D’OPTIMISATION 30

On interprète géométriquement le fait qu’une fonction soit convexe en annonçant qu’elle est
située sous ses cordes. La convexité est une notion globale, qui donne des informations sur le
caractère global d’un point de minimum.

Définition [Link].
On se donne un ensemble convexe X ⊂ Rn convexe et f : X → R une fonction convexe.
• Le problème minf (x) avec x ∈ X est dit convexe ssi la fonction objectif f est convexe et si
l’ensemble X des contraintes est convexe.
• Si la fonction f est strictement convexe et l’ensemble X est convexe, alors le problème minf (x)
avec x ∈ X est dit strictement convexe.

Théorème [Link]. (Condition suffisante d’optimisation globale)

Soient X ⊂ Rn un ensemble convexe, f : X → R une fonction et x∗ un minimum local de f sur
l’ensemble X.
• Si la fonction f est convexe, alors x∗ est un minimum global de f sur X.
• Si la fonction f est strictement convexe, alors x∗ est l’unique minimum global de f sur X.

2.3.3 Conditions d’optimalité

Conditions d’optimalité pour un problème d’optimisation sans contrainte

Les problèmes d’optimisation les plus simples sont ceux qui consistent à minimiser (ou maximiser)
une fonction f : Rn → R. Le problème général de l’optimisation sans contrainte peut être
formulé de la manière suivante : min f (x) avec x ∈ Rn . Il s’agit donc de déterminer un point x∗
de Rn tel que ∀x ∈ R on a f (x∗ ) 6 f (x), c’est-à-dire un minimum global de la fonction objectif f
sur Rn . Lorsque l’inégalité stricte f (x∗ ) < f (x) est vérifiée pour tout x ∈ Rn satisfaisant x =
6 x∗
le minimum global est unique. Pour beaucoup de problèmes d’optimisation sans contraintes, les
principales méthodes de résolution connues ne permettent pas la détermination d’un minimum
global : il faut alors se contenter de minimums locaux.

Condition nécessaire d’optimalité locale

On suppose que la fonction objectif f est suffisamment différentiable pour éviter toute difficulté
dans l’analyse des algorithmes de résolution. De plus, on se limite à une version locale du
problème de minimisation de la fonction f , soit qu’il existe un voisinage V (x∗ ) de x∗ tel que
∀x ∈ V (x∗ ) : f (x∗ ) 6 f (x)).
CHAPITRE 2. PROBLÈMES D’OPTIMISATION 31

Théorème [Link]. On se donne une fonction f : Rn → R. Si x∗ est un minimum local de f ,

alors ∇f (x∗ ) = 0 (condition d’optimalité de premier ordre) et le hessien ∇2 f (x∗ ) est matrice
semi-définie positive (condition d’optimalité de second ordre).

Un point x∗ qui vérifie la condition d’optimalité de premier ordre est appelé point stationnaire.

Condition suffisante d’optimalité locale

Théorème [Link]. Sous les mêmes conditions du théorème [Link], une condition suffisante
pour que x∗ soit un optimum local de f sur Rn est que ∇f (x∗ ) = 0 (stationnarité) et le hessien
∇2 f (x∗ ) est une matrice définie positive.

La stationnarité de f est une condition nécessaire d’optimalité. Pratiquement toutes les

méthodes d’optimisation sans contrainte commencent avec un choix d’un point initial x0 et
générent une suite de points x1 , x2 , ..., xk qui converge vers un point stationnaire x∗ .

Conditions d’optimalité pour un problème d’optimisation sous contraintes

Un problème d’optimisation sous contraintes s’énonce de la manière suivante :

min f (x) avec x ∈ X (2.4)

où X est un sous-ensemble non vide de Rn défini par des contraintes d’égalité ou d’inégalité

X = {x ∈ Rn : h(x) = 0, g(x) 6 0}

où h : Rn → Rp et g : Rn → Rq sont continues. Les écritures h(x) = 0 et g(x) 6 0 signifient que

∀i = 1, . . . , p, on a hi (x) = 0 et ∀j = 1, . . . , q, on a gj (x) 6 0

L’ensemble X est appelé ensemble ou domaine des contraintes. Tout point x ∈ Rn vérifiant :
x ∈ X, est appelé point admissible du problème 2.4. Concernant les contraintes d’inégalités,
nous aurons également besoin de la notion de contrainte active :

Définition [Link]. (Contraintes actives/inactives)

Une contrainte d’inégalité gj 6 0 pour j ∈ {1, . . . , q} est dite active en x̄ si gj (x̄) = 0 et elle est
dite inactive en x̄ si g(x̄) < 0.
CHAPITRE 2. PROBLÈMES D’OPTIMISATION 32

Il est à préciser que la notion de contrainte active est attrayante à cause du fait qu’au point
minimum local x∗ ∈ X, les contraintes actives peuvent être remplacées par des contraintes
d’égalité et les contraintes inactives peuvent être ignorées. Si l’intérêt de cette simplification
reste essentiellement théorique (on ne connaı̂t pas x∗ à l’avance), un intérêt pratique est que si
l’on trouve un minimum local du problème sans contraintes alors le point trouvé correspond
également à un minimum local du problème avec contraintes. En un point x ∈ X, l’ensemble
des contraintes actives est l’ensemble des indices j tel que gj (x) = 0. Remarquons également
que si en un point x ∈ X, la contrainte gk (x) n’est pas active, alors gk (x) < 0 et ainsi, par
continuité de g, pour tout x0 dans un voisinage de x, on aura encore l’inégalité gk (x0 ) < 0. Donc
localement, on est sûr que la contrainte est vérifiée.

Définition [Link]. (Contraintes qualifiées)

En un point x ∈ X, les contraintes sont dites qualifiées si et seulement si les vecteurs
(∇hi (x))i=1,...,p sont linéairement indépendants et si il existe une direction d orthogonale à
tous les vecteurs (∇hi (x))i=1,...,p telle que ∇gj (x)T d < 0 pour toutes les contraintes actives.
S’il y a une seule contrainte d’inégalité, cette contrainte est qualifiée en un point si et seulement
si son gradient est non nul quand elle est active.

Définition [Link]. (Lagrangien du problème)

Soit λ ∈ Rp et γ ∈ (R+ )q . On définit le Lagrangien du problème 2.4 par la relation

p q
X X
L(x, λ, γ) = f (x) + λi hi (x) + γj gj (x) (2.5)
i=1 j=1

ou plus généralement

L(x, λ, γ) = f (x) + hλ, h(x)iRp + hγ, g(x)iRq (2.6)

Les paramètres (λ, γ) sont appelés multiplicateurs de Lagrange.

Il est à noter que le Lagrangien fait intervenir autant de multiplicateurs que de contraintes, et
les multiplicateurs γj associés aux contraintes d’inégalité gj (x) 6 0 sont positifs ou nuls.
Les conditions nécessaires d’optimalité d’un problème d’optimisation avec contraintes d’inégalité
et d’égalité, se résument dans le théorème suivant.
CHAPITRE 2. PROBLÈMES D’OPTIMISATION 33

Théorème [Link]. (Conditions nécessaires d’optimalité) Considérons le problème

min f (x) avec x ∈ Rn sous les contraintes h(x) = 0 et g(x) 6 0.

où f , g et h sont supposées suffisamment différentiables. On note X le domaine des contraintes

et L le Lagrangien associé à la fonction f et aux contraintes X. Si x∗ est un minimum local de
f sur l’ensemble X et si les contraintes sont qualifiées en x∗ , alors il existe des multiplicateurs
(λ∗ , γ ∗ ) ∈ Rp × Rq+ tel que :
p q
(a) ∇x L(x∗ , λ∗ , γ ∗ ) = 0 ou encore ∇f (x∗ ) + λ∗i ∇hi (x∗ ) + γj∗ ∇gj (x∗ ) = 0.
P P
i=1 j=1

(b) ∀j = 1, . . . , q, on a γj∗ gj (x∗ ) = 0 i.e. pour tout j = 1, . . . , q, on a γj∗ = 0 ou gj (x∗ ) = 0.

Ces conditions sont dites relations de complémentarité.

(d) ∀j = 1, . . . , p, on a gj (x∗ ) 6 0.

(e) ∀j = 1, . . . , q, on a γj (x∗ ) > 0.

2.3.4 Résolution d’un problème d’optimisation continue

La résolution d’un problème d’optimisation continue peut être équivalente à la détermination

des points stationnaires en premier lieu. La recherche d’un point satisfaisant les conditions
d’optimalité représente un grand défi dont la difficulté se compare à celle de la détection
directe d’une solution optimale. Pour contourner cette problématique, on peut faire recours à la
génération d’une suite de points réalisables démarrant en un point convenable et convergeant vers
un point stationnaire approximatif vérifiant les conditions d’optimalité de 1er ordre. Le processus
considéré consiste à se déplacer itérativement d’un point satisfaisant certaines conditions
particulières vers un autre point adéquat tout en respectant des conditions similaires et le
passage s’effectue en choisissant une direction et un pas de déplacement convenable. La variété
et la multitude des méthodes proposées, pour la résolution de problèmes d’optimisation continue,
se reposent sur la diversité des directions choisies et des pas de déplacement utilisés.

D’autre part et étant donné la possibilité de proposer des approximations de la plus part
des modèles d’optimisation non linéaires via des modèles linéaires, une grande attention a été
associée au développement de méthodes de résolution itératives spécifiquement pour les modèles
CHAPITRE 2. PROBLÈMES D’OPTIMISATION 34

de la programmation linéaire durant ces dernières décennies. C’est ainsi que l’algorithme du
Simplexe a demeuré sans compétiteur sérieux, malgré sa complicité théorique exponentielle,
depuis 1947 jusqu’à l’arrivée de l’algorithme des ellipsoı̈des de Khanchion en 1979. Cependant,
l’algorithme polynomial des méthodes projectives pour la programmation linéaire proposé par
Karmarkar [149, 150, 151] a initié, en 1984, l’arrivée et la proposition d’une multitude de
nouvelles méthodes de résolution dont les méthodes de pénalités. Ces dernières peuvent être
classées en trois catégories :

• Méthodes de pénalité extérieure;

• Méthodes de pénalité intérieure;

• Méthodes de pénalité intérieure-extérieure (ou mixte).

Les fonctions de pénalités ont été utilisées depuis longtemps. Elles ont servi au début pour
résoudre des problèmes d’ingénierie comme la cristallographie avant d’être partie intégrante
de la programmation mathématique. L’idée de la pénalisation a été proposée par Courant [58]
en 1943. Cette proposition a été motivée par des considérations physiques sans liaison directe
avec les algorithmes de résolution de problèmes mathématiques. Il s’agissait alors de ramener la
résolution du problème :

min { f (x) : h(x) = 0 , x ∈ Rn }

à l’étude des points stationnaires de la fonction f (x) + µ h2 (x) avec µ → +∞. Ainsi prenait
naissance la notion de pénalités quadratiques. C’est vers les années cinquante, après le grand
développement qu’a connu la programmation mathématique sous l’impulsion de Dantzig [67],
Kuhn et Tucker [168] et bien d’autres, que d’autres fonctions de pénalités ont été suggérées.
Citons dans ce contexte qu’en 1954 et 1955, Frisch [106, 107] a mis en œuvre une méthode dite
“méthode potentielle logarithmique”et qui est basée sur l’utilisation du gradient de la fonction

m
X
f (x) + µ ln (−gi (x))
i=1

définie dans l’intérieur de l’ensemble réalisable pour étudier le problème

(P ) : min { f (x) : gi (x) ≤ 0 , 1 ≤ i ≤ m , x ∈ Rn }.

CHAPITRE 2. PROBLÈMES D’OPTIMISATION 35

Cette idée fut à l’origine de la fonction de barrière logarithmique. En 1955, Ablow et Brigham
[1] se sont servis des gradients des fonctions

m
X m
X
φ1 = f (x) + µ max( gi (x), 0 ) et φ2 = f (x) + µ (max( gi (x), 0 ))2
i=1 i=1

pour résoudre le problème (P). Vraisemblablement, cette méthode appliquée aux problèmes
non linéaires de petite taille était efficace puisque l’on obtenait une bonne approximation de
la solution du problème original quand le gradient de φ1 ou φ2 devenait nul pour une grande
valeur de µ. Signalons au passage que la fonction φ2 n’est autre qu’une extension naturelle de
la fonction de pénalités quadratiques proposée par Courant.

En 1959 et en 1961, pour résoudre le problème (P ), Caroll [36, 37] a présenté la fonction de
m
1
P
pénalités f (x) − µ gi (x)
. Il a, en plus, mentionné que si l’on se limite à l’intérieur du domaine
i=1
réalisable, alors pour µ = µk > 0, la fonction pénalisée admet un minimum local x(µk ) et la
suite {x(µk )} converge vers une solution du problème (P) quand µk & 0. La preuve rigoureuse
de ce résultat a été donnée par Fiacco et McCormick [97] en 1963.
La simplicité apparente des méthodes de pénalités a amené Zangwill [288, 289] en 1965 et
en 1967 ainsi que Fiacco et McCormick [98, 99] en 1968 à établir les bases fondamentales de
telles méthodes. Le premier a, en plus, proposé une nouvelle fonction de pénalités de la forme
f (x) + µ p( g(x) ) pour résoudre le problème :



 min f (x)

(T ) : s. à. gi (x) ≤ 0 pour 1≤i≤m


m+1≤j ≤m+q

 gj (x) = 0 pour

où f : Rn −→ R, g : Rn −→ Rm+q et p : Rm+q −→ R+ étant une fonction continue telle que

p(y) = 0 si y ≤ 0 et p(y) devient très grand autrement.

Zangwill, comme ceux qui l’ont précédé, s’est inspiré des méthodes de pénalités séquentielles,
c’est-à-dire qu’au lieu de résoudre le problème (T ), on minimise une suite de fonctions f (x) +
µk p( g(x) ) avec µk > 0 et µk −→ +∞. Sous certaines conditions sur les données du problème
(T ), on montre que la suite {x(µk )} des solutions optimales locales admet une sous-suite qui
converge vers une solution x∗ de (T). Alors que Fiacco et McCormick ont défini les méthodes de
CHAPITRE 2. PROBLÈMES D’OPTIMISATION 36

pénalités mixtes qui consistent à minimiser les suites de fonctions

m m+q
X 1 X
f (x) − µk ln (−gi (x)) + ( gj (x) )2 , µk & 0
i=1
µk j=m+1

pour avoir une solution du problème (T ). D’un autre côté, ils ont montré que sous certaines hy-
pothèses (conditions suffisantes d’optimalité, stricte complémentarité et régularité) les minimums
locaux x(µ) décrivent une trajectoire différentiable et que x(µ) −→ x∗ lorsque µ & 0.

Néanmoins, Murray [202, 203] en 1967 ainsi que Lootsma [184] en 1969 ont soulevé le
problème numérique des méthodes de pénalités séquentielles. Ils ont remarqué que le Hessien de
la fonction de pénalités est non borné lorsque le paramètre de pénalité µ est très grand ou très
petit selon la méthode de pénalités choisie. Par la suite, de nombreux chercheurs ont été amenés
à proposer d’autres méthodes afin d’éviter ce problème de mauvais conditionnement. Hestenes
[133] et Powell [225], en 1969 et d’une façon séparée, ont eu l’idée d’assembler les méthodes de
pénalités et des multiplicateurs de Lagrange. Il s’agissait alors de minimiser la fonction objectif
f (x) + λtk h(x) + 12 h(x)t Sh(x) avec S = diag(σ1 , . . . , σp ) et σi > 0, pour résoudre le problème

min { f (x) : hj (x) = 0 , 1 ≤ j ≤ p , x ∈ Rn }

Les travaux de Bertsekas [22, 23, 24] et Rockafellar [239, 240, 241] sont de bonnes références pour
plus de détails sur le développement de cette méthode dite méthode du Lagrangien augmenté.
En 1970, les méthodes de pénalités exactes ont été introduites par R. Fletcher [101]. Il s’agissait
de minimiser une seule fonction pénalisée pour µ plus grand “qu’une valeur seuil µ̄”afin de
trouver les solutions des problèmes (P ) ou (T ). De nombreux travaux ont été concentrés sur
ces méthodes entre les années 1970 et 1984. Parmi ces travaux, signalons ceux de Bazaraa et
Goode [14], Coleman et Conn [57], Fletcher [101], Mangasarian [187, 188] et Maratos [189].

Après le “fameux”article de Karmarkar [149] en 1984, les méthodes de pénalités séquentielles

et différentiables ont connu une nouvelle impulsion. De nouvelles stratégies ont été introduites
pour résoudre les suites de problèmes pénalisés. Toutes ces méthodes sont basées sur la
différentiabilité de la fonction pénalisée. Parmi ces travaux, on peut signaler ceux de Gould
[126, 127], Gill et al. [117], Broyden et Attia [29, 30], McCormick [194] et Dussault [83].

L’idée principale des méthodes de pénalités est de ramener la résolution d’un problème
avec contraintes à la résolution d’une suite de problèmes sans contrainte. Pour une description
CHAPITRE 2. PROBLÈMES D’OPTIMISATION 37

générale du processus de ces méthodes, on considère le problème

min { f (x) : gi (x) ≤ 0 , i = 1, ..., m } (2.7)

x∈Rn

Soit p : R −→ R la fonction définie par


 0 si y ≤ 0
p(y) =
 +∞ si y > 0

et considérons le problème sans contrainte, appelé problème pénalisé,

min { φ(x) = f (x) + P (x) } (2.8)

x∈Rn

où la fonction P , appelée fonction de pénalisation, est définie par

m
X
P (x) = p( gi (x) ) , ∀x ∈ Rn .
i=1

La proposition qui suit, dont la preuve est triviale, établit le lien existant entre les problèmes
(2.7) et (2.8).

Proposition [Link]. Si l’ensemble réalisable X = { x ∈ Rn : gi (x) ≤ 0, i = 1, . . . , m } est non

vide, alors la résolution du problème (2.7) est équivalente à celle du problème (2.8).

Remarque [Link]. La fonction de pénalité P étant, par construction, discontinue, la résolution

du problème (2.8) est aussitôt très difficile et l’approche telle que discutée n’est pas applicable
en pratique. Toutefois, en définissant des fonctions de pénalisation continues et à dérivées
continues, l’approche de pénalités garde toute son importance.

2.4 Optimisation combinatoire

2.4.1 Définition et concepts de base

Généralement, on peut qualifier de “combinatoire”tout problème dont la résolution se ramène

à l’examen d’un nombre fini de combinaisons. Bien souvent, on constate que cette résolution
est confrontée à une explosion au niveau du nombre de combinaisons à explorer. Un problème
d’optimisation combinatoire peut être défini comme suit : étant donne un ensemble X de
CHAPITRE 2. PROBLÈMES D’OPTIMISATION 38

combinaisons, et une fonction f : X → R, il s’agit de trouver la meilleure combinaison de X

minimisant la fonction f, i.e., x∗ ∈ X tel que f (x∗ ) 6 f (xi ) pour tout xi ∈ X. L’optimisation
combinatoire trouve des applications dans des domaines aussi variés que la gestion, l’ingénierie, la
conception, la production, les télécommunications, les transports, l’énergie, les sciences sociales
et l’informatique elle-même.

2.4.2 Complexité théorique d’un problème

La “complexité d’un problème”correspond à une estimation du nombre d’instructions à exécuter

pour la résoulution des instances du problème. Cette estimation est reliée à un ordre de grandeur
par rapport à la taille de l’instance. Il s’agit d’une estimation dans le pire des cas dans le sens
où la complexité d’un problème est définie en considérant son instance la plus difficile. Les
travaux théoriques, dans ce domaine, ont permis d’identifier différentes classes de problèmes
en fonction de la complexité de leur résolution [222]. En effet, il existe un très grand nombre
de classes différentes, et on se limitera à une présentation succincte permettant de caractériser
formellement la notion de problème combinatoire.

Problèmes de décision

Pour les problèmes de décision, c’est-à-dire les problèmes posant une question dont la réponse
est “oui”ou “non”, les classes de complexité ont été introduites et on a défini notamment les
deux classes P et NP.

• La classe P contient l’ensemble des problèmes polynomiaux, i.e., pouvant être résolus
par un algorithme de complexité polynomiale. Cette classe caractérise l’ensemble des
problèmes que l’on peut résoudre “efficacement”.

• La classe NP contient l’ensemble des problèmes polynomiaux non déterministes, i.e.,

pouvant être résolus par un algorithme de complexité polynomiale pour une machine non
déterministe que l’on peut considérer comme une machine capable d’exécuter, en parallèle,
un nombre fini d’alternatives. Intuitivement, cela signifie que la résolution des problèmes
NP peut nécessiter l’examen d’un grand nombre (éventuellement exponentiel) de cas, mais
que l’examen de chaque cas doit pouvoir être fait en un temps polynomial.
CHAPITRE 2. PROBLÈMES D’OPTIMISATION 39

La classe P est manifestement inclue dans la classe NP alors que la relation inverse n’a jamais
été ni montrée ni infirmée. Cependant, certains problèmes de la classe NP apparaissent plus
difficiles à résoudre dans l’absence d’un algorithme polynomial de résoulution avec une machine
déterministe. Les problèmes les plus difficiles appartenant à la classe NP constituent la classe
des problèmes NP-complets : un problème NP est NP-complet s’il est au moins aussi difficile à
résoudre que n’importe quel autre problème de la classe NP, i.e., si n’importe quel autre problème
NP peut être transformé en ce problème par une procédure polynomiale. Ainsi, les problèmes
NP-complets sont des problèmes combinatoires étant donné que leur résolution implique l’examen
d’un nombre exponentiel de situations. Tous les problèmes combinatoires n’appartiennent pas à
la classe NP-complet malgré sa cardinalité élevée. En effet, pour qu’un problème soit NP-complet,
il faut qu’il soit dans la classe NP, i.e., que l’examen de chaque cas puisse être réalisé efficacement,
par une procédure polynomiale. Si l’on enlève cette contrainte d’appartenance à la classe NP,
on se retrouve avec une classe plus générale à savoir celle des problèmes NP-difficiles, contenant
l’ensemble des problèmes qui sont “au moins aussi difficiles”que n’importe quel problème NP,
sans nécessairement appartenir à la classe NP.

Problèmes d’optimisation

Pour chaque problème d’optimisation, il est possible d’associer un problème de décision dont le
but est de déterminer l’existence d’une solution pour laquelle la fonction objectif soit supérieure
(resp. inférieure) ou égale à une valeur donnée. La complexité d’un problème d’optimisation est
liée à celle du problème de décision qui lui est associé. En particulier, si le problème de décision
est NP-complet alors le problème d’optimisation est dit NP-difficile.

Parmi les principaux outils de modélisation uilisés pour la résolution des problèmes d’optimisation
combinatoire, on peut citer la théorie des graphes. En effet, la modélisation par les graphes est
naturelle dans le cas de certains problèmes (plus court chemin,...). Les problèmes d’optimisation
combinatoire peuvent aussi se formuler comme des programmes linéaires en nombres entiers
où les variables sont astreintes à prendre des valeurs entières. Tout problème de type sac à
dos peut être représenté par un programme linéaire en nombres entiers, i.e., un ensemble de
contraintes linéaires et une fonction objectif linéaire portant sur des variables à valeurs entières.
CHAPITRE 2. PROBLÈMES D’OPTIMISATION 40

2.4.3 Exemples de problèmes d’optimisation combinatoire

Problème du voyageur de commerce

Il s’agit de trouver le chemin le plus court reliant n villes données, chaque ville ne devant être
visitée qu’une et une seule fois, et revenir à la ville de départ. La difficulté du problème vient
de l’explosion combinatoire du nombre de chemins à explorer lorsque l’on accroı̂t le nombre de
villes à visiter. Plus formellement, ce problème peut être modélisé comme suit : étant donné un
graphe non orienté complet G = (S, A) et une fonction de distance d : A → R+ , on cherche à
déterminer un cycle hamiltonien de distance totale minimale. Pour ce problème, trouver s’il
existe un chemin hamiltonien est un problème NP-complet et la recherche du plus court chemin
hamiltonien est un problème NP-difficile.

Problème du sac à dos quadratique

Il consiste à sélectionner un sous-ensemble d’objets dont le poids total ne dépasse pas une
capacité donnée c du sac à dos et de maximiser le profit total. Plus formellement, ce problème
peut être déffini de la manière suivante : supposons N = {1, . . . , n} un ensemble d’objets donné
où chaque objet j ∈ N a un poids positif wj . De plus, nous disposons d’une matrice d’ordre
n d’entiers non négatifs P = pij où le pij est un profit accompli en sélectionnant deux objets
différents i et j ∈ N . En outre, le profit pii est accompli si l’objet i ∈ N est choisi. Des variables
binaires xj seront introduites et indiqueront si l’objet j ∈ N est sélectionné. Ce problème peut
être formulé comme suit :

XX X
M aximiser pij xi xj tel que wj xj 6 c avec xj ∈ {0, 1} pour j ∈ N
i∈N j∈N j∈N

2.4.4 Familles des méthodes d’optimisation combinatoire

Il est important de savoir situer le problème d’optimisation traité, afin de choisir la méthode la
plus appropriée pour sa résolution. Il y a trois grandes familles de méthodes d’optimisation : les
méthodes énumeratives, les méthodes déterministes et les méthodes stochastiques.
CHAPITRE 2. PROBLÈMES D’OPTIMISATION 41

Méthodes énumeratives

L’évaluation de la valeur de la fonction objectif est effectuée en chaque point de l’espace des
solutions qui peut être fini ou infini mais discrétisé. Ces méthodes sont intéressantes lorsque le
nombre de points à traiter n’est pas très important mais ce qui n’est pas le cas dans la pratique.
Les méthodes énumeratives ont deux inconvénients majeurs :

• Inadaptation aux problèmes de grande taille.

• Absence de processus intelligent guidant la recherche vers un sous-espace sans parcourir

l’ensemble des solutions possibles.

Méthodes déterministes

Ces méthodes n’utilisent aucun concept aléatoire, et elles se caractérisent par une exploration
systématique de l’espace de recherche. Elles requirent, en général, des hypothèses sur la fonction
objectif, telles que la continuité et la dérivabilité en tout point du domaine de recherche. Les
méthodes déterministes se divisent en deux classes principales : les méthodes d’exploration
directe et les méthodes d’exploration indirecte. Ces dernières cherchent à atteindre les extrema
locaux en résolvant les systèmes d’équations, souvent non linéaires, obtenus en annulant le
vecteur gradient de la fonction étudiée. Les méthodes d’exploration directe recherchent les
optima locaux en se déplaçant dans une direction dépendant du gradient de la fonction. Deux
inconvénients majeurs se présentent pour l’ensemble des méthodes déterministes :

• Dans la pratique, les fonctions à optimiser peuvent ne pas être dérivables et souvent la
propriété de la continuité n’est pas satisfaite.

• Risque de convergence prématurée vers un optimum local, l’optimum global n’est obtenu
que lorsque le point initial de départ choisi est proche de cet optimum.

Parmi les méthodes déterministes connues et assez utilisées, on peut citer :

La méthode de gradient qui est simple à mettre en œuvre et donnant souvent de bons
résultats. Pour cette raison, elle est largement utilisée dans des applications pratiques. Cette
méthode procède de la façon suivante : à partir d’un point de départ x0 , on calcule le gradient
∇f (x0 ) indiquant la direction de la plus grande augmentation possible de la fonction f . On se
CHAPITRE 2. PROBLÈMES D’OPTIMISATION 42

déplace d’une quantité λ0 dans le sens opposé au gradient et on obtient le point suivant :

x1 = x0 − λ0 ∇f (x0 )/k∇f (x0 )k

Par la suite, on finit par engendrer une série de points x0 , x1 , x2 , . . . , xk qui se rapprochent de
plus en plus de l’optimum via la relation

xk+1 = xk − λk ∇f (xk )/k∇f (xk )k

où λk > 0 est le pas de déplacement associé à chaque itération. Si le pas est fixe, on parle de
méthode de gradient à pas prédéterminé. L’inconvénient d’une telle option est que la convergence
dépendra beaucoup du choix du pas et cela risque de ralentir le processus de résolution. Pour
remédier à ce défaut, la méthode de la plus forte pente est utilisée. Elle permet de se libérer du
choix de λk qui doit être calculé en minimisant à chaque itération la fonction g définie par la
relation g(λ) = f (xk − λ∇f (x0 )), c-à-d λk = arg min (f (xk − λ∇f (xk )) ) [50]. Cette approche
λ
est la base de l’algorithme de Hill-Climbing appelé également algorithme de descente de gradient.

La méthode de Newton dont l’idée de base, pour l’optimisation sans contrainte, consiste
à utiliser, de manière itérative, l’approximation quadratique de la fonction objectif f à l’itération
courante et de minimiser cette approximation. Cette méthode suppose que la fonction f est
continue et deux fois différentiable et que le hessien ∇2 f (xk ) est défini positif. De la même
manière que la méthode du gradient, la suite {xk }k est définie par la relation :

xk+1 = xk − [∇2 f (xk )]−1 ∇f (xk )

Il existe une littérature abondante portant sur les méthodes à base de Newton [158, 159, 160, 78].

D’autres méthodes déterministes peuvent être mentionnées à savoir la méthode multistart

consistant à effectuer une recherche locale à partir de plusieurs points répartis dans l’espace
de recherche. Un maillage adéquat doit être établi au préalable en respectant la forme de
la fonction objectif. Si le maillage est trop grand, il y a un risque de ne pas traiter certains
intervalles. Dans le cas contraire, la recherche ne sera pas efficace puisque plusieurs points de
départ donneront lieu au même résultat.
CHAPITRE 2. PROBLÈMES D’OPTIMISATION 43

Méthodes stochastiques

Il s’agit de méthodes itératives où l’optimisation est guidée partiellement ou totalement par un
processus stochastique. Lorsqu’on veut résoudre un problème difficile, dès que sa dimension
est grande, les méthodes d’exploration traditionnelles, déterministes ou énumératives peuvent
exiger un temps de calcul déraisonnable, et on a alors recours aux méthodes stochastiques.
Cependant, ces dernières présentent l’inconvénient de ne pas assurer la convergence que d’une
manière asymptotique [146, 226, 26].

Parmi les différentes méthodes stochastiques d’optimisation globale, on peut mentionner les
heuristiques modernes. Une heuristique peut être conçue pour résoudre un type de problème
donné, ou bien être conçue comme une méthode générale, qui peut être adaptée à divers
problèmes d’optimisation, et dans un tel cas il s’agit de métaheuristique.

Les métaheuristiques sont, à l’origine, dédiées aux problèmes combinatoires, où les paramètres
ne peuvent prendre que des valeurs discrètes. Pour l’optimisation continue, ces méthodes peuvent
être adaptées moyennant des transformations plus au moins aisées, en inventant une nouvelle
topologie. Chaque paramètre doit être discretisé de façon individuelle. La difficulté majeure
réside dans la détermination de la taille optimale du pas de discrétisation et de sa direction. Les
heuristiques comportent souvent plusieurs paramètres contrôlant les différents opérateurs et
l’influence du ou des processus stochastiques. L’efficacité d’une heuristique dépend du choix de
ses paramètres de contrôle. Ce réglage est complexe, surtout quand le nombre de paramètres
est élevé et quand la plage de variation de chacun de ces paramètres est étendue. Les différents
paramètres sont généralement corrélés, ce qui rend encore plus difficile leur réglage.

Les métaheuristiques progressent de façon itérative, en alternant des phases d’intensification,

de diversification et d’apprentissage, ou en mêlant ces notions de façon plus étroite. L’état de
départ est souvent choisi aléatoirement, l’algorithme se déroulant ensuite jusqu’à ce qu’un critère
d’arrêt soit atteint. Enfin, pour un jeu de paramètres de contrôle donnés, l’aspect stochastique
implique que les résultats varient d’une exécution à l’autre. Les principales métaheuristiques
modernes [25] les plus utilisées, suivant l’ordre chronologique d’apparition, sont les algorithmes
génétiques en 1975, la méthode du recuit simulé en 1983, la méthode de recherche tabou en
1986, l’algorithme de colonie de fourmis en 1990 et l’algorithme essaim de particules en 1995.
CHAPITRE 2. PROBLÈMES D’OPTIMISATION 44

2.4.5 Méthodes exactes et Méthodes approchées

Méthodes exactes

Le principe essentiel d’une méthode exacte consiste, généralement, à énumérer, souvent de

manière implicite, l’ensemble des combinaisons de l’espace de recherche. Parmi les méthodes
exactes, on retrouve les méthodes de séparation et évaluation, dites méthodes de Branch &
Bound, ainsi que la programmation dynamique.

Branch & bound

Branch & Bound est une technique effectuant un parcours en profondeur de l’arbre de recherche
afin de fournir une ou plusieurs solutions optimales à partir d’un ensemble de solutions potentielles.
À chaque étape de la recherche, correspondant à un nœud de l’arbre de recherche, l’algorithme
utilise une fonction Bound pour calculer une borne de l’ensemble des solutions du sous-arbre
prenant sa racine à ce nœud. En début de résolution, cette borne est initialisée à une valeur
maximale (en cas de minimisation). Si cette évaluation est moins bonne que la meilleure solution
trouvée jusqu’à ce niveau de recherche, tout le sous-arbre peut être coupé et ignoré. Il importe
de souligner que l’efficacité de l’algorithme Branch & Bound dépend étroitement du calcul de la
borne utilisée.

Programmation dynamique

La programmation dynamique est une méthode ascendante : on commence habituellement par

les sous-problèmes les plus simples et on remonte vers les sous-problèmes de plus en plus difficiles.
Elle est utilisée pour les problèmes satisfaisant au principe d’optimalité de Bellman : “dans une
séquence optimale (de décisions ou de choix), chaque sous-séquence doit aussi être optimale”.
Un exemple typique de tels problèmes correspond au plus court chemin entre deux sommets
d’un graphe. L’idée de base est d’éviter de calculer deux fois la même chose, généralement en
utilisant une table de résultats déjà déterminés, remplie au fur et à mesure que l’on résout les
sous-problèmes. Il est à noter que la programmation dynamique est utilisée pour résoudre des
problèmes polynomiaux et non des problèmes NP-difficiles.
CHAPITRE 2. PROBLÈMES D’OPTIMISATION 45

Méthodes approchées

Pour telles approches, on peut distinguer les approches par voisinage et les approches par
construction. Les approches par voisinage partent d’une ou plusieurs solutions initiales qu’elles
cherchent à améliorer à partir d’un voisinage défini, alors que les approches constructives partent
d’un ensemble de solutions vide et générent de nouvelles solutions de façon incrémentale en
ajoutant itérativement des composants aux solutions en cours de construction.

Approches par voisinage

L’idée de telles approches est de structurer l’ensemble des solutions en terme de voisinage, et
d’explorer cet ensemble en partant d’une ou plusieurs solutions initiales et en choisissant à
chaque itération une ou plusieurs solutions voisines d’une ou plusieurs solutions courantes. Le
voisinage d’une solution S est l’ensemble des solutions qui peuvent être atteintes à partir de S en
un seul “mouvement”, un mouvement étant par exemple, le changement de valeur d’une variable.
Un algorithme de recherche locale glouton cherche dans le voisinage une solution qui améliore
la qualité de la solution courante. Si une telle solution est trouvée, elle remplace la solution
courante et la recherche locale continue. Ces étapes sont répétées jusqu’à ce qu’aucune solution
meilleure ne puisse être retrouvée dans le voisinage de la solution courante et l’algorithme
termine avec un optimum local. L’optimum local est la meilleure solution parmi les solutions
du voisinage, contrairement à l’optimum global qui est la meilleure solution parmi toutes les
solutions possibles. Plusieurs améliorations à cet algorithme glouton ont été proposées, dans
la littérature pour essayer d’échapper aux optima locaux, notamment la recherche tabou et le
recuit simulé.
Recherche Tabou est une méthode heuristique d’optimisation combinatoire développée par
Glover [119]. Elle effectue des mouvements à partir d’une solution S vers une meilleure solution
S 0 appartenant au voisinage de S noté N (S). Si ce voisinage est trop grand, seulement une
partie V (S) ⊆ N (S) sera examinée. Pour éviter de rester bloqué dans le premier minimum local
rencontré, la méthode Tabou accepte des solutions voisines dont la qualité est moins bonne que
la solution courante. Elle se dirige alors vers la solution voisine qui dégrade le moins possible la
fonction objectif. Cette dégradation de f , que l’on espère être temporaire, devrait permettre à
l’algorithme d’atteindre des régions de l’espace contenant des solutions meilleures que celles
rencontrées jusqu’à date. Cependant, l’algorithme Tabou risque de boucler en revisitant des
CHAPITRE 2. PROBLÈMES D’OPTIMISATION 46

solutions antérieures pendant l’itération suivante (ou après quelques itérations intermédiaires).
Pour éviter ce phénomène, l’algorithme utilise une structure de mémoire dans laquelle il stocke
les mouvements interdits à chaque étape afin de ne pas obtenir une solution déjà rencontrée
récemment. Ces mouvements interdits à une itération donnée sont dits tabous, d’où le nom
attribué à la méthode proposée par Glover [118]. Le caractère tabou d’un mouvement doit
être temporaire afin de donner une plus grande flexibilité à l’algorithme en lui permettant de
remettre en question les choix effectués, une fois que les risques de bouclage ont été écartés. La
façon la plus simple de mettre en œuvre ce système d’interdictions consiste à garder en mémoire
les derniers mouvements effectués et à empêcher l’algorithme de faire les mouvements inverses
à ces derniers mouvements. Ces mouvements sont mémorisés dans une liste T appelée liste
tabou. La gestion de cette liste se fait de manière circulaire en remplaçant à chaque itération le
mouvement le plus ancien de la liste par le mouvement courant. Cependant, il peut se trouver
des cas où il est intéressant de révoquer le statut tabou d’un mouvement lorsque son application
à la solution courante permet d’atteindre une solution meilleure. La mise en œuvre d’un tel
mécanisme est réalisée à l’aide d’une fonction auxiliaire A appelée fonction d’aspiration.

Dans cette méthode, le compromis entre les mécanismes d’intensification/diversification peut

être géré par la taille de la liste tabou. Pour favoriser l’intensification de la recherche, il suffit de
diminuer la taille de la liste tabou, et contrairement, pour favoriser la diversification, il s’agit
d’augmenter la taille de cette liste.

Recuit simulé repose sur une analogie avec la thermodynamique. En effet, la recherche
par un système physique des états d’énergie les plus bas est l’analogue formel d’un processus
d’optimisation combinatoire. Le recuit est un processus physique de chauffage. Un système
physique porté à une température assez élevée devient liquide, dans ce cas il y a augmentation
du degré de liberté des atomes qui le composent. Inversement, lorsque l’on baisse la température,
le degré de liberté correspondant diminue jusqu’à l’obtention d’un solide. Suivant la façon dont
on diminue la température, on obtient des configurations d’énergie différentes :

• Baisse brutale de la température, la configuration atteinte est le plus souvent un état

métastable, dont l’énergie est supérieure à celle du minimum absolu. Le système est, en
quelque sorte, piégé dans ce minimum local.

• Baisse progressive de la température de façon à éviter de piéger le système dans des vallées
d’énergie élevée, pour l’envoyer vers les bassins les plus importants et les plus profonds, là
CHAPITRE 2. PROBLÈMES D’OPTIMISATION 47

où les baisses ultérieures de température le précipiteront vers les fonds.

La méthode d’optimisation du recuit simulé, a été proposée en 1982, par S. Kirkpatrick et al.
[154] à partir de la méthode de Metropolis et al. [197] utilisée pour modéliser les processus
physiques. Kirkpatrick s’est inspiré de la mécanique statistique en utilisant, en particulier, la
distribution de Bolzmann. Le recuit simulé permet de sortir d’un minimum local en acceptant
avec une certaine probabilité une dégradation de la fonction. Ainsi, la probabilité p qu’un
système physique passe d’un niveau d’énergie E1 à un niveau E2 est donnée par la relation :

E2 −E1
−
p=e kb T
(2.9)

où kb est la constante de Bolzmann et T désigne la température du système. La probabilité

d’observer une augmentation de l’énergie est d’autant plus grande que la température est élevée.
Au niveau du recuit simulé, il s’ensuit les faits suivants :

• une diminution de la fonction sera toujours acceptée,

• une augmentation de la fonction sera acceptée avec une probabilité définie selon une
formule de type 2.9.

Dans la méthode du recuit simulé, les mécanismes d’intensification et de diversification sont

contrôlés par la température. En effet, la température décroı̂t au fil du temps de sorte que la
recherche tend à s’intensifier vers la fin de l’algorithme.
Chapitre 3
L’optimisation multi-objectifs

L’optimisation multiobjective ou multi-objectifs est un axe de recherche très important puisque

la considération de toutes les facettes d’un problème réel traité implique souvent une nature
multi-objectifs du modèle engendré. Les premiers travaux menés sur les problèmes multi-objectifs
furent réalisés par Edgeworth au 19ème siècle et portés sur des études en économie. Ces travaux
ont été généralisés ultérieurement par Pareto.

En pratique, les problèmes d’optimisation rencontrés sont de nature multi-objectifs : plusieurs

fonctions objectifs contradictoires ou conflictuelles sont à satisfaire. L’optimisation multiobjective
est, de plus en plus, utilisée depuis environ trois décennies, et son application dans les problèmes
du monde réel ne cesse d’augmenter. Son but est de chercher à optimiser simultanément
plusieurs composantes de la fonction objectif principale. La solution du problème ne correspond
pas nécessairement à un vecteur unique, mais plutôt à un ensemble de solutions connu sous
l’appellation de l’ensemble de solutions Pareto optimales. Toute solution de cet ensemble est
optimale dans le sens qu’aucune amélioration ne peut être faite sur une composante du vecteur
sans dégradation d’au moins une autre composante.

49
CHAPITRE 3. L’OPTIMISATION MULTI-OBJECTIFS 50

3.1 Généralités

3.1.1 Formulations et concepts de base

Un problème d’optimisation avec objectifs multiples peut être représenté par le programme :

min f (x) avec g(x) 6 0 et h(x) = 0 où x ∈ Rn , f (x) ∈ Rk , g(x) ∈ Rm et h(x) ∈ Rp

Il est aussi possible de fournir une représentation similaire d’un problème multi-objectifs par la
formule suivante : (P ) min f (x) = (f1 (x), . . . , fk (x)) | x ∈ S et k > 2

• x, étant un vecteur solution (x1 , ..., xn ) d’un espace S de dimension n, représente des
instances des variables de décision xi .

• S représente l’ensemble des solutions réalisables respectant un ensemble de contraintes C

d’égalité, d’inégalité et des bornes explicites.

• f = (f1 , f2 , . . . , fk ) est le vecteur fonction objectif à optimiser où k représente le nombre

d’objectifs.

• Ψ = F (x) représente les points réalisables dans l’espace objectif Y = (y1 , ..., yk ) où
yi = fi (x) désigne un point de l’espace objectif.

Figure 3.1: Problème d’optimisation multiobjective.

Les problèmes multi-objectifs ont la particularité d’être beaucoup plus difficiles à traiter
que leur équivalent mono-objectif. La difficulté réside dans l’absence d’une relation d’ordre
total entre les solutions. Une solution peut être meilleure qu’une autre sur certains objectifs et
moins bonne sur les autres. Par conséquent, il n’existe généralement pas une solution unique qui
procure simultanément la solution optimale pour l’ensemble des objectifs. Le concept de solution
CHAPITRE 3. L’OPTIMISATION MULTI-OBJECTIFS 51

optimale devient moins pertinent en optimisation multiobjective. Dans ce cas, la solution

optimale ou de bonne qualité n’est plus une solution unique mais, un ensemble de solutions de
compromis entre les différents objectifs à optimiser. Il est vital pour identifier de tels meilleurs
compromis de définir une relation d’ordre entre ces éléments. La procédure la plus célèbre et la
plus utilisée, pour l’identification des meilleurs compromis, est la relation de dominance au sens
Pareto. L’ensemble des solutions identifiées est appelé le front Pareto, la surface de compromis
ou l’ensemble des solutions efficaces. Cet ensemble de solutions constitue un équilibre, dans
le sens qu’aucune amélioration ne peut être faite sur un objectif sans dégradation d’au moins
un autre objectif. La solution Pareto consiste à obtenir le front de Pareto ou d’approximer la
frontière de Pareto.

3.1.2 Notions de dominance

La résolution d’un problème d’optimisation multiobjective permet d’obtenir une multitude de

solutions. Seul un nombre restreint de telles solutions sera intéressant. Pour qu’une solution
soit intéressante, il faut qu’il existe une relation de dominance entre la solution considérée et les
autres solutions.

• Relation de dominance
Le vecteur x1 domine le vecteur x2 si x1 est au moins aussi bon que x2 relativement à tous
les objectifs, et x1 est strictement meilleur que x2 pour au moins un objectif.

• Optimalité locale au sens de Pareto

Un vecteur x ∈ Rn est dit optimal localement au sens de Pareto s’il existe un réel δ > 0
0 0
tel qu’il n’y ait pas de vecteur x qui domine le vecteur x avec x ∈ Rn ∩ B(x, δ) où B(x, δ)
représente une boule de centre x et de rayon δ.

• Optimalité globale au sens de Pareto

Un vecteur x est optimal globalement au sens de Pareto (ou optimal au sens de Pareto)
0 0
s’il n’existe pas de vecteur x tel que x domine le vecteur x.

• Cône négatif
Un cône négatif est défini dans Rk via la relation : C − = x | f (x) ∈ Rk et f (x) 6 0

• Théorème de contact
Un vecteur x est optimal au sens de Pareto pour un problème d’optimisation multiobjective
CHAPITRE 3. L’OPTIMISATION MULTI-OBJECTIFS 52

donné si (C − + x) ∩ F = {x}

Figure 3.2: Optimalité locale au sens de Pareto.

Figure 3.3: Théorème de contact

Lorsque l’on applique la définition de la dominance, on peut définir quatre régions auxquelles
on peut attribuer des niveaux de préférence. De telles régions sont représentées à la figure (3.4)
en reprenant le découpage défini par le cône négatif que l’on a introduit précédemment et en
l’étendant à tout l’espace.

La relation de dominance n’offre pas de degrés de liberté dans sa définition initiale car il
n’est pas possible d’inclure dans la définition de la relation de dominance une préférence d’un
objectif par rapport à un autre. Pour contourner ce manque de flexibilité, des relations dérivées
de la relation de dominance ont été développées. Les solutions obtenues via l’application des
relations dérivées de la dominance sont toutes optimales au sens de Pareto. La grande différence
rencontrée avec l’utilisation de telles relations consiste dans le fait que l’ensemble des solutions
CHAPITRE 3. L’OPTIMISATION MULTI-OBJECTIFS 53

Figure 3.4: Niveaux de préférence via la relation de dominance.

obtenu est un sous-ensemble de l’ensemble des solutions obtenues avec la relation de dominance
de Pareto. Pour le reste de cette section, on suppose que l’ensemble S k désigne l’ensemble des
solutions réalisables d’un problème d’optimisation à k fonctions objectifs.

• Optimalité lexicographique
Cette notion de l’optimalité permet d’inclure une préférence entre les diverses fonctions
objectifs [85]. Une solution x∗ ∈ S k est dite optimale au sens lexicographique si

x∗ 6 x, ∀x ∈ S k \ {x∗ }

Cette définition implique que l’utilisateur ait rangé par ordre d’importance les différents
objectifs et, qu’en conséquence, la comparaison entre les deux solutions se fera dans l’ordre
de classement des objectifs.

• Optimalité extrême
Similairement à la relation d’optimalité lexicographique, cette relation permet d’établir
une préférence entre critères. Cette préférence est établie en utilisant le principe des
pondérations. Plus un objectif sera important, plus son poids sera élevé [85]. Une solution
x∗ ∈ S k est dite extrême-optimale si, étant donné un vecteur de poids λ ∈ Rk tel que
λi = 1, x∗ est une solution optimale du problème de minimisation mono-objectif ayant
P
i
pour fonction objectif
k
X
λi .xi
i=1
CHAPITRE 3. L’OPTIMISATION MULTI-OBJECTIFS 54

et par conséquent
k
X k
X
λi .x∗i 6 λi .xi , ∀x ∈ S k \ {x∗ }
i=1 i=1

• Optimalité maximale
Cette relation, contrairement aux précédentes, ne permet pas d’introduire une préférence
entre objectifs [85]. Une solution x∗ ∈ S k est dite max-optimale si la valeur du pire objectif
est aussi petite que possible :

max x∗q 6 max xq avec x ∈ S k \ {x∗ }

q∈{1,...,k} q∈{1,...,k}

La a-dominance

Il s’agit d’une définition de dominance introduite par Othmani [217] en 1998. Une solution
x∗ ∈ S k a-domine une solution x ∈ S k s’il existe un ensemble de combinaisons de (k + 1 − a)
objectifs tel que :

(a) x∗j 6 xj pour tout indice j ∈ I(k+1−a) ,

(b) x∗i < xj pour au moins un indice j ∈ I(k+1−a) où I(k+1−a) représente l’ensemble des indices
correspondant à l’ensemble des combinaisons de tels objectifs.

Dominance au sens de Geoffrion

Une forme de dominance importante dans l’univers de l’optimisation multiobjective correspond

à la dominance au sens de Geoffrion [86, 198] et dont les solutions optimales obtenues sont
appelées solutions Pareto optimales propres. Une solution x∗ ∈ S est dite solution Pareto
optimale propre si :

• elle est Pareto optimale,

• il existe un nombre M > 0 tel que ∀i ∈ {1, . . . , k} et ∀x ∈ S vérifiant fi (x) < fi (x∗ ), il
existe un indice j tel que fj (x∗ ) < fj (x) et

fi (x∗ ) − fi (x)
6M
fj (x) − fj (x∗ )
CHAPITRE 3. L’OPTIMISATION MULTI-OBJECTIFS 55

Cette relation n’est quasiment jamais utilisée dans sa formulation originale. En général, on
utilise plutôt un résultat qui en découle. En effet, l’interprétation de cette relation [86] peut
s’énoncer de la manière suivante : “Les solutions Pareto optimales propres ont des compromis
bornés suivant leurs objectifs”. Un théorème relatif à la méthode de pondération des fonctions
objectifs utilisant ce résultat se présente comme suit :

Théorème [Link]. Soit la méthode d’agrégation des fonctions objectifs suivante :

k
X
feq (x) = wi .fi (x)
i=1

Supposons que la relation de convexité est satisfaite à savoir ∀i = 1, . . . , k, on a wi > 0 avec

k
wi = 1. Si x∗ est une solution optimale obtenue en utilisant la méthode d’agrégation ci-dessus,
P
i=1
alors cette solution est aussi Pareto optimale propre.

La méthode de pondération des fonctions objectifs, avec des poids respectant la relation de
convexité, permet d’obtenir des solutions avec des compromis bornés.

Ces différents types de relations de dominance permettent d’avoir suffisamment de degrés de

liberté pour choisir une relation qui reproduise au mieux le comportement d’un ingénieur ou
d’un décideur. Par exemple, la relation de dominance lexicographique permet de reproduire
le comportement d’un décideur qui choisirait une solution parmi les diverses solutions en
considérant des objectifs rangés par ordre d’importance. En effet, le décideur, quand il compare
deux solutions, il compare les valeurs des objectifs, jusqu’à ce qu’un objectif permette de
déterminer une préférence entre les deux solutions considérées. Une fois que la préférence entre
les deux solutions est déterminée, les objectifs restants ne sont plus pris en considération et la
comparaison s’arrête à ce stade.

La dominance est donc un outil, parmi d’autres, permettant de reproduire une démarche de
recherche d’optimum. Elle n’est pas la seule, bien sûr, mais elle représente un élément important
pour la résolution d’un problème.

3.1.3 Surface de compromis

Il est possible de former la surface de compromis (ou front de Pareto) en utilisant la règle de
classement basée sur la définition de la dominance. Ainsi, pour un problème d’optimisation à
deux objectifs f1 et f2 à minimiser dans Rn sous des contraintes de type g(x) 6 0 et h(x) = 0,
CHAPITRE 3. L’OPTIMISATION MULTI-OBJECTIFS 56

on définit S l’ensemble des valeurs du couple (f1 (x), f2 (x)) lorsque le vecteur x respecte les
contraintes g(x) 6 0 et h(x) = 0. On appelle P la surface de compromis telle qu’indiquée sur la
figure 3.5 pour un problème de type bi-objectif.

Figure 3.5: Représentation de la surface de compromis.

La forme de la surface de compromis engendrée dépend du type de problème que l’on cherche
à résoudre. L’une des formes les plus courantes est présentée à la figure 3.6. Une telle forme de
surface de compromis est typique d’un problème d’optimisation multi-objectifs sur un ensemble
de solutions convexe. Il s’agit du type d’ensemble que l’on rencontre la plupart du temps.

Figure 3.6: Formes les plus courantes de surface de compromis dans le cas bi-objectif.

On observe deux points caractéristiques associés à une surface de compromis :

• Point idéal : il correspond au point pour lequel les coordonnées sont obtenues en
optimisant chaque fonction objectif séparément.
CHAPITRE 3. L’OPTIMISATION MULTI-OBJECTIFS 57

• Point nadir : il s’agit d’un point dont les coordonnées correspondent aux pires valeurs
obtenues par chaque fonction objectif lorsque l’on restreint l’espace des solutions à la
surface de compromis.

Le point idéal est utilisé dans beaucoup de méthodes d’optimisation comme point de référence
alors que le point nadir sert à restreindre l’espace de recherche ; il est utilisé dans certaines
méthodes d’optimisation interactives.

Figure 3.7: Représentation du point idéal et du point ”nadir”

3.1.4 Convexité

Certaines méthodes d’optimisation multiobjective nécessitent de respecter certaines hypothèses.

Le plus souvent, les méthodes utilisées réclament la convexité de l’espace S des valeurs de
l’objectif f . Brièvement, un ensemble S est dit convexe si, pour toute paire donnée de points
distincts quelconques de cet ensemble, le segment reliant les deux points est contenu dans
l’ensemble S.

Figure 3.8: Exemples d’ensemble convexe et d’ensemble non convexe.

CHAPITRE 3. L’OPTIMISATION MULTI-OBJECTIFS 58

3.2 Méthodes d’optimisation multiobjective

Il existe un nombre important de méthodes d’optimisation multiobjective et leur catégorisation

peut être effectuée en cinq classes selon l’approche de résolution mathématique adoptée :

• Méthodes scalaires,

• Méthodes interactives,

• Méthodes floues,

• Méthodes exploitant une métaheuristique,

• Méthodes d’aide à la décision.

Une classification plus “fine”est développée dans la section 3.3.

3.2.1 Méthodes scalaires

A l’origine, les méthodes scalaires ont été appliquées pour transformer un problème multi-
objectifs en un autre problème mono-objectif. Plusieurs approches différentes ont été mises au
point pour assurer cette transformation et elles peuvent être regroupées en approches agrégatives
avec contraintes, approches agrégatives sans contraintes ou encore en approches agrégatives
hyprides.

Méthodes agrégatives sans contraintes

Elles correspondent à l’une des premières approches utilisées pour résoudre les problèmes multi-
objectifs [138]. L’ensemble de ces méthodes repose sur l’axiome suivant : tout décideur essaie
inconsciemment d’optimiser une fonction d’utilité (fonction choisie comme étant prioritaire). Les
modèles les plus utilisés sont le modèle additif et le modèle multiplicatif. Parmi ces méthodes,
on retrouve :

• Méthode de la somme pondérée

Elle est appelée aussi approche naı̈ve de l’optimisation multiobjective [55], et elle consiste
à additionner tous les objectifs tout en affectant à chacun d’eux un coefficient de poids.
Le coefficient associé à un objectif donné représente l’importance relative que le décideur
CHAPITRE 3. L’OPTIMISATION MULTI-OBJECTIFS 59

attribue à l’objectif en question. Cette méthode est simple à mettre en œuvre et elle est
efficace du point de vue algorithmique. En faisant varier les coefficients de pondération, on
peut retrouver la surface de compromis si le domaine réalisable est convexe. Cependant,
la difficulté essentielle de cette approche est la manière de détermination des poids de
chaque fonction objectif par le décideur et l’expression de l’interaction entre les différentes
fonctions. De plus, cette méthode ne permet pas de trouver les solutions enfermées dans
une concavité. Dans certains problèmes d’optimisation de structures mécaniques, elle peut
se comporter de manière catastrophique [167]. Certains travaux ont été focalisés pour
contourner ces deux difficultés [190, 191, 192].

• Méthode de Keeney-Raiffa
Cette méthode utilise le produit des fonctions objectifs pour se ramener à un problème
d’optimisation mono-objectif. L’approche utilisée est semblable à celle retrouvée dans
la méthode de pondération des fonctions objectifs. La fonction objectif, ainsi obtenue,
s’appelle fonction d’utilité de Keeney-Raiffa et elle est retrouvée dans la théorie de la
fonction utilité multi-attributs exposée dans [157].

Méthodes agrégatives avec contraintes

• Méthodes de compromis (Méthodes -contraintes)

Elles permettent de transformer un problème d’optimisation multi-objectifs en un problème
d’optimisation mono-objectif comportant quelques contraintes supplémentaires. La
démarche utilisée (détaillée ultérieurement) se résume à :

(a) choisir une fonction objectif à optimiser prioritairement ;

(b) choisir un vecteur de contraintes initial ;

(c) transformer le problème en conservant la fonction objectif prioritaire et en transfor-

mant les autres fonctions objectifs en contraintes d’inégalité.

Eschenauer et al. [92] ont montré que cette méthode peut se ramener à la méthode
de pondération des fonctions objectifs moyennant une légère transformation. Cette
méthode est gourmande en temps de calcul et la programmation de l’algorithme peut
être extrêmement difficile s’il y a trop de fonctions contraintes. Cependant, la relative
simplicité de l’énoncé de la méthode l’a rendue populaire. Cette méthode est aussi appellée
CHAPITRE 3. L’OPTIMISATION MULTI-OBJECTIFS 60

méthode -contrainte [198] et elle sera abordée d’une manière détailée dans le chapitre
suivant. Elle représente l’une des inspirations pour une nouvelle approche proposée.

• Méthode “but à atteindre”

Dans la littérature anglo-saxonne, on désigne cette méthode sous l’appellation goal attain-
ment method. La méthode n’impose pas d’évoluer dans un domaine réalisable convexe et
elle s’énonce comme suit :

(a) choisir un vecteur de fonctions objectif initial F ;

(b) choisir W une direction de recherche (des coefficients de pondération sont fournis, en
quelque sorte, comme pour la méthode de pondération des fonctions objectifs) ;

(c) chercher, ensuite, à minimiser un coefficient scalaire λ représentant l’écart par rapport
à l’objectif initial F que l’on s’était fixé.

Le principal avantage de cette méthode est qu’elle offre la possibilité de travailler avec un
ensemble de solutions S qui n’est pas nécessairement convexe. Cependant, il peut exister
des formes de domaines pour lesquelles la solution dépend du choix du but initial. Cette
conclusion peut être engendrée pour tous les types de méthodes basées sur une distance.

• Méthode “but à programmer”

Cette méthode (Goal programming) se rapproche beaucoup de la méthode du but à
atteindre. La principale différence est la structure du problème d’optimisation résultant
après la transformation. On se retrouve avec un problème d’optimisation ayant des
contraintes d’égalité et plus de contraintes d’inégalité. La méthode peut s’énoncer comme
suit :

(a) choisir un vecteur de fonctions objectifs initial F ;

(b) associer, à chaque objectif, deux nouvelles variables que l’on appelle “déviations”par
rapport au vecteur de fonctions objectifs initial fixé;

(c) minimiser, ensuite, l’une des deux variables. Le choix de la variable se fait en fonction
du type de dépassement voulu.

La méthode du but à programmer, semblable à la méthode du but à atteindre, soulève

les mêmes critiques. Dans certains cas, on peut “rater”des solutions cachées dans des
concavités [198].
CHAPITRE 3. L’OPTIMISATION MULTI-OBJECTIFS 61

D’autres méthodes peuvent aussi être indiquées et notamment la méthode d’ordonnancement lex-
icographique [55], la méthode des contraintes d’égalité propres [179], la méthode des contraintes
d’inégalité propres [181] ou encore la méthode min-max [198].

Méthodes agrégatives hybrides

Il est parfois possible d’exploiter plusieurs méthodes pour en extraire une nouvelle méthode.
Dans un tel cas, nous obtenons une “méthode hybride”. La méthode hybride la plus connue est
la méthode de Corley utilisant la méthode de pondération des fonctions objectifs et la méthode
de compromis. Elle combine les avantages des deux méthodes citées précédemment et elle est
efficace sur différents types de problèmes, qu’ils soient convexes ou non convexes. Cependant,
une difficulté survient : le nombre de paramètres à déterminer est doublé. Il sera beaucoup plus
difficile à l’utilisateur d’exprimer sa préférence en jouant sur l’ensemble des paramètres [198].

3.2.2 Méthodes itératives

Les méthodes itératives permettent à l’utilisateur de déterminer ses préférences relativement à

un compromis entre les divers objectifs au cours de l’optimisation. Elles forment la famille des
méthodes progressives permettant de chercher une et une seule solution. Dans cette panoplie de
méthodes, on peut citer ce qui suit.

• Méthode de compromis par substitution

Cette méthode a été très utilisée pour l’optimisation de ressources en eau [131]. Elle est
basée sur la méthode de compromis (-contraintes), à laquelle on ajoute un processus
interactif pour que la méthode converge vers la solution la plus susceptible de satisfaire
l’utilisateur. Le décideur est impliqué dans tout le processus pour l’évaluation de la valeur
des coefficients de pondérations, et les informations peuvent être obtenues progressivement
à chaque itération. Cette méthode nécessite moins d’hypothèses qu’une méthode à priori,
mais bon nombre de ses procédures sont plus complexes et peuvent prendre beaucoup
de temps pour le décideur. L’inconvénient de cette méthode est qu’il n’est pas toujours
évident de savoir quel prix on est prêt à payer pour un accroissement de la valeur d’une
fonction. Dans la plupart des cas, on peut être tenté de répondre un peu au hasard.
Ce type de réponses peut alors empêcher la méthode de trouver le ou les bons optima.
CHAPITRE 3. L’OPTIMISATION MULTI-OBJECTIFS 62

De plus, cette méthode n’est applicable qu’à des problèmes dont la fonction objectif de
référence est dérivable.

• Méthode de Fandel
Cette méthode aide l’utilisateur dans le choix de ses coefficients de pondération [92]. Tel est
le cas pour la méthode de pondération des fonctions objectifs, la variation des coefficients
wi permet de déterminer les points de la surface de compromis. En revanche, dans la
méthode de Fandel, on suppose que ces coefficients ne sont pas connus. On suppose aussi
que l’utilisateur cherche une solution qui soit proche de la solution idéale. Pour obtenir
ces coefficients, il faut calculer le minimum de chaque fonction objectif du problème (P )
tout en respectant les contraintes. Cela permettra de former, ensuite, le vecteur objectif
idéal, et de réduire la taille de l’espace de recherche en manipulant les contraintes. Par la
suite, il y aura minimisation des fonctions objectifs sur ce nouvel espace de recherche. La
méthode converge vers un point qui, normalement, doit satisfaire l’utilisateur. Par contre,
l’inconvénient de cette méthode, est que l’on ne peut déterminer qu’un seul point solution,
et non la totalité de la surface de compromis. La méthode suppose aussi l’hypothèse que
le vecteur solution qui satisfera l’utilisateur est le vecteur le plus proche de la solution
idéale. Il s’agit d’une hypothèse forte qui conduit cette méthode à ne pas pouvoir convenir
à tous les utilisateurs. Pour conclure, le mode d’interaction implique que, pour une bonne
utilisation de la méthode, l’utilisateur doit avoir une bonne connaissance à priori du
problème traité. Il doit être capable de trouver de bonnes bornes pour restreindre son
problème. Eschenauer et al. [92] ont traité aussi la méthode STEP similaire à la méthode
de Fandel mais tout en permettant de réduire l’espace de recherche étape par étape. Cette
dernière méthode nécessite de fonctionner avec des fonctions objectifs non nulles et son
champ d’application est limité.

• Méthode de Jahn
Cette méthode est complètement différente des deux autres méthodes précédentes. On
commence par effectuer un choix de point de départ, puis le problème est résolu pas à pas
à travers l’espace de recherche en direction de la solution optimale au sens de Pareto [92].
Cette méthode est fondée sur une méthode de minimisation cyclique. Elle est caractérisée
par les mêmes inconvénients que la méthode de Fandel, en plus, d’avoir besoin de connaı̂tre
les gradients de certaines expressions liées au problème d’optimisation : gradient du vecteur
fonction objectif et gradient du vecteur contrainte. Par conséquent, si le problème n’admet
CHAPITRE 3. L’OPTIMISATION MULTI-OBJECTIFS 63

pas de dérivées en certains points (comme c’est le cas pour les problèmes combinatoires),
cette méthode ne peut pas être appliquée. Il est à noter que la méthode de Geoffrion est
similaire à la méthode de Jahn. Elle repose sur l’algorithme de Franck-Wolfe [92].

• Méthode Simplex
Cette méthode n’a rien à voir avec la méthode du simplexe utilisée en programmation
linéaire. Il s’agit d’une méthode de recherche séquentielle [205] de l’optimum. Elle utilise
k + 1 essais (où k représente la dimension de la variable de décision x) pour définir une
direction d’amélioration des fonctions objectifs. L’amélioration est obtenue en utilisant
une méthode d’agrégation floue. On commence par choisir au hasard k + 1 valeurs pour la
variable de décision x. L’algorithme évalue alors les k + 1 points et supprime le point le
moins “efficace”. Il crée alors un nouveau point à partir du point supprimé (voir figure 3.9)
et il recommence l’évaluation. L’algorithme comporte quelques règles, qui permettent de

Figure 3.9: Choix d’un nouveau point par symétrie

choisir des points qui évitent de tourner autour d’une mauvaise solution. Les principales
règles peuvent être décrites comme suit.

1. Rejeter les pires solutions. Une nouvelle position de la variable de décision x est
calculée par réflexion de la position rejetée (voir figure 3.9). Après cette transforma-
tion, on recherche le nouveau pire point. La méthode est alors répétée en éliminant
ce point, etc. A chaque étape, on se rapproche de la zone où se trouve l’optimum
recherché.

2. Ne jamais revenir sur un point qui vient juste d’être rejeté. Sans cette règle,
l’algorithme pourrait osciller entre deux ”mauvais” points. Sur la figure 3.10, on peut
voir le cheminement de la méthode dans l’espace des variables de décision, dans le
cas d’un exemple à dimension deux. Sur cette même figure sont représentées des
courbes de niveau illustrant la “direction”d’amélioration de la fonction objectif à
optimiser. Dans cet exemple, l’optimisation se déroule de manière à maximiser le
pourcentage correspondant à la courbe de niveau.
3. Dilater le déplacement dans le sens de l’amélioration des fonctions objectifs.
CHAPITRE 3. L’OPTIMISATION MULTI-OBJECTIFS 64

Figure 3.10: Cheminement de la méthode Simplex.

4. Contracter le déplacement, si celui-ci a été fait dans une direction qui n’est pas
favorable à l’amélioration des fonctions objectifs (voir figure 3.11).

L’algorithme complet de la méthode Simplex est présenté à la figure 3.12 où W désigne le
point le moins favorable ou le point venant d’être rejeté, B correspond au point le plus
favorable alors que N est associé au second point le plus favorable.

Figure 3.11: Algorithme de la méthode Simplex.

CHAPITRE 3. L’OPTIMISATION MULTI-OBJECTIFS 65

Figure 3.12: Algorithme complet de la méthode Simplex.

3.2.3 Méthodes floues

Il est impossible de tout décrire, dans la vie courante, d’une manière binaire. Il suffit de
constater que la transition entre le jour et la nuit se fait progressivement, que la transformation
d’une matière d’un état solide à un état gazeux se réalise graduellement, etc. L’unique outil de
description en logique était binaire pendant longtemps et le tout a été décrit en termes de Vrai
ou Faux. L’handicap de cette description simpliste consiste en l’incapacité de traiter l’incertitude
et l’imprécision des connaissances humaines. Le professeur d’automatique de l’Université de
Californie à Berkeley, Lotfi Zadeh a élaboré une nouvelle logique basée sur les ensembles flous et
offrant l’option de traiter l’imprécision et l’incertitude dans la connaissance humaine ainsi que
les transitions progressives entre états [287, 233, 275].

La logique floue permet de prendre en compte une infinité de degrés de vérité contrairement
à la logique binaire, qui ne permet d’exprimer que deux valeurs de vérité. Parmi les méthodes
floues, on peut se référer à la méthode de Sakawa qui fait intervenir la logique floue à tous
les niveaux (sur les paramètres du problème ainsi que sur les paramètres des contraintes).
L’ensemble de solutions trouvées, lui aussi, fera intervenir la logique floue. De telles solutions
auront un niveau d’appartenance. Elles seront des solutions ayant une corrélation variable avec
l’objectif initial [245, 246]. La méthode de Sakawa est très intéressante, car elle permet de
CHAPITRE 3. L’OPTIMISATION MULTI-OBJECTIFS 66

prendre en compte l’exigence de l’utilisateur vis-à-vis de la réponse fournie par l’algorithme de

recherche. De cette manière, l’utilisateur peut obtenir un plus grand nombre de réponses s’il est
moins exigeant. Cependant, la méthode semble “lourde”à mettre en œuvre. Elle fait appel à des
ensembles flous et à des règles mathématiques difficiles à appliquer. On lui préfèrera l’approche
utilisée dans la méthode de Reardon : une méthode simplifiée de traitement multi-objectifs
utilisant la logique floue. Des exemples utilisant cette méthode peuvent être consultés via les
travaux de Reardon [230, 231, 232].

3.2.4 Méthodes exploitant une métaheuristique

Depuis la manifestation des approches Pareto à la fin des années 90 du siècle dernier, de
nombreuses métaheuristiques ont été adaptées au contexte multi-objectifs. Dans un premier
temps, les algorithmes évolutionnaires furent privilégiés car d’une part ils étaient très populaires
à cette époque, et d’autre part l’utilisation d’une population de solutions semblait être adaptée
pour la recherche d’un ensemble de solutions de compromis, qui peut être alors découvert
en une seule recherche. Peu à peu, d’autres métaheuristiques ont été proposées. La plupart
d’elles étaient issues d’adaptations de métaheuristiques ayant été initialement proposées dans
un cadre mono-objectif. L’adaptation des métaheuristiques classiques au contexte multiobjectif
impose l’obligation d’effectuer des choix permettant souvent d’obtenir des métaheuristiques
multi-objectifs originales. Les métaheuristiques ont reçu un intérêt grandissant et ont montré
leur efficacité dans de vastes domaines d’application en résolvant de nombreux problèmes
d’optimisation [262]. Deux types de métaheuristiques peuvent être distingués :

• Métaheuristiques à base de solution unique (S-META)

Elles manipulent et transforment une seule solution durant le processus de recherche
tels que les algorithmes de recherche par descente (Hill Climbing) très utilisé, faciles à
mettre en place et donnant de bons résultats [220, 221], de recherche tabou [119], de recuit
simulé [41], etc. Historiquement, les métaheuristiques à base de solutions uniques sont
apparues à peu près en même temps que les algorithmes évolutionnaires (voir figure 3.13).
Les S-META sont plutôt axées sur l’exploitation de l’espace de recherche. Les régions
prometteuses sont explorées localement dans l’espoir de trouver de meilleures solutions.

• Métaheuristiques à base de population (P-META)

Elles ne proposent plus une seule mais tout un ensemble de solutions potentielles évoluant
CHAPITRE 3. L’OPTIMISATION MULTI-OBJECTIFS 67

Figure 3.13: Historique d’apparition des différentes méthodes d’optimisation.

en parallèle. Cet ensemble est appelé population. Parmi les P-META, on retrouve les
algorithmes évolutionnaires ainsi que les algorithmes à essaim de particules. Les P-META
sont généralement plutôt exploratoires et permettent une meilleure diversification de
l’espace de recherche.

En termes de conception, deux critères contradictoires sont à prendre en compte lors du

développement d’une métaheuristique : l’exploration de l’espace de recherche (diversification),
et l’exploitation des meilleures solutions trouvées (intensification). Une métaheuristique est une
méthode très générale, qui nécessite quelques transformations (mineures en général) avant de
pouvoir être appliquée à la résolution d’un problème particulier. Si l’on considère les différentes
métaheuristiques, on constate qu’elles se répartissent en trois familles :

• Méthodes déterministes de recherche d’optimum local

Ces méthodes convergent rapidement mais, la plupart du temps, elles ne trouvent pas
l’optimum global. Elles se contentent de trouver un optimum local et ne reposent pas sur
un processus stochastique pour la recherche de l’optimum.

• Méthodes déterministes de recherche d’optimum global

Elles permettent de trouver un optimum global rapidement et ne reposent pas sur un
processus stochastique pour la recherche de l’optimum.

• Méthodes stochastiques de recherche d’optimum global

CHAPITRE 3. L’OPTIMISATION MULTI-OBJECTIFS 68

Elles reposent sur un processus stochastique chargé d’effectuer la recherche de l’optimum.

Elles sont moins performantes (du point de vue rapidité) que les méthodes déterministes,
mais elles peuvent trouver, en principe, un optimum global difficile à atteindre.

Les métaheuristiques peuvent aussi être cernées en trois catégories :

• Méthodes basées sur l’approche du recuit simulé telle que la méthode PASA (Pareto
Archived Simulated Annealing) développée [89] à EDF en France en 1998, et utilisant
une fonction d’agrégation des fonctions objectifs couplée avec un système d’archivage de
solutions non dominées. Pour cet algorithme, la population initiale présente dans l’archive
peut être issue d’une première optimisation multiobjective. La qualité des solutions,
initialement présentes dans l’archive, influencera la qualité du résultat obtenu à la fin de
l’optimisation courante. Un autre avantage de cette méthode est la facilité avec laquelle
on peut inclure des règles heuristiques pour la gestion de l’archive. Cette fléxibilité
peut permettre d’intégrer un “savoir ingénieur”susceptible d’améliorer la qualité de la
population obtenue à la fin de l’optimisation, mais surtout la vitesse de convergence vers
cette population d’individus archivés. Un défaut associé à cette méthode et que l’on peut
souligner est que la forme d’agrégation de la fonction objectif utilisée ne supporte que les
valeurs positives de fonctions objectifs. D’autre part, il est aussi possible de mentionner la
méthode M.O.S.A (Multiple Objective Simulated Annealing) proposée par Ulungu et al.
[270] en 1999 et utilisant le recuit simulé pour rechercher la surface de compromis.

• Méthodes basées sur l’approche de la recherche Tabou dont l’algorithme dit

“Tabou simple”est plus efficace [79] que le recuit simulé pour le problème modèle de
“coloriage d’un graphe”. Cependant, le mode de construction de la liste tabou - qui, pour
une simple raison d’économie de place mémoire, contient des mouvements interdits, et
non des configurations interdites - peut bloquer l’accès à certaines solutions, pourtant
non encore visitées. Pour éviter cet inconvénient, on peut employer une méthode plus
complexe dite “Tabou généralisée”prévoyant la possibilité d’annuler le statut tabou d’un
mouvement, lorsque le bénéfice escompté est “suffisant”. Cette circonstance est appréciée
à l’aide de la notion de “niveau d’aspiration”précisée et détaillée par Glover [118, 119] en
1986.

• Algorithmes génétiques qui sont bien adaptés au traitement d’un problème d’optimisation
multi-objectifs. Le nombre important d’articles ayant été publiés relativement à ce sujet
CHAPITRE 3. L’OPTIMISATION MULTI-OBJECTIFS 69

témoigne de son intérêt. De plus, ce domaine est très dynamique et ne cesse de se

développer. Parmi les méthodes génétiques, on mentionne les méthodes non agrégatives
comme la méthode VEGA (Vector Evaluated Genetic Algorithm) permetant de traiter
un problème d’optimisation multiobjective sans avoir à agréger les fonctions objectifs
en une seule fonction [55, 76]. Le danger associé à cette méthode est d’obtenir, en fin
d’optimisation, une population constituée d’individus moyens relativement à tous les
objectifs. Une telle population ne permet pas d’obtenir une surface de compromis bien
dessinée. En effet, la population va se concentrer autour d’un “point”moyen. Des artifices
ont été trouvés pour contrebalancer cet effet (utilisation d’espèce au sein d’un groupe, etc.).
De plus, il a été montré que cette méthode est équivalente à la méthode de pondération
des fonctions objectifs. Donc, elle ne permet pas d’obtenir des solutions qui se trouveraient
dans une concavité. Fonseca et Fleming [102] ainsi que Deb [76] ont présenté une autre
méthode génétique agrégative à savoir la méthode MOGA (Multiple Objective Genetic
Algorithm) utilisant la relation de dominance pour déterminer l’efficacité d’un individu.
La méthode MOGA ne permet pas, dans certains cas, d’obtenir une diversité dans la
représentation des solutions. Les méthodes NSGA [256] et NPGA [136] permettent d’éviter
cette difficulté. On peut aussi se référer à la méthode WARGA (Weighted Average Ranking
G.A.) et à la méthode SPEA (Strength Pareto Evolutionary Algorithm) [291].

3.2.5 Méthodes d’aide à la décision

Les méthodes présentées jusqu’ici étaient basées sur la relation de dominance. Cette relation peut
être définie de plusieurs manières : la dominance de Pareto, la dominance lexicographique, etc.
Elle permet de filtrer les éléments d’un ensemble, et de ne retenir que les éléments incomparables
entre eux. Cependant, il existe une autre approche pour obtenir un ensemble de solutions, qui
repose sur l’établissement d’une relation d’ordre entre les différents éléments. Ainsi, on peut, en
fonction de la relation d’ordre définie, obtenir un ensemble de solutions pour une relation d’ordre
partiel ou une et une seule solution lorsque l’ordre est complet. L’autre différence majeure, par
rapport aux méthodes d’optimisation multiobjective classiques, vient du fait que les méthodes
d’aide à la décision ne travaillent que sur des ensembles discrets versus des ensembles continus
adoptés par les méthodes d’optimisation multiobjective classiques. De plus, les méthodes d’aide
à la décision permettent de répondre à plusieurs problématiques, réunies dans le tableau suivant :
CHAPITRE 3. L’OPTIMISATION MULTI-OBJECTIFS 70

Problématique Résultat Procédure

Choix d’un sous-ensemble des actions les “meilleures”ou, Choix Sélection
à défaut, les plus “satisfaisantes”.
Tri par affectation des actions à des catégories prédéfinies. Tri Affectation
Rangement de classes d’équivalence composées d’actions, Rangement Classement
ces classes étant ordonnées de façon complète ou partielle.

L’aide à la décision propose une prise en compte des propriétés d’intransitivité des relations
d’ordre, et elle propose aussi des familles de méthodes destinées à résoudre des problématiques
différentes (Sélection, Tri, Rangement) de celles traitées par l’optimisation multiobjective clas-
sique. Lorsque l’on est confronté au domaine de l’aide à la décision, on remarque un certain
nombre de termes redondants : action, classement, ordre complet ou partiel. Une action désigne
un objet, une décision, un candidat, etc. C’est sur cette entité que va s’opérer la sélection (ou le
tri, ou le classement). Une méthode d’aide à la décision va donc permettre de choisir la meilleure
action, ou de classer des actions en fonction d’un ou plusieurs critères. En fonction du type de
classement que l’on désirera effectuer, on pourra utiliser différents types de règles de classement
ou de choix. Ces règles vont définir un ordre complet (si toutes les actions sont classées) ou
partiel (après le classement, il subsiste des actions incomparables, donc non classées). Parmi les
différentes méthodes d’aide à la décision, on retrouve les méthodes Electre (I, IS, II, III, IV et
TRI) puis les deux méthodes proches des méthodes Electre à savoir les méthodes Promethee (I
et II). Chacune de ces méthodes traite une problèmatique bien précise. Les éléments importants
qui différencient ces méthodes sont la définition de la relation de classement des actions (chaque
méthode exploite une relation de préférence différente) et la méthode d’exploitation des résultats.

3.3 Classification des méthodes de résolution

La résolution de problèmes multi-objectifs relève de deux disciplines assez distinctes. En effet,

le processus permettant de résoudre un tel problème peut être divisé en deux phases :

• la recherche des solutions de meilleur compromis et cela correspond à la phase

d’optimisation multiobjective.

• le choix de la solution à retenir et cela correspond à la tâche du décideur qui, parmi

l’ensemble des solutions de compromis, doit extraire celle(s) qu’il utilisera. Il s’agit alors
CHAPITRE 3. L’OPTIMISATION MULTI-OBJECTIFS 71

de décision multiobjective et cela fait appel à la théorie de la décision.

Il est essentiel de noter l’existence de cinq classifications différentes d’approches de résolution

pour les problèmes multi-objectifs. Le premier classement adopte un point de vue décideur
et les approches y associées sont classées en fonction de l’usage que l’on désire en faire. Le
deuxième classement adopte un point de vue concepteur et les approches correspondantes
sont triées selon leur façon de traiter les fonctions objectifs. Le troisième classement est lié
à la catégorie des algorithmes de résolution utilisés. Le quatrième classement est relatif à la
transformation mathématique du problème d’optimisation multi-objectifs initial. Finalement, la
cinquième classification des méthodes de résolution est plutôt une classification hiérarchique.
Ainsi et avant de se lancer dans la résolution d’un problème multi-objectifs, il est approprié de
se poser la question du type d’approche de résolution à utiliser.

3.3.1 Classification du point de vue décideur

On distingue, à cet égard, trois schémas possibles. Soit le décideur intervient dès le début de
la définition du problème, en exprimant ses préférences et ses exigences. Soit le décideur est
amené à contribuer, d’une manière active et progressive, lors du processus de la recherche de la
solution désirée. Soit le décideur effectue son choix dans l’ensemble des solutions proposées par
le solveur multi-objectifs. Cette classification peut s’énoncer comme suit.

• Les approches à priori : le décideur intervient en aval du processus d’optimisation, pour

définir la fonction d’agrégation modélisant le compromis désiré entre les différents objectifs.
Dans ce cas, le décideur est supposé disposer à priori des informations pertinentes portant
sur les différentes composantes de son problème afin d’effectuer sa priorisation. Cependant,
dans la plupart des cas, le décideur ne peut pas exprimer clairement sa fonction d’utilité
étant donné que les différents objectifs sont non commensurables.

• Les approches interactives : elles combinent, de manière cyclique et incrémentale, les

processus de décision et d’optimisation. Le décideur intervient de manière à modifier
certaines variables ou contraintes afin de diriger le processus d’optimisation. Le décideur
modifie ainsi interactivement le compromis entre ses préférences et les résultats. Cette
approche permet donc de bien prendre en compte les préférences du décideur, mais elle
nécessite sa présence tout au long du processus de recherche.
CHAPITRE 3. L’OPTIMISATION MULTI-OBJECTIFS 72

• Les approches à posteriori : il s’agit de chercher à fournir au décideur un ensemble

de bonnes solutions bien réparties. Le décideur peut ensuite, au regard de l’ensemble des
solutions, choisir ce qui lui semble le plus approprié. Ainsi, il n’est plus nécessaire de
modéliser les préférences du décideur (ce qui peut s’avérer être très difficile), mais il faut
en contrepartie fournir un ensemble de solutions bien réparties, ce qui peut également être
difficile et requérir un temps de calcul important.

3.3.2 Classification du point de vue concepteur

Il concerne un classement adoptant un point de vue plus théorique articulé autour des notions
d’agrégation et d’optimum Pareto. Dans cette classification, les approches utilisées pour la
résolution de problèmes multi-objectifs peuvent être classées en deux catégories [9] à savoir les
approches non Pareto et les approches Pareto.

Approches non Pareto

Les approches non Pareto ne traitent pas le problème comme un véritable problème multi-
objectifs. Elles cherchent à ramener le problème initial à un ou plusieurs problèmes mono-objectif.
Les approches non Pareto sont réparties en deux sous-catégories :

• Les approches scalaires qui transforment le problème multi-objectifs en problème

mono-objectif si le décideur est capable de quantifier, à l’avance, l’importance relative
des objectifs. Cela induit l’obtention d’une solution optimale unique et donc l’absence de
compromis à proposer au décideur. Lorsque l’on ne dispose pas de telles informations de
la part du décideur, on peut résoudre alors un ensemble de problèmes mono-objectif, en
faisant varier l’importance relative des objectifs.

• Les approches non scalaires qui maintiennent l’aspect multiobjectif, mais en traitant
séparément chacun des objectifs d’une manière individuelle [88]. A titre d’exemple,
l’algorithme VEGA (Vector Evaluated Genetic Algorithm) [250] utilise un principe de
sélection parallèle où une population de solutions est divisée en sous-populations, chacune
étant formée des meilleurs individus pour un objectif donné (une sous-population par
objectif à optimiser). Ces sous-populations sont combinées pour créer une nouvelle
population qui sera divisée en plusieurs, et ainsi de suite. Une autre approche non scalaire,
CHAPITRE 3. L’OPTIMISATION MULTI-OBJECTIFS 73

couramment utilisée, est la méthode lexicographique [104], où les objectifs sont classés à
priori par ordre d’importance par le décideur. Ensuite, les fonctions objectifs sont traitées
dans cet ordre durant le processus d’optimisation : toute amélioration d’un objectif donné
sera préférée à l’ensemble des améliorations possibles des objectifs moins bien classés par
le décideur.

Approches Pareto

Elles ne transforment pas les objectifs du problème et elles les traitent sans aucune distinction
pendant la résolution. Golberg [121] a peut-être été le premier à utiliser les approches Pareto
qui ont connu un essor remarquable à la fin des années 90. Et pendant quelques années, de
nombreux algorithmes proposés dans la littérature furent des approches Pareto appliquées sur
des algorithmes évolutionnaires. Ces approches consistent à utiliser la notion de dominance
Pareto pour comparer les solutions et leur affecter un fitness. Cette notion ne fournissant
qu’une relation d’ordre très partielle, diverses méthodes de calcul ont été proposées, utilisant
essentiellement la dominance relative des solutions d’un ensemble pour calculer leur fitness.
Globalement, le score affecté à une solution est défini en fonction des solutions qu’elle domine et
des solutions qui la dominent. Il existe beaucoup de méthodes employant une approche Pareto
[56], et les plus populaires étant certainement NSGA-II [77] et SPEA2 [292]. Le calcul des
fitness tel qu’il est réalisé par ces deux approches se résume brièvement comme suit.

• NSGA-II : le meilleur score (rang 1) est attribué aux solutions non dominées de la
population. Puis le second meilleur score (rang 2) est attribué aux solutions qui ne sont
dominées que par les solutions de rang 1, et ainsi de suite.

• SPEA2 : pour chaque solution x de la population, on calcule dans un premier temps son
poids, correspondant au nombre de solutions de la population qu’elle domine. Ensuite, le
score d’une solution est défini en additionnant les poids des solutions qui la dominent (un
score de 0 affecté à une solution indique alors qu’elle est non dominée).

3.3.3 Classification selon la classe des algorithmes de résolution utilisés

Tout comme l’optimisation mono-objectif, on distingue deux classes de résolution pour les
problèmes multi-objectifs selon la taille et la complexité du problème traité : les méthodes exactes
CHAPITRE 3. L’OPTIMISATION MULTI-OBJECTIFS 74

dédiées à résoudre les problèmes de petite taille et les méthodes approchées (les heuristiques et
particulièrement les métaheuristiques) permettant d’approximer les meilleures solutions pour les
problèmes de grande taille. Le choix de la méthode de résolution à mettre en œuvre dépendra
souvent de la complexité du problème. En effet, suivant sa complexité, le problème pourra ou
non être résolu de façon optimale. Dans le cas de problèmes NP-difficiles, deux possibilités
sont offertes. Si le problème est de petite taille, alors un algorithme exact permettant de
trouver la solution optimale peut être utilisé (Branch and Bound, programmation dynamique...).
Malheureusement, ces algorithmes, énumératifs par nature, souffrent de l’explosion combinatoire
et ne peuvent s’appliquer à des problèmes de grande taille (même si, en pratique, la taille n’est
pas le seul critère limitatif). Dans ce cas, il est nécessaire de faire appel à des heuristiques
permettant de trouver de bonnes solutions approximatives. Parmi ces heuristiques, on trouve
les métaheuristiques fournissant des schémas de résolution généraux permettant de les appliquer
potentiellement à tous les problèmes. L’objectif est de concevoir des algorithmes de plus en plus
performants en temps de calculs (raisonnable), en qualité de solutions produites (bonne qualité)
et permettant de traiter des problèmes de plus grande taille.

Méthodes exactes

Les méthodes exactes tels que le Branch and Bound, l’algorithme A∗ et la programmation
dynamique ont subi des révisions afin de les adapter au cas multi-objectifs. Cependant, ces
approches sont destinées à des problèmes de petite taille. Elles permettent, théoriquement, de
trouver une solution optimale grâce à un parcours exhaustif. Leur efficacité est mise en question
dès que la taille du problème augmente et que le nombre de critères retenus croı̂t. Elles ne sont
pas adaptées à des problèmes NP-difficiles.

• Algorithme A∗ : Stewart et White [259] proposèrent une version multiobjective de

l’algorithme A∗ (A∗ M O) en 1991. L’algorithme A* est maintenu dans sa forme originale.
Le poids d’un arc (u, v) dans le graphe de recherche, correspond à un n-uplet (c1 , c2 , . . . , cn )
où ci désigne le coût relatif à l’objectif fi induit par le passage de u à v. Le coût d’un
chemin correspond à la somme vectorielle des poids des arcs qui le composent. Les
fonctions k ∗ , g ∗ et h∗ prennent une forme non scalaire où k ∗ (u, v) désigne l’ensemble des
coûts non dominés des chemins reliant u à v et g ∗ (u) représente le coût de la recherche
ayant abouti à la solution intermédiaire u alors que h∗ (u) correspond à l’ensemble des
vecteurs coûts non dominés parmi l’ensemble k ∗ (u, v) \ v ∈ T où T représente l’ensemble
CHAPITRE 3. L’OPTIMISATION MULTI-OBJECTIFS 75

des états terminaux. Les nœuds du graphe sont triés et parcourus d’une manière similaire
au processus adopté par l’algorithme A∗ classique. L’ordre de tri est décrit par les relations
de dominance entre les vecteurs coûts f [259].

• Programmation dynamique : la technique de programmation dynamique multiobjec-

tive a été implémentée par Carraway et al. [35] pour la résolution du problème de routage
dans les réseaux. L’application de la programmation dynamique pour l’optimisation
multiobjective est rare car cela est difficile quand le nombre d’objectifs à optimiser est
élevé (> 2). La difficulté est liée au principe de monotoniété exigée par la méthode.
Ce principe réclame un grand volume d’espace de stockage qu’il faudra utiliser pour
sauvegarder l’ensemble des résultats des étapes antérieures, en plus d’un temps de calcul
très élevé.

• Branch and Bound : cela consiste à faire une énumération implicite en séparant le
problème en sous-problèmes qui doivent être évalués à l’aide d’une relaxation (continue ou
lagrangienne principalement) jusqu’à ne plus avoir que des problèmes faciles à résoudre ou
des problèmes ne pouvant pas, avec une certaine certitude, contenir de solution optimale.

Méthodes approchées

Ces méthodes sont, souvent, inspirées de mécanismes d’optimisation rencontrés dans la nature.
Elles sont utilisées pour les problèmes où l’on ne dispose pas d’algorithmes de résolution en
temps polynomial et pour lesquels on espère trouver une solution approchée de l’optimum
global. Elles cherchent à produire une solution de meilleure qualité possible dictée par des
heuristiques avec un temps de calcul raisonnable en examinant seulement une partie de l’espace
de recherche. Dans ce cas, l’optimalité de la solution n’est pas garantie ni l’écart avec la valeur
optimale. Parmi les heuristiques, on retrouve les métaheuristiques qui fournissent des schémas
de résolution généraux permettant de les appliquer potentiellement à tous les problèmes.

Méthodes hybrides

Une façon d’améliorer les performances d’un algorithme ou de combler certaines de ses lacunes
consiste à le combiner avec une autre méthode [261]. L’intérêt d’une telle approche coopérative
est de permettre à différentes méthodes d’optimisation de combiner leurs avantages dans le
but d’améliorer les performances globales afin d’obtenir de bon résultats. Actuellement, les
CHAPITRE 3. L’OPTIMISATION MULTI-OBJECTIFS 76

meilleurs résultats obtenus sont issus de ce type d’approches, en particulier sur les problèmes
provenant du monde réel [12]. Les coopérations étaient à l’origine essentiellement réalisées entre
différentes métaheuristiques. Récemment, on note la mise en œuvre de l’approche hybride : une
démarche assez originale visant à combiner les résolutions exactes et les métaheuristiques et
permettant de conserver au mieux les avantages de chacune des deux approches dans le but de
fournir des résultats supérieurs aux méthodes qui les composent.

• Coopération méta/méta : Les coopérations étaient à l’origine essentiellement réalisées

entre différentes métaheuristiques. A peu près tous les types d’approches ont été proposés
pour ce genre de coopération, et ainsi les métaheuristiques hybrides sont devenues assez
classiques dans le domaine de l’optimisation [12].

• Coopération méta/exacte : Les méthodes exactes permettent de résoudre des problèmes

de petite taille tandis que les métaheuristiques sont capables d’appréhender les problèmes de
grande taille sans pouvoir donner la solution optimale ni de prouver que la solution fournie
est optimale. Cependant, les méthodes exactes peuvent néanmoins être utiles lorsque
des sous-problèmes peuvent être extraits du problème global. Leur résolution permet, en
effet, de contribuer à la recherche de la solution globale, soit en combinant judicieuse-
ment différents sous-problèmes, soit en hybridant la résolution exacte de sous-problèmes
et la résolution heuristique du problème complet [80]. Cette constatation constitue le
point de départ d’une approche hybride, assez originale dans le contexte des problèmes
d’optimisation combinatoire visant à combiner résolutions exactes et métaheuristiques
permettant de conserver aux mieux les avantages de chacune des approches.
CHAPITRE 3. L’OPTIMISATION MULTI-OBJECTIFS 77

Figure 3.14: Classification des méthodes d’optimisation multiobjective

CHAPITRE 3. L’OPTIMISATION MULTI-OBJECTIFS 78

3.3.4 Classification mathématique

Cette classification ne considère que la manière de transformer un problème d’optimisation

multiobjectif en un autre problème d’optimisation multiobjective [86]. Elle ne s’occupe pas de
décrire les méthodes d’optimisation en elles-mêmes.

Formule de classification de Erghott

Les éléments nécessaires à la bonne spécification d’un problème d’optimisation multi-objectifs

sont les suivants :

• l’espace des variables de décision X ;

• l’espace des fonctions objectif Rn ;

• un espace ordonné Rp avec la relation de dominance au sens de Pareto comme relation

d’ordre noté ;

• un modèle de transformation (θ).

En 2000, Erghott [86] propose de référencer une méthode d’optimisation en utilisant l’expression

(X, f, Rn )/θ/(Rp , )

Cette expression reflète bien le processus de transformation d’un problème d’optimisation

multi-objectifs en un problème d’optimisation multi-objectifs qui soit adapté à la résolution par
une méthode de recherche d’optimum. Cette classification présente le grand avantage d’être
applicable aussi bien à des problèmes d’optimisation qu’à des méthodes d’optimisation. Tous
les problèmes d’optimisation ne se formulent pas sous la forme d’un problème de minimisation.
Par exemple, pour le problème suivant, on a deux maximisations et une minimisation, ce qui
induit la transformation engendrée :
 


 min f1 

 min f1

 


 max f  min −f

2 2
=⇒


 max f3 

 min −f3

 

 où x ∈ X ⊂ Rn
  où x ∈ X ⊂ Rn

CHAPITRE 3. L’OPTIMISATION MULTI-OBJECTIFS 79

3.3.5 Classification hiérarchique

Cette classification peut présenter certains inconvénients telle qu’une explosion du nombre de
niveaux hiérarchiques due au nombre important des éléments distinctifs décrivant une méthode
d’optimisation. Pour limiter cet inconvénient, on peut faire recours à un choix judicieux des
éléments descriptifs d’une méthode d’optimisation et limiter le domaine d’intervention de la
classification.

Figure 3.15: Hiérarchie des méthodes à priori.

A la lumière des diférentes descriptions et classifications citées auparavant, on peut distinguer

trois degrés associés à la classification hiérarchique de l’optimisation multiobjective. Le premier
degré concerne le choix de la méthode de résolution vis-à-vis l’implication du décideur (à priori,
à posteriori, progressivement). La branche des méthodes progressives est bien dissociée des deux
autres méthodes à cause, en particulier, de la phase d’interaction qui différencie les méthodes
progressives des méthodes à priori et à posteriori. Alors que les branches des méthodes à priori
et à posteriori ne sont pas indépendantes dans le sens où une méthode à priori peut très bien
être utilisée comme une méthode à posteriori en relançant la méthode d’optimisation à priori sur
plusieurs préférences du décideur. En revanche, la réciproque n’est pas nécessairement vraie : il
n’est pas intéressant d’utiliser une méthode à posteriori comme une méthode à priori (engendrer
une approximation de la surface de compromis et ne conserver que la solution qui représente le
compromis le plus proche de celui formulé par le décideur).
Le deuxième degré, relié à cette hiérarchie, correspond à la manière du traitement des fonctions
objectifs (approche aggrégative ou approche non agrégative). Le troisième degré concerne
CHAPITRE 3. L’OPTIMISATION MULTI-OBJECTIFS 80

“l’imbrication”de la méthode de traitement multi-objectifs dans la méthode d’optimisation. On

peut utiliser des méthodes de traitement multi-objectifs complètement découplées de la méthode
d’optimisation telle que la méthode de pondération des fonctions objectifs. On peut aussi utiliser
des méthodes de traitement multi-objectifs qui ne laissent pas le choix quant à la méthode
d’optimisation à utiliser telle que la méthode MOGA. On obtient alors l’hiérarchie indiquée à la
figure 3.15 pour une résolution à priori. Cette même figure peut facilement être adaptée pour la
résolution à posteriori.

Pour les méthodes progressives, le mode d’interaction est un élément discriminant. Lorsque
l’on analyse les modes de fonctionnement des méthodes interactives, on peut les classer en
quatre catégories :

• les interactions via la formulation des préférences (niveau I1) ;

• les interactions via la formulation des contraintes (niveau I2) ;

• les interactions hybrides via la formulation de préférences et de contraintes (niveau I3) ;

• les interactions d’un autre type telle que la sélection d’une sous-population de solutions
intéressantes (niveau I4).

On obtient alors l’hiérarchie illustrée à la figure 3.16 pour une résolution progressive.

Figure 3.16: Hiérarchie des modes d’interaction

Exploitation de la classification hiérarchique

Lorsque l’on désire effectuer le choix d’une méthode d’optimisation multiobjective, il est utile
de considérer plusieurs facteurs :
CHAPITRE 3. L’OPTIMISATION MULTI-OBJECTIFS 81

• Les exigences quant à la qualité de la solution

Certains problèmes présentent une grande difficulté pour la détermination d’un optimum
et ils seront très probablement mieux résolus via l’utilisation d’une métaheuristique du
type recuit simulé.

• La structure particulière de l’espace de recherche

La présence d’optima locaux implique une certaine influence sur le choix de la méthode
d’optimisation. Il est clair que pour certains problèmes très difficiles, il n’est pas possible
de disposer à l’avance de la proportion d’optima locaux et ainsi de juger de la difficulté
à priori du problème. La présence ou l’absence de l’aspect convexe de la surface de
compromis a un impact sur le choix de la méthode de traitement multi-objectifs. Dans ce
cas aussi, il n’est pas évident de juger de l’allure de la surface de compromis à priori, et
donc de choisir une méthode de traitement multi-objectifs adaptée au problème. En cas
de convexité du problème, il est possible de se servir d’une méthode de pondération des
fonctions objectifs, alors qu’en absence de convexité, on choisira plutôt une méthode dite
de Tchebychev.

• La capacité à exprimer précisément ses préférences

Lorsque les préférences sont bien fixées, on sélectionne une méthode de résolution de type
à priori. En effet, il faut bien avoir à l’esprit que chercher à approcher une surface de
compromis est une tâche qui peut être longue et difficile. Dans le cas contraire où les
préférences ne sont pas bien identifiées, on peut faire recours à l’une des deux options
suivantes :

• Aider le décideur à préciser ses préférences par l’intermédiaire d’une résolution

progressive du problème. Cette méthode de résolution n’a pas les faveurs des
utilisateurs, car elle mobilise le décideur tout au long de la recherche. De plus, la
durée qui sépare deux étapes d’interaction peut être longue.

• Approcher la surface de compromis en engendrant un nombre fini de solutions bien

réparties sur celle-ci : c’est l’approche à posteriori. Cette approche de la résolution
d’un problème multi-objectifs est commode, surtout quand le circuit de décision est
long et/ou mal identifié. Elle fournit ainsi l’occasion au décideur de juger les solutions
proposées, par comparaisons successives, ou d’extraire une solution en utilisant une
méthode d’aide à la décision.
CHAPITRE 3. L’OPTIMISATION MULTI-OBJECTIFS 82

Il est clair que si le décideur dispose déjà de ces réponses, la sélection d’une méthode n’en
sera que plus aisée. Cette hiérarchie peut être considérée plus comme un outil d’aide au
questionnement qu’un outil d’aide à la sélection.

Stratégie du choix d’une méthode

En exploitant cette classification, le choix d’une méthode de résolution peut se faire via les
réponses aux questions qui suivent.

• Quel mode de résolution choisir ? Il s’agit du 1er niveau de l’hiérarchie ;

• Quel mode de traitement du problème multiobjectif sélectionner ? Cela correspond au

2ème niveau de l’hiérarchie ;

• Quel type de couplage utiliser ? Cela est associé au 3ème niveau de l’hiérarchie ;

• Quel type de méthode considérer ? Il s’agit du 4ème niveau de l’hiérarchie ;

• Quel type d’élitisme choisir ? Cela correspond au 5ème niveau de l’hiérarchie.

CHAPITRE 3. L’OPTIMISATION MULTI-OBJECTIFS 83

Figure 3.17: Itinéraire hiérarchique des méthodes d’optimisation multiobjective

Vous aimerez peut-être aussi

Introduction à l'optimisation mathématique
Pas encore d'évaluation
Introduction à l'optimisation mathématique
11 pages
Méthodes d'Optimisation des Algorithmes
Pas encore d'évaluation
Méthodes d'Optimisation des Algorithmes
17 pages
Introduction à l'optimisation mathématique
Pas encore d'évaluation
Introduction à l'optimisation mathématique
3 pages
Cours Op Tim Multi
Pas encore d'évaluation
Cours Op Tim Multi
59 pages
Méthodes d'optimisation en ingénierie
Pas encore d'évaluation
Méthodes d'optimisation en ingénierie
27 pages
Optimisation Numérique : Concepts et Méthodes
Pas encore d'évaluation
Optimisation Numérique : Concepts et Méthodes
23 pages
Chapitre II 1
Pas encore d'évaluation
Chapitre II 1
8 pages
Optimisation et Matrices Semi-Définies
Pas encore d'évaluation
Optimisation et Matrices Semi-Définies
32 pages
Introduction à l'optimisation mathématique
Pas encore d'évaluation
Introduction à l'optimisation mathématique
1 page
Introduction à l'Optimisation Numérique
100% (1)
Introduction à l'Optimisation Numérique
43 pages
Optimisation Différentiable Convexe : Concepts et Méthodes
Pas encore d'évaluation
Optimisation Différentiable Convexe : Concepts et Méthodes
42 pages
Cours d'Optimisation en Génie Mécanique
Pas encore d'évaluation
Cours d'Optimisation en Génie Mécanique
108 pages
Méthodes d'Optimisation Énergétique
Pas encore d'évaluation
Méthodes d'Optimisation Énergétique
11 pages
Introduction à l'optimisation numérique
Pas encore d'évaluation
Introduction à l'optimisation numérique
16 pages
Techniques d'Optimisation Avancées
Pas encore d'évaluation
Techniques d'Optimisation Avancées
63 pages
Optimisation Combinatoire Methodes Approchees
Pas encore d'évaluation
Optimisation Combinatoire Methodes Approchees
135 pages
Introduction à l'optimisation mathématique
Pas encore d'évaluation
Introduction à l'optimisation mathématique
41 pages
Recherche Opérationnelle et Décision
Pas encore d'évaluation
Recherche Opérationnelle et Décision
25 pages
Introduction à l'Optimisation Mathématique
Pas encore d'évaluation
Introduction à l'Optimisation Mathématique
42 pages
Optimisation : Conditions et Exemples
Pas encore d'évaluation
Optimisation : Conditions et Exemples
11 pages
Techniques d'Optimisation Discrète et Continue
Pas encore d'évaluation
Techniques d'Optimisation Discrète et Continue
160 pages
Cours de Recherche Opérationnelle
Pas encore d'évaluation
Cours de Recherche Opérationnelle
90 pages
Introduction à l'optimisation pour ingénieurs
100% (1)
Introduction à l'optimisation pour ingénieurs
27 pages
Techniques d'Optimisation Mathématique
Pas encore d'évaluation
Techniques d'Optimisation Mathématique
8 pages
Optimisation : Minimiseurs et Minimums
Pas encore d'évaluation
Optimisation : Minimiseurs et Minimums
21 pages
Introduction à l'optimisation mathématique
Pas encore d'évaluation
Introduction à l'optimisation mathématique
22 pages
Fonction Objectif en Optimisation
Pas encore d'évaluation
Fonction Objectif en Optimisation
4 pages
Optimisation : Paraboles et Méthodes
Pas encore d'évaluation
Optimisation : Paraboles et Méthodes
46 pages
Optimisation Combinatoire Methodes Approchees (+)
Pas encore d'évaluation
Optimisation Combinatoire Methodes Approchees (+)
158 pages
Optimisation et Simulation en Ingénierie
Pas encore d'évaluation
Optimisation et Simulation en Ingénierie
62 pages
Optimisation et Simulation en Ingénierie
Pas encore d'évaluation
Optimisation et Simulation en Ingénierie
133 pages
Optimisation sous contraintes en mathématiques
Pas encore d'évaluation
Optimisation sous contraintes en mathématiques
91 pages
2025 - 2026 - ConvexiteOptimisation - Chapitre2 - 1 PLAN1 - ENEAM
Pas encore d'évaluation
2025 - 2026 - ConvexiteOptimisation - Chapitre2 - 1 PLAN1 - ENEAM
34 pages
Introduction à l'optimisation mathématique
Pas encore d'évaluation
Introduction à l'optimisation mathématique
39 pages
Optimisation Non Linéaire Sans Contraintes
Pas encore d'évaluation
Optimisation Non Linéaire Sans Contraintes
14 pages
Optimisation Avancée en Recherche Opérationnelle
100% (1)
Optimisation Avancée en Recherche Opérationnelle
85 pages
Pages 17 Sur 27 Depuis Optimisation Des Structures Mécaniques. (Bruyneel, Michael Craveur Etc.) (Z-Library)
Pas encore d'évaluation
Pages 17 Sur 27 Depuis Optimisation Des Structures Mécaniques. (Bruyneel, Michael Craveur Etc.) (Z-Library)
11 pages
Recherche Opérationnelle & Optimisation: Pr. Khalid RAHHALI
Pas encore d'évaluation
Recherche Opérationnelle & Optimisation: Pr. Khalid RAHHALI
29 pages
Algorithme d'Uzawa en optimisation
100% (1)
Algorithme d'Uzawa en optimisation
39 pages
Cours d'Optimisation Mathématique
Pas encore d'évaluation
Cours d'Optimisation Mathématique
54 pages
Optimisation Continue Sans Contraintes
Pas encore d'évaluation
Optimisation Continue Sans Contraintes
25 pages
Optimisation Numérique et Algorithmes
Pas encore d'évaluation
Optimisation Numérique et Algorithmes
44 pages
Optimisation Discrète et Méthodes
Pas encore d'évaluation
Optimisation Discrète et Méthodes
1 661 pages
Techniques d'Optimisation Continue
Pas encore d'évaluation
Techniques d'Optimisation Continue
1 535 pages
Introduction à l'Optimisation Mathématique
Pas encore d'évaluation
Introduction à l'Optimisation Mathématique
9 pages
Méthodes d'optimisation en gestion
Pas encore d'évaluation
Méthodes d'optimisation en gestion
11 pages
Programmation Mathématique et Optimisation
100% (1)
Programmation Mathématique et Optimisation
45 pages
Techniques d'optimisation mathématique
Pas encore d'évaluation
Techniques d'optimisation mathématique
16 pages
Introduction à la recherche opérationnelle
Pas encore d'évaluation
Introduction à la recherche opérationnelle
59 pages
Introduction à l'optimisation mathématique
Pas encore d'évaluation
Introduction à l'optimisation mathématique
47 pages
Optimisation Linéaire et Problème Dual
Pas encore d'évaluation
Optimisation Linéaire et Problème Dual
30 pages
Introduction à la Recherche Opérationnelle
100% (1)
Introduction à la Recherche Opérationnelle
175 pages
Méthodes de Résolution en Génie Informatique
Pas encore d'évaluation
Méthodes de Résolution en Génie Informatique
58 pages
Optimisation par Métaheuristiques en IA
Pas encore d'évaluation
Optimisation par Métaheuristiques en IA
19 pages
Cours d'Optimisation Non Linéaire
Pas encore d'évaluation
Cours d'Optimisation Non Linéaire
13 pages
Cours sur l'optimisation non linéaire
Pas encore d'évaluation
Cours sur l'optimisation non linéaire
53 pages
Optimisation Numérique et Contraintes
Pas encore d'évaluation
Optimisation Numérique et Contraintes
32 pages
Optimisation Mathématique en IA et Data Science
Pas encore d'évaluation
Optimisation Mathématique en IA et Data Science
48 pages
Introduction à l'optimisation mathématique
100% (1)
Introduction à l'optimisation mathématique
100 pages
Modèle d'ordre de service EXE1-T
Pas encore d'évaluation
Modèle d'ordre de service EXE1-T
2 pages
Évaluation sur volcans et séismes CM2
100% (1)
Évaluation sur volcans et séismes CM2
4 pages
Impact du PRB sur le débit LTE
Pas encore d'évaluation
Impact du PRB sur le débit LTE
2 pages
Véhicules Électriques : L'Avenir du Transport
Pas encore d'évaluation
Véhicules Électriques : L'Avenir du Transport
1 page
Annuaire Statistique de Dosso 2024
Pas encore d'évaluation
Annuaire Statistique de Dosso 2024
165 pages
Génération de Bond Graphs Électriques
Pas encore d'évaluation
Génération de Bond Graphs Électriques
26 pages
Protocole d'évaluation des systèmes de communication
Pas encore d'évaluation
Protocole d'évaluation des systèmes de communication
8 pages
Asservissement et régulation MCC 2021
Pas encore d'évaluation
Asservissement et régulation MCC 2021
6 pages
Générateur de chlore SANICLEAR : Guide d'installation
Pas encore d'évaluation
Générateur de chlore SANICLEAR : Guide d'installation
20 pages
Évaluation sur l'affectation en algorithmique
Pas encore d'évaluation
Évaluation sur l'affectation en algorithmique
2 pages
Types et prévention des défauts de soudage
Pas encore d'évaluation
Types et prévention des défauts de soudage
16 pages
Avantages et limites du coût standard
Pas encore d'évaluation
Avantages et limites du coût standard
3 pages
Enquête sur la Commune d'Alakamisy
Pas encore d'évaluation
Enquête sur la Commune d'Alakamisy
2 pages
Cours de géothermie et hydrothermalisme
Pas encore d'évaluation
Cours de géothermie et hydrothermalisme
34 pages
Examen de Thermodynamique et Cinétique
50% (6)
Examen de Thermodynamique et Cinétique
2 pages
Superficie et relief des États-Unis
Pas encore d'évaluation
Superficie et relief des États-Unis
8 pages
MATH 4 SC Et HP NO 4
Pas encore d'évaluation
MATH 4 SC Et HP NO 4
2 pages
Guide d'entretien pour projets en génie électrique
100% (1)
Guide d'entretien pour projets en génie électrique
3 pages
Installation et Configuration de Pfsense
Pas encore d'évaluation
Installation et Configuration de Pfsense
11 pages
Conditions pour Open-APIs M-Pesa
Pas encore d'évaluation
Conditions pour Open-APIs M-Pesa
5 pages
Cours d'Économétrie des Séries Temporelles
Pas encore d'évaluation
Cours d'Économétrie des Séries Temporelles
49 pages
Système Photovoltaïque pour l'UniPod
Pas encore d'évaluation
Système Photovoltaïque pour l'UniPod
53 pages
Optimisation de la Réassurance Proportionnelle
Pas encore d'évaluation
Optimisation de la Réassurance Proportionnelle
123 pages
Finlet G Vivre Et Lacher Prise PDF
100% (2)
Finlet G Vivre Et Lacher Prise PDF
143 pages
Maîtrise des Risques en Santé
Pas encore d'évaluation
Maîtrise des Risques en Santé
2 pages
Comprendre le récit historique
Pas encore d'évaluation
Comprendre le récit historique
33 pages
Examen Excel Université de Panama
Pas encore d'évaluation
Examen Excel Université de Panama
4 pages
Essais d'identification des sols
Pas encore d'évaluation
Essais d'identification des sols
19 pages
Participation politique en démocratie
100% (1)
Participation politique en démocratie
23 pages
Compétences en Statistiques et Graphisme
Pas encore d'évaluation
Compétences en Statistiques et Graphisme
74 pages

Problèmes d'optimisation : Concepts clés

Transféré par

Problèmes d'optimisation : Concepts clés

Transféré par

Chapitre 2

• problèmes statiques ou dynamiques,

• problèmes combinatoires ou à variables continues,

• problèmes dans l’incertain,

• problèmes à un ou plusieurs objectifs.

2.1.1 Notion de l’optimisation

f ∗ = inf f (x) avec x ∈ E

∀x ∈ E f (x) > f ∗ et ∀ > 0 ∃x ∈ E tel que f (x ) < f ∗ + 

f (x∗ ) = f ∗ = min f (x) avec x ∈ E

Un problème d’optimisation se définit comme la recherche du minimum ou du maximum

• consommer le minimum d’énergie (coût de fonctionnement),

• répondre à la demande de l’utilisateur (cahier des charges).

Un problème d’optimisation est défini par les éléments suivants :

• un espace de recherche (de décision) c-à-d un ensemble de solutions ou de configurations

• une ou plusieurs fonction(s) dite(s) objectif(s), à optimiser (minimiser ou maximiser),

• un ensemble de contraintes à respecter.

2.1.2 Vocabulaire et définitions

D’un point de vue mathématique, un problème d’optimisation se présentera sous la forme

Les vecteurs g(x) et h(x) représentent respectivement m contraintes d’inégalité et p contraintes

Figure 2.1: Les différents espaces de recherche.

Figure 2.2: Les différents minima.

2.1.3 Classification des problèmes d’optimisation

• Élaborer un modèle mathématique fournissant l’expression de l’objectif à optimiser et

• Développer un algorithme de résolution ;

• Évaluer la qualité des solutions produites.

Figure 2.3: Classification d’un problème d’optimisation.

2.2 Optimisation mono-objectif

• Espace décisionnel et espace objectif

• l’espace décisionnel, de dimension n, où n désigne le nombre de variables de décision.

• l’espace objectif correspondant à l’ensemble de définition de la fonction objectif et

2.2.1 Classification générale des méthodes de type mono-objectif

problèmes d’optimisation continue, il n’est pas possible de disposer d’algorithme permettant de

Figure 2.4: Classification d’un problème d’optimisation mono-objectif.

Les méthodes globales

Méthodes globales classiques : De telles méthodes peuvent être considérées comme

Métaheuristiques : L’idée directrice sur laquelle repose une métaheuristique est

Les méthodes locales

2.3 Optimisation continue

2.3.1 Formulation et concepts de base

Si l’espace décisionnel E est discret (E ⊂ Z n , un ensemble fini ou dénombrable), il s’agit de

Généralement, le traitement et l’étude dans le domaine de l’optimisation continue est

min f (x) avec x ∈ Rn sous la contrainte x ∈ X et X ⊂ Rn . (2.1)

Définition [Link]. (Minimum local/Minimum global)

x ∈ X et ∃r > 0 | ∀y ∈ X ∩ B(x, r), f (x) 6 f (y) (2.2)

On dit alors que f (x) est un minimum local de f sur X.

x ∈ X et ∀y ∈ X, f (x) 6 f (y) (2.3)

On dit alors que f (x) est un minimum global de f sur X.

Figure 2.5: Exemple de minimums ou maximums globaux et locaux.

2.3.2 Convexité et optimisation

Définition [Link]. On se donne un ensemble X ⊂ Rn .

Définition [Link]. On se donne un ensemble convexe X ⊂ Rn et une fonction f : X → R.

Théorème [Link]. (Condition suffisante d’optimisation globale)

2.3.3 Conditions d’optimalité

Conditions d’optimalité pour un problème d’optimisation sans contrainte

Condition nécessaire d’optimalité locale

Théorème [Link]. On se donne une fonction f : Rn → R. Si x∗ est un minimum local de f ,

Condition suffisante d’optimalité locale

La stationnarité de f est une condition nécessaire d’optimalité. Pratiquement toutes les

Conditions d’optimalité pour un problème d’optimisation sous contraintes

Un problème d’optimisation sous contraintes s’énonce de la manière suivante :

min f (x) avec x ∈ X (2.4)

où h : Rn → Rp et g : Rn → Rq sont continues. Les écritures h(x) = 0 et g(x) 6 0 signifient que

Définition [Link]. (Contraintes actives/inactives)

Définition [Link]. (Contraintes qualifiées)

Définition [Link]. (Lagrangien du problème)

L(x, λ, γ) = f (x) + hλ, h(x)iRp + hγ, g(x)iRq (2.6)

Les paramètres (λ, γ) sont appelés multiplicateurs de Lagrange.

Théorème [Link]. (Conditions nécessaires d’optimalité) Considérons le problème

min f (x) avec x ∈ Rn sous les contraintes h(x) = 0 et g(x) 6 0.

où f , g et h sont supposées suffisamment différentiables. On note X le domaine des contraintes

(b) ∀j = 1, . . . , q, on a γj∗ gj (x∗ ) = 0 i.e. pour tout j = 1, . . . , q, on a γj∗ = 0 ou gj (x∗ ) = 0.

(e) ∀j = 1, . . . , q, on a γj (x∗ ) > 0.

2.3.4 Résolution d’un problème d’optimisation continue

La résolution d’un problème d’optimisation continue peut être équivalente à la détermination

• Méthodes de pénalité extérieure;

• Méthodes de pénalité intérieure;

∀x ∈ E f (x) > f ∗ et ∀ > 0 ∃x ∈ E tel que f (x ) < f ∗ +