M061: Introduction á l’optimisation

DÉFINITIONS
OPTIMISATION SANS CONTRAINTES
METHODE DU GRADIENT
PROBLÉME D’OPTIMISATION AVEC CONTRAINTES

t
raf
M061: Introduction á l’optimisation

Aboubecrine ([email protected])

École Supérieure Polytechnique,

ISMS

Aboubecrine ([email protected]) M061: Introduction á l’optimisation

 M061: Introduction á l’optimisation
DÉFINITIONS
OPTIMISATION SANS CONTRAINTES
METHODE DU GRADIENT
PROBLÉME D’OPTIMISATION AVEC CONTRAINTES

t
raf
1 DÉFINITIONS

2 OPTIMISATION SANS CONTRAINTES

3 METHODE DU GRADIENT

4 PROBLÉME D’OPTIMISATION AVEC CONTRAINTES

Aboubecrine ([email protected]) M061: Introduction á l’optimisation

 M061: Introduction á l’optimisation
DÉFINITIONS
OPTIMISATION SANS CONTRAINTES
METHODE DU GRADIENT
PROBLÉME D’OPTIMISATION AVEC CONTRAINTES

t
minimun global(absolu)
Une solution x ∗ est un minimun global(absolu) de la fonction f sur le domaine

raf
S si
f (x ∗ ) ≤ f (x) ∀x ∈ S
la valeur optimale est f (x ∗ )

minimun local
Une solution x ∗ est un minimun local de la fonction f sur le domaine S s’il
existe  > 0 tel que:

f (x ∗ ) ≤ f (x) ∀x ∈ S ∩ B (x ∗ )

où,
B (x ∗ ) = {x ∈ Rn : kx − x ∗ k < }
est la boule de rayon  centrée en x ∗ .

Aboubecrine ([email protected]) M061: Introduction á l’optimisation

 M061: Introduction á l’optimisation
DÉFINITIONS
OPTIMISATION SANS CONTRAINTES
METHODE DU GRADIENT
PROBLÉME D’OPTIMISATION AVEC CONTRAINTES

t
raf
Remarques
Un minimum global est aussi un minimum local.
Il n’existe pas toujours de minimum global, ni de minimum local.
En général, il est difficile de trouver un minimum global.

Maximum global(local)
Le maximum global (local) est défini de façon semblable si en remplace
l’inégalité ≤ par ≥.

Aboubecrine ([email protected]) M061: Introduction á l’optimisation

 M061: Introduction á l’optimisation
Conditions d’optimalité
DÉFINITIONS
Généralisation de la condition nécéssaire du second ordre
OPTIMISATION SANS CONTRAINTES
Condition suffisante d’optimalité du second d’ordre
METHODE DU GRADIENT
Conditions d’optimalité pour les problı̈¿ 1 mes de maximisation
PROBLÉME D’OPTIMISATION AVEC CONTRAINTES 2

t
Soit un domaine D ⊆ Rn et une fonction f : D −→ R de n variables.

raf
On cherche un point x ∈ D qui minimise la valeur de f (x) sur D.
On écrit:
minn f (x)
x∈R

La fonction f est appelée fonction objectif.

Théorème (Condition nécéssaire du 1er ordre)

Si x ∗ est un minimun local de la fonction f sur Rn alors ∇f (x ∗ ) = 0

Point critique
Le point x est appelé point critique si ∇f (x) = 0

Exemple Déterminer les points critiques de la fonction

f (x, y ) = 31 x 3 + 43 y 3 − x 2 − 3x − 4y − 3

Aboubecrine ([email protected]) M061: Introduction á l’optimisation

 M061: Introduction á l’optimisation
Conditions d’optimalité
DÉFINITIONS
Généralisation de la condition nécéssaire du second ordre
OPTIMISATION SANS CONTRAINTES
Condition suffisante d’optimalité du second d’ordre
METHODE DU GRADIENT
Conditions d’optimalité pour les problı̈¿ 1 mes de maximisation
PROBLÉME D’OPTIMISATION AVEC CONTRAINTES 2

t
raf
Remarques
un point critique peut être:
un minimum local
un maximum local
un point de selle (ni minimum local, ni maximum local)

Aboubecrine ([email protected]) M061: Introduction á l’optimisation

 M061: Introduction á l’optimisation
Conditions d’optimalité
DÉFINITIONS
Généralisation de la condition nécéssaire du second ordre
OPTIMISATION SANS CONTRAINTES
Condition suffisante d’optimalité du second d’ordre
METHODE DU GRADIENT
Conditions d’optimalité pour les problı̈¿ 1 mes de maximisation
PROBLÉME D’OPTIMISATION AVEC CONTRAINTES 2

t
raf
Matrice Hessienne
Soit f (x) est une fonction de n variables. La matrice hessienne de f (x), notée
∇2 f (x), est la matrice (aij ) où aij = fx00i xj (x)

∂2f ∂2f ∂2f

 
∂x12 ∂x1 ∂x2
... ∂x1 ∂xn
∂2f ∂2f ∂2f
 
...
∇2 f (x) = 
 
∂x2 ∂x1 ∂x22 ∂x2 ∂xn 
... ... ... ...
 
 
∂2f ∂2f ∂2f
∂xn ∂x1 ∂xn ∂x2
... ∂xn2

Cette matrice est symétrique si toutes les dérivées sont continues.

Aboubecrine ([email protected]) M061: Introduction á l’optimisation

 M061: Introduction á l’optimisation
Conditions d’optimalité
DÉFINITIONS
Généralisation de la condition nécéssaire du second ordre
OPTIMISATION SANS CONTRAINTES
Condition suffisante d’optimalité du second d’ordre
METHODE DU GRADIENT
Conditions d’optimalité pour les problı̈¿ 1 mes de maximisation
PROBLÉME D’OPTIMISATION AVEC CONTRAINTES 2

t
raf
Rappel: Définitions
Une matrice A de dimension n × n est dite

Semi-définie positive si y T Ay ≥ 0 ∀y ∈ Rn
Définie positive si y T Ay > 0 ∀y ∈ Rn \{0}
Semi-définie négative si y T Ay ≤ 0 ∀y ∈ Rn
Définie négative si y T Ay < 0 ∀y ∈ Rn \{0}

Aboubecrine ([email protected]) M061: Introduction á l’optimisation

 M061: Introduction á l’optimisation
Conditions d’optimalité
DÉFINITIONS
Généralisation de la condition nécéssaire du second ordre
OPTIMISATION SANS CONTRAINTES
Condition suffisante d’optimalité du second d’ordre
METHODE DU GRADIENT
Conditions d’optimalité pour les problı̈¿ 1 mes de maximisation
PROBLÉME D’OPTIMISATION AVEC CONTRAINTES 2

t
Cas n=2
 
a11 a12
A=
a21 a22

raf
α1 = det[a11 ] = a11 , α2 = det(A) = a11 a22 − a21 a12
Si α1 > 0 et α2 > 0, alors A est définie positive
Si α1 < 0 et α2 > 0, alors A est définie négative
Si α2 < 0, alors A n’est ni définie positive ni définie négative (indéfinie)

Cas n=3
 
a11 a12 a13
A =  a21 a22 a23 
a31 a32 a33
 
a11 a12
α1 = det[a11 ] = a11 , α2 = det = a11 a22 − a21 a12 , α3 = det(A)
a21 a22
Si α1 > 0 et α2 > 0 et α3 > 0, alors A est définie positive
Si α1 < 0 et α2 > 0 et α3 < 0, alors A est définie négative
Si α2 < 0, alors A n’est ni définie positive ni définie négative (indéfinie)

Aboubecrine ([email protected]) M061: Introduction á l’optimisation

 M061: Introduction á l’optimisation
Conditions d’optimalité
DÉFINITIONS
Généralisation de la condition nécéssaire du second ordre
OPTIMISATION SANS CONTRAINTES
Condition suffisante d’optimalité du second d’ordre
METHODE DU GRADIENT
Conditions d’optimalité pour les problı̈¿ 1 mes de maximisation
PROBLÉME D’OPTIMISATION AVEC CONTRAINTES 2

t
Théorème (Condition nécessaire du second ordre)
Si x ∗ est un minimun local de la fonction f (x) sur Rn , alors

raf
∇f (x ∗ ) = 0 et y T ∇2 f (x ∗ )y ≥ 0 ∀y ∈ Rn

(i.e., la matrice hessienne ∇2 f (x ∗ ) est semi-définie positive).

Théorème (Condition suffisante du second ordre)

Soit x ∗ ∈ Rn . Si

∇f (x ∗ ) = 0, et y T ∇2 f (x ∗ )y > 0 ∀y ∈ Rn − {0}

(i.e ∇2 f (x ∗ ) est définie positive), alors x ∗ est un minimun local de la fonction

f sur Rn

Définition du point selle : Généralisation

Le point x est appelé point selle si ∇f (x) = 0 et la matrice hessienne ∇2 f (x)
est indéfinie (n’est ni semi-définie positive, ni définie positive, ni semi-définie
négative, ni définie négative).

Aboubecrine ([email protected]) M061: Introduction á l’optimisation

 M061: Introduction á l’optimisation
Conditions d’optimalité
DÉFINITIONS
Généralisation de la condition nécéssaire du second ordre
OPTIMISATION SANS CONTRAINTES
Condition suffisante d’optimalité du second d’ordre
METHODE DU GRADIENT
Conditions d’optimalité pour les problı̈¿ 1 mes de maximisation
PROBLÉME D’OPTIMISATION AVEC CONTRAINTES 2

t
Théorème (Condition nécessaire du second ordre )
Si x ∗ est un maximun local de la fonction f sur Rn , alors ∇f (x ∗ ) = 0 et

raf
y T ∇2 f (x ∗ )y ≤ 0 ∀y ∈ Rn (i.e la matrice Hessienne ∇2 f (x ∗ ) est semi-définie
négative).

Théorème (Condition suffisante du second ordre)

Soit x ∗ ∈ Rn . Si ∇f (x ∗ ) = 0, et si y T ∇2 f (x ∗ )y < 0 ∀y ∈ Rn − {0}(i.e
∇2 f (x ∗ ) est définie négative). alors x ∗ est un maximun local de f (x) sur Rn

Remarques
En pratique, pour résoudre un problème d’optimisation sans contraintes, on
trouve un point critique x ∗ et on étudie sa nature:
Si ∇2 f (x ∗ ) est définie positive, alors x ∗ est un minimum local
Si ∇2 f (x ∗ ) est définie négative, alors x ∗ est un maximum local
Si ∇2 f (x ∗ ) est indéfinie, alors x ∗ est un point de selle

Aboubecrine ([email protected]) M061: Introduction á l’optimisation

 M061: Introduction á l’optimisation
Conditions d’optimalité
DÉFINITIONS
Généralisation de la condition nécéssaire du second ordre
OPTIMISATION SANS CONTRAINTES
Condition suffisante d’optimalité du second d’ordre
METHODE DU GRADIENT
Conditions d’optimalité pour les problı̈¿ 1 mes de maximisation
PROBLÉME D’OPTIMISATION AVEC CONTRAINTES 2

t
raf
Exemple1
Déterminer le signe (définie positive ou négative) de la matrice suivante:
 
3 −2 0
A =  −1 2 −1 
0 −1 2

Exemple2
Soit
f (x, y ) = x 3 − 3x + y 3 + 3y 2 − 1
Identifier tous les points critiques et déterminer leur nature

Aboubecrine ([email protected]) M061: Introduction á l’optimisation

 M061: Introduction á l’optimisation
DÉFINITIONS
OPTIMISATION SANS CONTRAINTES
METHODE DU GRADIENT
PROBLÉME D’OPTIMISATION AVEC CONTRAINTES

t
raf
METHODE DU GRADIENT DANS R2
Cette méthode permet de trouver, en général, un minimum local d’une
fonction f (x, y ).
C’est une méthode itérative
(xk , yk ): point courant du début de l’itération k
dk = −∇f (xk , yk ): direction de descente au point (xk , yk )
h(α) = f ((xk , yk ) + αdk ): fonction à une variable à minimiser l̀’itération k

Aboubecrine ([email protected]) M061: Introduction á l’optimisation

 M061: Introduction á l’optimisation
DÉFINITIONS
OPTIMISATION SANS CONTRAINTES
METHODE DU GRADIENT
PROBLÉME D’OPTIMISATION AVEC CONTRAINTES

t
METHODE DU GRADIENT(pour un probléme de minimisation)
INITIALISATION:
Soit x0 ∈ Rn un estimé de la solution. Poser le compteur k ← 0.

raf
EVALUATION DU GRADIENT:
Calculer la direction dk = −∇f (xk ). Si kdk k = 0 alors on termine avec un
point critique xk . Sinon on poursuit ı̈¿ 12 la prochaine étape.
RECHERCHE DANS LA DIRECTION DE DESCENTE:
Soit xk+1 la solution produite par la résolution du probléme de
minimisation á une variable

min h(α) oú h(α) = f (xk + αdk )

α≥0

αk = argmin(h), xk+1 = xk + αk dk
Poser k ← k + 1, et retourner á l’étape précédente.

Exemple
Considérer la fonction à minimiser f (x1 , x2 ) = (x1 − 2)2 + (x2 − 3)2 avec
x = (x1 , x2 ). Trouver le point P1 obtenu avec la méthode du gradient à partir
du point P0 = (0, 0).
Aboubecrine ([email protected]) M061: Introduction á l’optimisation
 M061: Introduction á l’optimisation
Définition du problème
DÉFINITIONS
Optimisation sous une contrainte d’égalité
OPTIMISATION SANS CONTRAINTES
Optimisation avec une contrainte d’inégalité
METHODE DU GRADIENT
Optimisation avec plusieurs contraintes d’égalité
PROBLÉME D’OPTIMISATION AVEC CONTRAINTES

t
raf
Théorème (des valeurs extrémes pour des fonctions á deux variables)
Si f est continue sur un ensemble borné et fermé S de R2 , alors f atteint son
maximun global et son niminum global en des points de S.

Aboubecrine ([email protected]) M061: Introduction á l’optimisation

 M061: Introduction á l’optimisation
Définition du problème
DÉFINITIONS
Optimisation sous une contrainte d’égalité
OPTIMISATION SANS CONTRAINTES
Optimisation avec une contrainte d’inégalité
METHODE DU GRADIENT
Optimisation avec plusieurs contraintes d’égalité
PROBLÉME D’OPTIMISATION AVEC CONTRAINTES

t
Soient f et h deux fonctions différentiables et k une constante. Soit le

raf
problème suivant (1):

min f (x)
s.c. h(x) = k, x ∈ Rn
Pour ce problème, Lagrange a montré qu’à l’optimalité, le vecteur gradient de
la fonction objectif doit être perpendiculaire à la surface de niveau de la
contrainte.

Théorème (condition nécessaire du premier ordre de Lagrange)

Si x ∗ est un minimum local de la fonction f dans S, et si ∇h(x ∗ ) 6= 0, alors
h(x ∗ ) = k, et de plus il existe un scalaire λ ∈ R pour lequel :
∇f (x ∗ ) = λ∇h(x ∗ )

Aboubecrine ([email protected]) M061: Introduction á l’optimisation

 M061: Introduction á l’optimisation
Définition du problème
DÉFINITIONS
Optimisation sous une contrainte d’égalité
OPTIMISATION SANS CONTRAINTES
Optimisation avec une contrainte d’inégalité
METHODE DU GRADIENT
Optimisation avec plusieurs contraintes d’égalité
PROBLÉME D’OPTIMISATION AVEC CONTRAINTES

t
Soit le problème suivant :

raf
min f (x)
x
s.c x ∈S
S = {x ∈ R : h (x) ≤ k}
f , h : Rn −→ R différentiable et k une constante.
Ce problème est un cas particulier du problème (1) précédent. Les solutions
sont obtenues de la manière suivante:
Considèrer le problème sans contrainte et déterminer les points critiques
(i.e, les points où le gradient s’annule) et retenir ceux qui appartiennent à
S.
Appliquer la méthode du multiplicateur de Lagrange au problème obtenue
en remplaçant la contrainte d’inégalité par la contrainte d’égalité.
Le minimum ou maximum global sera l’un ou plusieurs des points
énumérés aux étapes précédentes.

Aboubecrine ([email protected]) M061: Introduction á l’optimisation

 M061: Introduction á l’optimisation
Définition du problème
DÉFINITIONS
Optimisation sous une contrainte d’égalité
OPTIMISATION SANS CONTRAINTES
Optimisation avec une contrainte d’inégalité
METHODE DU GRADIENT
Optimisation avec plusieurs contraintes d’égalité
PROBLÉME D’OPTIMISATION AVEC CONTRAINTES

t
Soit le problème suivant :
min f (x)

raf
x
s.c x ∈S
n
S = {x ∈ R : hj (x) = kj } j = 1, ..., m
f , hj : Rn −→ R différentiable et kj une constante j = 1, ..., m.
Pour ce problème, Lagrange a montré qu’à l’optimalité, le vecteur gradient de
la fonction objectif doit être une combinaison linéaire des gradients des
contraintes.

Théoréme (Condition nécessaire de 1er ordre de Lagrange)

Si x ∗ est un minimum local de la fonction f dans S où
{∇hj (x ∗ ) : j = 1, ..., m} est un ensemble linéairement indépendant, alors
hj (x ∗ ) = kj pour j = 1, ..., m, et de plus il existe λ ∈ Rm pour lequel
m
X
∇f (x ∗ ) = λj ∇hj (x ∗ )
j=1

Aboubecrine ([email protected]) M061: Introduction á l’optimisation