Optimisation

Essadek

Introduction

Optimisation
unidimensionnelle

Techniques d’optimisation Optimisation sans

contraintes

Optimisation avec
contraintes
Conditions nécessaires
d’optimalité

Essadek Conditions suffisantes

d’optimalité
Méthodes numériques
d’optimisation

EMI - Rabat. Dualité

lagrangienne

Algorithmes
Génie Civil évolutionnaires
 Optimisation
Table des matières
Essadek

Introduction

Optimisation
Introduction unidimensionnelle

Optimisation sans
contraintes
Optimisation unidimensionnelle Optimisation avec
contraintes
Conditions nécessaires
d’optimalité

Optimisation sans contraintes Conditions suffisantes

d’optimalité
Méthodes numériques
d’optimisation

Dualité
Optimisation avec contraintes lagrangienne

Algorithmes
évolutionnaires
Dualité lagrangienne

Algorithmes évolutionnaires
 Optimisation
Définitions
Essadek

Introduction
L’optimisation joue un rôle très important dans les Optimisation
unidimensionnelle
sciences de l’ingénieur.
Optimisation sans
En effet, plusieurs problèmes d’ingénieurs peuvent être contraintes
modélisés sous la forme : Optimisation avec
contraintes
 Conditions nécessaires


 min f (x) d’optimalité
Conditions suffisantes

 s.c. d’optimalité


Méthodes numériques

gi (x) ≤ 0 i = 1, . . . , p (1) d’optimisation

Dualité
g (x) = 0 i = p + 1, . . . , m

i lagrangienne



x ∈ S ⊂ Rn

Algorithmes
évolutionnaires

Où x ∈ Rn
f : Rn −→ R est appelée la fonction objectif.
∀i = 1, . . . , m, gi : Rn −→ R sont appelées les
contraintes.
 Optimisation
Définitions
Essadek

Introduction

Optimisation
unidimensionnelle
Un optimum global de (1) est une solution qui minimise
Optimisation sans
f (x) sur l’ensemble des solutions. contraintes
On dit qu’un vecteur x 0 est un optimum local si et Optimisation avec
contraintes
seulement si il existe un voisinage V (x 0 ) de x 0 tel que x 0 Conditions nécessaires
d’optimalité
soit un optimum global du problème Conditions suffisantes
d’optimalité
Méthodes numériques
 d’optimisation


 min f (x) Dualité
 s.c. lagrangienne


gi (x) ≤ 0 i = 1, . . . , p (2) Algorithmes
évolutionnaires
g (x) = 0 i = p + 1, . . . , m

 i



x ∈ S ∩ V (x 0 )
 Optimisation
Rappels
Essadek
Soit f : D ⊂ Rn −→ R de classe C 2 en x ∈ D.
Introduction
Gradient
Optimisation
Le gradient de f en x est défini par : unidimensionnelle

Optimisation sans
 ∂f  contraintes
∂x1 (x) Optimisation avec
∇f (x) = 
 ..  contraintes
.  Conditions nécessaires
d’optimalité
∂f
∂xn (x)
Conditions suffisantes
d’optimalité
Méthodes numériques
d’optimisation

Dualité
Matrice hessienne lagrangienne

La matrice hessienne de f en x est définie par : Algorithmes

évolutionnaires

∂2f ∂2f ∂2f

 
∂x12
(x) ∂x1 ∂x2 (x) ... ∂x1 ∂xn (x)
 2
∂ f ∂2f ∂2f

∂x2 ∂x1 (x) (x) ... ∂x2 ∂xn (x)
 
∂x22
Hf (x) = 
 
.. .. .. .. 

 . . . .


∂2f ∂2f ∂2f
∂xn ∂x1 (x) ∂xn ∂x2 (x) ... ∂x 2
n
(x)
 Optimisation
Rappels
Essadek

Introduction

Le déterminant de la matrice hessienne est appelé le Optimisation

unidimensionnelle
hessien de f. Optimisation sans
contraintes
Théorème de Schwartz Optimisation avec
Si pour tout i, j ∈ {1, . . . , n}, les dérivées secondes contraintes
Conditions nécessaires

∂2f d’optimalité

existent et sont continues, alors Conditions suffisantes

d’optimalité
∂xi ∂xj Méthodes numériques
d’optimisation

Dualité
∂2f ∂2f lagrangienne
∀i 6= j (x) = (x) Algorithmes
∂xi ∂xj ∂xj ∂xi évolutionnaires

Corollaire
La matrice hessienne est symétrique.
 Optimisation
Exemples
Essadek

Introduction

Optimisation
unidimensionnelle

Optimisation sans
Déterminer le gradient, la matrice hessienne et le hessien contraintes
dans les cas suivants : Optimisation avec
contraintes
I D = {(x, y ) ; x 2 y + 1 > 0} et Conditions nécessaires
d’optimalité
Conditions suffisantes
d’optimalité
∀(x, y ) ∈ D f (x, y ) = ln(x 2 y + 1) Méthodes numériques
d’optimisation

Dualité
I D = R3 et lagrangienne

Algorithmes
évolutionnaires
∀(x, y , z) ∈ D g(x, y , z) = x sin y + y sin z
 Optimisation
Jacobienne
Essadek
Soit f : Rn −→ Rp une fonction de plusieurs variables,
Introduction
qu’on peut représenter sous la forme : Optimisation
unidimensionnelle
 
f1 (x) Optimisation sans
contraintes
 f2 (x) 
f (x) =  .  ∀i = 1, . . . , p fi : Rn −→ R Optimisation avec
 
 ..  contraintes
Conditions nécessaires
d’optimalité
fp (x) Conditions suffisantes
d’optimalité
Méthodes numériques
d’optimisation

Dualité
Matrice Jacobienne lagrangienne

La matrice Jacobienne est définie pour tout x ∈ Rn par Algorithmes

évolutionnaires

(∇f1 (x))t
 
 ∇f2 (x))t 
Jf (x) = 
 
.. 
 . 
∇fp (x))t
 Optimisation
Jacobienne
Essadek

Introduction

La matrice Jacobienne s’écrit alors : Optimisation

unidimensionnelle

∂f1 ∂f1 ∂f1 Optimisation sans

 
contraintes
 ∂x1 (x) ∂x2 (x) . . . ∂xn
(x)  Optimisation avec
 ∂f2 ∂f2 ∂f2
  contraintes
(x) (x) . . . (x)
 Conditions nécessaires
 
Jf (x) = 
 ∂x1 ∂x 2 ∂xn  d’optimalité
Conditions suffisantes
.. ..  d’optimalité
 ...
 ... . . 
 Méthodes numériques
d’optimisation
 ∂fp ∂fp ∂fp 
Dualité
(x) (x) . . . (x) lagrangienne
∂x1 ∂x2 ∂xn
Algorithmes
évolutionnaires

Jacobien
Le jacobien d’une fonction f est le déterminant de la
matrice jacobienne de f .
 Optimisation
Formule de Taylor
Essadek

Formule de Taylor d’ordre 2 Introduction

Optimisation
On peut écrire la formule de Taylor pour une unidimensionnelle

approximation de y proche de x Optimisation sans

contraintes

Optimisation avec
1
f (y ) ' f (x) + ∇f (x) . (y − x) + (y − x)t Hf (x)(y − x) contraintes
2 Conditions nécessaires
d’optimalité
Conditions suffisantes
d’optimalité
Méthodes numériques
d’optimisation

Exemple Dualité
lagrangienne
Soit D = {(x, y ) ∈ R2; xy 6= 1 et (a, b) = (2, −1) et
Algorithmes
f : D −→ R définie par évolutionnaires

x −y
f (x, y ) =
xy − 1

définir un développement de Taylor d’ordre 2 au

voisinage de (a, b)
 Optimisation
Convexité
Essadek

Introduction

Optimisation
Ensemble convexe unidimensionnelle

Un ensemble S ⊂ Rn est convexe si et seulement si Optimisation sans

contraintes

∀x, y ∈ S Optimisation avec
=⇒ λx + (1 − λ)y ∈ S contraintes
∀λ ∈ [0, 1] Conditions nécessaires
d’optimalité
Conditions suffisantes
d’optimalité
Méthodes numériques
d’optimisation

Fonction convexe Dualité

Soient S ⊂ Rn un ensemble convexe, et f : S −→ R. lagrangienne

Algorithmes
On dit que la fonction f est convexe si et seulement si évolutionnaires


∀x, y ∈ S
=⇒ f (λx + (1 − λ)y ) ≤ λf (x) + (1 − λ)f (y )
∀λ ∈ [0, 1]
 Optimisation
Convexité
Essadek

Problème convexe Introduction

Le problème 1 est convexe si : Optimisation
unidimensionnelle
 Optimisation sans
 f est convexe contraintes
les fonctions gi (i = 1, . . . , m) sont convexes Optimisation avec
S ⊂ Rn est convexe fermé contraintes

Conditions nécessaires
d’optimalité
Conditions suffisantes
d’optimalité
Méthodes numériques
d’optimisation
Théorème Dualité
Si f est C 1 alors les conditions 1 et 2 sont équivalentes. lagrangienne

Si f est C 2 alors les conditions 1, 2 et 3 sont Algorithmes

évolutionnaires
équivalentes.
1. f est convexe.
2. ∀x, y : f (y ) > f (x) + ∇f t (x).(y − x)
3. ∀x, Hf (x) est une matrice semi-définie positive
(∀y , y t .Hf (x).y ≥ 0)
 Optimisation
Convexité
Essadek

Introduction

Optimisation
Théorème unidimensionnelle

Dans le cas d’un problème convexe, tout optimum local Optimisation sans
contraintes
est un optimum global.
Optimisation avec
contraintes
Exercice Conditions nécessaires
d’optimalité
Conditions suffisantes
1. Soit f : Rn −→ R une fonction convexe et g : R −→ R d’optimalité
Méthodes numériques

une fonction convexe et non décroissante. Montrer d’optimisation

Dualité
que la fonction composée g ◦ f est convexe. lagrangienne

2. Que peut-on dire de la convexité des fonctions Algorithmes

évolutionnaires
suivantes ?
I f (x1 , x2 , x3 ) = x12 − 3x22 + 2x32 − x1 x2
2 2
I h(x1 , x2 ) = ex1 +3x2 −x1 x2
I g(x1 , x2 ) = x1 x2 − α(x1 + x2 − 1)2
 Optimisation
Théorème de Weierstrass
Essadek
Théorème Introduction
Si f est une fonction réelle continue sur un compact Optimisation
K ⊂ Rn alors le problème d’optimisation : unidimensionnelle

Optimisation sans
 contraintes
min f (x)
Optimisation avec
x ∈K contraintes
Conditions nécessaires
d’optimalité

a une solution optimale x ∗. Conditions suffisantes

d’optimalité
Méthodes numériques
d’optimisation

Corollaire Dualité
Soit f une fonction réelle continue sur Rn tel que lagrangienne

Algorithmes
évolutionnaires
lim f (x) = +∞
kxk→+∞

Alors la problème 
min f (x)
x ∈ Rn
a une solution optimale x ∗ .
 Optimisation
Table des matières
Essadek

Introduction

Optimisation
Introduction unidimensionnelle

Optimisation sans
contraintes
Optimisation unidimensionnelle Optimisation avec
contraintes
Conditions nécessaires
d’optimalité

Optimisation sans contraintes Conditions suffisantes

d’optimalité
Méthodes numériques
d’optimisation

Dualité
Optimisation avec contraintes lagrangienne

Algorithmes
évolutionnaires
Dualité lagrangienne

Algorithmes évolutionnaires
 Optimisation
Introduction
Essadek

Introduction

Nous serons amené, dans les chapitres suivants, à Optimisation

unidimensionnelle
résoudre un problème d’optimisation à une seule variable Optimisation sans
du type contraintes

 min g(α) = f (x 0 + αd)


Optimisation avec
contraintes
 α≥0 Conditions nécessaires

x 0 est le dernier point obtenu (3) d’optimalité

 Conditions suffisantes
d’optimalité
d est une direction de descente

Méthodes numériques
d’optimisation

Puisque d est une direction de descente, alors il existe α Dualité

lagrangienne
suffisamment petit tel que f (x 0 + αd) < f (x 0 ). Algorithmes
On aura alors la condition suivante : évolutionnaires

 
dg
= ∇f t (x 0 ).d < 0
dα α=0
 Optimisation
Méthode de Newton-Raphson
Essadek

Introduction

Optimisation
unidimensionnelle
Dans cette méthode, la recherche d’un minimum de g Optimisation sans
consiste à trouver un point stationnaire α∗ , c’est-à-dire contraintes

Optimisation avec
vérifiant contraintes
dg 0 Conditions nécessaires
= g (α) = 0 d’optimalité

dα Conditions suffisantes
d’optimalité
Méthodes numériques
Si αk est le point obtenu à l’itération k , alors le point αk +1 d’optimisation

Dualité
est déterminé par la relation suivante : lagrangienne

0 Algorithmes

k +1 k g (αk ) évolutionnaires
α = α − 00 k
g (α )
 Optimisation
Méthode de la sécante
Essadek

Introduction

Optimisation
unidimensionnelle

Optimisation sans
Dans cette méthode, on approche la dérivée seconde par contraintes

Optimisation avec
0 0
00 k g (αk ) − g (αk −1 ) contraintes
g (α ) = Conditions nécessaires
d’optimalité
αk − αk −1 Conditions suffisantes
d’optimalité
Méthodes numériques

La formule de Newton devient : d’optimisation

Dualité
lagrangienne
0 αk − αk −1
αk +1 = αk − g (αk ) 0
Algorithmes
g (αk ) − g 0 (αk −1 ) évolutionnaires
 Optimisation
Table des matières
Essadek

Introduction

Optimisation
Introduction unidimensionnelle

Optimisation sans
contraintes
Optimisation unidimensionnelle Optimisation avec
contraintes
Conditions nécessaires
d’optimalité

Optimisation sans contraintes Conditions suffisantes

d’optimalité
Méthodes numériques
d’optimisation

Dualité
Optimisation avec contraintes lagrangienne

Algorithmes
évolutionnaires
Dualité lagrangienne

Algorithmes évolutionnaires
 Optimisation
Introduction
Essadek

Soit f : Rn −→ R. Introduction

On cherche à trouver la solution du problème : Optimisation

unidimensionnelle
 Optimisation sans
min f (x) contraintes
(4)
x ∈ Rn Optimisation avec
contraintes
Conditions nécessaires

Il s’agit de déterminer le minimum global x ∗ tel que :

d’optimalité
Conditions suffisantes
d’optimalité
Méthodes numériques
d’optimisation
∀x ∈ Rn , f (x ∗ ) ≤ f (x) Dualité
lagrangienne

L’unicité du minimum global est garantie si : Algorithmes

évolutionnaires

∀x ∈ Rn , tel que x 6= x ∗ on a f (x ∗ ) < f (x)

Dans le cas où le problème (4) est non convexe, les

méthodes de résolution permettent seulement de trouver
un minimum local.
 Optimisation
Conditions nécessaires d’optimalité locale
Essadek

Introduction

Optimisation
unidimensionnelle

On suppose que f est C 2 pour tout x ∈ Rn . Optimisation sans

contraintes

Théorème Optimisation avec

contraintes
Les conditions nécessaires pour que x∗ soit un optimum Conditions nécessaires
d’optimalité

local sont : Conditions suffisantes

d’optimalité
Méthodes numériques

1. La stationnarité d’optimisation

∇f (x ∗ ) = 0
Dualité
lagrangienne

Algorithmes
2. La matrice hessienne Hf (x ∗ ) est semi-définie évolutionnaires

positive.
 Optimisation
Conditions suffisantes d’optimalité locale
Essadek
On suppose que f est C 2 pour tout x ∈ Rn .
Introduction

Théorème Optimisation
unidimensionnelle
Les conditions suffisantes pour que x ∗ soit un optimum
Optimisation sans
local sont : contraintes

Optimisation avec
1. La stationnarité contraintes
∗
∇f (x ) = 0 Conditions nécessaires
d’optimalité
Conditions suffisantes
d’optimalité
2. La matrice hessienne Hf (x ∗ ) est définie positive. Méthodes numériques
d’optimisation

Dualité
lagrangienne
Remarque
Algorithmes
La condition (2) revient à supposer que f est strictement évolutionnaires

convexe dans un voisinage de x ∗ .

Théorème
Dans le cas d’une fonction convexe, une condition
nécessaire et suffisante pour que x ∗ soit un minimum
global est que ∇f (x ∗ ) = 0
 Optimisation
Méthodes Numériques
Essadek

La majorité des méthodes d’optimisation sans contraintes Introduction

dans Rn , consistent à chercher un point x ∗ stationnaire. Optimisation
unidimensionnelle
Donc, on cherche à résoudre le système d’équations non
Optimisation sans
linéaires contraintes
∂f
∀i = 1, . . . , n =0 Optimisation avec
∂xi contraintes
Conditions nécessaires
d’optimalité

L’utilisation de la méthode de Newton s’avère couteuse et Conditions suffisantes

d’optimalité

pas pratique. Méthodes numériques

d’optimisation

On cherche alors à procéder d’une manière itérative pour Dualité

lagrangienne
converger vers un optimum local ou un point stationnaire,
Algorithmes
de telle manière que l’itération k + 1 est définie à partir de évolutionnaires

l’itération k par :

xk +1 = xk + λk dk

où λk est un réel et dk une direction de déplacement

définie à partir du gradient.
 Optimisation
Méthode du gradient à pas prédéterminé
Essadek

Introduction

On part d’un point x0 et on effectue un déplacement dans Optimisation

unidimensionnelle
la direction opposée du gradient : Optimisation sans
contraintes

∇f (x k ) Optimisation avec
x k +1 = xk − λk contraintes
||∇f (x k )|| Conditions nécessaires
d’optimalité
Conditions suffisantes
d’optimalité
Où λk > 0 est choisi tel que Méthodes numériques
d’optimisation

Dualité
λk −→ 0

 lagrangienne

 k →∞
Algorithmes
évolutionnaires
+∞
P
= +∞



k =0

1
On peut, par exemple, choisir λk = k
 Optimisation
Méthode de la plus forte pente
Essadek

La méthode de la plus forte pente (steepest descent), Introduction

consiste à choisir comme direction de descente ∇f (x k ). Optimisation

unidimensionnelle
λk est choisi de telle manière qu’il minimise la fonction de Optimisation sans
la variable λ ≥ 0 contraintes

Optimisation avec
contraintes
k k
g(λ) = f (x − λ∇f (x )) Conditions nécessaires
d’optimalité
Conditions suffisantes
d’optimalité
Méthodes numériques
d’optimisation

Dualité
Algorithme lagrangienne

Choisir un point de départ x 0 . Algorithmes

évolutionnaires
Tant que condition d’arrêt non vérifiée, faire :
I dk = −∇f (x k ).
I Trouver λk tel que f (x k + λk dk ) = min {f (x k + λdk )}.
λ≥0
I xk +1 = xk + λk dk
 Optimisation
Méthode de la plus forte pente
Essadek

Introduction

Optimisation
Critères d’arrêt unidimensionnelle

Etant donné  > 0 suffisamment petit, on cite par Optimisation sans

contraintes
exemple les critères d’arrêt suivants : Optimisation avec
contraintes
Critère 1 : Conditions nécessaires

∂f d’optimalité

max < Conditions suffisantes

d’optimalité
i=1,...,n ∂xi Méthodes numériques
d’optimisation

Critère 2 : Dualité
n  lagrangienne
∂f 2
X 
k∇f k2 = < Algorithmes
∂xi évolutionnaires
i=1

Critère 2 :
|f (x k +1 ) − f (x k )| < 
 Optimisation
Méthodes de directions conjuguées
Essadek

Soit q une fonction quadratique strictement convexe Introduction

Optimisation
unidimensionnelle
1
q(x) = x T Ax + bT x + c Optimisation sans
2 contraintes

Optimisation avec
où A est une matrice carré symétrique de taille n, b un contraintes
Conditions nécessaires
vecteur et c une constante. d’optimalité
Conditions suffisantes
d’optimalité

Directions conjuguées Méthodes numériques

d’optimisation

On dit que les directions d0 , d1 , . . . , dn−1 sont Dualité

lagrangienne
mutuellement conjuguées par rapport à la forme Algorithmes
quadratique q(x) si évolutionnaires


∀i = 0, . . . , n − 1 
∀j = 0, . . . , n − 1 =⇒ diT .A.dj = 0
i 6= j

 Optimisation
Méthodes de directions conjuguées
Essadek

Introduction

Optimisation
La méthode de directions conjuguées consiste à unidimensionnelle

déterminer x k +1 pour k = 0, . . . , n − 2 à partir de x k , en Optimisation sans

contraintes
utilisant la formule : Optimisation avec
contraintes
Conditions nécessaires

x k +1 = x k + λk dk d’optimalité
Conditions suffisantes
d’optimalité
Méthodes numériques

Où λk est la valeur qui minimise q(x k + λdk ). d’optimisation

Dualité
L’optimum de q(x) sur Rn est le point lagrangienne

Algorithmes
n−1
X évolutionnaires

xn = x0 + λi di
i=0
 Optimisation
Méthode du gradient conjugué
Essadek

Introduction
L’idée de cette méthode est de déterminer les directions Optimisation
unidimensionnelle
conjuguées à partir d’une combinaison linéaire du
Optimisation sans
gradient de la fonction quadratique q(x). contraintes

Notons gk = ∇q(x k ) et posons d0 = −g0 . Optimisation avec

contraintes
On a alors Conditions nécessaires
d’optimalité
x k +1 = x k + λk dk Conditions suffisantes
d’optimalité
Méthodes numériques

Avec d’optimisation

gkT dk Dualité
λk = − lagrangienne
dkT Adk Algorithmes
évolutionnaires
dk +1 = −gk +1 + βk dk
gkT+1 Adk
βk =
dkT Adk
 Optimisation
Méthode du gradient conjugué
Essadek

Introduction

Optimisation
Théorème unidimensionnelle

Optimisation sans
A une itération k où l’optimum n’est pas atteint (gi 6= 0), contraintes
on a Optimisation avec
contraintes
1. Conditions nécessaires

g T gk
d’optimalité
Conditions suffisantes
λk = Tk 6= 0 d’optimalité

dk Adk Méthodes numériques

d’optimisation

Dualité
2. lagrangienne
gkT+1 [gk +1 − gk ] gkT+1 gk +1 Algorithmes
βk = = évolutionnaires
gkT gk gkT gk
3. Les directions d0 , . . . , dk +1 sont mutuellement
conjuguées.
 Optimisation
Table des matières
Essadek

Introduction
Introduction Optimisation
unidimensionnelle

Optimisation sans
Optimisation unidimensionnelle contraintes

Optimisation avec
contraintes
Optimisation sans contraintes Conditions nécessaires
d’optimalité
Conditions suffisantes
d’optimalité
Méthodes numériques

Optimisation avec contraintes d’optimisation

Dualité
Conditions nécessaires d’optimalité lagrangienne

Conditions suffisantes d’optimalité Algorithmes

évolutionnaires
Méthodes numériques d’optimisation

Dualité lagrangienne

Algorithmes évolutionnaires
 Optimisation
Introduction
Essadek

Introduction

Optimisation
unidimensionnelle

Dans ce chapitre, on s’intéresse au problème suivant Optimisation sans

contraintes
 Optimisation avec

 min f (x) contraintes
s.c. Conditions nécessaires

d’optimalité
(5) Conditions suffisantes
g (x) ≤ 0 i ∈ I = {1, . . . , m}
 i
 d’optimalité
 Méthodes numériques
x ∈ Rn d’optimisation

Dualité
lagrangienne
Soit X l’ensemble des solutions de (5) Algorithmes
évolutionnaires

X = {x ∈ Rn / gi (x) ≤ 0, ∀i ∈ I}
 Optimisation
Conditions nécessaires de
Essadek
Karush-Kuhn-Tucker
Introduction

Optimisation
unidimensionnelle
Théorème Optimisation sans
contraintes
On suppose que les fonctions f et gi (i ∈ I) sont
Optimisation avec
continûment différentiables. contraintes

Une condition nécessaire pour que x ∗ ∈ X soit un Conditions nécessaires

d’optimalité
Conditions suffisantes
optimum local de (5) est qu’il existe des nombres d’optimalité
Méthodes numériques

λi ≥ 0 (i ∈ I) appelés multiplicateurs de d’optimisation

Dualité
Karush-kuhn-Tucker, tels que : lagrangienne

Algorithmes
∗ ∗
 P
 ∇f (x ) + i∈I λi ∇gi (x ) = 0
évolutionnaires

(KKT) et (6)

∀i ∈ I, λi gi (x ∗ ) = 0

 Optimisation
Cas de problèmes avec contraintes d’égalité
Essadek
et d’inégalité
Introduction

Optimisation
unidimensionnelle

Optimisation sans
Soit le problème contraintes

 Optimisation avec
 min f (x) contraintes
 Conditions nécessaires

 s.c.

 d’optimalité
Conditions suffisantes

gi (x) ≤ 0 i ∈ I = {1, . . . , m} (7) d’optimalité

Méthodes numériques
d’optimisation
h (x) = 0 l ∈ L = {1, . . . , p}

 l


 Dualité
x ∈ Rn lagrangienne

Algorithmes
évolutionnaires
Soit X l’ensemble des solutions de (7)

X = {x ∈ Rn / gi (x) ≤ 0, ∀i ∈ I et hl (x) = 0, ∀l ∈ L}
 Optimisation
Cas de problèmes avec contraintes d’égalité
Essadek
et d’inégalité
Introduction

Optimisation
unidimensionnelle

Théorème Optimisation sans

contraintes
On suppose que les fonctions f , gi (i ∈ I) et hl (l ∈ L) sont Optimisation avec
continûment différentiables. contraintes
Conditions nécessaires
Une condition nécessaire pour que x ∗ ∈ X soit un d’optimalité
Conditions suffisantes

optimum local de (7) est qu’il existe des nombres d’optimalité

Méthodes numériques
d’optimisation
λi ≥ 0 (i ∈ I) et µl (l ∈ L), tels que :
Dualité
lagrangienne
∗ ∗ ∗
 P P
 ∇f (x ) + i∈I λi ∇gi (x ) + l∈L µl ∇hl (x ) = 0
 Algorithmes
évolutionnaires
(KKT) et

∀i ∈ I, λi gi (x ∗ ) = 0

(8)
 Optimisation
Cas de problèmes avec contraintes d’égalité
Essadek

Introduction

Dans le cas où on a seulement des contraintes égalité Optimisation

unidimensionnelle
 Optimisation sans

 min f (x) contraintes

s.c.
 Optimisation avec
(9) contraintes
h (x) = 0 l ∈ L = {1, . . . , p}
 l
 Conditions nécessaires
 d’optimalité

x ∈ Rn Conditions suffisantes
d’optimalité
Méthodes numériques
d’optimisation

La condition nécessaire pour que x ∗ soit un optimum Dualité

lagrangienne
local se réduit à Algorithmes
évolutionnaires
X
∇f (x ∗ ) + µl ∇hl (x ∗ ) = 0 (10)
l∈L

On retrouve les conditions de Lagrange.

 Optimisation
Fonctions de Lagrange
Essadek

Introduction
On considère le problème Optimisation
unidimensionnelle


 min f (x) Optimisation sans
contraintes
s.c.

(11) Optimisation avec
g (x) ≤ 0 i ∈ I = {1, . . . , m} contraintes
 i

 Conditions nécessaires

x ∈ S ⊂ Rn d’optimalité
Conditions suffisantes
d’optimalité
Méthodes numériques

On associe à chaque contrainte gi , (i ∈ I), un nombre d’optimisation

Dualité
réel positif λi ≥ 0 appelé multiplicateur de Lagrange. lagrangienne

On appelle fonction de Lagrange associée au problème Algorithmes

évolutionnaires
(11), la fonction
X
L(x, λ) = f (x) + λi gi (x)
i∈I
 Optimisation
Points-cols
Essadek

Introduction
Définition Optimisation
Soit x ∈ S et λ ≥ 0. On dit que (x, λ) est un point-col pour unidimensionnelle

la fonction de Lagrange L si Optimisation sans

contraintes
 Optimisation avec
∀x ∈ S L(x, λ) ≤ L(x, λ) contraintes
(12) Conditions nécessaires
∀λ ≥ 0 L(x, λ) ≤ L(x, λ) d’optimalité
Conditions suffisantes
d’optimalité
Méthodes numériques
d’optimisation

Dualité
Théorème lagrangienne

Soit x ∈ S et λ ≥ 0. (x, λ) est un point-col pour L(x, λ) si Algorithmes

évolutionnaires
et seulement si
I L(x, λ) = min L(x, λ)
x∈S
I ∀i ∈ I, gi (x) ≤ 0
I ∀i ∈ I, λi gi (x) = 0
 Optimisation
Points-cols
Essadek

Introduction

Optimisation
unidimensionnelle
Théorème Optimisation sans
Si (x, λ) est un point-col pour L(x, λ), alors x est un contraintes

optimum global de (11). Optimisation avec

contraintes
Conditions nécessaires

Exemple d’optimalité
Conditions suffisantes
d’optimalité

Vérifier l’existence de point-col pour le problème suivant Méthodes numériques

d’optimisation

Dualité
min −x 2

lagrangienne


Algorithmes
s.c.

(13) évolutionnaires

 2x − 1 ≤ 0
0≤x ≤1

 Optimisation
Conditions suffisantes d’optimalité
Essadek

Introduction

On considère le problème (7). Optimisation

unidimensionnelle

Définition Optimisation sans

contraintes
Soit S l’ensemble des contraintes :
Optimisation avec
contraintes
S(x) = {x : gi (x) ≤ 0 i = 1, . . . , m et hi (x) = 0 i = 1, . . . , p} Conditions nécessaires
d’optimalité
Conditions suffisantes
d’optimalité
Méthodes numériques
On dit qu’une contrainte d’inégalité gi est saturée en un d’optimisation

point x si gi (x) = 0. Dualité

lagrangienne
On note I(x) l’ensemble des indices des contraintes Algorithmes
saturées en x : évolutionnaires

I(x) = {i : gi (x) = 0}
 Optimisation
Conditions suffisantes d’optimalité
Essadek

Introduction

Notation Optimisation
unidimensionnelle
On note : Optimisation sans
I I + (x) l’ensemble des contraintes saturées en x dont contraintes

Optimisation avec
le multiplicateur de Lagrange associé est non nul : contraintes
Conditions nécessaires
d’optimalité
+
I (x) = {i ∈ I(x) tel que λi > 0} Conditions suffisantes
d’optimalité
Méthodes numériques
d’optimisation

Dualité
lagrangienne
I Soit l’ensemble Algorithmes
évolutionnaires

∇gi (x).y ≤ 0 i ∈ I(x)/I + (x) 

 

F + (x) = y : ∇gi (x).y = 0 i ∈ I + (x)
∇hi (x).y = 0 i = 1, . . . , p
 
 Optimisation
Conditions suffisantes d’optimalité
Essadek

Définition Introduction

Optimisation
Le hessien par rapport à la fonction de Lagrange est unidimensionnelle
défini par : Optimisation sans
contraintes

m p Optimisation avec
contraintes
X X
HL (x, λ, µ) = Hf (x) + λi Hgi (x) + µi Hhi (x) Conditions nécessaires
d’optimalité

i=1 i=1 Conditions suffisantes

d’optimalité
Méthodes numériques
d’optimisation

Dualité
Théorème lagrangienne

Soit x ∗ ∈ S. Si (x ∗ , λ, µ) vérifient les conditions du Algorithmes

évolutionnaires
premier ordre et si le hessien de la fonction de Lagrange
en (x ∗ , λ, µ) est défini positif sur F + (x ∗ ), c.à.d

∀y 6= 0 ∈ F + (x ∗ ) y t HL (x ∗ , λ, µ)y > 0

Alors x ∗ est un minimum local strict du problème (7).

 Optimisation
Récapitulation : Problèmes sans contraintes
Essadek

Introduction

Optimisation
unidimensionnelle

I Conditions nécessaires premier ordre : Optimisation sans

contraintes

Optimisation avec
∇f (x ∗ ) = 0 contraintes
Conditions nécessaires
d’optimalité
Conditions suffisantes
I Conditions nécessaires second ordre : d’optimalité
Méthodes numériques
I Conditions nécessaires premier ordre d’optimisation

I Hf (x ∗ ) semi défini positif Dualité

lagrangienne
I Conditions suffisantes : Algorithmes
évolutionnaires
I Conditions nécessaires premier ordre
I Hf (x ∗ ) défini positif
 Optimisation
Récapitulation : Problèmes sous contraintes
Essadek

Introduction

Optimisation
unidimensionnelle

I Conditions nécessaires premier ordre : Optimisation sans

contraintes
I λ≥0
Optimisation avec
I ∇L(x ∗ , λ, µ) = 0 contraintes
I λ.g(x ∗ ) = 0 Conditions nécessaires
d’optimalité
Conditions suffisantes
I Conditions nécessaires second ordre : d’optimalité
Méthodes numériques
d’optimisation
I Conditions nécessaires premier ordre
Dualité
I HL (x ∗ , λ, µ) semi défini positif sur F + (x ∗ ). lagrangienne

I Conditions suffisantes : Algorithmes

évolutionnaires
I Conditions nécessaires premier ordre
I HL (x ∗ , λ, µ) défini positif sur F + (x ∗ ).
 Optimisation
Méthode du gradient projeté
Essadek

Introduction

Afin d’adapter les méthodes d’optimisation sans Optimisation

unidimensionnelle
contraintes aux problèmes avec contraintes, Rosen a Optimisation sans
pensé à projeter à chaque étape le déplacement sur la contraintes

frontière du domaine, pour que le nouveau point obtenu Optimisation avec

contraintes
soit réalisable. Conditions nécessaires
d’optimalité

Pour définir la méthode du gradient projeté, on va Conditions suffisantes

d’optimalité
Méthodes numériques
commencer par le cas où les contraintes sont linéaires. d’optimisation

Dualité
 lagrangienne
 min f (x)
 Algorithmes
s.c.

évolutionnaires
(14)
a x ≤ bi i ∈ I1
 i


ai x = bi i ∈ I2

où ai est un vecteur ligne.

 Optimisation
Méthode du gradient projeté
Essadek

Introduction

Notations Optimisation
unidimensionnelle

I L’ensemble des indices des contraintes saturés au Optimisation sans

contraintes
point x est Optimisation avec
contraintes
0 Conditions nécessaires
I (x) = {i / i ∈ I1 ; ai x = bi } ∪ I2 d’optimalité
Conditions suffisantes
d’optimalité

I On note A0 la sous matrice de A constituée par les Méthodes numériques

d’optimisation

lignes i ∈ I 0 (x). Dualité

lagrangienne
I La matrice de projection est Algorithmes
évolutionnaires

t t −1
h i
P 0 = I − A0 . A0 .A0 .A0

I Soit X l’ensemble des points réalisables.

 Optimisation
Méthode du gradient projeté
Essadek

Algorithme Introduction

I Choisir un point de départ x0 ∈ X. Optimisation

unidimensionnelle

I Tant que (condition d’arrêt non vérifiée) Optimisation sans

contraintes
x k est le point courant. Optimisation avec
Déterminer A0 = A0 (x k ) contraintes
Conditions nécessaires

Calculer la matrice de projection P 0 d’optimalité

Conditions suffisantes

y ← −P 0 .∇f (x k ) d’optimalité
Méthodes numériques

t −1
h i d’optimisation

u ← − A0 .A0 .A0 .∇f (x k ) Dualité

lagrangienne
ui = min {uj } Algorithmes
j=1,...,n évolutionnaires
Si (y = 0)
Si (ui < 0)
0
Calculer A 0 la matrice obtenue en supprimant
0
la ligne i de A0 , puis calculer P 0 la matrice de
projection associée. Faire
0
y ← y 0 = −P 0 .∇f (x k )
 Optimisation
Méthode du gradient projeté
Essadek

Introduction

Optimisation
Sinon (Si ui ≥ 0) unidimensionnelle

x k satisfait les conditions nécessaires . Optimisation sans

contraintes
de (KKT). Sortir de la boucle.
Optimisation avec
Fin SI contraintes
Conditions nécessaires
Fin SI d’optimalité
Conditions suffisantes

αmax = max{α / x k + αy ∈ X } d’optimalité

Méthodes numériques

f (x k +1 ) = min 0 ≤ α ≤ αmax {f (x k + αy )}
d’optimisation

Dualité
k ←k +1 lagrangienne

Fin Tant que Algorithmes

évolutionnaires

Remarque
La condition d’arrêt peut être ky k ≤  et ui ≥ −, pour
une tolérance  choisie.
 Optimisation
Méthode du gradient projeté
Essadek

Cas de contraintes non linéaires Introduction

Optimisation
On considère le problème unidimensionnelle

 Optimisation sans

 min f (x) contraintes

s.c. Optimisation avec


(15) contraintes
g (x) ≤ 0 i ∈ I1 Conditions nécessaires

 i d’optimalité


gi (x) = 0 i ∈ I2 Conditions suffisantes
d’optimalité
Méthodes numériques
d’optimisation

On note I 0 (x) les indices des contraintes saturées en x. Dualité

lagrangienne

Algorithmes
I 0 (x) = {i1 , . . . , iq } évolutionnaires

g 0 (x) = [gi1 , . . . , giq ]t

On note J(x) le jacobien de g 0 évalué en x
On utilise la même procédure que pour le cas linéaire en
remplaçant A0 par J.
 Optimisation
Méthodes de pénalités
Essadek

Introduction

Optimisation
Soit le problème unidimensionnelle

Optimisation sans
 contraintes
 min f (x)
 Optimisation avec
s.c.
 contraintes
(16) Conditions nécessaires
g (x) ≤ 0 i = 1, . . . , m d’optimalité

 i

 Conditions suffisantes

x ∈ Rn d’optimalité
Méthodes numériques
d’optimisation

Dualité
et soit la fonction h : R −→ R, définie par lagrangienne

 Algorithmes
h(y ) = 0 si y ≤ 0 évolutionnaires

h(y ) = +∞ si y > 0

On note X l’ensemble des points réalisables de (16).

 Optimisation
Méthodes de pénalités
Essadek

Le principe des méthodes de pénalités, consiste à Introduction

Optimisation
remplacer le problème (16), par un problème sans unidimensionnelle
contraintes appelé problème pénalisé. Optimisation sans
contraintes

 min Φ(x) = f (x) + H(x) Optimisation avec
contraintes
s.c. (17) Conditions nécessaires
d’optimalité

x ∈ Rn Conditions suffisantes

d’optimalité
Méthodes numériques
d’optimisation

Où H est appelée fonction de pénalisation, et est définie Dualité

lagrangienne
par
m Algorithmes
X évolutionnaires
∀x, H(x) = h(gi (x))
i=1

L’optimum de Φ(x) appartient forcément à X , car sinon

Φ(x) = +∞, et pour tout x ∈ X , on a H(x) = 0, donc les
problèmes (16) et (17) sont équivalents.
 Optimisation
Méthode de pénalité extérieure
Essadek

La définition de la fonction H, présente une difficulté par Introduction

sa discontinuité. Pour cela on la définit par Optimisation
unidimensionnelle

h(y ) = 0 si y ≤ 0 Optimisation sans
contraintes
h(y ) = y 2 si y > 0 Optimisation avec
contraintes

et Conditions nécessaires
d’optimalité
m m Conditions suffisantes
X X 2 d’optimalité

gi+ (x)

∀x, H(x) = h(gi (x)) = Méthodes numériques
d’optimisation

i=1 i=1 Dualité

lagrangienne
avec gi+ (x)
= max{0 ; gi (x)}. le problème (16) est Algorithmes
remplacé par : évolutionnaires


 min Φ(x) = f (x) + r .H(x)
s.c. (18)
x ∈ Rn


où r > 0 est appelé coefficient de pénalité.

 Optimisation
Méthode de pénalité extérieure
Essadek

Introduction

Optimisation
unidimensionnelle
On commence par choisir un coefficient r1 > 0 pas très Optimisation sans
élevé, puis on résout le problème (18), en utilisant un contraintes

Optimisation avec
algorithme d’optimisation sans contraintes. contraintes
Soit x ∗ (r1 ) le point obtenu. Conditions nécessaires
d’optimalité
Conditions suffisantes
I Si H(x ∗ (r1 )) est suffisamment petit alors x ∗ (r1 ) est d’optimalité
Méthodes numériques

une bonne approximation de l’optimum. d’optimisation

Dualité
I Sinon, on choisit r2 > r1 , par exemple r2 = 10r1 , et lagrangienne

on résout le problème (18). Algorithmes

évolutionnaires
I A l’itération k + 1, il est préférable de prendre comme
point de départ x ∗ (rk ).
 Optimisation
Méthode de pénalité intérieure
Essadek
La méthode de pénalité extérieure présente
Introduction
l’inconvénient que l’optimum x ∗ est approché par
Optimisation
l’extérieur, puisque les points x1 , . . . , xk obtenus pour les unidimensionnelle

coefficients de pénalité t1 , . . . , rk n’appartiennent pas à X . Optimisation sans

contraintes
On définit une méthode appelée méthode de pénalité Optimisation avec
intérieure. contraintes
Conditions nécessaires

Soit B : R −→ R la fonction définie par : d’optimalité

Conditions suffisantes
d’optimalité
Méthodes numériques
m d’optimisation
X 1
B(x) = − Dualité
gi (x) lagrangienne
i=1
Algorithmes
évolutionnaires
La fonction B(x) est appelée fonction de pénalité
intérieure, et elle vérifie :
I B(x) ≥ 0 , ∀x ∈ int(X )
I lim B(x) = +∞
x→fr (X )
I B(x) est continue sur l’intérieur de X .
 Optimisation
Méthode de pénalité intérieure
Essadek

Introduction

Soit la fonction Optimisation

unidimensionnelle

Optimisation sans
Ψ(x) = f (x) + t.B(x, t) contraintes

Optimisation avec
contraintes
Conditions nécessaires
d’optimalité

I On choisit une valeur t1 > 0 et x0 ∈ int(X ) et on Conditions suffisantes

d’optimalité
Méthodes numériques
recherche le minimum de Ψ, on ne pourra jamais d’optimisation

franchir la frontière car au voisinage de celle-ci Dualité

lagrangienne
Ψ −→ +∞. Algorithmes
I On obtient un point x 1 = x(t1 ). Si t.B(t) est évolutionnaires

suffisamment petit, alors x 1 est une bonne

approximation de l’optimum, sinon on prend t2 < t1 et
on recommence la procédure.
 Optimisation
Table des matières
Essadek

Introduction

Optimisation
Introduction unidimensionnelle

Optimisation sans
contraintes
Optimisation unidimensionnelle Optimisation avec
contraintes
Conditions nécessaires
d’optimalité

Optimisation sans contraintes Conditions suffisantes

d’optimalité
Méthodes numériques
d’optimisation

Dualité
Optimisation avec contraintes lagrangienne

Algorithmes
évolutionnaires
Dualité lagrangienne

Algorithmes évolutionnaires
 Optimisation
Introduction
Essadek
Soit le problème
 Introduction

 min f (x) Optimisation
s.c.
 unidimensionnelle
(19)
 gi (x) ≤ 0
 i = 1, . . . , m Optimisation sans
contraintes
x ∈ S ⊂ Rn

Optimisation avec
contraintes
la fonction de Lagrange associée au problème (19) Conditions nécessaires
d’optimalité

s’écrit X
Conditions suffisantes
d’optimalité
Méthodes numériques
L(x, λ) = f (x) + λi gi (x) d’optimisation

i∈I Dualité
lagrangienne
On considère la fonction Algorithmes
évolutionnaires
w(λ) = min {L(x, λ)}
x∈S

On définit le problème dual par

  
max w(λ) = max min {L(x, λ)}

λ λ x∈S (20)
λ ∈ Rm

+
 Optimisation
Propriétés
Essadek

Introduction

Optimisation
unidimensionnelle

Optimisation sans
contraintes
Théorème faible de la dualité Optimisation avec
Si λ∗ est l’optimum du problème dual (20), alors contraintes
Conditions nécessaires
d’optimalité
Conditions suffisantes

∀λ : w(λ) ≤ w(λ∗ ) ≤ f (x ∗ ) d’optimalité

Méthodes numériques
d’optimisation

Dualité
lagrangienne
Théorème Algorithmes
évolutionnaires
La fonction duale w est une fonction concave de λ.
 Optimisation
Propriétés
Essadek

Introduction

Optimisation
unidimensionnelle
Théorème de la dualité
Optimisation sans
I Si le problème (19) admet un point-col (x ∗ , λ∗ ),alors contraintes

Optimisation avec
contraintes
w(λ∗ ) = f (x ∗ ) Conditions nécessaires
d’optimalité
Conditions suffisantes
d’optimalité

La valeur optimale du problème (19) est égale à la Méthodes numériques

d’optimisation

valeur optimale du problème dual (20). Dualité

lagrangienne
I Réciproquement s’il existe x∗
solution de (19) et λ∗ Algorithmes
tel que évolutionnaires

w(λ∗ ) = f (x ∗ )
alors le problème (19) admet le point-col (x ∗ , λ∗ ).
 Optimisation
Table des matières
Essadek

Introduction

Optimisation
Introduction unidimensionnelle

Optimisation sans
contraintes
Optimisation unidimensionnelle Optimisation avec
contraintes
Conditions nécessaires
d’optimalité

Optimisation sans contraintes Conditions suffisantes

d’optimalité
Méthodes numériques
d’optimisation

Dualité
Optimisation avec contraintes lagrangienne

Algorithmes
évolutionnaires
Dualité lagrangienne

Algorithmes évolutionnaires