Optimisation avec contraintes

Conditions d’optimalité
 Multiplicateurs de Lagrange
Considérons le problème de programmation mathématique suivant
Min f ( x )
Sujet à fi ( x ) = 0 i = 1,… , m (4.1)
x∈ X
où X ⊂ R n et les fonctions f : X → R1 , fi : X → R1 , i = 1,… , m.

Le lagrangien associé au problème (4.1) est obtenu comme suit en associant

un multiplicateur de lagrange λi à chaque fonction de contrainte fi :
m
L (λ, x) = f ( x) +  λ f ( x).
i =1
i i

Sans faire d'hypothèse particulière sur X ou sur les fonctions f et fi , nous

pouvons obtenir des conditions suffisantes très générales pour qu'un point x *
soit une solution optimale globale du problème (4.1).
Considérons le problème de programmation mathématique suivant
Min f ( x )
Sujet à fi ( x ) = 0 i = 1,… , m (4.1)
x∈ X

Théorème 4.1: Supposons que le lagrangien associé au problème (4.1)

m
L (λ, x ) = f ( x) +  λ f ( x)
i =1
i i

possède un minimum global x* sur X lorsque le vecteur de multiplicateurs

( )
λ = λ * . Si fi x* =0 pour tout i = 1,… , m, alors x* est une solution optimale
globale de (4.1).

Preuve. La preuve se fait par contradiction en supposant que x* n'est pas une
solution optimale de (4.1). Alors il existe un x tel que f i ( x ) = 0 pour tout
( )
i = 1,… , m, et f ( x ) < f x* .
Théorème 4.1: Supposons que le lagrangien associé au problème (4.1)
m
L (λ, x) = f ( x ) +  λ f ( x)
i =1
i i

*
possède un minimum global x sur X lorsque le vecteur de multiplicateurs
( )
λ = λ * . Si fi x* =0 pour tout i = 1,… , m, alors x* est une solution optimale
globale de (4.1).

Preuve. La preuve se fait par contradiction en supposant que x* n'est pas une
solution optimale de (4.1). Alors il existe un x tel que fi ( x ) =0 pour tout
i = 1,… , m, et f ( x ) < f x* . ( )
Par conséquent, pour tout λ
m m

 λi fi ( x ) =  λi fi ( x* ) = 0
i =1 i =1
et ainsi
m m
f (x)+  λi fi ( x ) < f ( x* ) +  λi fi ( x* ).
i =1 i =1
En prenant λ = λ * la relation précédente contredit le fait que x* est un
minimum global du lagrangien sur X lorsque λ = λ * . □
Exemple:
Min f ( x, y ) = x 2 + 2 y 2
Sujet à f1 ( x, y ) = x + y − b = 0.

( )
L ( λ , x, y ) = x 2 + 2 y 2 + λ ( x + y − b )

L convexe en ( x, y ) .Donc minimum atteint lorsque ∇ x , y L ( λ , x, y ) = 0

 2 x + λ  0 λ = −2 x 
∇ x , y L ( λ , x, y ) =   =   ⇔  ⇔ x = 2y
 4 y + λ   0 λ = − 4 y 

b
x + y − b = 2 y + y − b = 3y − b = 0 ⇔ y =
3

2b
Donc x = 2y =
3
4b
λ = −2 x = −
3
Considérons maintenant le problème de programmation mathématique suivant
Min f ( x )
Sujet à fi ( x ) ≤ 0 i = 1,… , m (4.2)
x∈ X

Théorème 5.2: Supposons que le lagrangien associé au problème (4.2)

m
L (λ, x ) = f ( x) +  λ f ( x)
i =1
i i

*
possède un minimum global x sur X lorsque le vecteur de multiplicateurs
( ) ( )
λ = λ * . Si fi x* ≤ 0 , λi* ≥ 0 et λi* fi x* = 0 pour tout i = 1,… , m, alors x* est
une solution optimale globale de (4.2).
Exemple:
Min f ( x ) = x 2
Sujet à f1 ( x ) = 2 x + 5 ≤ 0.

L ( λ , x ) = x2 + λ ( 2 x + 5)

L convexe en ( x ) .Donc minimum atteint lorsque ∇ x L ( λ , x ) = 0

∇ x L ( λ , x ) = 2 x + 2λ = 0 ⇔ x = −λ

5
2 x + 5 = −2λ + 5 = 0 ⇔ λ =
2 5
λ = ≥0
2
5
Donc x = −λ = − 2 x + 5 = 0  ( 2 x + 5) λ = 0
2
 Conditions d’optimalite de
Karush-Kuhn-Tucker (KKT)de premier ordre
Pour obtenir des conditions plus facilement vérifiables, il faut poser des
hypothèses sur X et les fonctions f et fi .
Si X est convexe, si f et fi sont différentiables et convexes dans le
problème (4.2)
Min f ( x )
Sujet à fi ( x ) ≤ 0 i = 1,… , m (4.2)
x∈ X
et si λi ≥ 0, i = 1,… , m,
m
alors le lagrangien L (λ, x) = f ( x) +  λ f ( x)
i =1
i i

est aussi une fonction convexe sur X puisque

λi ≥ 0 et fi ( x ) convexe  λi fi ( x ) convexe
m
f ( x) +  λ f ( x ) somme de fonctions convexes.
i =1
i i
Si f et fi sont differentiables et convexes et si λ ≥ 0, alors le lagrangien
m
L (λ, x ) = f ( x) +  λ f ( x ) est une fonction différentiable et convexe en x,
i =1
i i

et il s'ensuit qu'il possède un minimum global en x* sur X lorsque λ = λ * si

m

( )
∇ x L λ * , x = ∇f ( x ) +  λi*∇fi ( x ) = 0.
i =1
Alors le Théorème 4.2 peut s'écrire:
K-K-T
Théorème 4.2: Supposons que
le lagrangien associé au problème (5.2) S'il existe un λ * tel que
m m
L ( λ, x ) = f ( x ) +  λi fi ( x ) ( )
∇x L λ , x * *
= ∇f x +( ) 
*
λi*∇fi ( x* ) = 0
i =1 i =1

λ f (x ) = 0
*
possède un minimum global x sur X *
i i
*
i = 1,… , n
lorsque le vecteur de multiplicateur λ * . *
f (x ) ≤ 0 i = 1,… , n
( ) ( )
i
Si fi x* ≤ 0 , λi* ≥ 0 et λi* fi x* = 0
λi* ≥ 0 i = 1,… , n
pour tout i = 1,… , m,
alors x* est une solution optimale globale de (4.2).
Exemple.
Min 2 x12 + 2 x1 x2 + x22 − 10 x1 − 10 x2

Sujet à x12 + x22 ≤ 5 ⇔ x12 + x22 − 5 ≤ 0 λ1

3x1 + x2 ≤ 6 ⇔ 3 x1 + x2 − 6 ≤ 0 λ2

 4 x1 + 2 x2 − 10  + λ  2 x1  + λ 3 = 0 S'il existe un λ * tel que

 2 x1 + 2 x2 − 10  1  2 x2  2 1  m

( ) = ∇f ( x ) +  λ ∇f ( x ) = 0
∇x L λ , x * * * * *

λ1 ( x + x − 5 ) = 0
i i
2 2
i =1

λ f (x ) = 0
1 2

λ2 ( 3x1 + x2 − 6 ) = 0 i = 1,… , n
* *
i i

f (x ) ≤ 0
*
i = 1,… , n
x + x −5 ≤ 0
2
1
2
2
i

3x1 + x2 − 6 ≤ 0 λi* ≥ 0 i = 1,… , n

λ1 , λ2 ≥ 0
Exemple.
Min 2 x12 + 2 x1 x2 + x22 − 10 x1 − 10 x2
Sujet à x12 + x22 ≤ 5 ⇔ x12 + x22 − 5 ≤ 0 λ1
3x1 + x2 ≤ 6 ⇔ 3 x1 + x2 − 6 ≤ 0 λ2

 4 x1 + 2 x2 − 10  + λ  2 x1  + λ 3 = 0
 2 x1 + 2 x2 − 10  1  2 x2  2 1  Nous pouvons faire différentes
hypothèses sur quelle contrainte
λ1 ( x12 + x22 − 5 ) = 0 est active dans le but d'identifier
λ2 ( 3x1 + x2 − 6 ) = 0 des valeurs de x1 , x2 , λ1 , λ2
satisfaisant les conditions KKT.
x12 + x22 − 5 ≤ 0
3x1 + x2 − 6 ≤ 0 Supposons que la première est
λ1 , λ2 ≥ 0 active et que la seconde ne l'est pas:
x12 + x22 − 5 = 0
3 x1 + x2 − 6 < 0  λ2 = 0.
Exemple.
Min 2 x12 + 2 x1 x2 + x22 − 10 x1 − 10 x2
Sujet à x12 + x22 ≤ 5 ⇔ x12 + x22 − 5 ≤ 0 λ1
3x1 + x2 ≤ 6 ⇔ 3 x1 + x2 − 6 ≤ 0 λ2

 4 x1 + 2 x2 − 10  + λ  2 x1  + λ 3 = 0 Supposons que la première est

 2 x1 + 2 x2 − 10  1  2 x2  2 1  active et que la seconde ne l'est pas:
x1 + x2 − 5 = 0
2 2

λ1 ( x12 + x22 − 5 ) = 0 3 x1 + x2 − 6 < 0  λ2 = 0.

λ2 ( 3x1 + x2 − 6 ) = 0
Nous retrouvons alors le système
x12 + x22 − 5 ≤ 0 avec 3 équations et 3 inconnus suivant:
3x1 + x2 − 6 ≤ 0
4 x1 + 2 x2 − 10 + 2λ1 x1 = 0
λ1 , λ2 ≥ 0
2 x1 + 2 x2 − 10 + 2λ1 x2 = 0
x12 + x22 = 5
Donc Nous pouvons vérifier que
x1 = 1, x2 = 2, λ1 = 1, λ2 = 0 x1 = 1, x2 = 2, λ1 = 1
satisfont le système précédent.
satisfont les conditions KKT.
 Conditions K-K-T suffisantes
En utilisant le Théorème 4.2 nous venons de démontrer que les conditions
K-K-T sont suffisantes sous les hypothèses supplémentaires que X est
convexe et que les fonctions f et fi sont convexes sur X .

Nous pouvons démontrer ce résultat en utilisant plutôt l'inégalité du gradient.

Théorème 4.3: Supposons que X est convexe et que les fonctions f et fi sont
différentiables et convexes. Si les conditions de K-K-T sont vérifiées à x* ,
alors x* est un minimum global du problème ( 4.2 ) .
 Conditions K-K-T nécessaires
Revenons à l'analyse de la nécessité des conditions K-K-T .

( )
Supposons que x* ∈ X , f i x* ≤ 0, i = 1,… , m, est une solution locale du
problème ( 4.2 ) . Min f ( x )
Sujet à fi ( x ) ≤ 0 i = 1,… , m (4.2)
x∈ X
Notation: Dénotons l'ensemble des contraintes actives
( ) { ( ) }
A x* = i : f i x* = 0 = {i1 ,… , ik } ⊂ {1,… , m} .

HYPOTHÈSE À VÉRIFIER : Supposons que nous pouvons démontrer

qu'il n'existe pas de vecteur d ∈ R n tel que
( ) ( )
T
∇f i x *
d ≤0 i ∈ A x* ( 4.3)
∇f ( x )
T
*
d <0
HYPOTHÈSE À VÉRIFIE R : Supposons que nous pouvons démontrer
qu'il n'existe pas de vecteur d ∈ R n tel que  ∇f x* T 
( )
( ) ( )
T  i1 
∇fi x *
d ≤0 i∈ A x *
 ⋮ d ≤ 0
 T

∇f ( x )*
T
d < 0.
( )
∇fik x
*


Nous retrouvons les conditions K-K-T:

( ) +  λ ∇f ( x ) = 0
∇f x * *
i i
*

i =1

λ f (x ) = 0
*
i i
*
i = 1, … , n
f (x ) ≤ 0
i
*
i = 1, … , n
λi* ≥ 0 i = 1, … , n
Malheureusement
HYPOTHÈSE À VÉRIFIER : Supposons que nous pouvons démontrer
qu'il n'existe pas de vecteur d ∈ R n tel que

( ) ( )
T
∇f i x *
d ≤0 i ∈ A x* ( 4.3)
∇f ( x )
T
*
d <0

ne l'est pas nécessairement toute solution locale x* de tout

nécessairement pour toute
problème tel que l'illustre l'exemple suivant..
 Min f ( x1 , x2 ) = − x1
Sujet à f1 ( x1 , x2 ) = ( x1 − 1) + x2 ≤ 0
3

f 2 ( x1 , x2 ) = − x1 ≤ 0
f3 ( x1 , x2 ) = − x2 ≤ 0.
L'ensemble des solutions réalisables de ce problème est
représenté par la region en-dessous de la courbe de f1 ( x1 , x2 )
au-dessus de l'axe des x1 et à droite de l'axe des x2 .
x2

x1
 Min f ( x1 , x2 ) = − x1
Sujet à f1 ( x1 , x2 ) = ( x1 − 1) + x2 ≤ 0
3

f 2 ( x1 , x2 ) = − x1 ≤ 0
f3 ( x1 , x2 ) = − x2 ≤ 0.
L'ensemble des solutions réalisables de ce problème est
représentée par la region en-dessous de la courbe de f1 ( x1 , x2 )
au-dessus de l'axe des x1 et à droite de l'axe des x2 .
x2 Il est facile de vérifier que
x* = [1, 0] est une solution
T

optimale globale de ce problème.

• ( )
De plus A x* = {1,3}.
x* x1
 Min f ( x1 , x2 ) = − x1
Sujet à f1 ( x1 , x2 ) = ( x1 − 1) + x2 ≤ 0
3

f 2 ( x1 , x2 ) = − x1 ≤ 0
f3 ( x1 , x2 ) = − x2 ≤ 0.

Or ∇f x ( ) = [−1, 0]
* T
,

( )
T
∇f1 ( x ) = 3 ( x1 − 1) ,1 et ∇f1 x = [ 0,1]
 
2 * T
 
x2 ( )
∇f3 x* = [ 0, −1]
T

•
x* x1
 ( )
Or ∇f x* = [ −1, 0] ,
T



2 
 ( )
∇f1 ( x ) = 3 ( x1 − 1) ,1 et ∇f1 x = [ 0,1]
* T

( ) = [0, −1]
∇f 3 x * T

Ainsi le système

( ) d = −d < 0
T
*
∇f x 1

∇f ( x ) d = d ≤ 0
T
*
1 2

∇f ( x ) d = − d ≤ 0
x2 T
*
3 2

possède une solution d = [1, 0] .

•
x* x1
Ainsi le système

( ) d = −d < 0
T
*
∇f x 1

∇f ( x ) d = d ≤ 0
T
*
1 2

∇f ( x ) d = − d ≤ 0
T
*
3 2

possède une solution d = [1, 0].

Notons qu'au point x* la direction d = [1,0]

x2
pointe directement à l'extérieur du domaine réalisable.
Nous allons donc imposer certaines
restrictions sur les contraintes des
problèmes considérés pour éliminer
d
•
de telles situations.
x* x1
 Restrictions sur les fonctions de contraintes de
Kuhn-Tucker

Notation: Rɶ dénote le domaine réalisable du problème ( 4.2 )

{ }
δ Rɶ = x ∈ Rɶ : ∃i,1 ≤ i ≤ m, tel que f ( x ) = 0 .
i

Définition. Étant donné un point x ∈ δ Rɶ , f1 , … , f m satisfont les restrictions

sur les fonctions de contraintes au point x si pour tout vecteur dˆ solution du
système ∇f i ( x ) d ≤ 0, i ∈ A ( x ) , il existe une fonction différentiable
T

α :[ 0,1] → Rɶ tel que α ( 0 ) = x et α ′ ( 0 ) = σ dˆ , σ > 0.

Notation: Rɶ dénote le domaine réalisable du problème ( 4.2 )
{ }
δ Rɶ = x ∈ Rɶ : ∃i,1 ≤ i ≤ m, tel que f ( x ) = 0 .
i

Définition. Étant donné un point x ∈ δ Rɶ , f1 , … , f m satisfont les restrictions

sur les fonctions de contraintes au point x si pour tout vecteur dˆ solution du
système ∇fi ( x ) d ≤ 0, i ∈ A ( x ) , il existe une fonction différentiable
T

α :[ 0,1] → Rɶ tel que α ( 0 ) = x et α ′ ( 0 ) = σ dˆ , σ > 0.

Dans l'exemple précédent, les contraintes f1 , f 2 , f3

ne satisfont pas les restrictions sur les fonctions de
x2 contraintes au point x* ∈ δ Rɶ .
En effet, il n'existe pas de fonction
différentiable α prenant ses valeurs
dans Rɶ dont la pente à 0 est un
multiple positif de d , puisque d pointe
• d à l'extérieur de Rɶ .
* x1
x
Définition. Étant donné un point x ∈ δ Rɶ , f1 , … , f m satisfont les restrictions
sur les fonctions de contraintes au point x si pour tout vecteur dˆ solution du
système ∇fi ( x ) d ≤ 0, i ∈ A ( x ) , il existe une fonction différentiable
T

α :[ 0,1] → Rɶ tel que α ( 0 ) = x et α ′ ( 0 ) = σ dˆ , σ > 0.

Interprétation géométrique.

∇f1 ( x ) dˆ ≤ 0
T

∇f 2 ( x )
T
dˆ ≤ 0 α (θ ) = x + θ dˆ
x α (0) = x
α ′ ( 0 ) = dˆ

x + dˆ

f2 ( x ) f1 ( x )
Définition. Étant donné un point x ∈ δ Rɶ , f1 , … , f m satisfont les restrictions
sur les fonctions de contraintes au point x si pour tout vecteur dˆ solution du
système ∇f i ( x ) d ≤ 0, i ∈ A ( x ) , il existe une fonction différentiable
T

α :[ 0,1] → Rɶ tel que α ( 0 ) = x et α ′ ( 0 ) = σ dˆ , σ > 0.

Interprétation
Se référant à la notion de direction de descente, lorque ∇fi ( x ) d < 0, alors pour
T

un faible déplacement τ > 0 dans la direction d , f i ( x + τ d ) < fi ( x ) = 0. Ainsi, ce

déplacement nous garde dans le domaine réalisable par rapport à cette contrainte.
Les restrictions sur les fonctions de contraintes prolongent en quelque sorte cette
propriété même si ∇f i ( x ) d = 0 puisque la fonction α prend ses valeurs dans le
T

domaine réalisable Rɶ . <

Théorème 4.3: (Nécessité des conditions K-K-T) Soit x* ∈ X une solution
optimale locale du problème (4.2) où X est ouvert. Supposons de plus que
si x* ∈ δ Rɶ , alors f1 ,… , f m satisfont les restrictions sur les fonctions
de contraintes au point x* . Alors il existe un vecteur de multiplicateurs
λ * = λ1* ,… , λm*  ≥ 0 tel que
m

( ) 
∇f x * + λi*∇fi ( x* ) = 0
i =1

λi* fi ( x* ) = 0 i = 1,… , m.

Preuve. Si x* est un point intérieur du domaine réalisable Rɶ (i.e., fi x* < 0 ( )

pour tout i ), il suffit de prendre λi* = 0 pour tout i = 1,… , m. En effet dans ce
( )
cas si ∇f x* prenait une valeur différente de 0, il suffirait de considérer la
( )
direction d = −∇f x* qui serait une direction de descente de f à x* . Ainsi,
( )
il existerait un τ >0 suffisemment petit pour que x* + τ d ∈ B x* ∩ Rɶ avec
ε ( )
( ) ( )
f x* + τ d < f x* , une contradiction.
Soit x* ∈ δ Rɶ . Démontrons alors que
HYPOTHÈSE À VÉRIFIER : Supposons que nous pouvons démontrer
qu'il n'existe pas de vecteur d ∈ R n tel que
( ) ( )
T
∇f i x *
d ≤0 i ∈ A x* ( 4.3)
∇f ( x )
T
*
d <0
est effectivement vérifiée sous les hypothèses du théorème. En effet, pour
fin de contradiction, supposons qu'un tel vecteur dˆ existerait. Puisque
f1 ,… , f m satisfont les restrictions sur les fonctions de contraintes au point
x* , alors il existe une fontion différentiable α : [ 0,1] → Rɶ telle que α ( 0 ) = x*
et α ′ ( 0 ) = σ dˆ , σ > 0. Mais ainsi,
( ) = ∇f
f (α (θ ) ) − f x*
( x ) α ′ ( 0 ) = σ∇f ( x )
T T
lim * *
dˆ < 0,
θ →0 θ
ce qui implique l'existence d'un θˆ ∈ [ 0,1] assez petit pour que α θˆ ∈ Bε x* () ( )
( ( )) < f ( x ) , une contradiction puisque α (θˆ ) ∈ Rɶ.
tel que f α θˆ *

Le reste de la preuve se fait comme précédemment lorsque nous supposions que

l'hypothèse était vérifiée.