Minimisation sans contraintes :

Conditions d’Otpimalité

BELGACEM Rachid

UHBC. Uni de Chlef.

5 février 2021

BELGACEM Rachid (UHBC. Uni de Chlef.) Optimisation Sans contraintes 5 février 2021 1 / 34
 Conditions d’otpimalité

Considérons le problème d’optimisation suivant

(
min f (x )
(1)
x ∈ S ⊆ Rn .

BELGACEM Rachid (UHBC. Uni de Chlef.) Optimisation Sans contraintes 5 février 2021 2 / 34
 Direction admissible
Definition (Direction admissible)
On dit qu’un vecteur d ∈ Rn , d 6= 0 est une direction admissible au point
x dans S, s’il existe α0 > 0 tel que x + αd ∈ S pour tout α ∈ [0, α0 ] .

Figure – Illustration en deux dimensions de la direction admissible : d1 est une

direction admissible, d2 n’est pas une direction admissible,
BELGACEM Rachid (UHBC. Uni de Chlef.) Optimisation Sans contraintes 5 février 2021 3 / 34
 Direction admissible

Example
S = (x1 , x2 ) ∈ R2 : x1 , x2 ≥ 0 = R2+ .


1 Pour x = (1, 0)T , l’ensemble des directions admissibles au point x est

l’ensemble D (x ) = d = (d1 , d2 ) ∈ R2 : d2 ≥ 0 .


2 Pour x = (0, 2)T , l’ensemble des directions admissibles au point x est

2

l’ensemble D (x ) = d ∈ R : d1 ≥ 0 .
3 Pour x = (2, 3)T , l’ensemble des directions admissibles au point x est
l’ensemble D (x ) = R2 .

BELGACEM Rachid (UHBC. Uni de Chlef.) Optimisation Sans contraintes 5 février 2021 4 / 34
 Direction admissible

Proposition
Si x ∈ int S, alors D (x ) = Rn .

BELGACEM Rachid (UHBC. Uni de Chlef.) Optimisation Sans contraintes 5 février 2021 5 / 34
 Condition Nécessaire d’optimalité du premier Ordre

Condition Nécessaire d’optimalité du premier Ordre

Theorem (Condition Nécessaire d’optimalité du premier Ordre)
Supposons que f est de classe C 1 , si x ∗ réalise un minimum (global ou
local) pour (1) alors ∀d ∈ D (x ∗ ) : hd, ∇f (x ∗ )i ≥ 0.

Figure – Illustration de CN1 : x1 ne vérifie pas la CN1, mais x2 vérifie la CN1.

BELGACEM Rachid (UHBC. Uni de Chlef.) Optimisation Sans contraintes 5 février 2021 6 / 34
 Condition Nécessaire d’optimalité du premier Ordre

Démonstration.
Soit d ∈ D (x ∗ ). Donc, ∃α0 > 0, ∀α ∈ [0, α0 ] =⇒ x ∗ + αd ∈ S.
Considérons la fonction : ϕ (α) = f (x ∗ + αd) , on a

ϕ (α) = ϕ (0) + αϕ0 (0) + o (α) ,

avec ϕ0 (0) = ∇f (x ∗ )T d = h∇f (x ∗ ) , di . Pour α suffisamment petit, on a

f (x ∗ + αd) ≥ f (x ∗ ) =⇒ α h∇f (x ∗ ) , di + o (α) ≥ 0,

on divise par α et on le fait tendre vers 0, on obtient

h∇f (x ∗ ) , di ≥ 0.

BELGACEM Rachid (UHBC. Uni de Chlef.) Optimisation Sans contraintes 5 février 2021 7 / 34
 Condition Nécessaire d’optimalité du premier Ordre

n
CN1 : S = R

Theorem
Si S = Rn dans le problème (1), f est différentiable et si x ∗ est un
minimum local pour f , alors ∇f (x ∗ ) = 0.

Démonstration.
D’aprés le théorème précédent, on a ∀d ∈ D (x ∗ ) = Rn : h∇f (x ∗ ) , di ≥ 0,
donc h∇f (x ∗ ) , di = 0 pour tout d ∈ Rn , ce qui implique que
∇f (x ∗ ) = 0.

Definition
Un point x ∗ de Rn vérifiant ∇f (x ∗ ) = 0 est appelé point critique ou point
stationnaire .

BELGACEM Rachid (UHBC. Uni de Chlef.) Optimisation Sans contraintes 5 février 2021 8 / 34
 Condition Nécessaire d’optimalité du premier Ordre

La relation ∇f (x ∗ ) = 0 est aussi appelée équation d’Euler.

Ce théorème n’a pas de sens si la fonction f n’est pas différentiable comme
le montre dans la figure suivant

Figure – Minimum d’une fonction non différentiable.

BELGACEM Rachid (UHBC. Uni de Chlef.) Optimisation Sans contraintes 5 février 2021 9 / 34
 Condition Nécessaire d’optimalité du premier Ordre

La relation ∇f (x ∗ ) = 0 est aussi appelée équation d’Euler.

Ce théorème n’a pas de sens si la fonction f n’est pas différentiable comme
le montre dans la figure suivant

Figure – Minimum d’une fonction non différentiable.

BELGACEM Rachid (UHBC. Uni de Chlef.) Optimisation Sans contraintes 5 février 2021 9 / 34
 Condition Nécessaire d’optimalité du premier Ordre

Toutefois, la réciproque de ce théorème est fausse comme le voir dans la

figure. Cela signifie que le point critique n’est pas nécessairement un
minimum global. Ce peut-être un minimum local ( point B), un maximum
local (point C) ou ni l’un, ni l’autre ( point A).

Figure – Points critiques non optimaux.

BELGACEM Rachid (UHBC. Uni de Chlef.) Optimisation Sans contraintes 5 février 2021 10 / 34
 Condition Nécessaire d’optimalité du premier Ordre

Le résultat de ce théorème, est une condition nécessaire qui n’est en général

pas suffisante (cf. la fonction f de R dans R définie par f (x ) = x 3 ).

Figure – x ∗ = 0 vérifie la CN1 mais n’est pas un minimum de f .

BELGACEM Rachid (UHBC. Uni de Chlef.) Optimisation Sans contraintes 5 février 2021 11 / 34
 Condition Nécessaire d’optimalité du premier Ordre

Figure – Point-selle en P

BELGACEM Rachid (UHBC. Uni de Chlef.) Optimisation Sans contraintes 5 février 2021 12 / 34
 Condition Nécessaire et suffisante d’Ordre 1 Condition Nécessaire et suffisante d’Ordre 1

Condition Nécessaire et suffisante d’Ordre 1

Theorem (CNS1)
Soit f une fonction de classe C 1 et f est convexe sur l’ouvert convexe S,
alors x ∗ est un minimum global pour (1) si et seulement si
hx − x ∗ , ∇f (x ∗ )i ≥ 0, ∀x ∈ S.

Theorem (CNS1 : S = Rn )
Soit f : Rn −→ R, une fonction de classe C 1 et soit f est convexe sur Rn ,
alors x ∗ est un minimum global de f sur Rn si et seulement si ∇f (x ∗ ) = 0.

BELGACEM Rachid (UHBC. Uni de Chlef.) Optimisation Sans contraintes 5 février 2021 13 / 34
 Condition Nécessaire et suffisante d’Ordre 1 Condition Nécessaire et suffisante d’Ordre 1

Exercice

Exercice
On se donne le problème d’optimisation
(
min f (x ) = x12 + 12 x22 + 3x2 + 9
2
x1 ≥ 0 et x2 ≥ 0

1 La CN du Premier ordre pour un minimum local est-elles vérifier au

point x = [1, 3]> ?
2 La CN du Premier ordre pour un minimum local est-elles vérifier au
point x = [0, 3]> ?
3 La CN du Premier ordre pour un minimum local est-elles vérifier au
point x = [1, 0]> ?
4 La CN du Premier ordre pour un minimum local est-elles vérifier au
point x = [0, 0]> ?

BELGACEM Rachid (UHBC. Uni de Chlef.) Optimisation Sans contraintes 5 février 2021 14 / 34
 Condition Nécessaire et suffisante d’Ordre 1 Condition Nécessaire et suffisante d’Ordre 1

Corrigé
Soient f (x ) = x12 + 12 x22 + 3x2 + 9
2 et Ω = R2+ .
On a " #
2x1
∇f (x ) = .
x2 + 3
" # " #
1 2
. Pour x ∗ = , D (x ∗ ) = R2 , dans ce cas ∇f (x ∗ ) = 6 0R2 .
=
3 6
Donc, x ∗ ne" vérifie
# pas la condition nécessaire d’ordre 1.
0
. Pour x ∗ = on a D (x ∗ ) = d = (d1 , d2 ) ∈ R2 : d1 ≥ 0 et

3
" # " #
0 d1
∇f (x ∗ ) = . Donc, h∇f (x ∗ ) , di = 6d2 où d = . Pour
6 d2
que d soit admissible au x ∗ il suffit de prendre d1 ≥ 0 et d2 ∈ R. On
conclus que x ∗ ne vérifie pas la condition nécessaire
" # d’ordre 1 car d2
2
peut prendre des valeurs négatives i.g. d = admissible mais
−9
h∇f (x ∗ ) , di
" =#6 (−9) < 0.
BELGACEM Rachid (UHBC. Uni de Chlef.) Optimisation Sans contraintes 5 février 2021 15 / 34
 Condition Nécessaire et suffisante d’Ordre 1 Condition Nécessaire et suffisante d’Ordre 1

Corrigé

" #
1
x∗ , D (x ∗ ) = d = (d1 , d2 ) ∈ R2 : d1 ≥ 0 et

. Pour =
0
" # " #
0 −12
∇f (x ∗ ) = . On a h∇f (x ∗ ) , di = 2d1 + 3d2 , soit d =
6 5
admissible par contre h∇f (x ) , di = 2 (−12) + 3 (5) < 0 alors x ∗ ne
∗

vérifie pas la condition nécessaire d’ordre 1.

" #
0
x∗ , D (x ∗ ) = d = (d1 , d2 ) ∈ R2 : d1 , d2 ≥ 0 et

. Pour =
0
" #
0
∇f (x ∗ )
= . On a h∇f (x ∗ ) , di = 3d2 ≥ 0 alors x ∗ vérifie la
3
condition nécessaire d’ordre 1.

BELGACEM Rachid (UHBC. Uni de Chlef.) Optimisation Sans contraintes 5 février 2021 16 / 34
 Condition Nécessaire d’Ordre 2 Condition Nécessaire d’Ordre 2

Condition Nécessaire d’Ordre 2

Theorem (CN2)
Soient f est de classe C 2 , x ∗ est un minimum local pour (1) et d ∈ D (x ∗ ).
Si hd, ∇f (x ∗ )i = 0 alors d, ∇2 f (x ∗ ) d ≥ 0.

BELGACEM Rachid (UHBC. Uni de Chlef.) Optimisation Sans contraintes 5 février 2021 17 / 34
 Condition Nécessaire d’Ordre 2 Condition Nécessaire d’Ordre 2

Démonstration.
Raisonnons par l’absurde. Supposons qu’il existe d admissible au point x ∗
tel que hd, ∇f (x ∗ )i = 0 et d, ∇2 f (x ∗ ) d < 0. On a

α2 D E  
f (x ∗ + αd) = f (x ∗ ) + α hd, ∇f (x ∗ )i + d, ∇2 f (x ∗ ) d + o α2 ,
2
donc,

α2 D E  
f (x ∗ + αd) − f (x ∗ ) = α hd, ∇f (x ∗ )i + d, ∇2 f (x ∗ ) d + o α2 ,
2
pour α assez petit, on obtient

f (x ∗ + αd) − f (x ∗ ) < 0.

c’est une contradiction avec le fait que x ∗ minimum local.

BELGACEM Rachid (UHBC. Uni de Chlef.) Optimisation Sans contraintes 5 février 2021 18 / 34
 Condition Nécessaire d’Ordre 2 Condition Nécessaire d’Ordre 2

n
CN2 : S = R

◦
Corollaire (x ∗ ∈ S)
Soit f ∈ C 2 , x ∗ réalise un minimum local pour de f sur Rn alors
(
∇f (x ∗ ) = 0
d, ∇2 f (x ∗ ) d ≥ 0, ∀d ∈ Rn .

BELGACEM Rachid (UHBC. Uni de Chlef.) Optimisation Sans contraintes 5 février 2021 19 / 34
 Condition Nécessaire d’Ordre 2 Condition Nécessaire d’Ordre 2

Example
" #
0
Soit f (x ) = x12 − x22 et S = R2 . Pour x ∗ = on a ∇f (x ∗ ) = 0R2 et
0
" #
2 0
∇2 f (x ∗ )
= . On remarque que ∇2 f (x ∗ ) n’est pas semi définie
0 −2
positive alors x ∗ n’est pas un minimum local.

BELGACEM Rachid (UHBC. Uni de Chlef.) Optimisation Sans contraintes 5 février 2021 20 / 34
 CNS2

Condition Nécessaire et suffisante d’Ordre 2

Theorem (Condition Nécessaire et suffisante d’Ordre 2)

Soit f une fonction de classe C 2 , si on suppose que x ∗ vérifie
(
∇f (x ∗ ) = 0
d, ∇2 f (x ∗ ) d > 0, ∀d ∈ Rn+ .

Alors x ∗ est un minimum local strict.

BELGACEM Rachid (UHBC. Uni de Chlef.) Optimisation Sans contraintes 5 février 2021 21 / 34
 CNS2

Résultat général

∂2f ∂2f ∂2f

 
∂x12
(x ) ∂x2 ∂x1 (x ) ... ∂xn ∂x1 (x )
 
∂2f ∂2f ∂2f
∂x1 ∂x2 (x ) (x ) ... ∂xn x2 (x )
 
2
 ∂x22 
Hf = ∇ f (x ) =  .. ..
.
 .. 

 . . . ... 

∂2f ∂2f ∂2f
∂x1 xn (x ) ∂x2 xn (x ) ... ∂xn2
(x )
Dans le cas général, la recherche des extrema d’une fonction à plusieurs
variables est basée sur le résultat suivant

BELGACEM Rachid (UHBC. Uni de Chlef.) Optimisation Sans contraintes 5 février 2021 22 / 34
 CNS2

Résultat général
Soit P le point en lequel
∂f ∂f ∂f
= = ... = = 0.
∂x1 ∂x2 ∂xn
Alors
1 Si les mineures principaux de la matrice Hf au point P sont tout
strictement positifs, il s’agit d’un minimum.
2 Si les mineures principaux de la matrice Hf au point P sont de signe
alternés, le premier étant strictement négative, il s’agit d’un maximum.
3 Si les mineures ne vérifient pas l’une des conditions ci-dessus prises au
sens large, il ne s’agit ni d’un minimum ni d’un maximum, mais d’un
point-selle.
4 Si les conditions 1 et 2 se vérifient au sens large, alors on ne peut pas
conclure.

BELGACEM Rachid (UHBC. Uni de Chlef.) Optimisation Sans contraintes 5 février 2021 23 / 34
 CNS2

Dans le cas de fonctions à deux variables, on trouve

∂2f ∂2f
 
∂x12
(x ) ∂x2 ∂x1 (x )
Hf = ∇2 f (x ) =  2
∂ f ∂2f
.
∂x1 ∂x2 (x ) ∂x22
(x )

∂2f
∆1 = (x ) ,
∂x12
!2
∂2f ∂2f ∂2f
∆2 = (x ) (x ) − (x ) ,
∂x12 ∂x22 ∂x2 ∂x1

Ainsi
1 ∆1 > 0 et ∆2 > 0 −→ minimum.
2 ∆1 < 0 et ∆2 > 0 −→ maximum.
3 ∆1 quelconque et ∆2 < 0 −→ point-selle.
4 ∆1 quelconque et ∆2 = 0 −→ on ne peut pas conclure.
BELGACEM Rachid (UHBC. Uni de Chlef.) Optimisation Sans contraintes 5 février 2021 24 / 34
 CNS2

Exemple 1
Soit la fonction f (x , y ) = x 2 + y 2 .

∂f
(x ) = 2x = 0 =⇒ x = 0,
∂x
∂f
(y ) = 2y = 0 =⇒ y = 0,
∂x

il existe donc un point candidat en x ∗ = y ∗ = 0 ; ce point est forcément un

minimum puisque la matrice hessienne est définie positive. En effet
!
2 ∗ ∗ 2 0
Hf = ∇ f (x , y ) = .
0 2

Ici, ∆1 = 2 > 0 et ∆2 = 4 > 0. Par conséquent, f possède un minimum en

(x ∗ , y ∗ ) = (0, 0).

BELGACEM Rachid (UHBC. Uni de Chlef.) Optimisation Sans contraintes 5 février 2021 25 / 34
 CNS2

Figure – Graphe de z = f (x , y ) = x 2 + y 2

BELGACEM Rachid (UHBC. Uni de Chlef.) Optimisation Sans contraintes 5 février 2021 26 / 34
 CNS2

Exercice 1

Exercice

2
Soit la fonction f (x ) = 100 x2 − x12 + (1 − x1 )2 et les points
a = (1, 1)> et b = (−1, 2)> .
1 Calculer f (a), f (b), ∇f (a) et ∇f (b).
2 Discuter les conditions d’optimalité en a et en b sur la base des
résultats obtenus en (1) .
3 La direction d = a − b est-elle une direction de descente en b? Justifier.

BELGACEM Rachid (UHBC. Uni de Chlef.) Optimisation Sans contraintes 5 février 2021 27 / 34
 CNS2

Corrigé 1

1 f (a) = 0, f (b) = 104, ∇f (a) = (0, 0)> , ∇f (b) = (396, 200)>

2 ∇f (a) = 0 =⇒ a peut être un point extrême. ∇f (b) 6= 0 =⇒ b ne
peut pas être un point extrême.
3 d = a − b = (2, −1)> =⇒ h∇f (b), di = 592 > 0 Ça veut dire que d
est une direction pas descente en b.

BELGACEM Rachid (UHBC. Uni de Chlef.) Optimisation Sans contraintes 5 février 2021 28 / 34
 CNS2

Exercice 2

Exercice
On considère le problème de minimisation sur R2 , de la fonction g définie
par la relation :

∀ (x1 , x2 ) ∈ R2 , g(x1 , x2 ) = x12 + x22 + x1 x2

1 Montrer que la fonction g est coercive.

2 Montrer que la fonction g est strictement convexe sur R2 .
3 En déduire que g possède un unique minimum sur R2 et le déterminer.

BELGACEM Rachid (UHBC. Uni de Chlef.) Optimisation Sans contraintes 5 février 2021 29 / 34
 CNS2

Corrigé 2
1 On a :
2
x1 + x2 x12 x22 x2 x2 1

g(x1 , x2 ) = √ + + ≥ 1 + 2 = k(x1 , x2 )k2
2 2 2 2 2 2
et la fonction donc est coercive.
2
! hessienne de g en tout point x ∈ R est égale à
La matrice
2

2 1
. Cette matrice est définie positive (par le critère de
1 2
Sylvester par exemple) et donc g est strictement convexe.
3 g est continue et coercive donc possède au moins un minimum sur R2 .
De plus, g est strictement convexe donc ce minimum est unique. Ce
minimum est à rechercher parmi les points critiques : ceux ci sont tels
que : (
2x1 + x2 = 0
x1 + 2x2 = 0
soit x1 = x2 = 0. Il s’agit donc un minimum de g.
BELGACEM Rachid (UHBC. Uni de Chlef.) Optimisation Sans contraintes 5 février 2021 30 / 34
 CNS2

Exercice 3
Exercice
On se place dans R2 , et on note x = (x1 , x2 ) . On considère la fonction f de
R2 dans R définie par :
1 1 2 
f (x ) = hx , Bx i + hx , bi = x1 + αx22 + x1
2 2
où B et une matrice symétrique 2 × 2, b un vecteur de R2 et α ∈ R.
1 Préciser B et b, calculer ∇f (x ).
2 Donner une condition nécessaire pour que x soit minimum (lacal) de f .
1 Si α = 0, montrer que f possède un minimum et qu’il y a une infinité de
x réalisant ce minimum.
2 Si α 6= 0, quel est l’élément x ∗ pouvant éventuellement réaliser le
minimum ?
3 Si α > 0, x ∗ réalise-t-il le minimum de f ? pourquoi ?
4 Si α < 0, montrer que f ne possède pas de minimum.

BELGACEM Rachid (UHBC. Uni de Chlef.) Optimisation Sans contraintes 5 février 2021 31 / 34
 CNS2

Corrigé 3
1 Précisions B et b : !
x1 +1
1 0
∇f (x1 , x2 )= αx2 , ∇2 f (x1 , x2 )=
0 α
! ! !
1 0 x1 x1
(x1 , x2 ) = (x1 , x2 ) = x12 + αx22
0 α x2 αx2
!
1 0 1

D’où, B = H = et b = 0
0 α
(
x1 = −1
2 ∇f (x ) = 0 ⇐⇒
αx2 = 0

x1 = −1
1 Si α = 0 =⇒ il y a une infinité de solutions
∀x2

x1 = −1
2 Si α 6= 0 =⇒ =⇒ x ∗ = (−1, 0)
x2 = 0
3 Si α > 0 =⇒ x ∗ = (−1, 0) est un minimum local strict, car H est
définié positive.
4 Si α < 0, f ne possède pas de minimum car :la matrice H n’est pas semi
définié positive.
BELGACEM Rachid (UHBC. Uni de Chlef.) Optimisation Sans contraintes 5 février 2021 32 / 34
 CNS2

Exercice 4

Exercice
Soit
f (x , y ) = x 3 + y 3 − 3xy
1 Trouver tous les points (xb, yb ) ∈ R2 tels que ∇f (xb, yb )T = (0, 0) .
2 Parmi les points (xb, yb ) ∈ R2 tels que ∇f (xb, yb )T = (0, 0) , trouvez
ceux qui sont des solutions optimales locales strictes et celles qui ne
sont pas des solutions optimales locales strictes. Justifiez votre réponse.

BELGACEM Rachid (UHBC. Uni de Chlef.) Optimisation Sans contraintes 5 février 2021 33 / 34
 CNS2

Corrigé 4
1 Calculons les points stationnaires
( : (
3x 2 − 3y = 0 x2 − y = 0
T
∇f (x , y ) = (0, 0) ⇔ ⇔
3y 2 − 3x = 0 y2 − x = 0
Les solution de ce système sont (xb!1 , yb1 ) = (0, 0) et (xb2 , yb2 ) = (1, 1) .
6x −3
2 On a : ∇2 f (x , y ) = ,
−3 6y
1 pour (b
x1 , yb1 ) = (0, 0) , on a
 
2 0 −3
∇ f (b x1 , yb1 ) = est semi définie positive.
−3 0
Donc (0, 0) n’est pas une solution maximale locale et n’est pas une
solution minimale locale.
2 pour (bx2 , yb2 ) = (1, 1) , on a
 
6 −3
∇2 f (bx2 , yb2 ) = est définie positive.
−3 6
Donc (1, 1) est une solution minimale locale stricte.
BELGACEM Rachid (UHBC. Uni de Chlef.) Optimisation Sans contraintes 5 février 2021 34 / 34