Introduction

Optimisation avec contraintes d’égalité

Optimisation avec contraintes d’égalité et d’inégalité

Techniques d’optimisation
Cours5 : Optimisation non-linéaire avec contraintes - Conditions
d’optimalité

Abdelkader Benaouali

Ecole Militaire Polytechnique

2020/2021

Abdelkader Benaouali Techniques d’optimisation

 Introduction
Optimisation avec contraintes d’égalité
Optimisation avec contraintes d’égalité et d’inégalité

Somaire

1 Introduction

2 Optimisation avec contraintes d’égalité

Solution par substitution directe
Solution par les multiplicateurs de Lagrange

3 Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec une seule contrainte d’inégalité
Optimisation avec des contraintes inégalité
Cas général

Abdelkader Benaouali Techniques d’optimisation

 Introduction
Optimisation avec contraintes d’égalité
Optimisation avec contraintes d’égalité et d’inégalité

Introduction
c

Introduction :

Les problèmes d’optimisation sont très rarement sans contraintes.

De plus, les contraintes qui apparaissent dans ces problèmes sont

généralement non linéaires.

Cela motive notre intérêt pour la théorie générale de l’optimisation non-

linéaire avec contraintes.

Rappelez la formulation d’un problème d’optimisation général,

Minimiser f (X)
X


 hk (X) = 0, k = 1, 2, · · · , m
s.c. gj (X) ≤ 0, j = 1, 2, · · · , p

xi,inf ≤ xi ≤ xi,sup , i = 1, 2, · · · , n


Abdelkader Benaouali Techniques d’optimisation

 Introduction
Optimisation avec contraintes d’égalité
Optimisation avec contraintes d’égalité et d’inégalité

Introduction

Introduction :

Minimiser f (X)
X


 hk (X) = 0, k = 1, 2, · · · , m
s.c. gj (X) ≤ 0, j = 1, 2, · · · , p

xi,inf ≤ xi ≤ xi,sup , i = 1, 2, · · · , n


Une solution d’un problème d’optimisation contraint minimisera la fonction

objectif tout en satisfaisant les contraintes.

Abdelkader Benaouali Techniques d’optimisation

 Introduction
Optimisation avec contraintes d’égalité
Optimisation avec contraintes d’égalité et d’inégalité

Introduction

Introduction :

Minimiser f (X)
X


 hk (X) = 0, k = 1, 2, · · · , m
s.c. gj (X) ≤ 0, j = 1, 2, · · · , p

xi,inf ≤ xi ≤ xi,sup , i = 1, 2, · · · , n


Une solution d’un problème d’optimisation contraint minimisera la fonction

objectif tout en satisfaisant les contraintes.

Dans un problème bien formulé, le nombre de contraintes d’égalité

indépendantes doit être inférieur ou égal au nombre de variables, m ≤ n.
Lorsque m > n, le problème est sur défini et la solution peut ne pas exister.
Si m = n, les valeurs des variables sont déterminées de manière unique et il
n’y a pas de problème d’optimisation.

Abdelkader Benaouali Techniques d’optimisation

 Introduction
Optimisation avec contraintes d’égalité
Optimisation avec contraintes d’égalité et d’inégalité

Introduction

Introduction :

Minimiser f (X)
X


 hk (X) = 0, k = 1, 2, · · · , m
s.c. gj (X) ≤ 0, j = 1, 2, · · · , p

xi,inf ≤ xi ≤ xi,sup , i = 1, 2, · · · , n


Une solution d’un problème d’optimisation contraint minimisera la fonction

objectif tout en satisfaisant les contraintes.

Dans un problème bien formulé, le nombre de contraintes d’égalité

indépendantes doit être inférieur ou égal au nombre de variables, m ≤ n.

En un point admissible Xr une contrainte d’inégalité gj est dite active si

gj (Xr ) = 0 et inactive si l’inégalité stricte est satisfaite gj (Xr ) < 0.

Abdelkader Benaouali Techniques d’optimisation

 Introduction
Optimisation avec contraintes d’égalité
Optimisation avec contraintes d’égalité et d’inégalité

Introduction

Introduction :
Un exemple simple d’un problème d’optimisation avec contraintes :

min f (X) = 4 x21 − x1 − x2 − 2.5


 g1 (X) = 1.5 x21 − x22 − 2 x1 + 1 ≥ 0,
s.c.
 g (X) = x2 + 2 x2 − 2 x − 4.25 ≤ 0
2 2 1 1

Abdelkader Benaouali Techniques d’optimisation

 Introduction
Optimisation avec contraintes d’égalité
Optimisation avec contraintes d’égalité et d’inégalité

Introduction

Introduction :
Un exemple simple d’un problème d’optimisation avec contraintes :

0
x2

-1

-2 contours of

-3
-1.5 -1 -0.5 0 0.5 1 1.5 2 2.5
x1

Abdelkader Benaouali Techniques d’optimisation

 Introduction
Optimisation avec contraintes d’égalité
Optimisation avec contraintes d’égalité et d’inégalité

Introduction

Introduction :
Un exemple simple d’un problème d’optimisation avec contraintes :

0
x2

-1

-2 contours of

-3
-1.5 -1 -0.5 0 0.5 1 1.5 2 2.5
x1

Abdelkader Benaouali Techniques d’optimisation

 Introduction
Optimisation avec contraintes d’égalité
Optimisation avec contraintes d’égalité et d’inégalité

Introduction

Introduction :
Un exemple simple d’un problème d’optimisation avec contraintes :

0
x2

-1

-2 contours of

-3
-1.5 -1 -0.5 0 0.5 1 1.5 2 2.5
x1

Abdelkader Benaouali Techniques d’optimisation

 Introduction
Optimisation avec contraintes d’égalité
Optimisation avec contraintes d’égalité et d’inégalité

Introduction

Introduction :
Un exemple simple d’un problème d’optimisation avec contraintes :

0
x2

-1

-2 contours of

-3
-1.5 -1 -0.5 0 0.5 1 1.5 2 2.5
x1

Abdelkader Benaouali Techniques d’optimisation

 Introduction
Optimisation avec contraintes d’égalité
Optimisation avec contraintes d’égalité et d’inégalité

Introduction

Introduction :
Un exemple simple d’un problème d’optimisation avec contraintes :

0
x2

-1

-2 contours of

-3
-1.5 -1 -0.5 0 0.5 1 1.5 2 2.5
x1

Abdelkader Benaouali Techniques d’optimisation

 Introduction
Optimisation avec contraintes d’égalité
Optimisation avec contraintes d’égalité et d’inégalité

Introduction

Introduction :
Un exemple simple d’un problème d’optimisation avec contraintes :

0
x2

-1

-2 contours of

-3
-1.5 -1 -0.5 0 0.5 1 1.5 2 2.5
x1

Abdelkader Benaouali Techniques d’optimisation

 Introduction
Solution par substitution directe
Optimisation avec contraintes d’égalité
Solution par les multiplicateurs de Lagrange
Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité

Optimisation avec contraintes d’égalité :

Abdelkader Benaouali Techniques d’optimisation

 Introduction
Solution par substitution directe
Optimisation avec contraintes d’égalité
Solution par les multiplicateurs de Lagrange
Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité

Optimisation avec contraintes d’égalité :

Considérons le problème d’optimisation suivant avec des contraintes d’égalité,

Minimiser f (X)
X
(
hk (X) = 0, k = 1, 2, · · · , m
s.c.
xi,inf ≤ xi ≤ xi,sup , i = 1, 2, · · · , n
avec m≤n

Pour résoudre ce problème, plusieurs méthodes peuvent être utilisées :

Méthode de substitution directe

Méthode de la variation sous contraintes
Méthode des multiplicateurs de Lagrange

Abdelkader Benaouali Techniques d’optimisation

 Introduction
Solution par substitution directe
Optimisation avec contraintes d’égalité
Solution par les multiplicateurs de Lagrange
Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité

Solution par substitution directe

Optimisation avec contraintes d’égalité :

A. Solution par substitution directe

Résoudre les m contraintes d’égalité et exprimer l’ensemble des m variables

en terme des (n − m) variables restantes ;

Ces expressions sont substituées dans la fonction objectif originale. Il en

résulte une nouvelle fonction objectif n’impliquant que (n − m) variables ;

Le problème devient sans contraintes et peut être résolu à l’aide de techniques

vues précédemment.

Cette méthode, bien qu’elle semble simple en théorie, n’est utile que pour des
fonctions explicites simples.

En pratique, la plupart des fonctions contraintes sont non-linéaires, et souvent il

est impossible d’exprimer les m variables en termes des n−m variables restantes.

Abdelkader Benaouali Techniques d’optimisation

 Introduction
Solution par substitution directe
Optimisation avec contraintes d’égalité
Solution par les multiplicateurs de Lagrange
Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité

Solution par substitution directe

Optimisation avec contraintes d’égalité :

A. Solution par substitution directe
Exemple 1 :
min f (X) = 20 − x1 x2
(1)
s.c. x1 + x2 = 6

Abdelkader Benaouali Techniques d’optimisation

 Introduction
Solution par substitution directe
Optimisation avec contraintes d’égalité
Solution par les multiplicateurs de Lagrange
Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité

Solution par substitution directe

Optimisation avec contraintes d’égalité :

A. Solution par substitution directe
Exemple 1 :
min f (X) = 20 − x1 x2
(1)
s.c. x1 + x2 = 6

En utilisant l’équation de la contrainte, on exprime x2 en fonction de x1 :

x2 = 6 − x1

Abdelkader Benaouali Techniques d’optimisation

 Introduction
Solution par substitution directe
Optimisation avec contraintes d’égalité
Solution par les multiplicateurs de Lagrange
Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité

Solution par substitution directe

Optimisation avec contraintes d’égalité :

A. Solution par substitution directe
Exemple 1 :
min f (X) = 20 − x1 x2
(1)
s.c. x1 + x2 = 6

En utilisant l’équation de la contrainte, on exprime x2 en fonction de x1 :

x2 = 6 − x1
Après substitution, le problème devient sans contraintes à une seule variable :
min f (x1 ) = 20 − x1 (6 − x1 )

Abdelkader Benaouali Techniques d’optimisation

 Introduction
Solution par substitution directe
Optimisation avec contraintes d’égalité
Solution par les multiplicateurs de Lagrange
Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité

Solution par substitution directe

Optimisation avec contraintes d’égalité :

A. Solution par substitution directe
Exemple 1 :
min f (X) = 20 − x1 x2
(1)
s.c. x1 + x2 = 6

En utilisant l’équation de la contrainte, on exprime x2 en fonction de x1 :

x2 = 6 − x1
Après substitution, le problème devient sans contraintes à une seule variable :
min f (x1 ) = 20 − x1 (6 − x1 )

Un point stationnaire est déterminé par : f 0 (x1 ) = −6 + 2 x1 = 0 =⇒ x∗1 = 3

Puisque f 00 (X) = 2 est toujours positive, le point trouvé est un minimum.
On a x∗2 = 6 − x∗1 = 3. Donc, le point (3, 3) est la solution du problème (1).

Abdelkader Benaouali Techniques d’optimisation

 Introduction
Solution par substitution directe
Optimisation avec contraintes d’égalité
Solution par les multiplicateurs de Lagrange
Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité

Solution par substitution directe

Optimisation avec contraintes d’égalité :

A. Solution par substitution directe
Exemple 2 :
Trouver les dimensions d’une boite de volume maximal pouvant être inscrite dans
une sphère de rayon unitaire.

Abdelkader Benaouali Techniques d’optimisation

 Introduction
Solution par substitution directe
Optimisation avec contraintes d’égalité
Solution par les multiplicateurs de Lagrange
Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité

Solution par substitution directe

Optimisation avec contraintes d’égalité :

A. Solution par substitution directe
Exemple 2 :
Trouver les dimensions d’une boite de volume maximal pouvant être inscrite dans
une sphère de rayon unitaire.

On considère que l’origine du système de coordonnées est au centre du sphère

avec 2x1 , 2x2 , 2x3 sont les dimensions de la boite.

Abdelkader Benaouali Techniques d’optimisation

 Introduction
Solution par substitution directe
Optimisation avec contraintes d’égalité
Solution par les multiplicateurs de Lagrange
Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité

Solution par substitution directe

Optimisation avec contraintes d’égalité :

A. Solution par substitution directe
Exemple 2 :
min f (X) = −8 x1 x2 x3
(2)
s.c. x21 + x22 + x23 = 1

Abdelkader Benaouali Techniques d’optimisation

 Introduction
Solution par substitution directe
Optimisation avec contraintes d’égalité
Solution par les multiplicateurs de Lagrange
Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité

Solution par substitution directe

Optimisation avec contraintes d’égalité :

A. Solution par substitution directe
Exemple 2 :
min f (X) = −8 x1 x2 x3
(2)
s.c. x21 + x22 + x23 = 1

En utilisant l’équation de la contrainte, on élimine x3 : x3 = (1 − x21 − x22 )1/2

=⇒ min f (x1 , x2 ) = −8 x1 x2 (1 − x21 − x22 )1/2

Abdelkader Benaouali Techniques d’optimisation

 Introduction
Solution par substitution directe
Optimisation avec contraintes d’égalité
Solution par les multiplicateurs de Lagrange
Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité

Solution par substitution directe

Optimisation avec contraintes d’égalité :

A. Solution par substitution directe
Exemple 2 :
min f (X) = −8 x1 x2 x3
(2)
s.c. x21 + x22 + x23 = 1

En utilisant l’équation de la contrainte, on élimine x3 : x3 = (1 − x21 − x22 )1/2

=⇒ min f (x1 , x2 ) = −8 x1 x2 (1 − x21 − x22 )1/2

Conditions nécessaires :

x21
  
∂f 2 2 1/2
 ∂x1 = −8 x2 (1 − x1 − x2 ) − =0


(1 − x21 − x22 )1/2


x22
 
 ∂f
= −8 x1 (1 − x21 − x22 )1/2 − =0


(1 − x1 − x22 )1/2
2

∂x2
Abdelkader Benaouali Techniques d’optimisation
 Introduction
Solution par substitution directe
Optimisation avec contraintes d’égalité
Solution par les multiplicateurs de Lagrange
Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité

Solution par substitution directe

Optimisation avec contraintes d’égalité :

A. Solution par substitution directe
Exemple 2 :
min f (X) = −8 x1 x2 x3
(2)
s.c. x21 + x22 + x23 = 1

En utilisant l’équation de la contrainte, on élimine x3 : x3 = (1 − x21 − x22 )1/2

=⇒ min f (x1 , x2 ) = −8 x1 x2 (1 − x21 − x22 )1/2

Conditions nécessaires :

1 − 2 x21 − x22 = 0
(

1 − x21 − 2 x22 = 0

Abdelkader Benaouali Techniques d’optimisation

 Introduction
Solution par substitution directe
Optimisation avec contraintes d’égalité
Solution par les multiplicateurs de Lagrange
Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité

Solution par substitution directe

Optimisation avec contraintes d’égalité :

A. Solution par substitution directe
Exemple 2 :
min f (X) = −8 x1 x2 x3
(2)
s.c. x21 + x22 + x23 = 1

En utilisant l’équation de la contrainte, on élimine x3 : x3 = (1 − x21 − x22 )1/2

=⇒ min f (x1 , x2 ) = −8 x1 x2 (1 − x21 − x22 )1/2

Conditions nécessaires :
√
1 − 2 x21 − x22 = 0
(
x∗1 = 1/√3

=⇒
1 − x21 − 2 x22 = 0 x∗2 = 1/ 3

Abdelkader Benaouali Techniques d’optimisation

 Introduction
Solution par substitution directe
Optimisation avec contraintes d’égalité
Solution par les multiplicateurs de Lagrange
Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité

Solution par substitution directe

Optimisation avec contraintes d’égalité :

A. Solution par substitution directe
Exemple 2 :
min f (X) = −8 x1 x2 x3
(2)
s.c. x21 + x22 + x23 = 1

En utilisant l’équation de la contrainte, on élimine x3 : x3 = (1 − x21 − x22 )1/2

=⇒ min f (x1 , x2 ) = −8 x1 x2 (1 − x21 − x22 )1/2

Conditions nécessaires :
√
1 − 2 x21 − x22 = 0
(
x∗1 = 1/√3

=⇒
1 − x21 − 2 x22 = 0 x∗2 = 1/ 3
√
=⇒ x∗3 = 1/ 3

Abdelkader Benaouali Techniques d’optimisation

 Introduction
Solution par substitution directe
Optimisation avec contraintes d’égalité
Solution par les multiplicateurs de Lagrange
Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité

Solution par substitution directe

Optimisation avec contraintes d’égalité :

A. Solution par substitution directe
Exemple 2 :
min f (X) = −8 x1 x2 x3
(2)
s.c. x21 + x22 + x23 = 1

En utilisant l’équation de la contrainte, on élimine x3 : x3 = (1 − x21 − x22 )1/2

=⇒ min f (x1 , x2 ) = −8 x1 x2 (1 − x21 − x22 )1/2

Conditions suffisantes :
" #
1 32 16
H(x∗1 , x∗2 ) = √ Définie positive
3 16 32
1 1 1 8
La solution optimale : (x1 ∗, x∗2 , x∗3 ) = ( √ , √ , √ ) et fopt = − √
3 3 3 3 3
Abdelkader Benaouali Techniques d’optimisation
 Introduction
Solution par substitution directe
Optimisation avec contraintes d’égalité
Solution par les multiplicateurs de Lagrange
Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité

Solution par les multiplicateurs de Lagrange

Optimisation avec contraintes d’égalité :

B. Solution par les multiplicateurs de Lagrange

Abdelkader Benaouali Techniques d’optimisation

 Introduction
Solution par substitution directe
Optimisation avec contraintes d’égalité
Solution par les multiplicateurs de Lagrange
Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité

Solution par les multiplicateurs de Lagrange

Optimisation avec contraintes d’égalité :

B. Solution par les multiplicateurs de Lagrange

Dans le cas où la substitution directe ne peut pas être appliquée, la méthode des
multiplicateurs de Lagrange fournit une stratégie pour trouver la valeur optimale
d’une fonction sous contraintes d’égalité.

Considérons l’exemple suivant :

min f (X) = x21 + x22

s.c. x1 + 2 x2 + 4 = 0

Abdelkader Benaouali Techniques d’optimisation

 Introduction
Solution par substitution directe
Optimisation avec contraintes d’égalité
Solution par les multiplicateurs de Lagrange
Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité

Solution par les multiplicateurs de Lagrange

Optimisation avec contraintes d’égalité :

B. Solution par les multiplicateurs de Lagrange

Considérons l’exemple suivant :

min f (X) = x21 + x22

s.c. x1 + 2 x2 + 4 = 0

Abdelkader Benaouali Techniques d’optimisation

 Introduction
Solution par substitution directe
Optimisation avec contraintes d’égalité
Solution par les multiplicateurs de Lagrange
Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité

Solution par les multiplicateurs de Lagrange

Optimisation avec contraintes d’égalité :

B. Solution par les multiplicateurs de Lagrange

Considérons l’exemple suivant :

min f (X) = x21 + x22

s.c. x1 + 2 x2 + 4 = 0

L’extremum contraint correspond au point où la ligne d’équation x1 +2x2 +4 = 0

et une des courbes de niveau sont tangentes.

Abdelkader Benaouali Techniques d’optimisation

 Introduction
Solution par substitution directe
Optimisation avec contraintes d’égalité
Solution par les multiplicateurs de Lagrange
Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité

Solution par les multiplicateurs de Lagrange

Optimisation avec contraintes d’égalité :

B. Solution par les multiplicateurs de Lagrange

Considérons l’exemple suivant :

min f (X) = x21 + x22

s.c. x1 + 2 x2 + 4 = 0

En 3D, l’extremum contraint se trouve sur la courbe obtenue par l’intersection

de la surface de la fonction et la plan passant par la ligne de contrainte.

Abdelkader Benaouali Techniques d’optimisation

 Introduction
Solution par substitution directe
Optimisation avec contraintes d’égalité
Solution par les multiplicateurs de Lagrange
Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité

Solution par les multiplicateurs de Lagrange

Optimisation avec contraintes d’égalité :

B. Solution par les multiplicateurs de Lagrange
Considérons un autre exemple où la contrainte n’est pas linéaire :

min f (X) = x21 + x22

s.c. x1 x2 − 2 = 0

Abdelkader Benaouali Techniques d’optimisation

 Introduction
Solution par substitution directe
Optimisation avec contraintes d’égalité
Solution par les multiplicateurs de Lagrange
Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité

Solution par les multiplicateurs de Lagrange

Optimisation avec contraintes d’égalité :

B. Solution par les multiplicateurs de Lagrange
Considérons un autre exemple où la contrainte n’est pas linéaire :

min f (X) = x21 + x22

s.c. x1 x2 − 2 = 0

Abdelkader Benaouali Techniques d’optimisation

 Introduction
Solution par substitution directe
Optimisation avec contraintes d’égalité
Solution par les multiplicateurs de Lagrange
Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité

Solution par les multiplicateurs de Lagrange

Optimisation avec contraintes d’égalité :

B. Solution par les multiplicateurs de Lagrange
Considérons un autre exemple où la contrainte n’est pas linéaire :

min f (X) = x21 + x22

s.c. x1 x2 − 2 = 0

L’extremum contraint correspond au point où la courbe d’équation x1 x2 −2 = 0

et une des courbes de niveau sont tangentes (ont la même tangente).
Abdelkader Benaouali Techniques d’optimisation
 Introduction
Solution par substitution directe
Optimisation avec contraintes d’égalité
Solution par les multiplicateurs de Lagrange
Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité

Solution par les multiplicateurs de Lagrange

Optimisation avec contraintes d’égalité :

B. Solution par les multiplicateurs de Lagrange
Considérons un autre exemple où la contrainte n’est pas linéaire :

Au point optimal X ∗ , les courbes

de niveau de f et h ont :

Abdelkader Benaouali Techniques d’optimisation

 Introduction
Solution par substitution directe
Optimisation avec contraintes d’égalité
Solution par les multiplicateurs de Lagrange
Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité

Solution par les multiplicateurs de Lagrange

Optimisation avec contraintes d’égalité :

B. Solution par les multiplicateurs de Lagrange
Considérons un autre exemple où la contrainte n’est pas linéaire :

Au point optimal X ∗ , les courbes

de niveau de f et h ont :

la même tangente

Abdelkader Benaouali Techniques d’optimisation

 Introduction
Solution par substitution directe
Optimisation avec contraintes d’égalité
Solution par les multiplicateurs de Lagrange
Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité

Solution par les multiplicateurs de Lagrange

Optimisation avec contraintes d’égalité :

B. Solution par les multiplicateurs de Lagrange
Considérons un autre exemple où la contrainte n’est pas linéaire :

Au point optimal X ∗ , les courbes

de niveau de f et h ont :

la même tangente
une normale commune

Abdelkader Benaouali Techniques d’optimisation

 Introduction
Solution par substitution directe
Optimisation avec contraintes d’égalité
Solution par les multiplicateurs de Lagrange
Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité

Solution par les multiplicateurs de Lagrange

Optimisation avec contraintes d’égalité :

B. Solution par les multiplicateurs de Lagrange
Considérons un autre exemple où la contrainte n’est pas linéaire :

Au point optimal X ∗ , les courbes

de niveau de f et h ont :

la même tangente
une normale commune

=⇒ ∇f (X ∗ ) = λ ∇h(X ∗ )

avec λ est un scalaire, appelé multiplicateur de Lagrange

Abdelkader Benaouali Techniques d’optimisation

 Introduction
Solution par substitution directe
Optimisation avec contraintes d’égalité
Solution par les multiplicateurs de Lagrange
Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité

Solution par les multiplicateurs de Lagrange

Optimisation avec contraintes d’égalité :

B. Solution par les multiplicateurs de Lagrange
Pour montrer la relation précédente graphiquement, on considère l’exemple
suivant :

Minimiser f (X) s.c. h(X) = 0

avec :

f (X) = x1 + x2 , h(X) = x21 + x22 − 2

Abdelkader Benaouali Techniques d’optimisation

 Introduction
Solution par substitution directe
Optimisation avec contraintes d’égalité
Solution par les multiplicateurs de Lagrange
Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité

Solution par les multiplicateurs de Lagrange

Optimisation avec contraintes d’égalité :

B. Solution par les multiplicateurs de Lagrange

iso-contours de

f (X) = x1 + x2

Abdelkader Benaouali Techniques d’optimisation

 Introduction
Solution par substitution directe
Optimisation avec contraintes d’égalité
Solution par les multiplicateurs de Lagrange
Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité

Solution par les multiplicateurs de Lagrange

Optimisation avec contraintes d’égalité :

B. Solution par les multiplicateurs de Lagrange

region admissible :

iso-contours de

h(X) = x21 + x22 − 2

Abdelkader Benaouali Techniques d’optimisation

 Introduction
Solution par substitution directe
Optimisation avec contraintes d’égalité
Solution par les multiplicateurs de Lagrange
Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité

Solution par les multiplicateurs de Lagrange

Optimisation avec contraintes d’égalité :

B. Solution par les multiplicateurs de Lagrange

point réalisable

Abdelkader Benaouali Techniques d’optimisation

 Introduction
Solution par substitution directe
Optimisation avec contraintes d’égalité
Solution par les multiplicateurs de Lagrange
Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité

Solution par les multiplicateurs de Lagrange

Optimisation avec contraintes d’égalité :

B. Solution par les multiplicateurs de Lagrange

Étant donné un point réalisable (faisable) Xr , trouver δX tel que :

f (Xr + α δX) < f (Xr ) et h(Xr + αδX) = 0

Abdelkader Benaouali Techniques d’optimisation

 Introduction
Solution par substitution directe
Optimisation avec contraintes d’égalité
Solution par les multiplicateurs de Lagrange
Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité

Solution par les multiplicateurs de Lagrange

Optimisation avec contraintes d’égalité :

B. Solution par les multiplicateurs de Lagrange

on a :

Pour se déplacer δX à partir de Xr tel que f (Xr + α δX) < f (Xr ) on doit
avoir :
δX · ∇f (Xr ) < 0

Abdelkader Benaouali Techniques d’optimisation

 Introduction
Solution par substitution directe
Optimisation avec contraintes d’égalité
Solution par les multiplicateurs de Lagrange
Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité

Solution par les multiplicateurs de Lagrange

Optimisation avec contraintes d’égalité :

B. Solution par les multiplicateurs de Lagrange

Les normales à la surface de contrainte sont données par ∇h(X).

À noter que la direction de la normale est arbitraire du moment
qu’on a h(X) = −h(X) = 0

Abdelkader Benaouali Techniques d’optimisation

 Introduction
Solution par substitution directe
Optimisation avec contraintes d’égalité
Solution par les multiplicateurs de Lagrange
Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité

Solution par les multiplicateurs de Lagrange

Optimisation avec contraintes d’égalité :

B. Solution par les multiplicateurs de Lagrange

Les normales à la surface de contrainte sont données par ∇h(X).

À noter que la direction de la normale est arbitraire du moment
qu’on a h(X) = −h(X) = 0

Abdelkader Benaouali Techniques d’optimisation

 Introduction
Solution par substitution directe
Optimisation avec contraintes d’égalité
Solution par les multiplicateurs de Lagrange
Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité

Solution par les multiplicateurs de Lagrange

Optimisation avec contraintes d’égalité :

B. Solution par les multiplicateurs de Lagrange

Direction orthogonale par

rapport à

Pour se déplacer δX à partir de X et rester sur la surface de la contrainte, on

doit se déplacer dans une direction orthogonale à ∇h(X)

Abdelkader Benaouali Techniques d’optimisation

 Introduction
Solution par substitution directe
Optimisation avec contraintes d’égalité
Solution par les multiplicateurs de Lagrange
Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité

Solution par les multiplicateurs de Lagrange

Optimisation avec contraintes d’égalité :

B. Solution par les multiplicateurs de Lagrange

En résumé :

Si Xr appartient à la surface de la contrainte :

Pour s’assurer que h(Xr + X) = 0, il faut imposer δX orthogonal

à ∇h(Xr ), c.à.d :
δX · ∇h(Xr ) = 0

Mouvement assurant une descente f (Xr + α δX) < f (Xr )

seulement si :
δX · ∇f (Xr ) < 0

Abdelkader Benaouali Techniques d’optimisation

 Introduction
Solution par substitution directe
Optimisation avec contraintes d’égalité
Solution par les multiplicateurs de Lagrange
Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité

Solution par les multiplicateurs de Lagrange

Optimisation avec contraintes d’égalité :

B. Solution par les multiplicateurs de Lagrange

En résumé :

Une condition nécessaire pour que X ∗ soit un minimum local est qu’il
n’existe pas de direction d (ou δX) satisfaisant ces deux conditions :

Abdelkader Benaouali Techniques d’optimisation

 Introduction
Solution par substitution directe
Optimisation avec contraintes d’égalité
Solution par les multiplicateurs de Lagrange
Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité

Solution par les multiplicateurs de Lagrange

Optimisation avec contraintes d’égalité :

B. Solution par les multiplicateurs de Lagrange

En résumé :

Une condition nécessaire pour que X ∗ soit un minimum local est qu’il
n’existe pas de direction d (ou δX) satisfaisant ces deux conditions :

d · ∇h(X) = 0 d · ∇f (X) < 0

Abdelkader Benaouali Techniques d’optimisation

 Introduction
Solution par substitution directe
Optimisation avec contraintes d’égalité
Solution par les multiplicateurs de Lagrange
Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité

Solution par les multiplicateurs de Lagrange

Optimisation avec contraintes d’égalité :

B. Solution par les multiplicateurs de Lagrange

En résumé :

Une condition nécessaire pour que X ∗ soit un minimum local est qu’il
n’existe pas de direction d (ou δX) satisfaisant ces deux conditions :

d · ∇h(X) = 0 d · ∇f (X) < 0

La seule façon pour qu’une telle direction ne puisse exister est si ∇h(X)
et ∇f (X) sont parallèles, i.e. :

∇f (X ∗ ) = λ ∇h(X ∗ ) avec λ est un scalaire

Abdelkader Benaouali Techniques d’optimisation

 Introduction
Solution par substitution directe
Optimisation avec contraintes d’égalité
Solution par les multiplicateurs de Lagrange
Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité

Solution par les multiplicateurs de Lagrange

Optimisation avec contraintes d’égalité :

B. Solution par les multiplicateurs de Lagrange

optimum local contraint

optimum local contraint

Un optimum local contraint a lieu en X ∗ lorsque ∇f (X ∗ ) et ∇h(X ∗ )

sont parallèles, i.e. : ∇f (X ∗ ) = λ ∇h(X ∗ )

Abdelkader Benaouali Techniques d’optimisation

 Introduction
Solution par substitution directe
Optimisation avec contraintes d’égalité
Solution par les multiplicateurs de Lagrange
Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité

Solution par les multiplicateurs de Lagrange

Optimisation avec contraintes d’égalité :

B. Solution par les multiplicateurs de Lagrange

Condition de Lagrange
∗
Soit X un point régulier qui est un minimum local de f (X) sous contraintes
hk (X) = 0, k = 1, · · · , m. Alors, ils existent des multiplicateurs de Lagrange
uniques λ∗k (k = 1, · · · , m) tels que :
m

 X
 ∇f (X ∗ ) +

λ∗ ∇hk (X ∗ ) = 0 k
 k=1
hk (X ∗ ) = 0 ,

k = 1, · · · , m


La condition de Lagrange fournit une condition nécessaire pour qu’un point

soit un minimum local. Elle n’est généralement pas suffisante, i.e. elle ne suffit
pas pour dire que le point X ∗ est la solution.

Abdelkader Benaouali Techniques d’optimisation

 Introduction
Solution par substitution directe
Optimisation avec contraintes d’égalité
Solution par les multiplicateurs de Lagrange
Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité

Solution par les multiplicateurs de Lagrange

Optimisation avec contraintes d’égalité :

B. Solution par les multiplicateurs de Lagrange

Condition de Lagrange
∗
Soit X un point régulier qui est un minimum local de f (X) sous contraintes
hk (X) = 0, k = 1, · · · , m. Alors, ils existent des multiplicateurs de Lagrange
uniques λ∗k (k = 1, · · · , m) tels que :
m

 X
 ∇f (X ∗ ) +

λ∗ ∇hk (X ∗ ) = 0 k
 k=1
hk (X ∗ ) = 0 ,

k = 1, · · · , m


Ces conditions du premier ordre sont appelées conditions de Karush-Kuhn-Tucker

(KKT). Comme dans le cas sans contrainte, on doit passer par les conditions
suffisantes du second ordre pour savoir la nature du point stationnaire.

Abdelkader Benaouali Techniques d’optimisation

 Introduction
Solution par substitution directe
Optimisation avec contraintes d’égalité
Solution par les multiplicateurs de Lagrange
Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité

Solution par les multiplicateurs de Lagrange

Optimisation avec contraintes d’égalité :

B. Solution par les multiplicateurs de Lagrange
On définit le Lagrangien (fonction de Lagrange) comme
m
X
L(X, λ) = f (X) + λk hk (X)
k=1
= f (X) + λ · hk (X)

Un point stationnaire du Lagrangien, par rapport à X et à λ, satisfait ∇L = 0 :

( )
∇x L
tel que ∇L =
∇λ L

Abdelkader Benaouali Techniques d’optimisation

 Introduction
Solution par substitution directe
Optimisation avec contraintes d’égalité
Solution par les multiplicateurs de Lagrange
Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité

Solution par les multiplicateurs de Lagrange

Optimisation avec contraintes d’égalité :

B. Solution par les multiplicateurs de Lagrange
On définit le Lagrangien (fonction de Lagrange) comme
m
X
L(X, λ) = f (X) + λk hk (X)
k=1
= f (X) + λ · hk (X)

Un point stationnaire du Lagrangien, par rapport à X et à λ, satisfait ∇L = 0 :

 m
∂L(X ∗ , λ∗ )
 X
∗
λ∗k ∇hk (X ∗ ) = 0


 = 0 (i = 1, . . . , n) =⇒ ∇f (X ) +
∂xi

k=1
 ∂L(X ∗ , ∂λ∗ )

∗
= 0 (k = 1, . . . , m) =⇒ hk (X ) = 0 , k = 1, · · · , m



λk

Abdelkader Benaouali Techniques d’optimisation

 Introduction
Solution par substitution directe
Optimisation avec contraintes d’égalité
Solution par les multiplicateurs de Lagrange
Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité

Solution par les multiplicateurs de Lagrange

Optimisation avec contraintes d’égalité :

B. Solution par les multiplicateurs de Lagrange
Exemple 1 :
min f (X) = 20 − x1 x2
s.c. x1 + x2 = 6

Abdelkader Benaouali Techniques d’optimisation

 Introduction
Solution par substitution directe
Optimisation avec contraintes d’égalité
Solution par les multiplicateurs de Lagrange
Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité

Solution par les multiplicateurs de Lagrange

Optimisation avec contraintes d’égalité :

B. Solution par les multiplicateurs de Lagrange
Exemple 1 :
min f (X) = 20 − x1 x2
s.c. x1 + x2 = 6

On définit le Lagrangien comme :

L(x1 , x2 , λ) = 20 − x1 x2 + λ (x1 + x2 − 6)

Abdelkader Benaouali Techniques d’optimisation

 Introduction
Solution par substitution directe
Optimisation avec contraintes d’égalité
Solution par les multiplicateurs de Lagrange
Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité

Solution par les multiplicateurs de Lagrange

Optimisation avec contraintes d’égalité :

B. Solution par les multiplicateurs de Lagrange
Exemple 1 :
min f (X) = 20 − x1 x2
s.c. x1 + x2 = 6

On définit le Lagrangien comme :

L(x1 , x2 , λ) = 20 − x1 x2 + λ (x1 + x2 − 6)
Les points stationnaires du Lagrangien :
 ∂L(x , x , λ)
1 2
 = −x2 + λ = 0



 ∂x1 Un seul point stationnaire

∂L(x1 , x2 , λ)

= −x1 + λ = 0 =⇒ (x∗1 , x∗2 ) = (3 , 3)


 ∂x2
avec λ∗ = 3

 ∂L(x1 , x2 , λ)

 = x1 + x2 − 6 = 0
∂λ
Abdelkader Benaouali Techniques d’optimisation
 Introduction
Solution par substitution directe
Optimisation avec contraintes d’égalité
Solution par les multiplicateurs de Lagrange
Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité

Solution par les multiplicateurs de Lagrange

Optimisation avec contraintes d’égalité :

B. Solution par les multiplicateurs de Lagrange
Exemple 1 :

7
-2

11
-1 -1 1

-5
-7 -10 3 5.66
24.3333

3
16.3333
.6 .3

5.6
6 67

8.3
66 33
19
21.6667

-2
66
7 3

.3
333

33
3
5

4 -5
0.3
3 333
5.6 3
x2

3 13 11 667
. 66 8.3
333
67
16
2 .33
33
11
19

13.6667
1
16.3333
19
0
21.6667

-1 24.3333
-1 0 1 2 3 4 5 6 7
x1

Abdelkader Benaouali Techniques d’optimisation

 Introduction
Solution par substitution directe
Optimisation avec contraintes d’égalité
Solution par les multiplicateurs de Lagrange
Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité

Solution par les multiplicateurs de Lagrange

Optimisation avec contraintes d’égalité :

B. Solution par les multiplicateurs de Lagrange
Exemple 1 :

Abdelkader Benaouali Techniques d’optimisation

 Introduction
Solution par substitution directe
Optimisation avec contraintes d’égalité
Solution par les multiplicateurs de Lagrange
Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité

Solution par les multiplicateurs de Lagrange

Optimisation avec contraintes d’égalité :

B. Solution par les multiplicateurs de Lagrange
Exemple 3 :
min f (X) = x21 + x22
s.c. x21 + 2 x22 − 1 = 0

Abdelkader Benaouali Techniques d’optimisation

 Introduction
Solution par substitution directe
Optimisation avec contraintes d’égalité
Solution par les multiplicateurs de Lagrange
Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité

Solution par les multiplicateurs de Lagrange

Optimisation avec contraintes d’égalité :

B. Solution par les multiplicateurs de Lagrange
Exemple 3 :
min f (X) = x21 + x22
s.c. x21 + 2 x22 − 1 = 0

   
2 x1 2 x1
∇f (X) = , ∇h(X) =
2 x2 4 x2

Abdelkader Benaouali Techniques d’optimisation

 Introduction
Solution par substitution directe
Optimisation avec contraintes d’égalité
Solution par les multiplicateurs de Lagrange
Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité

Solution par les multiplicateurs de Lagrange

Optimisation avec contraintes d’égalité :

B. Solution par les multiplicateurs de Lagrange
Exemple 3 :
min f (X) = x21 + x22
s.c. x21 + 2 x22 − 1 = 0

   
2 x1 2 x1
∇f (X) = , ∇h(X) =
2 x2 4 x2

 m
x∗1 + λ∗ x∗1 = 0
(
 X
 ∇f (X ∗ ) + λ∗k ∇hk (X ) = 0 ∗
=⇒


k=1
x∗2 + 2 λ∗ x∗2 = 0



hk (X ∗ ) = 0 , (k = 1, · · · , m) =⇒ (x∗1 )2 + 2 (x∗2 )2 − 1 = 0


Abdelkader Benaouali Techniques d’optimisation

 Introduction
Solution par substitution directe
Optimisation avec contraintes d’égalité
Solution par les multiplicateurs de Lagrange
Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité

Solution par les multiplicateurs de Lagrange

Optimisation avec contraintes d’égalité :

B. Solution par les multiplicateurs de Lagrange
Exemple 3 :
min f (X) = x21 + x22
s.c. x21 + 2 x22 − 1 = 0

   
2 x1 2 x1
∇f (X) = , ∇h(X) =
2 x2 4 x2

  ∗ ∗ ∗

  x1 + λ x1 = 0 =⇒ x∗1 = 0 ou λ∗ = −1



 x∗ + 2 λ∗ x∗ = 0 =⇒ 1
2 2 x∗2 = 0 ou λ∗ = −

 2

(x∗1 )2 + 2 (x∗2 )2 − 1 = 0



Abdelkader Benaouali Techniques d’optimisation

 Introduction
Solution par substitution directe
Optimisation avec contraintes d’égalité
Solution par les multiplicateurs de Lagrange
Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité

Solution par les multiplicateurs de Lagrange

Optimisation avec contraintes d’égalité :

B. Solution par les multiplicateurs de Lagrange
Exemple 3 : (Cont.)
 ∗

 x1 = 0 ou λ∗ = −1

1

x∗2 = 0 ou λ∗ = −

 2

(x∗1 )2 + 2 (x∗2 )2 − 1 = 0



 x∗1 = 0 1 1
 =⇒ x∗2 = ± √ et λ∗ = −
=⇒ 2 2
 x∗ = 0

=⇒ x∗1 = ±1 et λ∗ = −1
2

Abdelkader Benaouali Techniques d’optimisation

 Introduction
Solution par substitution directe
Optimisation avec contraintes d’égalité
Solution par les multiplicateurs de Lagrange
Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité

Solution par les multiplicateurs de Lagrange

Optimisation avec contraintes d’égalité :

B. Solution par les multiplicateurs de Lagrange
Exemple 3 : (Cont.)
 ∗

 x1 = 0 ou λ∗ = −1

1

x∗2 = 0 ou λ∗ = −

 2

(x∗1 )2 + 2 (x∗2 )2 − 1 = 0



 x∗1 = 0 1 1
 =⇒ x∗2 = ± √ et λ∗ = −
=⇒ 2 2
 x∗ = 0

=⇒ x∗1 = ±1 et λ∗ = −1
2

   
0 0 " # " #
1 −1
Quatre points stationnaires
   
 1   1 
√ −√ 0 0
2 2
Abdelkader Benaouali Techniques d’optimisation
 Introduction
Solution par substitution directe
Optimisation avec contraintes d’égalité
Solution par les multiplicateurs de Lagrange
Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité

Solution par les multiplicateurs de Lagrange

Optimisation avec contraintes d’égalité :

B. Solution par les multiplicateurs de Lagrange
Exemple 3 : (Cont.)    
0 0 " # " #
1 −1
Quatre points stationnaires
   
 1   1 
√ −√ 0 0
2 2

0.5

-0.5

-1

Abdelkader Benaouali Techniques d’optimisation

 Introduction
Solution par substitution directe
Optimisation avec contraintes d’égalité
Solution par les multiplicateurs de Lagrange
Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité

Solution par les multiplicateurs de Lagrange

Optimisation avec contraintes d’égalité :

B. Solution par les multiplicateurs de Lagrange
Exemple 4 :
min f (X) = x21 + x1 x2 + x22
s.c. x21 + x22 = 8

Abdelkader Benaouali Techniques d’optimisation

 Introduction
Solution par substitution directe
Optimisation avec contraintes d’égalité
Solution par les multiplicateurs de Lagrange
Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité

Solution par les multiplicateurs de Lagrange

Optimisation avec contraintes d’égalité :

B. Solution par les multiplicateurs de Lagrange
Exemple 4 :
min f (X) = x21 + x1 x2 + x22
s.c. x21 + x22 = 8

   
2 x1 + x2 2 x1
∇f (X) = , ∇h(X) =
2 x2 + x1 2 x2

Abdelkader Benaouali Techniques d’optimisation

 Introduction
Solution par substitution directe
Optimisation avec contraintes d’égalité
Solution par les multiplicateurs de Lagrange
Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité

Solution par les multiplicateurs de Lagrange

Optimisation avec contraintes d’égalité :

B. Solution par les multiplicateurs de Lagrange
Exemple 4 :
min f (X) = x21 + x1 x2 + x22
s.c. x21 + x22 = 8

   
2 x1 + x2 2 x1
∇f (X) = , ∇h(X) =
2 x2 + x1 2 x2

2 x∗1 + x∗2 + 2 λ∗ x∗1 = 0 x∗2 = −2x∗1 (λ∗ + 1)

 (
 =⇒ (1)


2 x∗2 + x∗1 + 2 λ∗ x∗2 = 0 =⇒ x∗1 = −2x∗2 (λ∗ + 1) (2)


(x∗1 )2 + (x∗2 )2 − 8 = 0

(3)

Abdelkader Benaouali Techniques d’optimisation

 Introduction
Solution par substitution directe
Optimisation avec contraintes d’égalité
Solution par les multiplicateurs de Lagrange
Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité

Solution par les multiplicateurs de Lagrange

Optimisation avec contraintes d’égalité :

B. Solution par les multiplicateurs de Lagrange
Exemple 4 :
min f (X) = x21 + x1 x2 + x22
s.c. x21 + x22 = 8

   
2 x1 + x2 2 x1
∇f (X) = , ∇h(X) =
2 x2 + x1 2 x2

2 x∗1 + x∗2 + 2 λ∗ x∗1 = 0 x∗2 = −2x∗1 (λ∗ + 1)

 (
 =⇒ (1)


2 x∗2 + x∗1 + 2 λ∗ x∗2 = 0 =⇒ x∗1 = −2x∗2 (λ∗ + 1) (2)


(x∗1 )2 + (x∗2 )2 − 8 = 0

(3)

(1) et (2) =⇒ x∗1 = −2(−2x∗1 (λ∗ +1))(λ∗ +1) =⇒ x∗1 = 4x∗1 (λ∗ +1)2

Abdelkader Benaouali Techniques d’optimisation

 Introduction
Solution par substitution directe
Optimisation avec contraintes d’égalité
Solution par les multiplicateurs de Lagrange
Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité

Solution par les multiplicateurs de Lagrange

Optimisation avec contraintes d’égalité :

B. Solution par les multiplicateurs de Lagrange
Exemple 4 : (cont.)

(1) et (2) =⇒ x∗1 = −2(−2x∗1 (λ∗ +1))(λ∗ +1) =⇒ x∗1 = 4x∗1 (λ∗ +1)2

Abdelkader Benaouali Techniques d’optimisation

 Introduction
Solution par substitution directe
Optimisation avec contraintes d’égalité
Solution par les multiplicateurs de Lagrange
Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité

Solution par les multiplicateurs de Lagrange

Optimisation avec contraintes d’égalité :

B. Solution par les multiplicateurs de Lagrange
Exemple 4 : (cont.)

(1) et (2) =⇒ x∗1 = −2(−2x∗1 (λ∗ +1))(λ∗ +1) =⇒ x∗1 = 4x∗1 (λ∗ +1)2

x∗1 1 − 4(λ∗ + 1)2 = 0

 
=⇒

Abdelkader Benaouali Techniques d’optimisation

 Introduction
Solution par substitution directe
Optimisation avec contraintes d’égalité
Solution par les multiplicateurs de Lagrange
Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité

Solution par les multiplicateurs de Lagrange

Optimisation avec contraintes d’égalité :

B. Solution par les multiplicateurs de Lagrange
Exemple 4 : (cont.)

(1) et (2) =⇒ x∗1 = −2(−2x∗1 (λ∗ +1))(λ∗ +1) =⇒ x∗1 = 4x∗1 (λ∗ +1)2

x∗1 1 − 4(λ∗ + 1)2 = 0

 
=⇒

1 3
=⇒ x∗1 = 0 ou λ∗ = − ou λ∗ = −
2 2

Abdelkader Benaouali Techniques d’optimisation

 Introduction
Solution par substitution directe
Optimisation avec contraintes d’égalité
Solution par les multiplicateurs de Lagrange
Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité

Solution par les multiplicateurs de Lagrange

Optimisation avec contraintes d’égalité :

B. Solution par les multiplicateurs de Lagrange
Exemple 4 : (cont.)

(1) et (2) =⇒ x∗1 = −2(−2x∗1 (λ∗ +1))(λ∗ +1) =⇒ x∗1 = 4x∗1 (λ∗ +1)2

x∗1 1 − 4(λ∗ + 1)2 = 0

 
=⇒

1 3
=⇒ x∗1 = 0 ou λ∗ = − ou λ∗ = −
2 2

• L’équation (1) avec x∗1 = 0 donne x∗2 = 0, alors que (0, 0) ne vérifie pas la
contrainte (équation (3)). Donc x∗1 = 0 n’est pas acceptable.

Abdelkader Benaouali Techniques d’optimisation

 Introduction
Solution par substitution directe
Optimisation avec contraintes d’égalité
Solution par les multiplicateurs de Lagrange
Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité

Solution par les multiplicateurs de Lagrange

Optimisation avec contraintes d’égalité :

B. Solution par les multiplicateurs de Lagrange
Exemple 4 : (cont.)

(1) et (2) =⇒ x∗1 = −2(−2x∗1 (λ∗ +1))(λ∗ +1) =⇒ x∗1 = 4x∗1 (λ∗ +1)2

x∗1 1 − 4(λ∗ + 1)2 = 0

 
=⇒

1 3
=⇒ x∗1 = 0 ou λ∗ = − ou λ∗ = −
2 2

• L’équation (1) avec x∗1 = 0 donne x∗2 = 0, alors que (0, 0) ne vérifie pas la
contrainte (équation (3)). Donc x∗1 = 0 n’est pas acceptable.
1
• Pour λ∗ = − , l’équation (1) donne x∗2 = −x∗1 .
2
3
• Pour λ∗ = − , l’équation (1) donne x∗2 = x∗1 .
2
Abdelkader Benaouali Techniques d’optimisation
 Introduction
Solution par substitution directe
Optimisation avec contraintes d’égalité
Solution par les multiplicateurs de Lagrange
Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité

Solution par les multiplicateurs de Lagrange

Optimisation avec contraintes d’égalité :

B. Solution par les multiplicateurs de Lagrange
Exemple 4 : (cont.)

1
• Pour λ∗ = − , l’équation (1) donne x∗2 = −x∗1 .
2
Donc, L’équation (3) devient (x∗1 )2 = 4 =⇒ x∗1 = ±2
" # " #
2 −2
Deux points stationnaires
−2 2

Abdelkader Benaouali Techniques d’optimisation

 Introduction
Solution par substitution directe
Optimisation avec contraintes d’égalité
Solution par les multiplicateurs de Lagrange
Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité

Solution par les multiplicateurs de Lagrange

Optimisation avec contraintes d’égalité :

B. Solution par les multiplicateurs de Lagrange
Exemple 4 : (cont.)

1
• Pour λ∗ = − , l’équation (1) donne x∗2 = −x∗1 .
2
Donc, L’équation (3) devient (x∗1 )2 = 4 =⇒ x∗1 = ±2
" # " #
2 −2
Deux points stationnaires
−2 2
3
• Pour λ∗ = − , l’équation (1) donne x∗2 = x∗1 .
2
Donc, L’équation (3) devient (x∗1 )2 = 4 =⇒ x∗1 = ±2
" # " #
2 −2
Deux points stationnaires
2 −2
Abdelkader Benaouali Techniques d’optimisation
 Introduction
Solution par substitution directe
Optimisation avec contraintes d’égalité
Solution par les multiplicateurs de Lagrange
Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité

Solution par les multiplicateurs de Lagrange

Optimisation avec contraintes d’égalité :

B. Solution par les multiplicateurs de Lagrange
Exemple 4 : (cont.)

1
x2

-1

-2

-3
-3 -2 -1 0 1 2 3
x1

Abdelkader Benaouali Techniques d’optimisation

 Introduction
Solution par substitution directe
Optimisation avec contraintes d’égalité
Solution par les multiplicateurs de Lagrange
Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité

Solution par les multiplicateurs de Lagrange

Optimisation avec contraintes d’égalité :

B. Solution par les multiplicateurs de Lagrange [Conditions suffisantes]

Abdelkader Benaouali Techniques d’optimisation

 Introduction
Solution par substitution directe
Optimisation avec contraintes d’égalité
Solution par les multiplicateurs de Lagrange
Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité

Solution par les multiplicateurs de Lagrange

Optimisation avec contraintes d’égalité :

B. Solution par les multiplicateurs de Lagrange [Conditions suffisantes]
Les conditions KKT sont des conditions nécessaires, i.e. si un point satisfait
ses conditions, il est seulement garanti que ce point est stationnaire (minimum,
maximum ou selle).
Les conditions suffisantes sont obtenues en examinant les exigences du 2eme ordre.
Soit f et h des fonctions deux fois cont. différentiables. Le point X ∗ est un
minimum local strict s’ils existent des multiplicateurs de Lagrange λ∗ tels que :

Abdelkader Benaouali Techniques d’optimisation

 Introduction
Solution par substitution directe
Optimisation avec contraintes d’égalité
Solution par les multiplicateurs de Lagrange
Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité

Solution par les multiplicateurs de Lagrange

Optimisation avec contraintes d’égalité :

B. Solution par les multiplicateurs de Lagrange [Conditions suffisantes]
Les conditions KKT sont des conditions nécessaires, i.e. si un point satisfait
ses conditions, il est seulement garanti que ce point est stationnaire (minimum,
maximum ou selle).
Les conditions suffisantes sont obtenues en examinant les exigences du 2eme ordre.
Soit f et h des fonctions deux fois cont. différentiables. Le point X ∗ est un
minimum local strict s’ils existent des multiplicateurs de Lagrange λ∗ tels que :

Les conditions KKT sont satisfaites en ce point (X ∗ est un point KKT) ;

Abdelkader Benaouali Techniques d’optimisation

 Introduction
Solution par substitution directe
Optimisation avec contraintes d’égalité
Solution par les multiplicateurs de Lagrange
Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité

Solution par les multiplicateurs de Lagrange

Optimisation avec contraintes d’égalité :

B. Solution par les multiplicateurs de Lagrange [Conditions suffisantes]
Les conditions KKT sont des conditions nécessaires, i.e. si un point satisfait
ses conditions, il est seulement garanti que ce point est stationnaire (minimum,
maximum ou selle).
Les conditions suffisantes sont obtenues en examinant les exigences du 2eme ordre.
Soit f et h des fonctions deux fois cont. différentiables. Le point X ∗ est un
minimum local strict s’ils existent des multiplicateurs de Lagrange λ∗ tels que :

Les conditions KKT sont satisfaites en ce point (X ∗ est un point KKT) ;

La matrice hessienne du Lagrangien ∇2x L (X ∗ , λ∗ ) est définie positive dans
le sous-espace tangent aux contraintes linéarisées, i.e. :

wT ∇2x L (X ∗ , λ∗ ) w > 0,
pour tout vecteur w tel que ∇hk (X ∗ )T w = 0, k = 1, · · · , m.

Abdelkader Benaouali Techniques d’optimisation

 Introduction
Solution par substitution directe
Optimisation avec contraintes d’égalité
Solution par les multiplicateurs de Lagrange
Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité

Solution par les multiplicateurs de Lagrange

Optimisation avec contraintes d’égalité :

B. Solution par les multiplicateurs de Lagrange [Conditions suffisantes]
Exemple 1 :
min f (X) = 20 − x1 x2
s.c. x1 + x2 = 6

Abdelkader Benaouali Techniques d’optimisation

 Introduction
Solution par substitution directe
Optimisation avec contraintes d’égalité
Solution par les multiplicateurs de Lagrange
Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité

Solution par les multiplicateurs de Lagrange

Optimisation avec contraintes d’égalité :

B. Solution par les multiplicateurs de Lagrange [Conditions suffisantes]
Exemple 1 :
min f (X) = 20 − x1 x2
s.c. x1 + x2 = 6

L(x1 , x2 , λ) = 20 − x1 x2 + λ (x1 + x2 − 6)
" #
0 −1
2
La matrice hessienne du Lagrangien ∇x L =
−1 0

Un seul point stationnaire trouvé (x∗1 , x∗2 ) = (3 , 3) avec λ∗ = 3

On doit déterminer la nature de la matrice hessienne du Lagrangien ∇2x L (X ∗ , λ∗ )

dans le sous-espace tangent aux contraintes linéarisées défini par :

∇h(X ∗ )T w = 0 avec ∇h(X) = [1 1]T

Abdelkader Benaouali Techniques d’optimisation
 Introduction
Solution par substitution directe
Optimisation avec contraintes d’égalité
Solution par les multiplicateurs de Lagrange
Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité

Solution par les multiplicateurs de Lagrange

Optimisation avec contraintes d’égalité :

B. Solution par les multiplicateurs de Lagrange [Conditions suffisantes]
Exemple 1 : Cont.
Les directions w = (w1 , w2 )T qui définissent le sous-espace tangent aux contraintes
linéarisées :
∇h (X ∗ )T w = w1 + w2 = 0
=⇒ w2 = −w1
" #
w1
=⇒ w =
−w1
" #" #
0 −1 w1
T ∗ ∗
∇2x = 2 w12 > 0
 
w L (X , λ ) w = w1 −w1
−1 0 −w1

=⇒ Le point (x∗1 , x∗2 ) = (3 , 3) est un minimum local

Abdelkader Benaouali Techniques d’optimisation

 Introduction
Solution par substitution directe
Optimisation avec contraintes d’égalité
Solution par les multiplicateurs de Lagrange
Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité

Solution par les multiplicateurs de Lagrange

Optimisation avec contraintes d’égalité :

B. Solution par les multiplicateurs de Lagrange [Conditions suffisantes]
Exemple 3 :
min f (X) = x21 + x22
s.c. x21 + 2 x22 − 1 = 0

Abdelkader Benaouali Techniques d’optimisation

 Introduction
Solution par substitution directe
Optimisation avec contraintes d’égalité
Solution par les multiplicateurs de Lagrange
Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité

Solution par les multiplicateurs de Lagrange

Optimisation avec contraintes d’égalité :

B. Solution par les multiplicateurs de Lagrange [Conditions suffisantes]
Exemple 3 :
min f (X) = x21 + x22
s.c. x21 + 2 x22 − 1 = 0

L(x1 , x2 , λ) = x21 + x22 + λ (x21 + 2 x22 − 1)

 
0 " #
−1 ±1
∗
4 points stationnaires  1  avec λ = 2 et avec λ∗ = −1
 
±√ 0
2
" #
2 + 2λ 0
2
La matrice hessienne du Lagrangien ∇x L =
0 2 + 4λ

et ∇h(X) = [2 x1 4 x2 ]T
Abdelkader Benaouali Techniques d’optimisation
 Introduction
Solution par substitution directe
Optimisation avec contraintes d’égalité
Solution par les multiplicateurs de Lagrange
Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité

Solution par les multiplicateurs de Lagrange

Optimisation avec contraintes d’égalité :

B. Solution par les multiplicateurs de Lagrange [Conditions suffisantes]
Exemple 3 : Cont.
" # " #
−1 1 0 0
∗
• Pour λ = , ∇2x L(X ∗ , λ∗ ) = et ∇h(X ) = ∗
√
2 0 0 ±2 2
" #
√
∗ T
w1
∇h (X ) w = ±2 2 w2 = 0 =⇒ w=
0
" #" #
1 0 w1
T ∗ ∗
∇2x = w12 > 0
 
w L (X , λ ) w = w1 0
0 0 0

1
=⇒ Les deux points (0 , ± √ ) sont des minima locaux.
2

Abdelkader Benaouali Techniques d’optimisation

 Introduction
Solution par substitution directe
Optimisation avec contraintes d’égalité
Solution par les multiplicateurs de Lagrange
Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité

Solution par les multiplicateurs de Lagrange

Optimisation avec contraintes d’égalité :

B. Solution par les multiplicateurs de Lagrange [Conditions suffisantes]
Exemple 3 : Cont.
" # " #
0 0 ±2
∗
• Pour λ = −1 , ∇2x L(X ∗ , λ∗ ) = et ∗
∇h(X ) =
0 −2 0
" #
0
∇h (X ∗ )T w = ±2 w1 = 0 =⇒ w=
w2
" #" #
0 0 0
wT ∇2x L (X ∗ , λ∗ ) w = = −2 w22 < 0
 
0 w2
0 −2 w2

=⇒ Les deux points (±1 , 0) sont des maxima locaux.

Abdelkader Benaouali Techniques d’optimisation

 Introduction Optimisation avec une seule contrainte d’inégalité
Optimisation avec contraintes d’égalité Optimisation avec des contraintes inégalité
Optimisation avec contraintes d’égalité et d’inégalité Cas général

Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité et d’inégalité :

Abdelkader Benaouali Techniques d’optimisation

 Introduction Optimisation avec une seule contrainte d’inégalité
Optimisation avec contraintes d’égalité Optimisation avec des contraintes inégalité
Optimisation avec contraintes d’égalité et d’inégalité Cas général

Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité et d’inégalité :

Comme déjà mentionné, en un point réalisable X, une contrainte d’inégalité

gj (X) est dite active si gj (X) = 0 et dite inactive si l’inégalité stricte est
satisfaite gj (X) < 0.

Comme les minimas ne sont pas connus a priori, on ne sait pas si une inégalité
est active ou inactive au point optimal. Le statut de la contrainte d’inégalité
(active ou inactive) doit être déterminé dans le cadre de la solution du problème.

Généralement, si le minimum non contraint (contraintes ignorées) viole au moins

une des contraintes, le minimum contraint a lieu sur la frontière de la zone
admissible. Dans ce cas, une contrainte, ou plus, est active.

Si, par contre, le minimum non contraint satisfait toutes les contraintes, ce point
est aussi le minimum contraint. Dans ce cas, les contraintes sont inactives.

Abdelkader Benaouali Techniques d’optimisation

 Introduction Optimisation avec une seule contrainte d’inégalité
Optimisation avec contraintes d’égalité Optimisation avec des contraintes inégalité
Optimisation avec contraintes d’égalité et d’inégalité Cas général

Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité et d’inégalité :

Un exemple de problème d’optimisation avec contrainte d’inégalité :

min f (x1 , x2 ) = (x1 − 1.5)2 + (x2 − 1.5)2

(
x1 + x2 − 2 ≤ 0
s.c.
−x1 ≤ 0 ; −x2 ≤ 0

Abdelkader Benaouali Techniques d’optimisation

 Introduction Optimisation avec une seule contrainte d’inégalité
Optimisation avec contraintes d’égalité Optimisation avec des contraintes inégalité
Optimisation avec contraintes d’égalité et d’inégalité Cas général

Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité et d’inégalité :

Un exemple de problème d’optimisation avec contrainte d’inégalité :

min f (x1 , x2 ) = (x1 − 1.5)2 + (x2 − 1.5)2

(
x1 + x2 − 2 ≤ 0
s.c.
−x1 ≤ 0 ; −x2 ≤ 0

2
(1.5,1.5) minmum contraint

1
Zone
réalisable

0 1 2

Abdelkader Benaouali Techniques d’optimisation

 Introduction Optimisation avec une seule contrainte d’inégalité
Optimisation avec contraintes d’égalité Optimisation avec des contraintes inégalité
Optimisation avec contraintes d’égalité et d’inégalité Cas général

Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité et d’inégalité :

Un exemple de problème d’optimisation avec contrainte d’inégalité :

min f (x1 , x2 ) = (x1 − 1.5)2 + (x2 − 1.5)2

(
x1 + x2 − 2 ≤ 0
s.c.
−x1 ≤ 0 ; −x2 ≤ 0

2
(1.5,1.5) minmum contraint
La contrainte
est active 1
en
Zone
réalisable

0 1 2

Abdelkader Benaouali Techniques d’optimisation

 Introduction Optimisation avec une seule contrainte d’inégalité
Optimisation avec contraintes d’égalité Optimisation avec des contraintes inégalité
Optimisation avec contraintes d’égalité et d’inégalité Cas général

Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec contraintes d’égalité et d’inégalité :

Un autre exemple avec les mêmes contraintes mais une fonction objectif modifiée :

min f (x1 , x2 ) = (x1 − 0.5)2 + (x2 − 0.5)2

(
x1 + x2 − 2 ≤ 0
s.c.
−x1 ≤ 0 ; −x2 ≤ 0

2
minmum contraint
La contrainte
est inactive 1
en (0.5,0.5)

0 1 2

Abdelkader Benaouali Techniques d’optimisation

 Introduction Optimisation avec une seule contrainte d’inégalité
Optimisation avec contraintes d’égalité Optimisation avec des contraintes inégalité
Optimisation avec contraintes d’égalité et d’inégalité Cas général

Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec une seule contrainte d’inégalité

Optimisation avec contraintes d’égalité et d’inégalité :

A. Optimisation avec une seule contrainte d’inégalité

Abdelkader Benaouali Techniques d’optimisation

 Introduction Optimisation avec une seule contrainte d’inégalité
Optimisation avec contraintes d’égalité Optimisation avec des contraintes inégalité
Optimisation avec contraintes d’égalité et d’inégalité Cas général

Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec une seule contrainte d’inégalité

Optimisation avec contraintes d’égalité et d’inégalité :

A. Optimisation avec une seule contrainte d’inégalité
Pour déterminer les conditions d’optimalité, on considère l’exemple suivant :

Minimiser f (X) s.c. g(X) ≤ 0

avec :

f (X) = x21 + x22 , g(X) = x21 + x22 − 1

Abdelkader Benaouali Techniques d’optimisation

 Introduction Optimisation avec une seule contrainte d’inégalité
Optimisation avec contraintes d’égalité Optimisation avec des contraintes inégalité
Optimisation avec contraintes d’égalité et d’inégalité Cas général

Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec une seule contrainte d’inégalité

Optimisation avec contraintes d’égalité et d’inégalité :

A. Optimisation avec une seule contrainte d’inégalité

minimum de
sans tenir compte
des contraintes

isocontours de

f (X) = x21 + x22

Abdelkader Benaouali Techniques d’optimisation

 Introduction Optimisation avec une seule contrainte d’inégalité
Optimisation avec contraintes d’égalité Optimisation avec des contraintes inégalité
Optimisation avec contraintes d’égalité et d’inégalité Cas général

Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec une seule contrainte d’inégalité

Optimisation avec contraintes d’égalité et d’inégalité :

A. Optimisation avec une seule contrainte d’inégalité

zone réalisable :

isocontours de

g(X) = x21 + x22 − 1

Abdelkader Benaouali Techniques d’optimisation

 Introduction Optimisation avec une seule contrainte d’inégalité
Optimisation avec contraintes d’égalité Optimisation avec des contraintes inégalité
Optimisation avec contraintes d’égalité et d’inégalité Cas général

Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec une seule contrainte d’inégalité

Optimisation avec contraintes d’égalité et d’inégalité :

A. Optimisation avec une seule contrainte d’inégalité

comment reconnaitre si
est un minimum local ?

Xr indique un point réalisable.

Abdelkader Benaouali Techniques d’optimisation

 Introduction Optimisation avec une seule contrainte d’inégalité
Optimisation avec contraintes d’égalité Optimisation avec des contraintes inégalité
Optimisation avec contraintes d’égalité et d’inégalité Cas général

Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec une seule contrainte d’inégalité

Optimisation avec contraintes d’égalité et d’inégalité :

A. Optimisation avec une seule contrainte d’inégalité

comment reconnaitre si
Le minimum non contraint
est un minimum local ?
de est à l'intérieur du
domaine réalisable

On est loin des frontières, les conditions d’optimalité sont les mêmes que pour
un problème non-contraint :
∇f (X ∗ ) = 0 et ∇2 f (X ∗ ) est définie positive

Abdelkader Benaouali Techniques d’optimisation

 Introduction Optimisation avec une seule contrainte d’inégalité
Optimisation avec contraintes d’égalité Optimisation avec des contraintes inégalité
Optimisation avec contraintes d’égalité et d’inégalité Cas général

Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec une seule contrainte d’inégalité

Optimisation avec contraintes d’égalité et d’inégalité :

A. Optimisation avec une seule contrainte d’inégalité

comment reconnaitre si
Le minimum non contraint
est un minimum local ?
de est à l'intérieur du
domaine réalisable

La contrainte n’est pas active au point minimum local (g(X ∗ ) < 0)

Le minimum local est identifié en utilisant les mêmes conditions que
dans le cas sans contraintes.

Abdelkader Benaouali Techniques d’optimisation

 Introduction Optimisation avec une seule contrainte d’inégalité
Optimisation avec contraintes d’égalité Optimisation avec des contraintes inégalité
Optimisation avec contraintes d’égalité et d’inégalité Cas général

Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec une seule contrainte d’inégalité

Optimisation avec contraintes d’égalité et d’inégalité :

A. Optimisation avec une seule contrainte d’inégalité
Considérons un autre exemple similaire :

Minimiser f (X) s.c. g(X) ≤ 0

avec :

f (X) = (x1 − 1.1)2 + (x2 − 1.1)2 , g(X) = x21 + x22 − 1

Abdelkader Benaouali Techniques d’optimisation

 Introduction Optimisation avec une seule contrainte d’inégalité
Optimisation avec contraintes d’égalité Optimisation avec des contraintes inégalité
Optimisation avec contraintes d’égalité et d’inégalité Cas général

Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec une seule contrainte d’inégalité

Optimisation avec contraintes d’égalité et d’inégalité :

A. Optimisation avec une seule contrainte d’inégalité

minimum de
sans tenir compte
des contraintes

isocontours de

f (X) = (x1 − 1.1)2 + (x2 − 1.1)2

Abdelkader Benaouali Techniques d’optimisation

 Introduction Optimisation avec une seule contrainte d’inégalité
Optimisation avec contraintes d’égalité Optimisation avec des contraintes inégalité
Optimisation avec contraintes d’égalité et d’inégalité Cas général

Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec une seule contrainte d’inégalité

Optimisation avec contraintes d’égalité et d’inégalité :

A. Optimisation avec une seule contrainte d’inégalité

zone réalisable :

isocontours de

g(X) = x21 + x22 − 1

Abdelkader Benaouali Techniques d’optimisation

 Introduction Optimisation avec une seule contrainte d’inégalité
Optimisation avec contraintes d’égalité Optimisation avec des contraintes inégalité
Optimisation avec contraintes d’égalité et d’inégalité Cas général

Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec une seule contrainte d’inégalité

Optimisation avec contraintes d’égalité et d’inégalité :

A. Optimisation avec une seule contrainte d’inégalité

comment reconnaitre si
est un minimum local ?

Xr indique un point réalisable.

Abdelkader Benaouali Techniques d’optimisation

 Introduction Optimisation avec une seule contrainte d’inégalité
Optimisation avec contraintes d’égalité Optimisation avec des contraintes inégalité
Optimisation avec contraintes d’égalité et d’inégalité Cas général

Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec une seule contrainte d’inégalité

Optimisation avec contraintes d’égalité et d’inégalité :

A. Optimisation avec une seule contrainte d’inégalité

le minimum local non

comment reconnaitre si contraint de a lieu en
est un minimum local ? dehors de la region réalisable

Le minimum local contraint a lieu sur la surface définie par la contrainte

Abdelkader Benaouali Techniques d’optimisation

 Introduction Optimisation avec une seule contrainte d’inégalité
Optimisation avec contraintes d’égalité Optimisation avec des contraintes inégalité
Optimisation avec contraintes d’égalité et d’inégalité Cas général

Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec une seule contrainte d’inégalité

Optimisation avec contraintes d’égalité et d’inégalité :

A. Optimisation avec une seule contrainte d’inégalité

le minimum local non

comment reconnaitre si contraint de a lieu en
est un minimum local ? dehors de la region réalisable

On a effectivement un problème d’optimisation avec une contrainte

d’égalité (g(X ∗ ) = 0)

Abdelkader Benaouali Techniques d’optimisation

 Introduction Optimisation avec une seule contrainte d’inégalité
Optimisation avec contraintes d’égalité Optimisation avec des contraintes inégalité
Optimisation avec contraintes d’égalité et d’inégalité Cas général

Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec une seule contrainte d’inégalité

Optimisation avec contraintes d’égalité et d’inégalité :

A. Optimisation avec une seule contrainte d’inégalité

Le minimum local contraint a lieu lorsque −∇f (X) et ∇g(X) sont parallèles

−∇f (X ∗ ) = µ ∇g(X ∗ )

Abdelkader Benaouali Techniques d’optimisation

 Introduction Optimisation avec une seule contrainte d’inégalité
Optimisation avec contraintes d’égalité Optimisation avec des contraintes inégalité
Optimisation avec contraintes d’égalité et d’inégalité Cas général

Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec une seule contrainte d’inégalité

Optimisation avec contraintes d’égalité et d’inégalité :

A. Optimisation avec une seule contrainte d’inégalité

ce n'est pas un minimum

local contraint car
pointe vers l'interieur du
domaine réalisable

Le minimum local contraint a lieu lorsque −∇f (X) et ∇g(X) sont parallèles

−∇f (X ∗ ) = µ ∇g(X ∗ )

Abdelkader Benaouali Techniques d’optimisation

 Introduction Optimisation avec une seule contrainte d’inégalité
Optimisation avec contraintes d’égalité Optimisation avec des contraintes inégalité
Optimisation avec contraintes d’égalité et d’inégalité Cas général

Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec une seule contrainte d’inégalité

Optimisation avec contraintes d’égalité et d’inégalité :

A. Optimisation avec une seule contrainte d’inégalité

c'est un minimum local

contraint comme
pointe vers l'exterieur du
domaine réalisable

Le minimum local contraint a lieu lorsque −∇f (X) et ∇g(X) pointent vers
la même direction :
−∇f (X ∗ ) = µ ∇g(X ∗ ) et µ > 0

Abdelkader Benaouali Techniques d’optimisation

 Introduction Optimisation avec une seule contrainte d’inégalité
Optimisation avec contraintes d’égalité Optimisation avec des contraintes inégalité
Optimisation avec contraintes d’égalité et d’inégalité Cas général

Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec une seule contrainte d’inégalité

Optimisation avec contraintes d’égalité et d’inégalité :

A. Optimisation avec une seule contrainte d’inégalité

c'est un minimum local

contraint comme
pointe vers l'exterieur du
domaine réalisable

La contrainte est active au point minimum local (g(X ∗ ) = 0)

−∇f (X ∗ ) = µ ∇g(X ∗ ) et µ>0

Abdelkader Benaouali Techniques d’optimisation

 Introduction Optimisation avec une seule contrainte d’inégalité
Optimisation avec contraintes d’égalité Optimisation avec des contraintes inégalité
Optimisation avec contraintes d’égalité et d’inégalité Cas général

Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec une seule contrainte d’inégalité

Optimisation avec contraintes d’égalité et d’inégalité :

A. Optimisation avec une seule contrainte d’inégalité

En résumé :

Soit à résoudre :
Minimiser f (X) s.c. g(X) ≤ 0
Si X ∗ correspond à un minimum local contraint du problème, alors
Cas 1 : Cas 2 :
Le minimum non contraint est à Le minimum non contraint est à
l’intérieur du domaine réalisable. l’extérieur du domaine réalisable.
g(X ∗ ) < 0 g(X ∗ ) = 0
∇f (X ∗ ) = 0 −∇f (X ∗ ) = µ∗ ∇g(X ∗ )
=⇒ ∇f (X ∗ ) = 0 et µ∗ > 0

Abdelkader Benaouali Techniques d’optimisation

 Introduction Optimisation avec une seule contrainte d’inégalité
Optimisation avec contraintes d’égalité Optimisation avec des contraintes inégalité
Optimisation avec contraintes d’égalité et d’inégalité Cas général

Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec une seule contrainte d’inégalité

Optimisation avec contraintes d’égalité et d’inégalité :

A. Optimisation avec une seule contrainte d’inégalité

En résumé :

On définit le Lagrangien comme

L(X, µ) = f (X) + µ g(X)
Si X ∗ correspond à un minimum local contraint du problème, alors
Cas 1 : Cas 2 :
Le minimum non contraint est à Le minimum non contraint est à
l’intérieur du domaine réalisable. l’extérieur du domaine réalisable.
g(X ∗ ) < 0 g(X ∗ ) = 0
∇x L(X ∗ , µ∗ ) = 0 et µ = 0 ∇x L(X ∗ , µ∗ ) = 0 et µ∗ > 0
=⇒ ∇f (X ∗ ) = 0 ⇒ −∇f (X ∗ ) = µ∗ ∇g(X ∗ )

Abdelkader Benaouali Techniques d’optimisation

 Introduction Optimisation avec une seule contrainte d’inégalité
Optimisation avec contraintes d’égalité Optimisation avec des contraintes inégalité
Optimisation avec contraintes d’égalité et d’inégalité Cas général

Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec une seule contrainte d’inégalité

Optimisation avec contraintes d’égalité et d’inégalité :

A. Optimisation avec une seule contrainte d’inégalité

Conditions nécessaires (une seule contrainte d’inégalité)

Soit X ∗ un point régulier qui est un minimum local de f (X) sous une contrainte
g(X) ≤ 0 . Alors, il existe un multiplicateur de Lagrange unique µ∗ tel que :
1 ∇x L(X ∗ , µ∗ ) = 0
2 g(X ∗ ) ≤ 0
3 µ∗ ≥ 0
4 µ∗ g(X ∗ ) = 0

La dernière condition traduit les deux cas (contrainte active ou inactive)

Abdelkader Benaouali Techniques d’optimisation

 Introduction Optimisation avec une seule contrainte d’inégalité
Optimisation avec contraintes d’égalité Optimisation avec des contraintes inégalité
Optimisation avec contraintes d’égalité et d’inégalité Cas général

Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec une seule contrainte d’inégalité

Optimisation avec contraintes d’égalité et d’inégalité :

A. Optimisation avec une seule contrainte d’inégalité

Conditions nécessaires (une seule contrainte d’inégalité)

Soit X ∗ un point régulier qui est un minimum local de f (X) sous une contrainte
g(X) ≤ 0 . Alors, il existe un multiplicateur de Lagrange unique µ∗ tel que :
1 ∇x L(X ∗ , µ∗ ) = 0
2 g(X ∗ ) ≤ 0
3 µ∗ ≥ 0
4 µ∗ g(X ∗ ) = 0

• contrainte inactive : g(X ∗ ) < 0 =⇒ µ∗ = 0

• contrainte active : g(X ∗ ) = 0 =⇒ µ∗ ≥ 0
Abdelkader Benaouali Techniques d’optimisation
 Introduction Optimisation avec une seule contrainte d’inégalité
Optimisation avec contraintes d’égalité Optimisation avec des contraintes inégalité
Optimisation avec contraintes d’égalité et d’inégalité Cas général

Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec une seule contrainte d’inégalité

Optimisation avec contraintes d’égalité et d’inégalité :

A. Optimisation avec une seule contrainte d’inégalité

Conditions nécessaires (une seule contrainte d’inégalité)

Soit X ∗ un point régulier qui est un minimum local de f (X) sous une contrainte
g(X) ≤ 0 . Alors, il existe un multiplicateur de Lagrange unique µ∗ tel que :
1 ∇x L(X ∗ , µ∗ ) = 0
2 g(X ∗ ) ≤ 0
3 µ∗ ≥ 0
4 µ∗ g(X ∗ ) = 0

Un cas particulier a lieu lorsque g(X ∗ ) = 0 et µ∗ = 0 : Le minimum non

contraint est sur la frontière du domaine réalisable (cas 3).

Abdelkader Benaouali Techniques d’optimisation

 Introduction Optimisation avec une seule contrainte d’inégalité
Optimisation avec contraintes d’égalité Optimisation avec des contraintes inégalité
Optimisation avec contraintes d’égalité et d’inégalité Cas général

Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec une seule contrainte d’inégalité

Optimisation avec contraintes d’égalité et d’inégalité :

A. Optimisation avec une seule contrainte d’inégalité
Exemple 5 :
min f (X) = x21 + x22 − 3 x1 x2
s.c. x21 + x22 − 6 ≤ 0

Abdelkader Benaouali Techniques d’optimisation

 Introduction Optimisation avec une seule contrainte d’inégalité
Optimisation avec contraintes d’égalité Optimisation avec des contraintes inégalité
Optimisation avec contraintes d’égalité et d’inégalité Cas général

Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec une seule contrainte d’inégalité

Optimisation avec contraintes d’égalité et d’inégalité :

A. Optimisation avec une seule contrainte d’inégalité
Exemple 5 :
min f (X) = x21 + x22 − 3 x1 x2
s.c. x21 + x22 − 6 ≤ 0

L(x1 , x2 , µ) = x21 + x22 − 3 x1 x2 + µ (x21 + x22 − 6)

Abdelkader Benaouali Techniques d’optimisation

 Introduction Optimisation avec une seule contrainte d’inégalité
Optimisation avec contraintes d’égalité Optimisation avec des contraintes inégalité
Optimisation avec contraintes d’égalité et d’inégalité Cas général

Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec une seule contrainte d’inégalité

Optimisation avec contraintes d’égalité et d’inégalité :

A. Optimisation avec une seule contrainte d’inégalité
Exemple 5 :
min f (X) = x21 + x22 − 3 x1 x2
s.c. x21 + x22 − 6 ≤ 0

L(x1 , x2 , µ) = x21 + x22 − 3 x1 x2 + µ (x21 + x22 − 6)

∂L(x∗1 , x∗2 , µ∗ )


 = 2 x1 − 3 x2 + 2 µ x1 = 0


 ∂x1

∂L(x∗1 , x∗2 , µ∗ )




 = 2 x2 − 3 x1 + 2 µ x2 = 0
∂x2


 x21 + x22 − 6 ≤ 0




µ≥0






µ (x21 + x22 − 6) = 0


Abdelkader Benaouali Techniques d’optimisation

 Introduction Optimisation avec une seule contrainte d’inégalité
Optimisation avec contraintes d’égalité Optimisation avec des contraintes inégalité
Optimisation avec contraintes d’égalité et d’inégalité Cas général

Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec une seule contrainte d’inégalité

Optimisation avec contraintes d’égalité et d’inégalité :

A. Optimisation avec une seule contrainte d’inégalité
Exemple 5 :
min f (X) = x21 + x22 − 3 x1 x2
s.c. x21 + x22 − 6 ≤ 0

Cas 1 : contrainte inactive ou bien µ = 0

  

  2 x∗1 − 3 x∗2 = 0  x∗1 = 0


 =⇒
 2 x∗ − 3 x∗ = 0  x∗ = 0
2 1 2




g(x∗1 , x∗2 ) = x∗1 2 + x∗2 2 − 6 = −6 < 0


Donc, le point (0 , 0) satisfait les conditions KKT (candidat à être

minimum).

Abdelkader Benaouali Techniques d’optimisation

 Introduction Optimisation avec une seule contrainte d’inégalité
Optimisation avec contraintes d’égalité Optimisation avec des contraintes inégalité
Optimisation avec contraintes d’égalité et d’inégalité Cas général

Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec une seule contrainte d’inégalité

Optimisation avec contraintes d’égalité et d’inégalité :

A. Optimisation avec une seule contrainte d’inégalité
Exemple 5 :
min f (X) = x21 + x22 − 3 x1 x2
s.c. x21 + x22 − 6 ≤ 0

Cas 2 : contrainte active ou bien g = 0

2 x∗1 − 3 x∗2 + 2 µ x∗1 = 0 2 (1 + µ) x∗1 − 3 x∗2 = 0

 ( (


 =⇒
2 x∗2 − 3 x∗1 + 2 µ x∗2 = 0 2 (1 + µ) x∗2 − 3 x∗1 = 0







=⇒ x∗1 2 = x∗2 2







 x∗1 2 + x∗2 2 − 6 = 0 =⇒ x∗1 2 = x∗2 2 = 3
√ √ √ √



( 3, 3) , ( 3, − 3)



=⇒


 √ √ √ √
(− 3, 3) , (− 3, − 3)


Abdelkader Benaouali Techniques d’optimisation

 Introduction Optimisation avec une seule contrainte d’inégalité
Optimisation avec contraintes d’égalité Optimisation avec des contraintes inégalité
Optimisation avec contraintes d’égalité et d’inégalité Cas général

Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec une seule contrainte d’inégalité

Optimisation avec contraintes d’égalité et d’inégalité :

A. Optimisation avec une seule contrainte d’inégalité
Exemple 5 :
min f (X) = x21 + x22 − 3 x1 x2
s.c. x21 + x22 − 6 ≤ 0

Cas 2 : contrainte active ou bien g = 0

2 x∗1 − 3 x∗2 + 2 µ x∗1 = 0 2 (1 + µ) x∗1 − 3 x∗2 = 0

 ( (


 =⇒
2 x∗2 − 3 x∗1 + 2 µ x∗2 = 0 2 (1 + µ) x∗2 − 3 x∗1 = 0







=⇒ x∗1 2 = x∗2 2







 x∗1 2 + x∗2 2 − 6 = 0 =⇒ x∗1 2 = x∗2 2 = 3
√ √ √ √



( 3, 3) , ( 3, − 3)



=⇒


 √ √ √ √
(− 3, 3) , (− 3, − 3)


Abdelkader Benaouali Techniques d’optimisation

 Introduction Optimisation avec une seule contrainte d’inégalité
Optimisation avec contraintes d’égalité Optimisation avec des contraintes inégalité
Optimisation avec contraintes d’égalité et d’inégalité Cas général

Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec une seule contrainte d’inégalité

Optimisation avec contraintes d’égalité et d’inégalité :

A. Optimisation avec une seule contrainte d’inégalité
Exemple 5 :
min f (X) = x21 + x22 − 3 x1 x2
s.c. x21 + x22 − 6 ≤ 0

Cas 2 : contrainte active ou bien g = 0

2 x∗1 − 3 x∗2 + 2 µ x∗1 = 0 2 (1 + µ) x∗1 − 3 x∗2 = 0

 ( (


 =⇒
2 x∗2 − 3 x∗1 + 2 µ x∗2 = 0 2 (1 + µ) x∗2 − 3 x∗1 = 0







=⇒ x∗1 2 = x∗2 2







 x∗1 2 + x∗2 2 − 6 = 0 =⇒ x∗1 2 = x∗2 2 = 3
√ √ √ √



( 3, 3) , ( 3, − 3)



=⇒


 √ √ √ √
(− 3, 3) , (− 3, − 3)


Abdelkader Benaouali Techniques d’optimisation

 Introduction Optimisation avec une seule contrainte d’inégalité
Optimisation avec contraintes d’égalité Optimisation avec des contraintes inégalité
Optimisation avec contraintes d’égalité et d’inégalité Cas général

Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec une seule contrainte d’inégalité

Optimisation avec contraintes d’égalité et d’inégalité :

A. Optimisation avec une seule contrainte d’inégalité
Exemple 5 :
min f (X) = x21 + x22 − 3 x1 x2
s.c. x21 + x22 − 6 ≤ 0

Cas 2 : contrainte active ou bien g = 0

√ √ 1
1. (x∗1 , x∗2 ) = ( 3, 3 ) et µ = > 0 =⇒ candidat à être minimum
2
√ √ 1
2. (x∗1 , x∗2 ) = ( − 3, − 3 ) et µ = > 0 =⇒ candidat à être minimum
2
√ √ 5
3. (x∗1 , x∗2 ) = ( 3, − 3 ) et µ = − < 0 =⇒ ne satisfait pas les
2
conditions KKT
√ √ 5
4. (x∗1 , x∗2 ) = ( − 3, 3 ) et µ = − < 0 =⇒ ne satisfait pas les
2
conditions KKT
Abdelkader Benaouali Techniques d’optimisation
 Introduction Optimisation avec une seule contrainte d’inégalité
Optimisation avec contraintes d’égalité Optimisation avec des contraintes inégalité
Optimisation avec contraintes d’égalité et d’inégalité Cas général

Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec une seule contrainte d’inégalité

Optimisation avec contraintes d’égalité et d’inégalité :

A. Optimisation avec une seule contrainte d’inégalité
Exemple 5 :
min f (X) = x21 + x22 − 3 x1 x2
s.c. x21 + x22 − 6 ≤ 0

Résumé : Les points KKT (candidats pour être minimum ) sont :

√ √ 1
1. (x∗1 , x∗2 ) = ( 3, 3 ) et µ =
2
√ √ 1
2. (x∗1 , x∗2 ) = ( − 3, − 3 ) et µ =
2
3. (x∗1 , x∗2 ) = ( 0, 0 ) et µ = 0

Abdelkader Benaouali Techniques d’optimisation

 Introduction Optimisation avec une seule contrainte d’inégalité
Optimisation avec contraintes d’égalité Optimisation avec des contraintes inégalité
Optimisation avec contraintes d’égalité et d’inégalité Cas général

Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec une seule contrainte d’inégalité

Optimisation avec contraintes d’égalité et d’inégalité :

A. Optimisation avec une seule contrainte d’inégalité
Exemple 5 :
4

3
-7
-5
2 -3
-1
1
1

0
-4 -3 -2 -1 1 2 3 4

-1

-2

-3

-4

Dans le cas d’une contrainte d’inégalité active avec un multiplicateur de Lagrange

positif, les points KKT ne peuvent pas être des maxima locaux !
Abdelkader Benaouali Techniques d’optimisation
 Introduction Optimisation avec une seule contrainte d’inégalité
Optimisation avec contraintes d’égalité Optimisation avec des contraintes inégalité
Optimisation avec contraintes d’égalité et d’inégalité Cas général

Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec une seule contrainte d’inégalité

Optimisation avec contraintes d’égalité et d’inégalité :

B. Optimisation avec des contraintes inégalité

Abdelkader Benaouali Techniques d’optimisation

 Introduction Optimisation avec une seule contrainte d’inégalité
Optimisation avec contraintes d’égalité Optimisation avec des contraintes inégalité
Optimisation avec contraintes d’égalité et d’inégalité Cas général

Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec une seule contrainte d’inégalité

Optimisation avec contraintes d’égalité et d’inégalité :

B. Optimisation avec des contraintes inégalité
p
X
Le Lagrangien : L(X, µ) = f (X) + µj gj (X)
j=1

Conditions nécessaires (contraintes d’inégalité)

Soit X ∗ un point régulier qui est un minimum local de f (X) sous contraintes
gj (X) ≤ 0, j = 1, · · · , p . Alors, ils existent des multiplicateurs de Lagrange
uniques µ∗j , j = 1, · · · , p tels que :
1 ∇x L(X ∗ , µ∗ ) = 0
2 gj (X ∗ ) ≤ 0, j = 1, · · · , p
3 µ∗j ≥ 0, j = 1, · · · , p
4 µ∗j gj (X ∗ ) = 0, j = 1, · · · , p

Abdelkader Benaouali Techniques d’optimisation

 Introduction Optimisation avec une seule contrainte d’inégalité
Optimisation avec contraintes d’égalité Optimisation avec des contraintes inégalité
Optimisation avec contraintes d’égalité et d’inégalité Cas général

Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec une seule contrainte d’inégalité

Optimisation avec contraintes d’égalité et d’inégalité :

B. Optimisation avec des contraintes inégalité
Conditions nécessaires (contraintes d’inégalité)

Soit X ∗ un point régulier qui est un minimum local de f (X) sous contraintes
gj (X) ≤ 0, j = 1, · · · , p . Alors, ils existent des multiplicateurs de Lagrange
uniques µ∗j , j = 1, · · · , p tels que :
1 ∇x L(X ∗ , µ∗ ) = 0
2 gj (X ∗ ) ≤ 0, j = 1, · · · , p
3 µ∗j ≥ 0, j = 1, · · · , p
4 µ∗j gj (X ∗ ) = 0, j = 1, · · · , p

En général, la condition µ∗j gj (X ∗ ) = 0 mène à 2p cas de solutions distinctes.

Pour chaque cas, on doit résoudre les conditions nécessaires restantes.

Abdelkader Benaouali Techniques d’optimisation

 Introduction Optimisation avec une seule contrainte d’inégalité
Optimisation avec contraintes d’égalité Optimisation avec des contraintes inégalité
Optimisation avec contraintes d’égalité et d’inégalité Cas général

Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec une seule contrainte d’inégalité

Optimisation avec contraintes d’égalité et d’inégalité :

B. Optimisation avec des contraintes inégalité
Exemple 6 :
min f (X) = (x1 − 10)2 + (x2 − 8)2
(
g1 (x1 , x2 ) = x1 + x2 − 12 ≤ 0
s.c.
g2 (x1 , x2 ) = x1 − 8 ≤ 0

Abdelkader Benaouali Techniques d’optimisation

 Introduction Optimisation avec une seule contrainte d’inégalité
Optimisation avec contraintes d’égalité Optimisation avec des contraintes inégalité
Optimisation avec contraintes d’égalité et d’inégalité Cas général

Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec une seule contrainte d’inégalité

Optimisation avec contraintes d’égalité et d’inégalité :

B. Optimisation avec des contraintes inégalité
Exemple 6 :
min f (X) = (x1 − 10)2 + (x2 − 8)2
(
g1 (x1 , x2 ) = x1 + x2 − 12 ≤ 0
s.c.
g2 (x1 , x2 ) = x1 − 8 ≤ 0

L(x1 , x2 , µ1 , µ2 ) = (x1 − 10)2 + (x2 − 8)2 + µ1 (x1 + x2 − 12) + µ2 (x1 − 8)

Abdelkader Benaouali Techniques d’optimisation

 Introduction Optimisation avec une seule contrainte d’inégalité
Optimisation avec contraintes d’égalité Optimisation avec des contraintes inégalité
Optimisation avec contraintes d’égalité et d’inégalité Cas général

Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec une seule contrainte d’inégalité

Optimisation avec contraintes d’égalité et d’inégalité :

B. Optimisation avec des contraintes inégalité
Exemple 6 :
min f (X) = (x1 − 10)2 + (x2 − 8)2
(
g1 (x1 , x2 ) = x1 + x2 − 12 ≤ 0
s.c.
g2 (x1 , x2 ) = x1 − 8 ≤ 0

L(x1 , x2 , µ1 , µ2 ) = (x1 − 10)2 + (x2 − 8)2 + µ1 (x1 + x2 − 12) + µ2 (x1 − 8)

2 (x∗1 − 10) + µ∗1 + µ∗2 = 0


g1 et g2 inactives (µ∗1 = 0, µ∗2 = 0)

 

2 (x∗2 − 8) + µ∗1 = 0

 

 
 g1 inactive et g2 active (µ∗1 = 0, g2 = 0)

 


g1 ≤ 0 , g2 ≤ 0


 ∗ ∗

 g1 active et g2 inactive (g1 = 0, µ∗2 = 0)
µ1 , µ 2 ≥ 0
 

 
g1 et g2 actives (g1 = 0, g2 = 0)

 

 ∗
µ1 g1 = 0 , µ∗2 g2 = 0

Abdelkader Benaouali Techniques d’optimisation

 Introduction Optimisation avec une seule contrainte d’inégalité
Optimisation avec contraintes d’égalité Optimisation avec des contraintes inégalité
Optimisation avec contraintes d’égalité et d’inégalité Cas général

Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec une seule contrainte d’inégalité

Optimisation avec contraintes d’égalité et d’inégalité :

B. Optimisation avec des contraintes inégalité
Exemple 6 :
min f (X) = (x1 − 10)2 + (x2 − 8)2
(
g1 (x1 , x2 ) = x1 + x2 − 12 ≤ 0
s.c.
g2 (x1 , x2 ) = x1 − 8 ≤ 0

Cas 1 : g1 et g2 inactives (µ1 = 0, µ2 = 0)

2 (x∗1 − 10) = 0
( ( ∗
x1 = 10
∗
=⇒
2 (x2 − 8) = 0 x∗2 = 8
(
g1 (10, 8) = 6 > 0
les deux contraintes sont violées
g2 (10, 8) = 2 > 0

Ce cas ne donne pas de point candidat à être minimum.

Abdelkader Benaouali Techniques d’optimisation
 Introduction Optimisation avec une seule contrainte d’inégalité
Optimisation avec contraintes d’égalité Optimisation avec des contraintes inégalité
Optimisation avec contraintes d’égalité et d’inégalité Cas général

Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec une seule contrainte d’inégalité

Optimisation avec contraintes d’égalité et d’inégalité :

B. Optimisation avec des contraintes inégalité
Exemple 6 :
min f (X) = (x1 − 10)2 + (x2 − 8)2
(
g1 (x1 , x2 ) = x1 + x2 − 12 ≤ 0
s.c.
g2 (x1 , x2 ) = x1 − 8 ≤ 0

Cas 2 : g1 inactive et g2 active (µ∗1 = 0, g2 = 0)

g2 = 0 =⇒ x∗1 = 8

2 (x∗1 − 10) + µ∗2 = 0 µ∗2 = 4

(
=⇒
x∗1 = 8 et µ∗1 =0 =⇒
2 (x∗2 − 8) = 0 =⇒ x∗2 = 8

g1 (8, 8) = 4 > 0 le point (8, 8) n’est pas admissible

Ce cas ne donne pas de point candidat à être minimum.

Abdelkader Benaouali Techniques d’optimisation
 Introduction Optimisation avec une seule contrainte d’inégalité
Optimisation avec contraintes d’égalité Optimisation avec des contraintes inégalité
Optimisation avec contraintes d’égalité et d’inégalité Cas général

Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec une seule contrainte d’inégalité

Optimisation avec contraintes d’égalité et d’inégalité :

B. Optimisation avec des contraintes inégalité
Exemple 6 :
min f (X) = (x1 − 10)2 + (x2 − 8)2
(
g1 (x1 , x2 ) = x1 + x2 − 12 ≤ 0
s.c.
g2 (x1 , x2 ) = x1 − 8 ≤ 0

Cas 3 : g1 active et g2 inactive (g1 = 0, µ∗2 = 0)

g1 = 0 =⇒ x∗1 = 12 − x∗2
 ∗
x2 = 5
x∗2 ) µ∗1
( 
2 (2 − + =0


x∗1 = 12 − x∗2 =⇒ =⇒ µ∗1 = 6 > 0
2 (x∗2 − 8) + µ∗1 =0 

 ∗
x1 = 7

g2 (7, 5) = −1 < 0 le point (7, 5) est un candidat à être minimum.

Abdelkader Benaouali Techniques d’optimisation
 Introduction Optimisation avec une seule contrainte d’inégalité
Optimisation avec contraintes d’égalité Optimisation avec des contraintes inégalité
Optimisation avec contraintes d’égalité et d’inégalité Cas général

Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec une seule contrainte d’inégalité

Optimisation avec contraintes d’égalité et d’inégalité :

B. Optimisation avec des contraintes inégalité
Exemple 6 :
min f (X) = (x1 − 10)2 + (x2 − 8)2
(
g1 (x1 , x2 ) = x1 + x2 − 12 ≤ 0
s.c.
g2 (x1 , x2 ) = x1 − 8 ≤ 0

Cas 4 : g1 et g2 actives (g1 = 0, g2 = 0)

g1 = 0 et g2 = 0 =⇒ x∗1 = 8 et x∗2 = 4

−4 + µ∗1 + µ∗2 = 0 µ∗1 = 8 > 0

( (
x∗1 = 8 et x∗2 =4 =⇒ =⇒
−8 + µ∗1 = 0 µ∗2 = −4 < 0

µ∗2 < 0 =⇒ le point (8, 4) ne satisfait pas les conditions KKT

Abdelkader Benaouali Techniques d’optimisation

 Introduction Optimisation avec une seule contrainte d’inégalité
Optimisation avec contraintes d’égalité Optimisation avec des contraintes inégalité
Optimisation avec contraintes d’égalité et d’inégalité Cas général

Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec une seule contrainte d’inégalité

Optimisation avec contraintes d’égalité et d’inégalité :

B. Optimisation avec des contraintes inégalité
Exemple 6 :
10

18
68

48

8
58

28
98

88

38
78

6 8

18
68

48

28
58

5
98

88

38
78
10
8

4
18

3 28
11

48 38
8

68 58
2
12 13

98 88 78
8

10 48
1 8
8

58
14
8

68
0
0 1 2 3 4 5 6 7 8 9 10

Abdelkader Benaouali Techniques d’optimisation

 Introduction Optimisation avec une seule contrainte d’inégalité
Optimisation avec contraintes d’égalité Optimisation avec des contraintes inégalité
Optimisation avec contraintes d’égalité et d’inégalité Cas général

Optimisation avec contraintes d’égalité et d’inégalité

Cas général

Optimisation avec contraintes d’égalité et d’inégalité : [Cas général]

Abdelkader Benaouali Techniques d’optimisation

 Introduction Optimisation avec une seule contrainte d’inégalité
Optimisation avec contraintes d’égalité Optimisation avec des contraintes inégalité
Optimisation avec contraintes d’égalité et d’inégalité Cas général

Optimisation avec contraintes d’égalité et d’inégalité

Cas général

Optimisation avec contraintes d’égalité et d’inégalité : [Cas général]

Considérons un problème d’optimisation général avec des contraintes d’égalité
et autres d’inégalité

Minimiser f (X)
X


 hk (X) = 0, k = 1, 2, · · · , m
s.c. gj (X) ≤ 0, j = 1, 2, · · · , p

xi,inf ≤ xi ≤ xi,sup , i = 1, 2, · · · , n


Les conditions d’optimalité pour ce problème peuvent être obtenues en modifient

la formule du Lagrangien :
m p
X X
L(X, λ, µ) = f (X) + λk hk (X) + µj gj (X)
k=1 j=1
où µj sont les multiplicateurs de Lagrange associés aux contraintes d’inégalité
et λk sont ceux associés aux contraintes d’égalité.

Abdelkader Benaouali Techniques d’optimisation

 Introduction Optimisation avec une seule contrainte d’inégalité
Optimisation avec contraintes d’égalité Optimisation avec des contraintes inégalité
Optimisation avec contraintes d’égalité et d’inégalité Cas général

Optimisation avec contraintes d’égalité et d’inégalité

Cas général

Optimisation avec contraintes d’égalité et d’inégalité : [Cas général]

Conditions nécessaires (cas général)

∗
Soit X un point régulier qui est un minimum local de f (X) sous contraintes
d’égalité et d’inégalité. Alors, ils existent des multiplicateurs de Lagrange uniques
λ∗ (taille m) et µ∗ (taille p) tels que :

1 ∇x L(X ∗ , λ∗ , µ∗ ) = 0

2 hk X ∗ ) = 0, k = 1, · · · , m
3 gj (X ∗ ) ≤ 0, j = 1, · · · , p
4 µ∗j ≥ 0, j = 1, · · · , p
5 µ∗j gj (X ∗ ) = 0, j = 1, · · · , p

Ce sont les conditions nécessaires du premier ordre, appelées les conditions de

Karush-Kuhn-Tucker (KKT), pour un problème général avec contraintes.
Abdelkader Benaouali Techniques d’optimisation
 Introduction Optimisation avec une seule contrainte d’inégalité
Optimisation avec contraintes d’égalité Optimisation avec des contraintes inégalité
Optimisation avec contraintes d’égalité et d’inégalité Cas général

Optimisation avec contraintes d’égalité et d’inégalité

Cas général

Optimisation avec contraintes d’égalité et d’inégalité : [Cas général]

Conditions nécessaires (cas général)

∗
Soit X un point régulier qui est un minimum local de f (X) sous contraintes
d’égalité et d’inégalité. Alors, ils existent des multiplicateurs de Lagrange uniques
λ∗ (taille m) et µ∗ (taille p) tels que :
m p
X X
1 ∇f (X) + λk ∇hk (X) + µj ∇gj (X) = 0
k=1 j=1
2 hk X ∗ ) = 0, k = 1, · · · , m
3 gj (X ∗ ) ≤ 0, j = 1, · · · , p
4 µ∗j ≥ 0, j = 1, · · · , p
5 µ∗j gj (X ∗ ) = 0, j = 1, · · · , p

Ce sont les conditions nécessaires du premier ordre, appelées les conditions de

Karush-Kuhn-Tucker (KKT), pour un problème général avec contraintes.
Abdelkader Benaouali Techniques d’optimisation
 Introduction Optimisation avec une seule contrainte d’inégalité
Optimisation avec contraintes d’égalité Optimisation avec des contraintes inégalité
Optimisation avec contraintes d’égalité et d’inégalité Cas général

Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec une seule contrainte d’inégalité

Optimisation avec contraintes d’égalité et d’inégalité : [Cas général]

Exemple 7 :
min f (X) = (x1 − 1)2 + x2 − 2
(
h(x1 , x2 ) = x2 − x1 − 1 = 0
s.c.
g(x1 , x2 ) = x1 + x2 − 4 ≤ 0

Abdelkader Benaouali Techniques d’optimisation

 Introduction Optimisation avec une seule contrainte d’inégalité
Optimisation avec contraintes d’égalité Optimisation avec des contraintes inégalité
Optimisation avec contraintes d’égalité et d’inégalité Cas général

Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec une seule contrainte d’inégalité

Optimisation avec contraintes d’égalité et d’inégalité : [Cas général]

Exemple 7 :
min f (X) = (x1 − 1)2 + x2 − 2
(
h(x1 , x2 ) = x2 − x1 − 1 = 0
s.c.
g(x1 , x2 ) = x1 + x2 − 4 ≤ 0

L(x1 , x2 , λ, µ) = (x1 − 1)2 + x2 − 2 + λ (x2 − x1 − 1) + µ (x1 + x2 − 4)

Abdelkader Benaouali Techniques d’optimisation

 Introduction Optimisation avec une seule contrainte d’inégalité
Optimisation avec contraintes d’égalité Optimisation avec des contraintes inégalité
Optimisation avec contraintes d’égalité et d’inégalité Cas général

Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec une seule contrainte d’inégalité

Optimisation avec contraintes d’égalité et d’inégalité : [Cas général]

Exemple 7 :
min f (X) = (x1 − 1)2 + x2 − 2
(
h(x1 , x2 ) = x2 − x1 − 1 = 0
s.c.
g(x1 , x2 ) = x1 + x2 − 4 ≤ 0

L(x1 , x2 , λ, µ) = (x1 − 1)2 + x2 − 2 + λ (x2 − x1 − 1) + µ (x1 + x2 − 4)

2 (x∗1 − 1) − λ∗ + µ∗ = 0




1 + λ∗ + µ∗ = 0






x∗2 − x∗1 − 1 = 0


 ∗


 x1 + x∗2 − 4 ≤ 0


µ (x∗1 + x∗2 − 4) = 0 , µ∗ ≥ 0


Abdelkader Benaouali Techniques d’optimisation

 Introduction Optimisation avec une seule contrainte d’inégalité
Optimisation avec contraintes d’égalité Optimisation avec des contraintes inégalité
Optimisation avec contraintes d’égalité et d’inégalité Cas général

Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec une seule contrainte d’inégalité

Optimisation avec contraintes d’égalité et d’inégalité : [Cas général]

Exemple 7 :
min f (X) = (x1 − 1)2 + x2 − 2
(
h(x1 , x2 ) = x2 − x1 − 1 = 0
s.c.
g(x1 , x2 ) = x1 + x2 − 4 ≤ 0

Cas 1 : contrainte active ou bien g = 0


∗ 3
x∗2 − x∗1 − 1 = 0  x1 =
( 
2
=⇒
x∗1 + x∗2 − 4 = 0  ∗
 x2 =
5
2
1 − λ∗ + µ∗ = 0 λ∗ = 0
( (
=⇒
1 + λ ∗ + µ∗ = 0 µ∗ = −1 < 0 ce n’est pas un candidat

Abdelkader Benaouali Techniques d’optimisation

 Introduction Optimisation avec une seule contrainte d’inégalité
Optimisation avec contraintes d’égalité Optimisation avec des contraintes inégalité
Optimisation avec contraintes d’égalité et d’inégalité Cas général

Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec une seule contrainte d’inégalité

Optimisation avec contraintes d’égalité et d’inégalité : [Cas général]

Exemple 7 :
min f (X) = (x1 − 1)2 + x2 − 2
(
h(x1 , x2 ) = x2 − x1 − 1 = 0
s.c.
g(x1 , x2 ) = x1 + x2 − 4 ≤ 0

Cas 2 : contrainte inactive ou bien µ = 0

 ∗
λ = −1
2 (x∗1 − 1) − λ∗ = 0
 
 


 
 ∗ 1
1 + λ∗ = 0 =⇒ x1 =
  2

 ∗ 
x2 − x∗1 − 1 = 0  x∗ = 3


2
2
   
1 3 1 3
g , = −2 < 0 =⇒ , est un candidat à être un minimum
2 2 2 2

Abdelkader Benaouali Techniques d’optimisation

 Introduction Optimisation avec une seule contrainte d’inégalité
Optimisation avec contraintes d’égalité Optimisation avec des contraintes inégalité
Optimisation avec contraintes d’égalité et d’inégalité Cas général

Optimisation avec contraintes d’égalité et d’inégalité

Optimisation avec une seule contrainte d’inégalité

Optimisation avec contraintes d’égalité et d’inégalité : [Cas général]

Exemple 7 :

1.7
0.
75
2.5 75

5
0.

2.7
5

3.75
2

5
.2
-0 -0

0.7
1.5

1.7
.2
5

2.75
1

.25
-1
0.5
-0.

0.7
-1

25

1.75
.2

5
5

0
0 0.5 1 1.5 2 2.5 3

Abdelkader Benaouali Techniques d’optimisation

 Introduction Optimisation avec une seule contrainte d’inégalité
Optimisation avec contraintes d’égalité Optimisation avec des contraintes inégalité
Optimisation avec contraintes d’égalité et d’inégalité Cas général

Optimisation avec contraintes d’égalité et d’inégalité

Cas général

Optimisation avec contraintes d’égalité et d’inégalité : [Conditions suffisantes]

Abdelkader Benaouali Techniques d’optimisation

 Introduction Optimisation avec une seule contrainte d’inégalité
Optimisation avec contraintes d’égalité Optimisation avec des contraintes inégalité
Optimisation avec contraintes d’égalité et d’inégalité Cas général

Optimisation avec contraintes d’égalité et d’inégalité

Cas général

Optimisation avec contraintes d’égalité et d’inégalité : [Conditions suffisantes]

Les conditions suffisantes sont obtenues en examinant les exigences du 2eme
ordre :

Les conditions KKT sont satisfaites en ce point (X ∗ est un point KKT) ;

pour tout vecteur w 6= 0 tel que :
∇hk (X ∗ )T w = 0, k = 1, · · · , m ;
∇gj (X ∗ )T w = 0, pour tout j tel que µj > 0
∇gj (X ∗ )T w ≤ 0, pour tout j tel que µj = 0

La matrice hessienne du Lagrangien ∇2x L (X ∗ , λ∗ , µ∗ ) est définie positive :

wT ∇2x L (X ∗ , λ∗ , µ∗ ) w > 0,

Abdelkader Benaouali Techniques d’optimisation