MTH1101: Introduction à l’optimisation

DÉFINITIONS
OPTIMISATION SANS CONTRAINTES
MÉTHODE DU GRADIENT
PROBLÈME D’OPTIMISATION AVEC CONTRAINTES

aft
MTH1101: Introduction à l’optimisation

Issmail El Hallaoui
Dr Polytechnique Montréal
Département de Mathématiques et de Génie Industriel

. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Issmail El Hallaoui MTH1101: Introduction à l’optimisation
 MTH1101: Introduction à l’optimisation
DÉFINITIONS
OPTIMISATION SANS CONTRAINTES
MÉTHODE DU GRADIENT
PROBLÈME D’OPTIMISATION AVEC CONTRAINTES

1 DÉFINITIONS

aft
2 OPTIMISATION SANS CONTRAINTES
Conditions d’optimalité
Généralisation de la condition nécessaire du second ordre
Condition suffisante d’optimalité du second d’ordre
Conditions d’optimalité pour les problèmes de maximisation

3 MÉTHODE DU GRADIENT
Dr
4 PROBLÈME D’OPTIMISATION AVEC CONTRAINTES
Définition du problème
Optimisation sous une contrainte d’égalité
Optimisation avec une contrainte d’inégalité
Optimisation avec plusieurs contraintes d’égalité

. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Issmail El Hallaoui MTH1101: Introduction à l’optimisation
 MTH1101: Introduction à l’optimisation
DÉFINITIONS
OPTIMISATION SANS CONTRAINTES
MÉTHODE DU GRADIENT
PROBLÈME D’OPTIMISATION AVEC CONTRAINTES

Minimun global(absolu)

aft
Une solution x∗ est un minimun global(absolu) de la fonction f sur le domaine
S si
f(x∗ ) ≤ f(x) ∀x ∈ S.
La valeur optimale est f(x∗ ).

Soit ϵ > 0
Bϵ (x∗ ) = {x ∈ Rn : ∥x − x∗ ∥ < ϵ}.
Cet ensemble est communément appelé boule de rayon ϵ centrée en x∗ .

Minimun local
Dr
Une solution x∗ est un minimun local de la fonction f sur le domaine S si

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

. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Issmail El Hallaoui MTH1101: Introduction à l’optimisation
 MTH1101: Introduction à l’optimisation
Conditions d’optimalité
DÉFINITIONS
Généralisation de la condition nécessaire du second ordre
OPTIMISATION SANS CONTRAINTES
Condition suffisante d’optimalité du second d’ordre
MÉTHODE DU GRADIENT
Conditions d’optimalité pour les problèmes de maximisation
PROBLÈME D’OPTIMISATION AVEC CONTRAINTES

Dans cette section, nous considérons le problème suivant minx∈Rn f(x). La

fonction f est appelée fonction objectif.

aft
Théorème (Condition nécessaire 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.
Dr
Exemple: déterminer les points critiques de la fonction
f(x, y) = 13 x3 + 43 y3 − x2 − 3x − 4y − 3.

Hessien d’une fonction

Le hessien d’une fonction f au point x0 , noté ∇2 f(x0 ), est la matrice (aij ) où
aij = f′′xi xj (x0 ).

. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Issmail El Hallaoui MTH1101: Introduction à l’optimisation
 MTH1101: Introduction à l’optimisation
Conditions d’optimalité
DÉFINITIONS
Généralisation de la condition nécessaire du second ordre
OPTIMISATION SANS CONTRAINTES
Condition suffisante d’optimalité du second d’ordre
MÉTHODE DU GRADIENT
Conditions d’optimalité pour les problèmes de maximisation
PROBLÈME D’OPTIMISATION AVEC CONTRAINTES

Rappel: définitions

aft
Une matrice A de dimension n × n est dite

Semi-définie positive si yT Ay ≥ 0 ∀y ∈ Rn
Définie positive si yT Ay > 0 ∀y ∈ Rn \{0}
Semi-définie négative si yT Ay ≤ 0 ∀y ∈ Rn
Définie négative si yT Ay < 0 ∀y ∈ Rn \{0}
Dr
Théorème (Condition nécessaire du second ordre: généralisation)
Si x∗ est un minimun local de la fonction f sur Rn , alors ∇f(x∗ ) = 0 et
yT ∇2 f(x∗ )y ≥ 0 ∀y ∈ Rn (i.e la matrice Hessienne ∇2 f(x∗ ) est semi-définie
positive).

. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Issmail El Hallaoui MTH1101: Introduction à l’optimisation
 MTH1101: Introduction à l’optimisation
Conditions d’optimalité
DÉFINITIONS
Généralisation de la condition nécessaire du second ordre
OPTIMISATION SANS CONTRAINTES
Condition suffisante d’optimalité du second d’ordre
MÉTHODE DU GRADIENT
Conditions d’optimalité pour les problèmes de maximisation
PROBLÈME D’OPTIMISATION AVEC CONTRAINTES

aft
Théorème (Condition suffisante du second ordre)
Soit x∗ ∈ Rn . Si ∇f(x∗ ) = 0, et si yT ∇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

Dr
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).

. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Issmail El Hallaoui MTH1101: Introduction à l’optimisation
 MTH1101: Introduction à l’optimisation
Conditions d’optimalité
DÉFINITIONS
Généralisation de la condition nécessaire du second ordre
OPTIMISATION SANS CONTRAINTES
Condition suffisante d’optimalité du second d’ordre
MÉTHODE DU GRADIENT
Conditions d’optimalité pour les problèmes de maximisation
PROBLÈME D’OPTIMISATION AVEC CONTRAINTES

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

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
yT ∇2 f(x∗ )y ≤ 0 ∀y ∈ Rn (i.e la matrice Hessienne ∇2 f(x∗ ) est semi-définie
négative). Dr
Théorème (Condition suffisante du second ordre)
Soit x∗ ∈ Rn . Si ∇f(x∗ ) = 0, et si yT ∇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 la fonction f sur Rn .

. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Issmail El Hallaoui MTH1101: Introduction à l’optimisation
 MTH1101: Introduction à l’optimisation
DÉFINITIONS
OPTIMISATION SANS CONTRAINTES
MÉTHODE DU GRADIENT
PROBLÈME D’OPTIMISATION AVEC CONTRAINTES

METHODE DU GRADIENT(pour un problème de minimisation)

Initialisation:

aft
Soit x0 ∈ Rn un estimé de la solution. Poser le compteur k ← 0.
Trouver une direction de descente:
Calculer la direction dk = −∇f(xk ). Si ∥dk ∥ = 0 alors on termine avec un
point critique xk . Sinon on poursuit à la prochaine étape.
Trouver le pas:
Soit xk+1 la solution produite par la résolution du problème de
minimisation à une variable
Dr min h(α) où
α≥0

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

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). .
. .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.

Issmail El Hallaoui MTH1101: Introduction à l’optimisation

 MTH1101: 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é
MÉTHODE DU GRADIENT
Optimisation avec plusieurs contraintes d’égalité
PROBLÈME D’OPTIMISATION AVEC CONTRAINTES

aft
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.
Dr
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Issmail El Hallaoui MTH1101: Introduction à l’optimisation
 MTH1101: 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é
MÉTHODE DU GRADIENT
Optimisation avec plusieurs contraintes d’égalité
PROBLÈME D’OPTIMISATION AVEC CONTRAINTES

Soient f et h deux fonctions différentiables et k une constante. Soit le problème

aft
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.
Dr
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∗ ) ̸= 0, alors
h(x∗ ) = k, et de plus il existe un scalaire λ ∈ R pour lequel :
∇f(x∗ ) = λ∇h(x∗ ).

. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Issmail El Hallaoui MTH1101: Introduction à l’optimisation
 MTH1101: 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é
MÉTHODE DU GRADIENT
Optimisation avec plusieurs contraintes d’égalité
PROBLÈME D’OPTIMISATION AVEC CONTRAINTES

Soit le problème suivant :

aft
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 à
Dr
S.
Appliquer la méthode du multiplicateur de Lagrange au problème obtenu
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.

. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Issmail El Hallaoui MTH1101: Introduction à l’optimisation
 MTH1101: 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é
MÉTHODE DU GRADIENT
Optimisation avec plusieurs contraintes d’égalité
PROBLÈME D’OPTIMISATION AVEC CONTRAINTES

Soit le problème suivant :

min f (x)

aft
x
s.c x ∈ S
S = {x ∈ Rn : 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)
Dr
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 λ ∈ R pour lequel
∑
m
∇f (x∗ ) = λj ∇hj (x∗ )
j=1

. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Issmail El Hallaoui MTH1101: Introduction à l’optimisation