Conditions d’optimalité

Problème d’optimisation avec contraintes

22 octobre 2019

Conditions d’optimalité Problème d’optimisation avec contrainte

3.1 Conditions d’optimalité :

On considère le problème d’optimisation très général de la forme :

(P) : " min f(x) , sc : x ∈ X "

où X ⊂ Rp est non vide et f : X → R différentiable.

Conditions d’optimalité Problème d’optimisation avec contrainte

3.1 Conditions d’optimalité :

Nous donnons une condition d’optimalité du problème (P) , puis

nous explicitons cette condition dans les cas suivants :
1) X ouvert de Rp
2) X convexe de Rp
3) X défini par des égalités ou des inégalités

Conditions d’optimalité Problème d’optimisation avec contrainte

3.1 Conditions d’optimalité :

Définition 3.1 Soient X ⊂ Rp , x ∈ X et d ∈ Rp . d est dite

direction admissible en x si et seulement si

∃η > 0, ∀t ∈]0, η] , x + td ∈ X .

Conditions d’optimalité Problème d’optimisation avec contrainte

3.1 Conditions d’optimalité :

Définition 3.2 Soient X ⊂ Rp et x ∈ X. On appelle cône tangent

à X en x (noté Tx (X)), l’ensemble des vecteurs v ∈ Rp tels que :

∃vn ∈ Rp , ∃εn > 0 vérifiant : lim vn = v et lim εn = 0 tels

n→+∞ n→+∞
que εn vn + x ∈ X.

image.png
Autrement dit : le cône tangent est l’ensemble des directions
admissibles dans X en x, ainsi que les limites de ces directions.

Conditions d’optimalité Problème d’optimisation avec contrainte

3.1 Conditions d’optimalité :

Proposition 3.3 Soit X ⊂ Rp tel que X̊ 6= ∅ et x ∈ X . Alors :

Conditions d’optimalité Problème d’optimisation avec contrainte

3.1 Conditions d’optimalité :

Proposition 3.3 Soit X ⊂ Rp tel que X̊ 6= ∅ et x ∈ X . Alors :

1) Tx (X) est un cône fermé.

Conditions d’optimalité Problème d’optimisation avec contrainte

3.1 Conditions d’optimalité :

Proposition 3.3 Soit X ⊂ Rp tel que X̊ 6= ∅ et x ∈ X . Alors :

1) Tx (X) est un cône fermé.
2) x ∈
/ X ⇒ Tx (X) = ∅.

Conditions d’optimalité Problème d’optimisation avec contrainte

3.1 Conditions d’optimalité :

Proposition 3.3 Soit X ⊂ Rp tel que X̊ 6= ∅ et x ∈ X . Alors :

1) Tx (X) est un cône fermé.
2) x ∈
/ X ⇒ Tx (X) = ∅.
3) x ∈ X̊ ⇒ Tx (X) = Rp .

Conditions d’optimalité Problème d’optimisation avec contrainte

3.1 Conditions d’optimalité :

Théorème 3.4 Soit X ⊂ Rp et f : X → R une fonction

différentiable et x ∗ est un point de minimum local de f alors :

∀v ∈ Tx ∗ (X), < ∇f (x ∗ ), v >≥ 0 .

Conditions d’optimalité Problème d’optimisation avec contrainte

3.1 Conditions d’optimalité :
Preuve. Soit v ∈ Tx ∗ (X), v 6= 0 alors ∃vn −→ v et εn −→ 0 tels
que :

xn = x ∗ + εn vn ∈ X .

Conditions d’optimalité Problème d’optimisation avec contrainte

3.1 Conditions d’optimalité :
Preuve. Soit v ∈ Tx ∗ (X), v 6= 0 alors ∃vn −→ v et εn −→ 0 tels
que :

xn = x ∗ + εn vn ∈ X .

Pour n assez grand , xn est au voisinage de x ∗ , si bien que

par l’optimalité local en x ∗ , on a :
f (x ∗ + εn vn ) ≥ f (x ∗ ) .

Conditions d’optimalité Problème d’optimisation avec contrainte

3.1 Conditions d’optimalité :
Preuve. Soit v ∈ Tx ∗ (X), v 6= 0 alors ∃vn −→ v et εn −→ 0 tels
que :

xn = x ∗ + εn vn ∈ X .

Pour n assez grand , xn est au voisinage de x ∗ , si bien que

par l’optimalité local en x ∗ , on a :
f (x ∗ + εn vn ) ≥ f (x ∗ ) .
f est différentiable en x ∗ , donc
f (x ∗ + εn vn )=f (x ∗ )+ < ∇f (x ∗ ), εn vn > +kεn vn kε(εn vn )

Conditions d’optimalité Problème d’optimisation avec contrainte

3.1 Conditions d’optimalité :
Preuve. Soit v ∈ Tx ∗ (X), v 6= 0 alors ∃vn −→ v et εn −→ 0 tels
que :

xn = x ∗ + εn vn ∈ X .

Pour n assez grand , xn est au voisinage de x ∗ , si bien que

par l’optimalité local en x ∗ , on a :
f (x ∗ + εn vn ) ≥ f (x ∗ ) .
f est différentiable en x ∗ , donc
f (x ∗ + εn vn )=f (x ∗ )+ < ∇f (x ∗ ), εn vn > +kεn vn kε(εn vn )
Donc :
f (x ∗ + εn vn ) − f (x ∗ )
εn = < ∇f (x ∗ ), vn > +kvn kε(εn vn ) ≥ 0.

Conditions d’optimalité Problème d’optimisation avec contrainte

3.1 Conditions d’optimalité :
Preuve. Soit v ∈ Tx ∗ (X), v 6= 0 alors ∃vn −→ v et εn −→ 0 tels
que :

xn = x ∗ + εn vn ∈ X .

Pour n assez grand , xn est au voisinage de x ∗ , si bien que

par l’optimalité local en x ∗ , on a :
f (x ∗ + εn vn ) ≥ f (x ∗ ) .
f est différentiable en x ∗ , donc
f (x ∗ + εn vn )=f (x ∗ )+ < ∇f (x ∗ ), εn vn > +kεn vn kε(εn vn )
Donc :
f (x ∗ + εn vn ) − f (x ∗ )
εn = < ∇f (x ∗ ), vn > +kvn kε(εn vn ) ≥ 0.
En faisant tendre n vers +∞ on obtient :
< ∇f (x ∗ ), v >≥ 0
Conditions d’optimalité Problème d’optimisation avec contrainte
3.1 Conditions d’optimalité :

Corollaire 3.5 Soit f : X → R une fonction différentiable .

a) Soit X un convexe de Rp et x ∗ un minimum local de f alors :

∀x ∈ X, < ∇f (x ∗ ), x − x ∗ >≥ 0 (1)

b) Si f est convexe sur X convexe alors (1) est une condition
suffisante pour que x ∗ soit un minimum global de f sur X.

Conditions d’optimalité Problème d’optimisation avec contrainte

3.1 Conditions d’optimalité :

Preuve.
a) ∀x ∈ X , x − x ∗ ∈ Tx ∗ (X). En effet , On a :

x , x ∗ ∈ X =⇒ ∀t ∈ [0, 1], tx + (1 − t)x ∗ ∈ X

=⇒ x ∗ + t(x − x ∗ ) ∈ X
=⇒ x − x ∗ ∈ Tx ∗ (X)

Conditions d’optimalité Problème d’optimisation avec contrainte

3.1 Conditions d’optimalité :

Preuve.
a) ∀x ∈ X , x − x ∗ ∈ Tx ∗ (X). En effet , On a :

x , x ∗ ∈ X =⇒ ∀t ∈ [0, 1], tx + (1 − t)x ∗ ∈ X

=⇒ x ∗ + t(x − x ∗ ) ∈ X
=⇒ x − x ∗ ∈ Tx ∗ (X)
b) Comme f est convexe alors ∀x , y ∈ X ,
f (y ) ≥ f (x )+ < ∇f (x ), y − x >
Pour x = x ∗ on aura :
f (y ) ≥ f (x ∗ )+ < ∇f (x ∗ ), x − x ∗ >
On a : < ∇f (x ∗ ), x − x ∗ >≥ 0 , donc ∀y ∈ X,
f (y ) ≥ f (x ∗ )
D’où x ∗ est un minimum absolu de f sur X.

Conditions d’optimalité Problème d’optimisation avec contrainte

3.1 Conditions d’optimalité :

Corollaire 3.6 Soit X un ouvert de Rp et f : X → R. Si x ∗ est un

minimum local de f sur X alors

∇f (x ∗ ) = 0 .

Conditions d’optimalité Problème d’optimisation avec contrainte

3.1 Conditions d’optimalité :

Preuve. D’après la proposition 3.3, On a

x ∗ ∈ X = X̊ ⇒ Tx ∗ (X) = Rp .

D’après le théorème 3.4 :

∀v ∈ Rp , < ∇f (x ∗ ), v >≥ 0.

Conditions d’optimalité Problème d’optimisation avec contrainte

3.1 Conditions d’optimalité :

Preuve. D’après la proposition 3.3, On a

x ∗ ∈ X = X̊ ⇒ Tx ∗ (X) = Rp .

D’après le théorème 3.4 :

∀v ∈ Rp , < ∇f (x ∗ ), v >≥ 0.

En remplace v par -v on obtient :

< ∇f (x ∗ ), −v >≥ 0 .
Donc :
∀v ∈ Rp , < ∇f (x ∗ ), v >= 0 ⇒ ∇f (x ∗ ) = 0 .

Conditions d’optimalité Problème d’optimisation avec contrainte

3.2 Condition d’optimisation pour les poblèmes avec
contraintes d’égalités :
Dans cette section , on étudie le problème d’optimisation convexe
sous contraintes d’égalités qu’on peut formuler comme suit :


 min f (x ),


(PE ) : x ∈ Rp ,



hi (x ) = 0, i = 1, ...., n.


Conditions d’optimalité Problème d’optimisation avec contrainte

3.2 Condition d’optimisation pour les poblèmes avec
contraintes d’égalités :
Dans cette section , on étudie le problème d’optimisation convexe
sous contraintes d’égalités qu’on peut formuler comme suit :


 min f (x ),


(PE ) : x ∈ Rp ,



hi (x ) = 0, i = 1, ...., n.


On note X le domaine admissible défini par :

X = {x ∈ R p : hi (x ) = 0, i = 1, ...., n}
= {x ∈ R p : h(x ) = 0}

où h : R p → R n , avec h(x ) = (h1 (x ), ...., hn (x ))

Conditions d’optimalité Problème d’optimisation avec contrainte
3.2 Condition d’optimisation pour les poblèmes avec
contraintes d’égalités :

Étape 1 : Qualification des contraintes d’égalité .

Définition 3.7 : La contrainte 00 h(x ) = 000 du problème (PE ) est
dite qualifiée en x ∈ X si h est différentiable en x et si :

Tx (X ) = { v ∈ R p / < ∇hi (x ), v >= 0 ; i = 1, ...., n } = KerJh(x )

(2)
En pratique, (2) est difficile à vérifier,

Conditions d’optimalité Problème d’optimisation avec contrainte

3.2 Condition d’optimisation pour les poblèmes avec
contraintes d’égalités :

Définition 3.8 : Soit x ∈ X , on suppose que h est de classe C 1 au

voisinage de x. On dit que les contraintes de (PE ) sont régulières
en x ou que x est régulier si Jh(x) est surjective :

Conditions d’optimalité Problème d’optimisation avec contrainte

3.2 Condition d’optimisation pour les poblèmes avec
contraintes d’égalités :

Définition 3.8 : Soit x ∈ X , on suppose que h est de classe C 1 au

voisinage de x. On dit que les contraintes de (PE ) sont régulières
en x ou que x est régulier si Jh(x) est surjective :
Proposition 3.9 : Le point x ∈ X est régulier, si et seulement
si :
S = { ∇hi (x ) ; i = 1, ...., n}
est libre.

Conditions d’optimalité Problème d’optimisation avec contrainte

3.2 Condition d’optimisation pour les poblèmes avec
contraintes d’égalités :

Définition 3.8 : Soit x ∈ X , on suppose que h est de classe C 1 au

voisinage de x. On dit que les contraintes de (PE ) sont régulières
en x ou que x est régulier si Jh(x) est surjective :
Proposition 3.9 : Le point x ∈ X est régulier, si et seulement
si :
S = { ∇hi (x ) ; i = 1, ...., n}
est libre.
Proposition 3.10 : Soit x ∈ X . Si x est régulier, alors les
contraintes d’égalité ” h = 0 ” sont qualifiées au point x c’est
à dire :
Tx (X ) = KerJh(x ).

Conditions d’optimalité Problème d’optimisation avec contrainte

3.2 Condition d’optimisation pour les poblèmes avec
contraintes d’égalités :

Étape 2 : condition nécessaire d’optimalité

Théorème 3.11 ( Théorème de Lagrange )
Soient f : R p → R et h : R p → R n sont différentiables en x ∗ .
Supposons que la contrainte 00 h(x ) = 000 est qualifiée en x ∗ . Si x ∗
est un point de minimum local de f sur X, alors il existe des réels
λ∗1 , ...., λ∗n , tels que :
i=n
∇f (x ∗ ) + λ∗i ∇hi (x ∗ ) = 0.
X
(3)
i=1

Le vecteur λ∗ = (λ∗1 , ...., λ∗n )T est appelé multiplicateur de

Lagrange et est determiné de façon unique .

Conditions d’optimalité Problème d’optimisation avec contrainte

3.2 Condition d’optimisation pour les poblèmes avec
contraintes d’égalités :

Terminologie :

1) Le point λ∗ est aussi appelé solution duale de (PE ) . x ∗

solution primale de (PE ) et ( x ∗ , λ∗ ) solution primale - duale
de (PE ) .
2) On appelle point stationnaire du (PE ) , tout point x vérifiant
les conditions nécessaire d’optimalité du premier ordre :
 Pp
 ∇f (x ) + i=1 λi ∇hi (x ) = 0



 h(x ) = 0

Conditions d’optimalité Problème d’optimisation avec contrainte

3.3. Condition d’optimalité pour les problèmes avec
contraintes d’inégalités :



 min f (x ),


(PI ) : x ∈ Rp ,



gj (x ) ≤ 0, j = 1, ...., m.


On note X le domaine admissible défini par :

X = {x ∈ R p : gj (x ) ≤ 0, j = 1, ...., m}
= {x ∈ R p : g(x ) ≤ 0}

où g : R p → R m , avec g(x ) = (g1 (x ), ...., gm (x ))

Conditions d’optimalité Problème d’optimisation avec contrainte

3.3. Condition d’optimalité pour les problèmes avec
contraintes d’inégalités :

Étape 1 : Qualification des contraintes d’inégalité .

Définition 3.12 : La contrainte 00 g(x ) ≤ 000 du problème (PI ) est
dite qualifiée en x ∈ X si g est différentiable en x et si :

Tx (X ) = {v ∈ R p : pour tout j actif en x , < ∇gj(x ), v > ≤ 0}

(4)

Conditions d’optimalité Problème d’optimisation avec contrainte

3.3. Condition d’optimalité pour les problèmes avec
contraintes d’inégalités :

Étape 1 : Qualification des contraintes d’inégalité .

Définition 3.12 : La contrainte 00 g(x ) ≤ 000 du problème (PI ) est
dite qualifiée en x ∈ X si g est différentiable en x et si :

Tx (X ) = {v ∈ R p : pour tout j actif en x , < ∇gj(x ), v > ≤ 0}

(4)
On dit que j est actif en x ou la contrainte gj est active en x si
et seulement si
gj (x ) = 0
En pratique, (4) est difficile à vérifier,

Conditions d’optimalité Problème d’optimisation avec contrainte

3.3. Condition d’optimalité pour les problèmes avec
contraintes d’inégalités :

Une autre condition suffisante est souvent utilisée en pratique :

Proposition 3.13 : La contrainte 00 g(x ) ≤ 000 du problème (PI )
est qualifiée en x ∈ X si les gradients des contraintes actives en x
sont libres .
Dans le cas convexe , on a :

Conditions d’optimalité Problème d’optimisation avec contrainte

3.3. Condition d’optimalité pour les problèmes avec
contraintes d’inégalités :

Une autre condition suffisante est souvent utilisée en pratique :

Proposition 3.13 : La contrainte 00 g(x ) ≤ 000 du problème (PI )
est qualifiée en x ∈ X si les gradients des contraintes actives en x
sont libres .
Dans le cas convexe , on a :
Proposition 3.14 : Si les fonctions gj , j = 1, ......, m sont
convexes , alors La contrainte 00 g(x ) ≤ 000 du problème (PI )
est qualifiée en tout point de X , s’il existe x0 ∈ X tel que
pour tout j = 1, ......, m on a :
• Soit gj (x0 ) < 0.

• Soit gj est affines .

Conditions d’optimalité Problème d’optimisation avec contrainte

3.3. Condition d’optimalité pour les problèmes avec
contraintes d’inégalités :

Étape 2 : Condition necessaire d’optimalité :

Si x est solution du problème (PI ) et si ces contraintes sont
qualifiées en x (au sens de la proposition 3.13) , alors la condition
nécessaire d’optimalité :

∀v ∈ Tx (X), < ∇f (x ), v >≥ 0 (5)

s’écrit :

∀v ∈ R p , [∀j actif en x , < ∇gj (x ), v >≤ 0] =⇒< ∇f (x ), v >≥ 0

En utilisant le lemme de Farkas :

Conditions d’optimalité Problème d’optimisation avec contrainte

3.3. Condition d’optimalité pour les problèmes avec
contraintes d’inégalités :

Lemme 3.15 : (Lemme de Farkas) soient v1 , ...., vl un enssemble

de vecteurs de R p et u ∈ R p . Alors les propositions suivantes sont
équivalentes :
( i ) ∀x ∈ R n , [∀j = 1, ...., l, < vj , x >≤ 0] =⇒< u, x >≥ 0
( ii ) Il existe des réels λ1 , ...., λl > 0 tels que :

j=l
X
u=− λj vj
j=1

On obtient alors :

Conditions d’optimalité Problème d’optimisation avec contrainte

3.3. Condition d’optimalité pour les problèmes avec
contraintes d’inégalités :

Théorème 3.16 : ( CN d’optimalité du 1er ordre sous contraintes

d’inégalités )
Soit x ∗ ∈ X , supposons f et g différentiables en x ∗ et les
contraintes qualifiées en x ∗ . Si x ∗ est un point de minimum local
de f sur X , alors il existe des réels positifs ou nuls λ∗1 , ...., λ∗m tels
que :
j=m
λ∗j ∇gj (x ∗ ) = 0,
X
∇f (x ∗ ) +
j=1

avec pour tout j=1 , .... , m , λ∗j ≥ 0 et λ∗j gj (x ∗ ) = 0.

Conditions d’optimalité Problème d’optimisation avec contrainte

3.3. Condition d’optimalité pour les problèmes avec
contraintes d’inégalités :

Terminologie :
1) On appelle point stationnaire de (PI ) tout point x vérifiant les
conditions nécessaires d’optimalité du 1er ordre :


Xm
∇f (x ) + λi ∇gj (x ) = 0,






 j=1



 λj ≥ 0, ∀j = 1, ...., m.,



λj gj (x ) = 0, ∀j = 1, ...., m.


pour un certain multiplicateur λ ∈ R m .

Conditions d’optimalité Problème d’optimisation avec contrainte

3.1 Conditions d’optimalité :

2) Les relations λj gj (x ) = 0 sont appelées relations de

complémentarité et signifie :

soit λj = 0 , soit gj (x ) = 0.

Ces relations sont trivialement satisfaites pour toute contrainte

active en x et indiquent que pour toute contrainte inactive le
multiplicateur λj correspondant est nul .

Conditions d’optimalité Problème d’optimisation avec contrainte

3.4. Problémes avec contraintes d’inegalité et d’inégalité :



 min f (x ),



 x ∈ Rp ,


(PEI ) :



 hi (x ) = 0, i = 1, ...., n



gj (x ) ≤ 0, j = 1, ...., m.


Le domaine admissible X est alors défini par :

X = {x ∈ R p /h(x ) = 0 et g(x ) ≤ 0}

Conditions d’optimalité Problème d’optimisation avec contrainte

3.4. Problémes avec contraintes d’inegalité et d’inégalité :
Les contraintes sont dites qualifiées au point x ∈ X si chacune est
qualifiée au sens des définitions vues précédemment à savoir :

Conditions d’optimalité Problème d’optimisation avec contrainte

3.4. Problémes avec contraintes d’inegalité et d’inégalité :
Les contraintes sont dites qualifiées au point x ∈ X si chacune est
qualifiée au sens des définitions vues précédemment à savoir :

Définition 3.17 : les contraintes de (PEI ) sont dites qualifiées

au point x ∈ X si g et h sont différentiables au point x et si :
Tx (X ) = {v ∈ R p ; ∀i = 1, ...., n, < ∇hi (x ), v >= 0,
et pour toute contrainte j active , < ∇gj (x ), v >≤ 0}

Conditions d’optimalité Problème d’optimisation avec contrainte

3.4. Problémes avec contraintes d’inegalité et d’inégalité :
Les contraintes sont dites qualifiées au point x ∈ X si chacune est
qualifiée au sens des définitions vues précédemment à savoir :

Définition 3.17 : les contraintes de (PEI ) sont dites qualifiées

au point x ∈ X si g et h sont différentiables au point x et si :
Tx (X ) = {v ∈ R p ; ∀i = 1, ...., n, < ∇hi (x ), v >= 0,
et pour toute contrainte j active , < ∇gj (x ), v >≤ 0}

Définition 3.18 : ( C.S de qualification des contraintes ) Les

contraintes du problème (PEI ) sont qualifiées au point x ∈ X
si les gradients des contraintes actives en x :

{∇hi (x ); i = 1, ...., n} ∪ {∇gj (x ); j active }

sont linéairement indépendants .

Conditions d’optimalité Problème d’optimisation avec contrainte
3.4. Problémes avec contraintes d’inegalité et d’inégalité :

On introduit le Lagrangien associé au probléme (PEI ) :

n
X m
X
L(x , λ, µ) = f (x ) + λi hi (x ) + µj gj (x ), x ∈ R p , λ ∈ R n , µ ∈
i=1 j=1
Rm

Conditions d’optimalité Problème d’optimisation avec contrainte

3.4. Problémes avec contraintes d’inegalité et d’inégalité :
Théorème 3.19 : (CN d’optimalité de Karush - Kuhn - Tucker :
KKT ) Soit x ∗ ∈ X un point admissible de(PEI ) . Supposons f , g
et h différentiables en x ∗ et les contraintes qualifiées au point x ∗ .
Si x ∗ est un point de minimum local de f sur X alors il existe
λ∗ ∈ R n , et µ∗ ∈ R m tels que :

Conditions d’optimalité Problème d’optimisation avec contrainte

3.4. Problémes avec contraintes d’inegalité et d’inégalité :
Théorème 3.19 : (CN d’optimalité de Karush - Kuhn - Tucker :
KKT ) Soit x ∗ ∈ X un point admissible de(PEI ) . Supposons f , g
et h différentiables en x ∗ et les contraintes qualifiées au point x ∗ .
Si x ∗ est un point de minimum local de f sur X alors il existe
λ∗ ∈ R n , et µ∗ ∈ R m tels que :

∇x L(x ∗ , λ∗ , u ∗ ) = 0,





h (x ∗ ) = 0; i = 1, ...., n,


 i




 gj (x ∗ ) ≤ 0; j = 1, ...., m,
uj∗ gj (x ∗ ) = 0; j = 1, ...., m








uj∗ ≥ 0; j = 1, ...., m


Si de plus le probléme(PEI ) est convexe , alors les conditions

de KKT sont suffisantes pour que x ∗ soit un point de
minimum global de f sur X . Conditions d’optimalité Problème d’optimisation avec contrainte
3.4. Problémes avec contraintes d’inegalité et d’inégalité :

Conditions d’optimalité Problème d’optimisation avec contrainte