Cours d'Optimisation

16 novembre 2021
Chapitre 1
Rappels mathématiques

1.1 Introduction
L'optimisation est une branche des mathématiques, dont le but est de chercher
à résoudre analytiquement ou numériquement, la meilleur solution ( ) à un
problème donné. L'origine du mot optimale provient du Latin qui signie
l'optimale

le meilleur. De nos jours, l'optimisation joue un rôle très important dans diérents
optimum

domaines de la vie. Voici quelques domaines d'applications de l'optimisation :

 Transport et livraisons.
 Fabrication et production.
 Agriculture et génie civil.
 Finance, vente et marketing
 Gestion de stock
 Recherche et gestion des bases de données.
 ...
On distingue deux grandes familles de techniques d'optimisation, et cela suivant le
problème posé :
 Techniques d'optimisation sans contraintes.
 Techniques d'optimisation sous contraintes.
En optimisation, on parle souvent de la fonction coût (objectif). C'est la fonction
à minimiser/maximiser.
1.1.1 Notations
Dans ce qui suit, on considère la notation des variables suivantes :
 n, m, p, ..., des scalaires qui indiquent souvant les dimensions,
 x, y, t, λ, α..., des variables scalaires,
 x, y, X, Y, ..., des vecteurs colonne,
 A, M, P, ..., des matrices.
 E, I, ..., ensembles ou intervalles
1
 y

x
0

Figure 1.1  Exemple d'une fonction coût

1.1.2 Vecteur
Le vecteur réel X de dimension n, se met sous la forme :
 
x1
 x2 
X= 
 ...  (1.1)
xn
ou encore de la manière suivante :
X=

x1 x2 ... xn
0
(1.2)
 deux vecteurs sont égaux ssi tous leurs éléments sont égaux.
 Le produit scalaire de deux vecteurs X et Y est déni par :
n
X
0 0
XY =YX= xi yi
i=1

 Les deux vecteurs X et Y sont orthogonaux si :

X0 Y = 0

 La norme d'un vecteur X est :

√
|X| = X0 X

 L'inégalité de Cauchy-Schwarz est vériée pour les deux vecteurs X et Y :

|X0 Y| ≤ |X|.|Y|

2
1.1.3 Matrice
Dans ce cours on ne considère que les matrice réelles. Une matrice A de dimension
m × n est donnée par :  
a11 a12 ... a1n
 a21 a22
A=
 ... ...
... a2n 

... ... 
(1.3)
am1 am2 ... amn
La matrice transposée de la matrice A qu'on note A ou A , est de dimension
0 T

n × m est la suivante :  
a11 a21 ... am1
 a12
A=
 ...
a22
...
... am2 

... ... 
(1.4)
a1n a2n ... amn
La somme (diérence) de deux matrice de dimensions identiques est une matrice de
même dimension, dont les élements sont égaux à la somme (diérence) des éléments
de même position.
Le produit de deux matrice A (m × p) et B (p × n) est une matrice C (m × n)
dont les élements sont :
p
X
cij = aik bkj i = 1, ..., m j = 1, ..., n
k=1

La multiplication des matrices requière une attention partculière, le nombre de

colonne de la première doit être égale au nombre de ligne de la deuxième. Prenant
l'exemple illsutratif suivant : soit un vecteur X de dimension n alors,
 
x1
  x2 
X0 X =

x1 x2 ... xn  
 ... 
xn
= x21 + x22 + ... + x2n

Le résultat du produit X X est un scalaire.

0

3
  
x1
 x2  
XX0 = 

 ...  x1 x2 ... xn


xn
 2 
x1 x1 x2 ... x1 xn
 x2 x1 x22 ... x2 xn 
= ...

... ... ... 
xn x1 xn x2 ... x2n

Le résultat du produit XX est une matrice.

0

Une matrice est dite carrée dans le cas particulier où n = m. On déni la matrice
identité I de la manière suivante :
 
1 0 ... 0
 0
I=
 ...
1
...
...
...
0 
... 
(1.5)
0 0 ... 1
Souvent on indique la dimension n de la matrice identité I . n

Exercice 1. Opérations sur les matrices et les vecteurs

. Soit les deux vecteurs A = [1, 2, 3] et B = [−1, 0, 2] . Eectuer les opérations sui-
0 0

vantes :
a. AB . 0

b. A B.
0

c. AB0 B

1.1.4 Valeurs propres

On appel le scalaire λ valeur propre de la matrice A s'il existe un vecteur non nul
V tel que :
AV = λV
Le vecteur V est appelé vecteur propre de la matrice A associé à la valeur propre
λ ( Exp. A = [3 2 ; 3 − 2], V = [2 1] , λ = 4).
0

Les valeurs propres présentent la solution de l'équation caractéristique suivante :

|A − λIn | = 0

4
 Le déterminant d'une matrice A peut être donné par le produit de ses valeurs
propres qu'on note {λ } .n
i i=1
n
Y
|A| = λi

Si la matrice carrée A est symétrique alors :

i=1

1. Les valeurs propres sont positifs.

2. Les vecteurs propres associées aux diérentes valeurs propres sont orthogonaux.
3. Il existe une base orthogonale où chaque élément présente un vecteur propre de
A.
La matrice carrée A est inversible si son déterminant est diérent de zéro. La
matrice inverse est notée A , on a alors :
−1

AA−1 = In

La trace de A est la somme de ses éléments diagonaux :

(1.6)
n
X
T r(A) = aii
i=1

La
P trace d'une matrice carrée est égale à la somme de ces valeurs propres T r(A) =
λ.
Une matrice est dite symétrique si elle vérie la condition :
i

A=A 0
(1.7)
Dans ce qui suit on ne considère que le cas des matrices carrées et symétriques, sauf
si on l'indique clairement.
Exercice 2.
Soit la matrice carrée A dont les valeurs propres sont : λ = 1, λ
1 2 =2 et λ
3 .
=5
1. Quelles sont les dimensions de la matrice A ?
2. Que peut on dire sur la positivité de la matrice A ?
3. Comment déterminer l'équation caractéristique de A ?
4. Calculer le déterminant de A.
5. La matrice A est elle inversible? Pourquoi?
6. Calculer la trace de la matrice A.

5
1.2 Positivité
1.2.1 Dénition
 Une fonction f (x) est dite positive ssi f (x) > 0, ∀x ∈ <.
 Une matrice symétrique A est dénie positive ssi X AX > 0, ∀X 6= 0.
0

 Une matrice symétrique A de dimension n est dénie positive si toutes les valeurs
propres sont positives λ > 0, ∀i = 1, ..., n.
 Une matrice A de dimension n est dénie positive si tous les mineurs principaux
i

sont positifs.
1.2.2 Exemples
1. La fonction f (x) =x − 4x + 5 est dénie positive sur l'ensemble <.
2

2. La matrice : A = 21 12 est dénie positive, car ses valeurs propres sont po-
sitives. Les valeurs propres sont les solutions de l'équation caractéristique |A −
λI | = 0.
2

Exercice 3. Matrice positive

. Déterminer parmi les matrices suivantes celles qui sont dénies positives :
a.  
2 1
A=
1 2
b.  
2 −1
B=
−1 2
Utiliser la dénition ensuite les valeurs propres.
1.3 Convexité
1.3.1 Fonction convexe
Soit la fonction f , dénie sur un intervalle I de < , telle que ∀(x , x ) ∈ I et
n 2

∀α ∈ [0, 1], on dit que la fonction f est convexe (ou plus exactement strictement
1 2

convexe) si elle vérie l'inégalité suivante :

f (αx + (1 − α)x ) ≤ αf (x ) + (1 − α)f (x )
1 2 1 2(1.8)
Si la fonction f (x) ∈ <, elle est convexe si on a f (x) ≥ 0 sur le domaine
00

de dénition.
Remarque

6
 Figure 1.2  Exemple d'une fonction convexe

1.3.2 Ensemble convexe

Un ensemble Ω ⊂ < est dit convexe ssi :
n

∀u, v ∈ Ω et ∀α ∈ [0, 1], on a x = αu + (1 − α)v ∈ Ω (1.9)

Exercice 4. Démontrer que l'ensemble dénie par Ω = { X ∈ <n : a0X ≥ β}, où
a ∈ <n et β ∈ <, est convexe, Ω est appelé demi-espace halfspace .

Figure 1.3  Illustration d'ensembles convexes et non vonvexes

1.4 Le gradient
Soit f (X) une fonction scalaire de n variables. Le gradient de la fonction f qu'on
note ∇f est un vecteur ligne dont les élements sont les dérivées partielles de la fonction
f suivant chaque variable.

∂f
(1.10)
h i
∂f ∂f ∂f
∇f = = ∂x1 ...
∂x2 ∂xn
∂X

Exemple Trouver le gradient de la fonction f (x, y) = x 2

+ xy + y 2 .

7
Solution

∂f
= 2x + y,
∂x
∂f
= x + 2y,
∂y
∂f
= [2x + y , x + 2y]
∂X

1.5 Le Hessien
Soit f (X) une fonction scalaire de n variables. Le Hessien de la fonction f , qu'on
note Hf est une matrice de dimension n × n, dont les élements sont les dérivées
partielles d'ordre deux de la fonction f .

∂ 2 f (X) ∂ 2 f (X) ∂ 2 f (X)

(∂x1 )2 ∂x1 ∂x2 ... ∂x1 ∂xn

(1.11)
∂ 2 f (X) ∂ 2 f (X) ∂ 2 f (X)
∂ 2 f (X) 
 
∂x2 ∂x1 (∂x2 )2 ... ∂x2 ∂xn

Hf = 2
= 
(∂X) 
 ... ... ... ... 

∂ 2 f (X) ∂ 2 f (X) ∂ 2 f (X)
∂xn ∂x1 ∂xn ∂x2 ... (∂xn )2

 Trouver le Hessien de la fonction f (x, y) = x + xy + y .

Exemple
2 2

 Démontrer que cette matrice est dénie positive?


Solution

∂f ∂ 2f
= 2x + y, −→ =2
∂x (∂x)2
∂ 2f
−→ =1
∂x∂y
∂f ∂ 2f
= x + 2y, −→ =2
∂y (∂y)2
∂ 2f
−→ =1
∂y∂x
 
2 1
Hf =
1 2
 Pour démontrer que cette matrice est dénie positive, on doit calculer les valeurs
propores correspondantes.
8
 L'équation caractéristique dans ce cas est donnée par :
(2 − λ)2 − 1 = 0
(2 − λ − 1)(2 − λ + 1) = 0
λ1 = 1, λ2 = 3
Les deux valeurs propres sont positives, ainsi, la matrice est dénie positive.
Une fonction f (X) est convexe ssi Hf (X) est semi-denie positif pour
tout X
Remarque

Exercice 5. Gradient et Hessien

. Considérons la fonction scalaire suivante :
f (x, y) = x − y + x2 y + xy 2
a. Calculer les dérivées partielles f = et f = .
x
∂f
y
∂f

Trouver les extrémums en résolvant les équations f et f .

∂x ∂y
b. x =0 y =0
c. Calculer le Hessein de la fonction f .
d. Déduire la nature des extrémums.
1.6 Exercices de synthèse
Exercice 6. Régression linéaire
. Soit un ensemble de n points dans le plan {X = [x , y ] } , ces points sont souvent
0 n

les résultats d'une experience. Les points ne sont pas sur la même ligne, Cependant
i i i i=1

on veut trouver la ligne approchant au mieux ce nuage de points. Pour cela on utlise
la méthode des moindres carrées, et on choisis la relation suivante y = ax + b avec
(a, b) ∈ < . La fonction objective est la somme des carrées des erreurs (cette fonction
2

est convexe) : n
X
f (a, b) = (yi − (axi + b))2

Claculer le gradient de la fonction f (a, b).

i=1
a.

b. Ecrire le système d'équations qui donne les extremums.

c. Donner l'écriture matricielle correspondante à ce système.
d. Trouver les coecients (a, b) qui minimisent cette fonction.
Exercice 7.
Soit la fonction réelle à deux variables :
f (x, y) = x − x2 y + xy 2

9
1. Calculer le Jacobien,
2. Calculer le Hessien,
3. Déterminer l'équation caractéristique du Hessien,
4. Donner les valeurs propres de cette matrice,
5. Cette matrice est elle dénie positive, pourquoi?
6. Calculer le déterminant en utilisant les valeurs propres.
7. Trouver analytiquement les optimums de cette fonction. Quelle sont leurs na-
tures?

10
1.7 Solutions des exercices
Solution Ex. 1.
   
1 −1 0 2
 AB0 =  2  [−1 0 2] =  −2 0 4  .
3 −3 0 6
 
−1
 0
A B = [1 2 3]  0  = 5 .
2
 Le calcul de l'expressionAB0 Bpeut se faire de deux façon diérentes, suivant
l'ordre dans lequel
 nous calculons
 le produit
 :
−1 0 2 −1 5
 (AB )B =  −2 0 4   0  =  10 
0

−3 0 6 2 15
   
1 5
 A(B0 B) =  2  × 5 =  10 
3 15

Lors de calcul du produit de plusieurs matrices il est souvent préférable de commencer

Remarque

par le calcule des produits qui minimisent le nombre d'opérations de multiplications.

Solution Ex. 2.
La matrice carrée A dispose des 3 valeurs propres : λ = 1, λ = 2 et λ = 5. alors :
1 2 3

1. La matrice A est de dimension 3 × 3 (car elle est carrée et dispose de 3 valeurs

propres).
2. La matrice A et positive car toutes les valeurs propres sont positives.
3. L'équation caractéristique de A est donnée par la résolution de l'équation :
det(A − λI) = 0

Dans notre cas, on en plus (λ − λ )(λ − λ )(λ − λ ) = 0

1 3 3

4. Le déterminant de A est égale à :

3
Y
det(A) = λi = λ1 × λ2 × λ3 = 10
i=1

5. La matrice A est inversible, car le déterminant est non nul.

11
 6. La trace de la matrice A est égale à la somme des éléments de sa diagonale. elle
est égale aussi à la somme des valeurs propres.
3
X
trace(A) = λi = λ1 + λ2 + λ3 = 8
i=1

Solution Ex. 3.
Deux méthodes permettent de déterminer si une matrice réelle C de dimension (n × n)
est dénie positive ou non :
1. Par dénition
La matrice C est dénie positive si on a X CX > 0, ∀X ∈ < .
0 ∗n

(a)     
2 1 2 1 x
A= , X0 AX = [x y] =
1 2 1 2 y

= 2x2 + 2xy + 2y 2 = x2 + y 2 + (x + y)2 ≥ 0, ∀(x, y) ∈ <∗ 2

Ainsi, la matrice A est dénie positive car pour (x, y) 6= (0, 0) on a x + y + 2 2

(x + y) > 0.
2

(b)     
2 −1 0 2 −1 x
B= , X BX = [x y] =
−1 2 −1 2 y

= 2x2 − 2xy + 2y 2 = x2 + y 2 + (x − y)2 > 0, ∀(x, y) ∈ <∗ 2

Ainsi, la matrice B est dénie positive car pour (x, y) 6= (0, 0) on a x + y + 2 2

(x − y) > 0.
2

2. Utilisation des valeurs propres

La matrice est positive si toutes ces valeurs propres sont positives.
(a) pour A
   
2 1 1 0
det(A − λI2 ) = det −λ = (2 − λ)2 − 1
1 2 0 1
Le déterminant s'annule pour λ 1 =1 et λ 2 =3
(b) pour B
   
2 −1 1 0
det(B − λI2 ) = det −λ = (2 − λ)2 − 1
−1 2 0 1
Le déterminant s'annule pour λ 1 =1 et λ 2 =3

12
Solution Ex. 4.
Soit Z = λX + (1 − λ)Y pour λ ∈ [0, 1]. Alors :
a0 Z = a0 (λX + (1 − λ)Y)
= λa0 X + (1 − λ)a0 Y
≥ λβ + (1 − λ)β = β ( on a λ ≥ 0 et (1 − λ) ≥ 0 )
a0 Z ≥ β ⇒ Z ∈ Ω
par conséquent, Ω est un ensemble convexe.
Solution Ex. 5.

1. Calcul des gradients

∂f
fx = = 1 − 2xy + y 2
∂x
∂f
fy = = −1 − x2 + 2xy
∂y
2. En sommant les deux équations et
fx = 0 fy = 0 , on obtient :
y 2 − x2 = 0 ⇒ y = ±x

 Soit y = x alors on a :
1 − 2x2 + x2 = 0 → 1 − x2 = 0 → x = ±1
ainsi on a deux points : (1, 1) et (−1, −1)
 Soit y = −x alors on a :
1 + 2x2 + x2 = 1 + 3x2 = 0
cette équation n'a pas de solution dans <
3. ∂ 2f
= −2y
(∂x)2
∂ 2f
= −2x + 2y
∂x∂y
∂ 2f
= 2x
(∂y)2
∂ 2f
= −2x + 2y
∂y∂x
 
−2y −2x + 2y
Hf =
−2x + 2y 2x

13
 4.  
−2 0

Hf (1, 1) = −→ |Hf (1, 1)| = −4 < 0
0 2
, ainsi ce point est un point de selle (col ou en anglais )

saddle point

 
2 0
Hf (−1, −1) = −→ |Hf (−1, −1)| = −4 < 0
0 −2
, ainsi ce point est aussi un point de selle.
Solution Ex. 6.

1. Les gradients suivant les variable a et b sont comme suit :

n n n n
∂f X X X X
= 2(−yi + axi + b)xi = 2a x2i + 2b xi − 2 yi xi
∂a i=1 i=1 i=1 i=1

n n n
∂f X X X
= 2(−yi + axi + b) = 2a xi + 2nb − 2 yi
∂b i=1 i=1 i=1

2. Sachant que cette fonction est convexe, l'extremum et donné par le système sui-
vant :
n
X n
X n
X
x2i a+ xi b = yi x i
i=1 i=1 i=1
Xn Xn
xi a + n b = yi
i=1 i=1

3. Les coecients a et b sont données en résolvant le système d'équation précedent,

soit :
 n
X n
x2i
 
S11 =

 X
 
 Z = yi xi
 1

 i=1



Xn i=1
n
S12 = S21 = xi  X
Z2 = yi

 

i=1

 

 i=1
 S22 = n
4. L'écriture matricielle correspondante est :
    
S11 S12 a Z1
=
S21 S22 b Z2

14
 on obtient alors :
S12 Z2 − S22 Z1
a= 2 −S S
S12 11 22
S12 Z1 − S11 Z2
b= 2
S12 − S11 S22

La gure 1.4 montre le résultat après exécution du programme suivant :

Programme Matlab

%% Construction d'un nuage de points

a=2;
1

b=3;
2

N=100;
3

x=3+10∗ rand (1 ,N) ;

4

y=a ∗ x+b+3∗ randn (1 ,N) ;

5

plot (x ,y , ' . ' ) , hold on

6

%% Calcul des parametres

7

S11=sum(x.^2) ;
8

S12=sum(x) ;
9

S21=S12 ;
10

S22=N;
11

Z1=sum(y. ∗ x) ;
12

Z2=sum(y) ;
13

14

a=(S12 ∗Z2−S22 ∗ Z1) /(S12^2−S11 ∗ S22) ;

15

b=(S21 ∗Z1−S11 ∗ Z2) /(S12^2−S11 ∗ S22) ;

16

%% Dessin des resultats

17

x_min=min(x) ;
18

x_max=max(x) ;
19

pas=(x_max−x_min) /20;
20

x=(x_min: pas :x_max) ;

21

y_est=a ∗ (x_min: pas :x_max)+b;

22

23

plot (x , y_est , ' r ' , 'LineWidth ' ,3)

24

xlabel ( 'x ' )

25

ylabel ( 'y ' )

26

legend ( 'Nuage de points ' , ' Droite estimee ' )

27

28

Solution Ex. 7.

15
 Figure 1.4  Regression lineaire
Soit la fonction réelle à deux variables :
f (x, y) = x − x2 y + xy 2
1. Calcule du Jacobien,  
∂f
1 − 2xy + y 2
 
∂x
Jf = ∇f 0 =  =
   
∂f
∂y −x2 + 2xy2

2. Le Hessien 
−2y −2x + 2y

Hf =
−2x + 2y 2x
3. L'équation caractéristique du Hessien est donnée par :
det(H − λI) = 0 → (−2y − λ)(2x − λ) − (−2x + 2y)2 = 0
λ2 + 2(y − x)λ − (−2x + 2y)2 − 4xy = 0
4. Les valeurs propres sont les solutions de l'équation caractéristique de cette ma-
trice, c'est une équation du deuxième ordre alors :
∆ = 4(y − x)2 + 16(y − x)2 + 16xy = 20(y − x)2 + 16xy
Les solution sont alors : √
−2(y − x) + ∆ p
λ1 = = x − y + 5(y − x)2 + 4xy
2
16
 √
−2(y − x) − ∆ p
λ2 = =x−y− 5(y − x)2 + 4xy
2
5. Pour que cette matrice soit dénie positive, il faut que λ > 0 et λ >0 . Cela
dépend des valeur attribuées aux variables x et y.
1 2

6. Le déterminant est donné par le produit des valeurs propres :

 p  p 
2 2
det(Hf ) = λ1 ×λ2 = x − y + 5(y − x) + 4xy x − y − 5(y − x) + 4xy

det(Hf ) = −4(x2 + y 2 − xy)

7. L'optimum de cette fonction est obtenu analytiquement comme suit :
 
∂f
1 − 2xy + y 2
   
∂x 0 (1)
0
Jf = ∇f =  = =
   
∂f
∂y −x2 + 2xy2 0 (2)
De la deuxième équation on tire :
x2 − 2xy = 0 → x(x − 2y) = 0

on élimine la solution x = 0 car elle ne vérie pas la première équation. Alors on

prend x = 2yet en replpace dans la première équation on trouve :
r
1
1 − 4y 2 + y 2 = 0 → y = ±
3
q h q i0
1 √2 √2 1
y= 3 → x= 3
→ X1 = 3
, 3
q h q i0
y = − 3 → x = − √3 → X2 = √3 , −1
1 2 −2
3

La nature des points dépend de la valeur de la Hessienne à ces points :

det(H) = −4(x2 + y 2 − xy)

pour X on a det(H(X = X1)) = − pour X on a det(H(X = X2)) = −

4 4

pour les deux points on a det(H) < 0 alors on a deux points de celle.
1 3 2 3

17
Chapitre 2
Optimisation sans contraintes : méthodes
locales

2.1 Dénitions
2.1.1 Dénition 1
Soit f (X) une fonction de < n
→ <n ; Le problème d'optimisation sans contraintes
s'écrit de la façon suivante :
minimiser la fonction f (X) avec X ∈ < . n

La fonction f (X) est souvent appelée : fonction coût, fonction objectif ou critère
d'optimisation.
2.1.2 Dénition 2
On dit que X est un point qui minimise la fonction f (X) sur l'ensemble < ssi :
∗ n

∀X ∈ <n , f (X∗ ) ≤ f (X)

2.2 Théorèmes d'existence de l'optimum

2.2.1 Théorème 1
Soit la fonction f (X) : < n
→< diérentiable sur < , on dit que f (X) à un optimum
n

au point X si :
∗

∇f (X∗ ) = 0

 X est appelé point stationnaire de la fonction f (X).

Remarques
∗

 La relation ∇f (X ) = 0 est aussi appelée équation d'

∗
Euler .
18
  Ce théorème n'a aucun sens si la fonction n'est pas diérentiable (Exemple fonc-
tion en V).
2.2.2 Théorème 2
Soit la fonction f (X) : < → < convexe et continument diérentiable à l'ordre
n

deux sur < , on dit que f (X) à un minimum global au point X ssi :
n ∗

∇f (X∗ ) = 0

L'égalité précédente engendre un ensemble de n équations qui peuvent être, dans

certains cas, résolues analytiquement. Cependant, on a souvent recours à résoudre cet
ensemble d'équation numériquement et par des algorithmes itératifs. On construit ainsi,
une suite de solutions qui converge vers la solution optimale X , X , ..., X = X .
0 1 ∞
∗

2.3 Le développement en série de Taylor

Dans le cas unidimensionnel, la dérivée d'une fonction en un point, est comme suit :
f (x) − f (a) f (a + h) − f (a)
f 0 (a) = lim = lim
x→a x−a h→0 h
on peut faire l'approximation suivante :
f (x) − f (a) ≈ f 0 (a)(x − a)

soit :
f (x) ≈ f (a) + f 0 (a)(x − a)
ou encore
f (a + ∆x) ≈ f (a) + f 0 (a)∆x
pour plus de précision, on ajoute les termes :
1 1 (m)
f (x) ≈ f (a) + f 0 (a)(x − a) + f 00 (a)(x − a)2 + ... + f (a)(x − a)m
2 m!
(2.1)
m
X 1 (i)
= f (a)(x − a)i
i=0
i!

Cette dernière expression est appelée développement en série de d'ordre m au

voisinage du point a.
Taylor

19
 Dans le cas multidimensionnel, le développement en série de du premier
ordre de la fonction f (X) au voisinage du vecteur A, est donné par :
Taylor

(2.2)
n 
X ∂f (X) 
f (A + ∆X) ≈ f (A) + ∇f (A)∆X = f (A) + (xi − ai )
i=1
∂x i

x i =ai

Le développement en série de Taylor du second ordre est :

1
f (A + ∆X) ≈ f (A) + ∇f (A)∆X + ∆X0 Hf (A)∆X
n  2! n
1 X ∂ 2 f (X) 

X ∂f (X) 
≈ f (A) + (xi − ai ) +  xi =ai (xi − ai )(xj − aj )
∂x i

x =a 2! ∂x i ∂x j

(2.3)
i=1 i i i,j=1 x =a
j j

2.4 Problème d'optimisation à une seule variable

Certains problèmes d'optimisation à plusieurs variables, peuvent être amenés à un
problème équivalent à une seul variables uniquement. Dans cette partie nous allons
examiner certains problèmes de ce type. Mais avant cela, voici les étapes pour résoudre
ce type d'exercice.
1. Lire attentivement le problème
2. Faire des gures d'illustration
3. Identier les variables
4. Dénir la fonction à optimiser f (x, y, z, ...)
5. Reformuler la fonction suivant une seule variable f (x)
6. Résoudre l'équation = 0 df (x)

7. Réécrire la solution suivant les variables initiales.

dx

Exercice 8. Boite à volume maximal

.
En utilisant une feuil de dimensions L × H , on veut déterminer les dimensions corres-
pondantes d'une boite dont le volume est maximal.
a.Dessiner sur une feuil le croquis de cette boite.
b.Déterminer la fonction à minimiser correspondante à ce problème suivant la hau-
teur h.
20
 c. Déterminer les dimension de la boite à volume maximal.
d. Donner le résultat pour une page de dimension A4 (21 × 29.7).
e. Trouver le même résultat en utilisant Matlab (dessiner la fonction de volume ainsi
que sa dérivée en fonction de la variable h.
Exercice 9. Aire maximale
.
La parabole d'équation y = − x + 8 coupe l'axe des abscisses en A et B. Le point
2 2

P (x; y) se déplace sur la parabole entre A et B . Soit A la projection du point P sur

9
0

la droite (AB).
a. Représenter graphiquement cet énoncé.
b. Déterminer les coordonnées du point P pour que l'aire du triangle rectangle A P B 0

soit maximale.

2.5 Les méthodes de descente

Les méthodes de descente sont des techniques itératives permettant de trouver le
minimum d'une fonction donnée. Le principe est de proposer un point initiale X ,
ensuite on cherche à trouver un autre point X qui vérie la condition f (X ) < f (X ).
0

Par la suite, X devient le point initiale pour la nouvelle itération et ainsi de suite
1 1 0

jusqu'à l'obtention du point minimale.

1

Le point X peut être mis sous la forme suivante :

1

X1 = X0 + ρ0 ∆X0
où ρ ∈ < est appelé le
∗+
et ∆X un vecteur de < appelé n

. Ainsi, à la première itération on doit trouver ρ et ∆X qui satisfont la

0 pas de descente 0 direction

condition f (X ) < f (X ). Et en générale, à la k itération, on a :

de descente 0 0
ième
1 0

X = X + ρ ∆X
k+1 k k k (2.4)
et on doit trouver ρ ∈ < et ∆X qui satisfont la condition f (X ) < f (X ).
k
∗+
k k+1 k

Le pas de descente ρ est déterminé soit analytiquement en minimisant la

fonction argminf (X + s∆X). Soit itérativement en minimisant la fonction f (X +
Remarque

ρ∆X), suivant la variable ρ. L'algorithme correspondant dans ce cas est comme suit :
s≥0

 Connaissant la direction ∆X et soit deux réelles 0 < α < 0.5 et 0 < β < 1.
 ρ ← 1.
 while f (X + ρ∆X) > f (X) + αρ∇f (X)∆X, ρ : = βρ.
21
Remarque en pratique, souvent, on prend α ∈ [0.01 , 0.3] et β ∈ [0.1 , 0.8].
2.6 Méthode du gradient
2.6.1 Principe
La méthode du gradient est une technique de descente (itérative) permettant de
trouver le minimum d'une fonction donnée. La façon la plus évidente de trouver une
direction est l'utilisation de la dérivée. Ainsi, pour trouver la direction de descente, on
utilise le sens inverse de la dérivée. A cet eet, on prend ∆X = −∇f (X) . La relation
0

itérative correspondante à la méthode du gradient est la suivante :

f (X ) ≈ f (X ) + ρ ∇f (X )∆X
k+1 k k k k (2.5)
Si ρ est constant, cette méthode est qualiée de méthode du gradient à pas xe.
Lorsque ρ varie, on parle de la méthode du gradient à pas variable.
k
k

2.6.2 Algorithme
 connaissant la valeur initiale X ,
 Répéter
0

1. ∆X ← −∇f (X) . 0

2. Choisir le pas ρ (s'il est xe on ignore cette étape).

3. Mettre à jours X ← X + ρ∆X.
 Arrêter lorsque la condition de convergence est satisfaite.
La condition de convergence est souvent pris comme : k∇f (X)k ≤η avec η un
nombre petit et positif.
2

2.6.3 Exemple
Soit une fonction cout f (X) quadratique en < sous la forme :
2

f (X) = x2 + 3y 2 ,

avec X = [x, y]0. Il est évident que l'origine est le point minimisant cette fonction.
 Résolution avec un pas xe
Dans ce cas on recherche un pas ρ optimale c'est celui qui minimise une certaine
fonction, on a :
∇f (X) = [ 2x , 6y]
ξ(ρ) = X − ρ∇f (X)0 = [(1 − 2ρ)x , (1 − 6ρ)y]0

22
 Pour l'obtention du paramètre ρ, considérons la fonction g(ρ) qu'on doit mini-
miser suivant ρ :
g(ρ) = f (ξ(ρ))
= (1 − 2ρ)2 x2 + (1 − 6ρ)2 y 2 ,
g 0 (ρ) = −4(1 − 2ρ)x2 − 36(1 − 6ρ)y 2

la paramètre ρ qui minimise la fonction g(ρ) est celui qui satisfait g (ρ) = 0,
0

soit :
(2.6)
2 2
x + 9y
ρ= 2 2
2x + 54y
L'équation itérative de résolution de ce problème est donc :
 X = [x , y] = [3 , 5] ,
0 0

 Répéter
1. ∆X ← −[ 2x , 6y] . 0

2. ρ = x2 +9y 2

3. X ← X + ρ∆X.
2x2 +54y 2

 Arrêter lorsque k∆Xk ≤ 10 . 2 −3

 Résolution avec un pas itératif Lorsqu'on choisis un pas itératif alors, la

2

deuxième étape dans l'algorithme est remplacée par la boucle suivante :

soit α = 0.25 , β = 0.5 ρ = 1 alors
pour une direction donnée ∆X = −[2X(1) , 6X(2)] , 0

 faire :
Y = X + ρ∆X,
f (Y) = Y(1)2 + 3Y(2)2 ,
∇f (X) = [2X(1) , 6X(2)],

 si f (Y) < f (X) + αρ∇f (X)∆X

n
 sinon
ρ = βρ
 n
Exercice 10.
Soit la fonction réelle à deux variables :
f (x, y) = x(2 + x) + y 2 + 4

23
 f(x,y)=x2+3y2

20

15

10
z

0
2
2
1 1
0 0
−1 −1
−2 −2
y x

Figure 2.1  Allure de la fonction f (x, y) = x2 + 3y2

f(x,y)=x2+3y2
5

0
y

−1

−2

−3

−4

−5
−5 −4 −3 −2 −1 0 1 2 3 4 5
x

Figure 2.2  vue de haut de la fonction f (x, y) = x2 + 3y2

24
 1. Calculer le Jacobien,
2. Calculer le Hessien,
3. Déterminer l'équation caractéristique du Hessien,
4. Donner les valeurs propres de cette matrice,
5. Cette matrice est elle dénie positive, pourquoi?
6. Calculer le déterminant en utilisant les valeurs propres.
7. Trouver analytiquement l'optimum de cette fonction, quelle est sa nature?
8. Utiliser la méthode du gradient pour déterminer cet extremum.
9. Calculer le pas optimale.
10. Donner l'algorithme correspondant à cette fonction pour le calcul du pas de façon
itérative.
2.7 Méthode de Newton
2.7.1 Principe
La méthode de Newton fait partie des méthodes de descente. Cette technique
cherche à minimiser le développement en série de Fourier du second ordre de la fonction
f (X) ∈ C suivant la quantité ∆X :
2

1
f (X + ∆X) ≈ f (X) + ∇f (X)∆X + ∆X0 Hf (X)∆X
2!
le ∆X qui minimise la partie droite est comme suit :
∆X = −Hf (X)−1 ∇f (X)0
pour la convergence cette méthode on calcule la quantité positive ∇f (X) Hf (X)
1 0 −1
∇f (X)
et on vérie qu'elle est inférieur ou égale à une certaine précision.
2

2.7.2 Algorithme
 connaissant la valeur initiale X , et la précision 
 Répéter
0

1. ∆X ← −Hf (X) ∇f (X) ,

−1 0

2. on arrêter si ∇f (X) Hf (X) ∇f (X) ≤ .

1 0 −1

3. Choisir le pas ρ (s'il est xe on ignore cette étape).

2

4. Mettre à jours X ← X + ρ∆X.

25
2.7.3 Exemple
Reprenant l'exemple de la section précédente, soit une fonction cout f (X) quadra-
tique en < :
2

f (X) = x2 + 3y 2 ,
avec X = [x, y]0.
Donner la forme quadratique correspondante, puis déterminer le minimum par la
méthode de Newton.
on a :
∇f (X)= [2x, 6y]
1
 
2 0 −1 2 0
Hf = −→ Hf
=
0 6 0 1
  6
x
∆X = −Hf −1 ∇f (X) = −
y
1
  
1 0 −1 1
 
2 0 2x
2 ∇f (X) Hf (X) ∇f (X) = 2 2x 6y 0 1
6y
6

2.8 La méthode Quasi-Newton

Soit les matrices A et B :

Problème des matrices mal conditionnées

   
1.2644 1.8426 7725.7 −3533.8
A= −→ A−1 =
2.7640 4.0284 −5300.8 2424.9

B=

2645
1. 1.8426

−→ B −1
=

4358.5 −1993.6


2.7640 4.0284 −2990.4 1368.1

Nous remarquons que B ne dière de A que sur l'élément de position (1,1) et cette
diérence est de l'ordre de 10 .−4

Si on a les deux problèmes AX = [1 1] et BX = [1 1] , cela donne respectivement

0 0

les solutions suivantes :X = [4191.8 − 2.8759] et X = [2364.8 − 1622.3] .

0 0

On remarque que pour une petit erreur de 10 la solution varie énormément. La

−4

cause principale de cette diérence peut être expliqué par rapport aux valeurs propres
correspondantes des deux matrices A et B qui sont [0.0001 5.2927] et [0.0002 5.2927] ,0 0

respectivement.
On peut dire qu'il y a un certain déséquilibre entre les valeurs propres de ces ma-
trices. On dit qu'on a des matrices mal conditionnées.

26
2.8.1 Introduction
La méthode de Newton requière l'inversion du Hessien. L'inversion des matrices est
une opération qui est souvent lourde et peut être la cause d'une instabilité numérique
si la matrice est mal conditionnée. Dans ces conditions, on applique la méthode Quasi-
Newton.
2.8.2 Principe
Le principe de cette méthode est de remplacer la matrice inverse du Hessien Hf (X ) −1

par une matrice symétrique et semi-dénie positive qu'on appel Qf (X ) = Q . Le

k

Hessien peut être approximé par :

k k

Hf (Xk+1 ) (Xk+1 − Xk ) = ∇f (Xk+1 ) − ∇f (Xk )

Si on multiplie cette équation par l'inverse du Hessien, on s'aperçois que la matrice
Q k+1doit satisfaire la condition suivante :
Qk+1 (∇f (Xk+1 ) − ∇f (Xk )) = Xk+1 − Xk
De cette façon, on a éviter le passage par l'inversion d'une matrice. mais on a recours
à la résolution d'un système d'équations linéaires.
Cette technique est très utilisée dans beaucoup de problèmes, cependant,
elle nécessite un nombre d'itérations très important si le problème est mâle conditionné
Remarques

ou si une mauvaise estimée initiale du Hessien est utilisée.

La première méthode quasi-Newton est appelée DFP, elle a été découverte en 1959
par Davidson, ensuite Fletcher et Powell ont exploité ces propriétés durant la décen-
nie suivante. Cette méthode exploite la variation du gradient entre deux itérations.
L'une des formes récursives les plus utilisées est celle nommée BFGS (Broyden, Flet-
cher, Goldfarb et Shanno) découverte en 1970. Dans cette méthode on ne cherche pas
à résoudre un système d'équations linéaires mais on utilise des formules algébriques
(multiplication de vecteurs et de matrices). alors on à :
0
Qk+1 = (I − ρk dXk Yk0 ) Qk (I − ρk dXk Yk0 ) + dXk ρk dX0k
dXk = Xk+1 − Xk
Yk = ∇f (Xk+1 ) − ∇f (Xk )

Lorsqu'on traite un problème de grande dimension, il n'est pas possible de sauve-

garder toutes les données à cet eet, il existe une version limitée en espace de cette
méthode dont le nom est L-BFGS (Limited-memory BFGS).
27
2.9 Méthodes du gradient conjugué
L'inconvénient de la méthode du gradient, c'est quelle eectue, souvent, beaucoup de
zigzags avant d'atteindre la solution souhaité. An d'éliminer ce problème, la méthode
du gradient conjugué, cherche une nouvelle direction à chaque itération.
2.9.1 Principe
A l'itération k, on cherche l'inverse du gradient et on lui ajoute une combinaison
linéaire des anciens vecteurs de direction, an d'obtenir un nouveau vecteur conjugué
de direction.

Figure 2.3  Problème de rapidité de convergence de la méthode du gradient

2.9.2 Problème introductif

 Question : Comment résoudre l'équation à une seule variable ax − b = 0, en
utilisant les techniques de descente?
 Indication La réponse passe par l'utilisation de l'équation ax − bx − c = 0
1 2

 Réponse : Cette équation peut être vue comme étant un problème de minimi-
2

sation de la forme quadratique ax − bx − c = 0. Eectivement, la dérivée de

1 2

cette équation donne notre équation ax − b = 0.

2

2.9.3 Dénition
Deux vecteurs U et V dans < sont conjugués par rapport à une forme bilinéaire
n

de matrice symétrique dénie positive Q (on dit aussi qu'ils sont Q-orthogonaux), si :
U0 QV = 0

28
Remarques

1. Pour Q = I on retrouve la dénition classique de l'orthogonalité.

2. Un ensemble nie de vecteurs {U } est dit Q-Orthogonal si U QU
k
= 0 ∀i 6= j .
Ces vecteurs sont en plus linéairement indépendants.
i i=1 i j

2.9.4 Résolution d'un système d'équations linéaire

La résolution d'un système d'équation linéaire de la forme QX = B peut être vue
comme un problème d'optimisation (recherche du minimum) d'une fonction quadra-
tique de la forme :
min 2 X QX − B X
 
1 T T

On note que la solution optimale de ce problème d'optimisation n'est autre que la

solution du système d'équations linéaire.
Chaque solution peut être mis sous la forme d'une combinaison linéaire d'un en-
semble de vecteurs Q-orthogonal {U } , alors :n
i i=1

X ∗ = α1 U1 + α1 U1 + ... + αn Un

pour déterminer le coecient α , on multiplie à gauche par la quantité U Q. Cela nous

T

donne :
i i

T ∗ T
U QX i U B i
αi = =
UiT QUi UiT QUi
Cela montre que la solution X peut être obtenue par :
∗

n
∗
X UiT B
X = T QU i
U
i=1
Ui i

Suivant cette expression, on peut dire que la solution X peut être considérer comme
∗

le résultat d'un processus itératif de n étapes où à chaque étape on ajoute un terme

αU.
i i

2.9.5 Théorème des directions conjuguées

Soit l'ensemble {U } Q-orthogonale. Pour un vecteur X quelconque, la séquence
n−1

{X } générée suivant l'expression :

i i=0 0
i

Xk+1 = Xk + αk Uk

où gkT Uk
αk = −
UkT QUk
29
 et
gk = QXk − B
converge vers la solution unique X de QX = B après n itérations (c-à-d X
∗
n = X∗ ).
2.9.6 Algorithme
1. Pour X donné, on prend U = −g = B − QX
0 0 0 0

2. α = −
k
gkT Uk
UkT QUk
3. X = X + α U
k+1 k k k

4. g = QX − B
k+1 k+1

5. β =
k
T
gk+1 QUk
UkT QUk
6. U = −g + β U
k+1 k+1 k k

La direction à l'itération k représente une combinaison linéaire des anciennes direc-

tions de descente.

30
2.10 Solutions des exercices
Solution Ex. 8.

1. La hauteur est donnée par la variable h. suivant la gure 2.4.

Figure 2.4  Croquis de la boite

2. Le volume de la boite est donné par la relation :

V =a×b×h
a = L − 2h
b = H − 2h
V (h) = (L − 2h)(H − 2h)h
V (h) = 4h3 − 2(L + H)h2 + LHh

3. La dérivation de V (h) donne :

dV (h)
= 12h2 − 4(L + H)h + LH
dh
Le maximum de cette fonction vérie la solution de l'équation = 0. dV (h)

Les solutions de cette équation sont h = 40.4mm et h = 128.58mm. Suivant le

dh

problème posé, la hauteur h ne peut pas être plus grande que min(H, L).
1 2
1

Les dimensions de la boites sont alors :

2

 La hauteur h = 40.4 mm.

 La longueur a = H − 2h = 216.2 mm.
 La largeur b = L − 2h = 129.2 mm.
Le volume maximale correspondant est alors V = 1.1285 × 10 mm . 6 3

Sachant quen 1L = 1000cm le volume en litre vaut V = 1.128 L

3

31
 Programme Matlab

La gure 2.5, présente le tracé de la fonction V (h) pour h allant de 0 à 1

.
2 min(H, L)
Cette gure est le résultats du programme Matlab . .

Figure 2.5  Volume en fonction de la hauteur

L=210;
H=297;
1

a=min(H,L) /2;
2

h=0:a ;
4

V=4∗h.^3 − 2 ∗ (L+H) ∗h.^2+L∗H∗h;

5

figure , hold on
6

plot (h,V)
7

xlabel ( 'h(mm) ' )

8

ylabel ( 'V(mm^3) ' )

9

t i t l e ( ' Variation du volume en fonction de la auteur ' )

10

[V_max, i_max]=max(V) ;
11

h_max=h(i_max) ;
12

plot (h_max,V_max, ' ∗ r ' )

13

line ([h_max h_max] ,[0 V_max] , ' LineStyle ' , '−− ' , ' Color ' , ' r ' )
14

line ([0 h_max] ,[V_max V_max] , ' LineStyle ' , '−− ' , ' Color ' , ' r ' )
15

Vp=12∗h.^2 − 4 ∗ (L+H) ∗h+L∗H;

16

h_zero=find (abs(Vp)<1)
17

Vp_max= Vp(i_max) ;
18

subplot (2 ,1 ,2) , hold on , plot (h, Vp)

19

20

32
 xlabel ( 'h(mm) ' ) , ylabel ( 'V' ' ' ) ,
t i t l e ( ' Variation de la derivee en fonction de la hauteur ' )
21

22

Solution Ex. 9.

1. l'Aire du triangle rectangle est égal à S(x, y) = ( AB + x) × y. Les coordonnées

1

des points A et B sont A(6, 0) et B(−6, 0) et suivant la fonction on obtient la

2

surface : 2 2 4
S = (− x2 + 8) × (6 + x) = − x3 − x2 + 8x + 48
9 9 3

Figure 2.6  Dessin du triangle rectangle

La dérivé de la surface suivant la variable x donne :
dS(x) 2 8
= − x2 − x + 8
dx 3 3
Le maximum de cette fonction est atteint pour x = 2. Les deux gures 2.6 et 2.7,
sont les résultats du programme Matlab ci-dessus. Suivant l'allure de la dérivée
gure 2.7, il est claire que le maximum est atteint au voisinage du point dont
l'abscisse est 2.
figure , hold on
x= − 6:0.01:6;
1

y=−2∗x.^2/9+8;
2

plot (x ,y , 'k ' ) ;

3

33
 Figure 2.7  Allure de la surface ainsi que sa dérivée suivant x.

xlabel ( 'x ' )

ylabel ( 'y ' )
5

t i t l e ( 'y=−2∗x.^2/9+8 ' )
6

x1=4;
8

y1=−2∗x1^2/9+8;
9

plot ([ x1 , x1 ] ,[0 y1 ] , 'b ' )

10

plot ([ − 6 x1 ] ,[0 y1 ] , 'b ' )

11

12

x2=4;
13

y2=−2∗x2^2/9+8;
14

f i l l ([ − 6 x2 x2 − 6] ,[0 0 y2 0] , 'b ' )

15

16

figure , hold on
17

S=−2∗x.^3/9 −4∗ x.^2/3+8 ∗ x+48;

18

Sp=−2∗x.^2/3 −8∗ x/3+8;

19

plot (x ,S, 'k ' )

20

plot (x ,Sp , ' r ' )

21

legend ( 'S(x) ' , 'S ' ' (x) ' )

22

grid on
23

xlabel ( 'x ' )

24

ylabel ( 'y ' )

25

26

34
Solution Ex. 10.
Soit la fonction réelle à deux variables :
f (x, y) = x2 + 2x + y 2 + 4

1. Calcule du Jacobien,
 
∂f  
∂x 2x + 2
Jf = ∇f 0 =  =
   
∂f
∂y 2y

2. Le Hessien 2 0
 
Hf =
0 2
3. L'équation caractéristique du Hessien est donnée par :
det(H − λI) = 0 → (2 − λ)2 = 0

4. Les valeurs propres de la matrice H sont les solutions de l'équation caractéris-

tique de cette matrice, alors :
f

(2 − λ)2 = 0 → λ1 = λ2 = 2

5. La matrice est dénie positive, car les valeurs propres sont positives.
6. Le déterminant est donné par le produit des valeurs propres :
det(Hf ) = λ1 × λ2 = 4

7. L'optimum de cette fonction est obtenu analytiquement lorsqu'on résous le sys-

tème d'équations suivant :
 
∂f    
∂x 2x + 2 0 (1)
0
Jf = ∇f =  = =
   
∂f
∂y 2y 0 (2)
soit :
x = 1 et y = 0
l'optimum est f (−1, 0) = 3, et présente un minimum car on peut facilement
démonter l'une des propriétés suivantes :
 det(H ) > 0 et H > 0
 Toutes les valeurs propres sont positives
f 11

 La matrice est dénie positive

35
8. Par la suite on déterminera la méthode de résolution à pas xe uniquement. Dans
ce cas on recherche un pas ρ optimale qui minimise une certaine fonction, on a :
∇f (X) = [ 2x + 2 , 2y]
 
x − 2ρ(x + 1)
ξ(ρ) = X − ρ∇f (X)0 =  
y − 2ρy

Pour l'obtention du paramètre ρ, considérons la fonction g(ρ) qu'on doit minimiser

suivant ρ :
g(ρ) = f (ξ(ρ))
= [x − 2ρ(x + 1)]2 + 2[x − 2ρ(x + 1)] + [y − 2ρy]2 + 4 (2.7)
g 0 (ρ) = −4(x + 1)[x − 2ρ(x + 1)] − 4(x + 1) − 4y[y − 2ρy]

la paramètre ρ qui minimise la fonction g(ρ) est celui qui satisfait g (ρ) = 0, soit :
0

(2.8)
2 2
1 x + 2x + y + 1 1
ρ= × 2
= 2
2 (x + 1) + y 2

Ci-dessous, l'algorithme pour résoudre numériquement ce problème avec une pré-

cision de  = 10 et en prenant comme point initial X = [3 , 5] :
−3 0

 Initialisation
0

X = [x , y]0 = [3 , 5]0
ρ = 21
 Répéter
(a) ∆X ← −[ 2x + 2 , 2y] . 0

(b) X ← X + ρ∆X.
(c) Arrêter lorsque k∆Xk = (2x + 2)
2
2
2
+ 4y 2 ≤ 10−3 .

36
Chapitre 3
Optimisation avec contraintes : méthodes
globales

3.1 Dénitions
Un problème d'optimisation avec ou sous contrainte est donné sous la forme sui-
vante :
minf (X) X ∈ <n
hi (X) = 0 i = 1, ..., p
gj (X) = 0 j = 1, ..., q

Cette forme est appelée forme standard.

Exemple

 f (x) = x avec x ≥ 1,
2


f (x, y) = x2 + y 2
x+y =5

3.2 Conditions d'optimialité

Les conditions d'optimalité sont les mêmes que pour des problèmes sans contrainte
avec une légère modication.

37
3.2.1 Cas d'une contrainte d'inégalité
Soit le problème suivant :
minf (X) X ∈ <n
g(X) ≤ 0

Si f (X) et g(X) sont des fonctions diérentiables de < dans <, et si X n ∗

est un minimum local de f sur l'ensemble {X/g(X) ≤ 0}. Si on suppose de plus que
Théorème

∇g(X ) 6= 0 alors, il existe γ ≥ 0 tel que :

∗

∇f (X∗ ) + γg(X∗ ) = 0
γg(X∗ ) = 0

de plus, si f et g sont convexes alors ces deux égalités sont susentes pour assurer que
X est un minimum local.
∗

Exp.

f (x) = x2 f (x) = x2
x≥1 g(x) = 1 − x ≤ 0

alors :
f (x) = 2x ; g(x) = 1 − x d'où g (x) = −1 6= 0
0 0

les conditions de convergence peuvent s'écrire :

2x∗ + γ(−1) = 0 γ = 0 ⇒ x∗ = 0 non admissible
γ(1 − x∗ ) = 0 x∗ = 1 ⇒ γ = 2

Exercice 11.
. Quel est le minimum de l de fer nécessaire pour clôturer une zone rectangulaire de
surface S.
3.2.2 Le Lagrangien du problème
Le Lagrangien d'un problème d'optimisation sous contraintes se met sous la forme :
(3.1)
p
X q
X
L(X, λ, γ) = f (X) + λi hi (X) + γi gi (X)
i=1 j=1

où les vecteurs λ = [λ λ ...λ ] et γ = [γ γ ...γ ] sont appelés les multiplicateurs de

Lagrange. L'intérêt du Lagrangien est de ramener un problème d'optimisation sous
1 2 p 1 2 q

contraintes en un problème d'optimisation sans contraintes.

38
Exp.

f (x) = x2 f (x) = x2
x≥1 g(x) = 1 − x ≤ 0 −→ L(x, γ) = x2 + γ(1 − x)

Exercice 12.
.
On veut résoudre le problème d'optimisation suivant :
f (x, y) = (x − 5)2 + (y − 2)2

Sous la contrainte suivante :

y − x = −3
a. Trouver graphiquement la solution.
b. En utilisant les multiplicateurs de Lagrange, trouver les solutions analytiquement.
3.2.3 Cas d'une contrainte d'égalité
Un problème d'optimisation statique qui fait intervenir un ensemble de p contrainte
d'égalité est formulé comme suit :

minL(X)
f (X) = 0
avec :
f (X) = [f 1 (X), ..., f p (X)]T
Les conditions nécessaires pour l'existence d'un point stationnaire sont données par :

f (X) = 0
LX + λT fX = 0
λ est appelé vecteur adjoint, ses composantes sont appelées les coecients de Lagrange.
Ce sont des variables intermédiaires dont l'introduction permet de simplier les calcul.
Ainsi on a un système linéaire de n + p équations et n + p inconnues X et λ. On
déni la fonction H par :
L + λT f
les conditions d'optimalité s'écrivent alors H = 0. X

Trouver le vecteur X qui minimise la fonction L(X) = x 2

+ x22 avec la
condition 2x + x = 4.
Exemple 1
1 2

39
Solution

H = L + λT f = x21 + x22 + λ(2x1 + x2 + 4)

HX = 0 donne :
 ∂H
 ∂x1 = 2x1 + 2λ = 0
HX = 0 −→
∂H
= 2x2 + λ = 0


On considérons la contrainte 2x + x = 4, on obtient un système à 3 équations et 3

∂x2

inconnus.
1 2

Exercice 13.
On veut Déterminer les dimensions d'une boîte en carton parallélépipédique (comme
une boite d'allumette) et dépourvue de couvercle dont la construction demande le
moins de carton possible tout en ayant une contenance V déterminée.
a. Dénir les variables correspondantes à ce problème.
b. Donner une formulation mathématique de ce problème d'optimisation sous contraintes(En
déterminant la fonction coût et la contrainte).
c. En éliminant une variable (la hauteur), trouver les points stationnaires puis ré-
soudre le problème en tant que problème d'optimisation sans contrainte. (Indi-
cation : éliminer la contrainte)
d. Démontrer que l'optimum obtenu présente bien un minimum.
3.3 Méthode du gradient projeté
3.3.1 Introduction
Cette méthode est semblable à celle vue au chapitre précédente alors on a :
Xk+1 = Xk − ρk ∇f (Xk ) (3.2)
Soit Ω l'ensemble des vecteurs X qui vérient les contraintes. Si X vérie les
contraintes h(X ) = 0 et g(X ) ≤ 0, rien ne garantie que X vérie à son tour ces
k

contraintes.
k k k+1

La méthode du gradient projeté consiste alors à la projection du point X sur

l'ensemble Ω.
k

3.3.2 Projection sur un convexe

Soit Ω un convexe fermé de < , la projection d'un point X ∈ < sur Ω, notée
n n

P (X) est dénie comme l'unique solution de :

Ω
1
max kX − Yk
2
Y∈Ω 2
2 (3.3)
40
3.3.3 Algorithme
Cette méthode se base sur un algorithme identique à celui du gradient, sauf qu'on
doit ajouter la projection du point sur l'ensemble Ω :
Y = X − ρ ∇f (X )
k k k k (3.4)
pour obtenir le point
X k+1= P (Y ) Ω k (3.5)
Le vecteur Y peut être obtenu en minimisant la fonction :
k

min kX − ρ ∇f (X ) − Yk avec Y ∈ < sous les contraintes (3.6)

1 2 n
k k k 2
2
donc c'est un problème d'optimisation sur un convexe.
Exp.

1
f (x, y) = (x2 + 7y 2 )
2
y−x=1

Sol. X∗ = [−0.875 0.125]0

41
3.4 Solutions des exercices
Solution Ex. 11.
.
On à le système :
 f (x, y) = (x − 5)2 + (y − 2)2


y − x = −3


Sous la forme standard on obtient :

 f (x, y) = (x − 5)2 + (y − 2)2


g(x, y) = y − x + 3 = 0


Le Lagrangien s'écrit sous la forme :

H = f + λg

H = (x − 5)2 + (y − 2)2 + λ(y − x + 3)

Le système d'équations pour la résolution de ce problème est :


 Hx = 2(x − 5) − λ = 0 . . . . . . (1)



Hy = 2(y − 2) + λ = 0 . . . . . . (2)




y − x + 3 = 0 . . . . . . . . . . . . . . . (3)



(1) + (2) → x − 5 + y − 2 = 0 . . . . . . (4)

y =7−x
(4)et(2) →
y =x−3
on tire alors
7 − x = x − 3 =⇒ x = 5ety = 2
le Hessien correspondant au point (5, 2) est :
 
2 0
Hf (5, 2) =
0 2
Suivant les exercices précédents, le Hessien est déni positif alors en ce point on à un
minimum.
42
Solution Ex. 12.
.
 Soit un rectangle dont la longueur a et la largeur b voir gure ci-contre. La
surface de ce rectangle est S = a × b.

𝑆 𝑏

Figure 3.1  Rectangle de dimension a × b

 Pour clôturer ce rectangle, nous avons besoins d'un l de longueur L = 2(a + b).
 La contrainte correspondante à ce problème est la surface S . Tandis que la fonc-
tion à minimisé est la longueur L.
 Ainsi le Hessien correspondant est donné par :
H = L − λS = 2a + 2y − λab
 Calcul des dérivées
∂H

 ∂a = 2 − λb = 0
HX = 0 −→
∂H
= 2 − λa = 0

∂b
de ces deux équations on tire a = b.
 En utilisant la contrainte, on obtient : √
ab = S → a2 = S → a = b = S
Solution Ex. 13.
.
 Considérons les trois variables x, y et z représentant les dimensions de la boite.
 Le volume de la boite est donné par la relation (Représente la contrainte) :
V = xyz
 La boite étant sans couvercle alors, la surface correspondante à la somme des 5
faces est donnée par :
S = xy + 2(xz + yz)

43
 Figure 3.2  Boite sans couvercle.
Cette équation représente la fonction à minimisé, car on cherche le minimum de
carton possible pour couvrir les surfaces.
 on à : V
z=
xy
 alors, f (x, y) = xy + +
2V 2V

 le point stationnaire est


y
donné pour :
x

∂f 2V

 ∂x =y− x2 =0 → 2V = yx2

∂f 2V
=x− =0 → 2V = xy 2


∂y y2

alors
xy 2 = yx2 =⇒ x = y
 Enn on obtient V = 2x et
√ q
3
→ x = y = 2V3
z = 3 V4
 Pour déterminer la naturede l'optimum on doit calculer les dérivées partielles :
∂2f 4V ∂2f

 ∂x2 = x3 ∂x∂y =1

 ∂f ∂2f 4V
∂y∂x 1 =

∂y 2 y3

alors le Hessien est donné par :

 4V 
x3 1
H= 
4V
1 y3

 au point optimum H(√2V , √2V ) on obtient :

3 3

 
2 1
H= 
1 2
on a det H = 3 > 0 et H 11 =2>0 alors ce point présente un minimum.
44
Chapitre 4
Programmation linéaire

4.1 Exemples introductifs

Représenter graphiquement les solutions des inégalités suivantes :
x−8≥0
x + y2 ≤ 1
2

Comment résoudre graphiquement le système d'équations suivant :


x−y =1
6x + 8y = 2

4.2 Dénitions 1
La programmation linéaire, est une méthode d'optimisation, dont la fonction coût
(objective) et les contraintes sont linéaires. Ainsi dans ce chapitre on ne considère que
la résolution des équations linéaires.
La forme standard et compacte d'un problème de programmation linéaire (PL) est
donnée par :
min C X (fonction coût)
T


sous les contraintes





 AX = B
X≥0


Où : X , B et C sont des vecteurs de dimensions n et A une matrice de dimension

m × n.
Si la contrainte 1 est donnée sous la forme d'une inégalité AX ≤ B, elle peut être
remis sous la forme d'une égalité comme suit : AX + Y = B où Y (i) ≥ 0 Ainsi le

45
problème devient :
min C T X



AX + Y = B


 X≥0
Y ≥0


Y est appelée variable d'écart (slack variable).

Considérons le problème suivant :

Exemple 1



 min z = x1 − x2
2x1 + x2 ≥ 2

x + 3x2 ≤ 3
 1


x1 , x2 ≥ 0
Ce problème se transforme sous la forme standard comme suit :


 min z = x1 − x2
2x1 + x2 − x3 = 2

x + 3x2 + x4 = 3
 1


x1 , x2 , x3 , x4 ≥ 0

4.3 Dénitions 2
On considère le domaine des solutions réalisable comme étant l'intersection d'un
sous-espace avec l'orthant positif (quadrant en 2D, Octant en 3D, et orthant en di-
mension n). Les points extrêmes des solutions réalisables sont appelées solutions de
base.
4.4 Le théorème fondamentale de la programmation linéaire
Étant donné un programme linéaire (PL) sous la forme standard
 min C T X


AX = B
X≥0


où A est une matrice m × n de rang m, alors :

1. S'il existe une solution réalisable au programme linéaire, alors il possède une
solution de base réalisable.
2. S'il existe une solution réalisable optimale au programme linéaire, alors il existe
une solution de base réalisable optimale.
46
4.5 Relation avec la convexité
4.5.1 Dénition
Un point X appartenant à un ensemble convexe Ω, est dit , s'il n'existe
pas deux points distincts X et X dans Ω qui satisfont :
point extrême

1 2

X = αX1 + (1 − α)X2

pour α ∈]0, 1[.

4.5.2 Équivalence entre point extrême et solution de base
Soit A une matrice de dimension m × n et de rang m, et B = {B } , m vecteurs.
m

Soit K le polytope convexe constitué des n vecteurs X qui satisfont

i i=1


AX = B
X≥0
Un vecteur X est un point extrême de K si et seulement si X est une solution de
base réalisable.
4.5.3 Exemple
considérons le problème de PL suivant :

x1 + x2 + x3 = 1
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0

Cette gure montre la surface (le triangle), où appartient la solution admissible. Les
trois sommets du triangle présentent les solutions de base (1,0,0), (0,1,0) et (0,0,1).
4.6 Résolution graphique
Une entreprise fabrique des vêtements pour femme. Les prots réalisés sont de 50$
par robe et de 30$ par chemisier vendu. Combien de robes et de chemisiers doit-elle
vendre pour réaliser un prot maximum en respectant les conditions suivantes :
 On ne peut pas fabriquer plus de 80 items de vêtement par mois.
 Il faut deux heures pour coudre une robe et une heure pour coudre un chemisier,
alors que la machine à coudre n'est disponible que pendant cent heures par mois.
Résoudre graphiquement ce problème.

47
 Figure 4.1  Ensemble des solutions possibles pour le problème précédent

Réponse Formulation
 du problème

 max f (x1 , x2 ) = 50x1 + 30x2
x1 + x2 ≤ 80

2x + x2 ≤ 100
 1


x1 ≥ 0, x2 ≥ 0
La solution à ce problème correspond à l'un des sommets du polygones [0 0], [0 50], [20 60]
et [0 80], alors on remplace ces coordonnées dans la fonction f (x , x ). on trouve que
le maximum de prot correspond au point [20 60]
1 2

4.7 La méthode du simplexe

4.7.1 Introduction
L'idée de la méthode du simplexe est de démarrer avec une solution réalisable de
base (l'un des points extrêmes) de l'ensemble des contraintes d'un problème sous sa
forme standard et de passer à un autre de telle façon à minimiser la fonction coût
jusqu'à l'obtention du minimum. On note qu'il est susant de se limité au solutions
réalisable de base dans notre recherche du point optimale réalisable.
4.7.2 Algorithme (Etapes)
Les étapes constituants cette méthode sont comme suit :
1. Mise sous la forme standard
48
 Figure 4.2  Résolution géométrique du programme linéaire

2. Ajout des variables d'écart

3. Création du tableau
4. Recherche du pivot
5. Création du nouveau tableau
6. arrêter si toutes les valeurs de la dernière ligne sont positives
7. Identication de la valeur optimale
4.7.3 Exemple 1
Pour illustrer cette méthode on considère le programme linéaire suivant : On veut
maximiser la fonction coût suivante :
f (X) = 12x1 + 16x2

sous les contraintes suivantes :


 10x1 + 20x2 ≤ 120
8x + 8x2 ≥ 80
 1
x1 ≥ 0, x2 ≥ 0
An d'appliquer l'algorithme du simplexe, on doit mettre le problème sous sa forme
standard. Ainsi, il faut transformer le problème de maximisation en un problème de
49
minimisation. Cela est fait simplement en multipliant la fonction f (X) par −1, et en
introduisant les 2 variables non négatives d'écart x et x . le problème se reformule
comme suit :
3 4

On veut minimiser la fonction coût suivante :

h(X) = −12x1 − 16x2

sous les contraintes suivantes :

10x1 + 20x2 + x3 = 120
8x1 + 8x2 + x4 = 80
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0

On construit ainsi le tableau suivant :

x1 x2 x3 x4 b
l1 1 2 1 0 12 (12/2=6 )
l2 1 1 0 1 10 (10/1=10)
l3 -12 -16 0 0
−16 est la plus petite valeur, on choisi alors la colonne a , on divise les éléments de
la colonne b par ceux de la colonne a . Ensuite on choisis le pivot qui me donne le
2

rapport le plus petit soit 2 dans ce cas.

2

x1 x2 x3 x4 b
1/2 1 1/2 0 6
l1
1
l2 1 0 1 10
l -12
3 -16 0 0
Il faut annuler tous les éléments de la colonne a sauf le pivot, alors on obtient les
équations des nouvelles lignes comme suit :
2

l2 = l2 − l1

l3 = l3 + 16l1
Le tableau devient :
x1 x2 x3 x4 b
1/2 1 1/2 0 6 (6/0.5=12)
l1
1/2 0 -1/2 1 4 (4/0.5=8
l2 )
-4 0 8 0
l3
On répète les mêmes opérations, on obtient :
50
 x1 x2 x3 x4 b
1/2 1 1/2 0 6
l1
1 0 -1 2 8
l2
-4 0 8 0
l3
pour annuler les éléments de la colonne 1, on met à jours les nouvelles lignes comme
suit : 1
l1 = l1 − l2
2
l3 = l3 + 4l2
x1 x2 x3 x4 b
0 1 5/2 -1 2
l1
1 0 -1 2 8
l2
0 0 4 8
l3

Il n'y-a pas d'éléments négatifs dans la dernière ligne alors les solutions sont :

x1 = 8
x2 = 2
Ainsi le maximum de la fonctions sous les contraintes est max f (x , x ) = 152.
1 2

4.7.4 Exemple 2
Résoudre le problème du paragraphe résolution graphique. En utilisant cet algo-
rithme.
4.7.5 Exemple 3
On veut maximiser la fonction coût suivante :
f (X) = 3x1 + x2 + x3

sous les contraintes suivantes :

2x1 + x2 + x3 ≤ 2
x1 + 2x2 + 3x3 ≤ 5
2x1 + 2x2 + x3 ≤ 6
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0

An d'appliquer l'algorithme du simplexe, on doit mettre le problème sous sa forme

standard. Ainsi, il faut transformer le problème de maximisation en un problème de
minimisation. Cela est fait simplement en multipliant la fonction f (X) par −1, et en
51
introduisant les 3 variables non négatives d'écart x , x et x . le problème se reformule
comme suit :
4 5 6

On veut minimiser la fonction coût suivante :

h(X) = −3x1 − x2 − 3x3
sous les contraintes suivantes :
2x1 + x2 + x3 + x4 = 2
x1 + 2x2 + 3x3 + x5 = 5
2x1 + 2x2 + x3 + x6 = 6
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, x5 ≥ 0, x6 ≥ 0
On construit ainsi le tableau suivant :
x1 x2 x3 x4 x5 x6 b
2 1 1 1 0 0 2
1 2 3 0 1 0 5
2 2 1 0 0 1 6
rT -3 -1 -3 0 0 0 0
***********************
x1 x2 x3 x4 x5 x6 b
2 1 1 1 0 0 2
-3 0 1 -2 1 0 1
-2 0 -1 -2 0 1 2
rT -1 0 -2 1 0 0 2
***********************
x1 x2 x3 x4 x5 x6 b
5 1 0 3 -1 0 1
-3 0 1 -2 1 0 1
-5 0 0 -4 1 1 3
rT -7 0 0 -3 2 0 4
***********************
x x2 x3 x4 x5 x6 b
1 1/5 0 3/5 -1/5 0 1/5
1

0 3/5 1 -1/5 2/5 0 8/5

0 1 0 -1 0 1 4
r 0 T
7/5 0 6/5 3/5 0 27/5
52