Module : Optimisation Année 2020-2021

Solution de la série de TD 2

Exercice 1 Soit la fontion objectif

f (x) = 2x31 + x22 + x21 x22 + 4x1 x2 + 3

1. Trouver une approximation linéaire de f (x) au point x + δ si xT = [1 1].

2. Trouver une approximation quadratique de f (x) au même point.

Solution
Rappelons la formule de Taylor,
1
f (x + δ) = f (x) + g(x)T δ + δ T H(x)δ + o kδk2


2
avec δ T = [δ1 δ2 ].
1. L'approximation linéaire
 2     
6x1 + 2x1 x22 + 4x2 1 12
g(x) = ⇐⇒ g =
2x2 + 2x21 x2 + 4x1 1 8

Ainsi
f (x1 + δ1 , x2 + δ2 ) = 11 + 12δ1 + 8δ2
2. L'approximation quadratique
     
12x1 + 2x22 4x1 x2 + 4 1 14 8
H(x) = ⇐⇒ H =
4x1 x2 + 4 2 + 2x21 1 8 4

Ainsi
f (x1 + δ1 , x2 + δ2 ) = 11 + 12δ1 + 8δ2 + 7δ12 + 8δ1 δ2 + 2δ22

Exercice 2 Une fonction quadratique à n variables est donnée par

1
f (x) = a + bT x + xT Qx
2
où Q est une matrice symétrique n × n, montrer que le gradient et le Hessien de f (x) sont
donnés par : g(x) = b + Qx et H(x) = Q respectivement.

Solution    
q1 x1

Rappel : Soit Q =  q2 x2
   
.. et x = ..
  
. .
   
   
qn xn
Si nous avons
 
q1

 q2 
f = xT Q = x 1 x2 · · · xn ..  = q 1 x1 + q 2 x2 + · · · + q n xn
 
.

 
qn

1
alors  
q1
 q2 
g= .. =Q
 
 . 
qn
De même, si nous avons
 
x1

 x2 
f = QT x = q 1 q2 · · · qn ..  = q 1 x1 + q 2 x2 + · · · + q n xn
 
.

 
xn
alors  
q1
 q2 
T
g= ..  = QT = Q
 
 . 
qn
Revenons à l'exercice :
Nous avons
1
f (x) = a + bT x + xT Qx
2
ainsi
1

T
T 
g(x) = bT Qx + xT Q
+
2
1
Qx + QT x


g(x) = b +
2
puisque Q est symétrique ie. (Q = Q ), alors
T

g(x) = b + Qx

Si on dérive une seconde fois ce résultat, on obtient

H(x) = QT = Q

Exercice 3 Le point xTa = [2 4] est un minimiseur possible pour le problème

1 2
x1 + 4x22 − 4(3x1 + 8x2 ) + 100

min f (x) =
4
sc c1 (x) = x1 = 2
c2 (x) = x2 ≥ 0

1. Trouver les directions admissibles

2. Vérier si les conditions du second ordre sont vériées.
Solution
1. Les directions
 admissibles

d1
Soit d = une direction admissible.
d2
D'après
  la gure les seules directions admissibles possibles sont de la forme d =
0
d2

2
 Figure 1  Directions admissibles
2. Vérier si les conditions du second ordre sont vériées. Pour cela
(i) g(x̄)T d ≥ 0 (i) g(x̄)T d = 0
 
⇐⇒
(ii) Si g(x̄)T d = 0 alors dT H(x̄)d ≥ 0 (ii) Si g(x̄)T d = 0 alors 2d22 ≥ 0

Donc les conditions du second ordre sont vériées.

Exercice 4 Classier les matrices suivantes (DP, SDP, DN, SDN, Ind).
     
5 3 1 −5 1 1 −1 2 −3
(a) H =  3 4 2  , (b) H =  1 −2 2  et (c) H =  2 4 5 
1 2 6 1 2 −4 −3 5 −20

Solution  
5 3 1
(a) H =  3 4 2 . Calculons ses mineurs principaux
1 2 6
∆1 = 5 > 0, ∆2 = 11 > 0 et ∆3 = 54 > 0.
Ainsi, puisque tous les mineurs principaux sont strictement positifs alors la matrice H
est dénie positive.
 
−5 1 1
(b) H =  1 −2 2 . Calculons ses mineurs principaux
1 2 −4
∆1 = −5 < 0, ∆2 = 9 > 0 et ∆3 = −10 < 0.
Ainsi, la 
matrice H est dénie
 négative.
−1 2 −3
(c) H =  2 4 5 . Calculons ses mineurs principaux
−3 5 −20
∆1 = −1 < 0, ∆2 = −8 < 0 et ∆3 = 89 > 0.
Ainsi, puisque tous les mineurs principaux sont parfois positifs et négatifs alors la
matrice H est indénie.

Exercice 5 Trouver et classier les points stationnaires de la fonction

f (x) = x21 − x22 + x23 − 2x1 x3 − x2 x3 + 4x1 + 12

3
Solution
Tout d'abord, calculons le gradient de f
 
2x1 − 2x3 + 4
g(x) =  −2x2 − x3 
2x3 − 2x1 − x2

Ensuite résolvons le système g(x) = 0


 2x1 − 2x3 + 4 = 0
−2x2 − x3 = 0
2x3 − 2x1 − x2 = 0


Après résolution on trouve le point x̄ = (−10, 4, −8).

Maintenant, pour déterminer la nature de ce point, calculons le hessien, puis détermi-
ner sa nature
 
2 0 −2
H(x) =  0 −2 −1 
−2 −1 2
Avec ∆1 = 2 > 0, ∆2 = −4 < 0 et ∆3 = −2 < 0. Donc H est indénie ainsi le point x̄
est un point selle.
Exercice 6 Montrer que la fonction

2
f (x) = x2 − x21 + x51

possède un seul point stationnaire qui n'est ni un maximum ni un minimum.

Solution :
Tout d'abord, calculons le gradient de f
∂f
 
 
 ∂x1  −4x1 (x2 − x21 ) + 5x41
g(x) =  =
   
 ∂f  2
2 (x2 − x1 )
∂x2
Ensuite résolvons le système g(x) = 0

−4x1 (x2 − x21 ) + 5x41 = 0
2 (x2 − x21 ) = 0

Après résolution on trouve le point x̄ = (0, 0).

Maintenant, pour déterminer la nature de ce point, calculons le hessien, puis détermi-
ner sa nature

∂ 2f ∂ 2f
 
 
 ∂x21 ∂x1 ∂x2  20x31 + 12x21 − 4x2 −4x1  
 
 ⇐⇒ H(0, 0) = 0 0
H(x) =  =
  0 2
 ∂ 2f 2
∂ f  −4x1 2
∂x2 ∂x1 ∂x22
Or cette matrice est SDP. Donc on ne peut rien dire sur la nature du point stationnaire
x̄. Pour cela il faut regarder le quatrième terme dans le développement de Taylor.

4
 1 ∂ 3 f (x̄) 3 ∂ 3 f (x̄) 2 ∂ 3 f (x̄) ∂ 3 f (x̄) 3
 
T 1 T 2
f (x̄ + d)−f (x̄) = g (x̄) d+ d H (x̄) d+ d +3 2 d d2 + 3 d1 d2 + d +o
2 3! ∂x31 1 ∂x1 ∂x2 1 ∂x1 ∂x22 ∂x32 2

On a
∂ 3 f (x) 2 ∂ 3 f (x? )
= 60x1 + 24x1 ⇐⇒ =0
∂x31 ∂x31
∂ 3 f (x) ∂ 3 f (x? )
= −4 ⇐⇒ = −4
∂x21 ∂x2 ∂x21 ∂x2
∂ 3 f (x) ∂ 3 f (x? )
= 0 ⇐⇒ =0
∂x1 ∂x22 ∂x1 ∂x22
∂ 3 f (x) ∂ 3 f (x? )
= 0 ⇐⇒ =0
∂x32 ∂x32
Ainsi

  
1 0 0 d1 1 
−12d21 d2 + o kdk3



f (x̄ + d) − f (x̄) = d1 d2 +
2 0 2 d2 3!

f (x̄ + d) − f (x̄) = d22 − 2d21 d2 + o kdk3

Si d2 < 0 alors f (x̄ + d) − f (x̄) > 0 donc x̄ est un minimum.

Si d2 > 0 alors pour un d2 très petit et d1 6= 0 f (x̄ + d) − f (x̄) < 0 donc x̄ est un
maximum.
Ce qui implique que x̄ est un point selle.

Exercice 7 L'un des points xa = [1 −1]T , xb = [0 0]T et xc = [1 1]T minimise la fonction

f (x) = 100(x2 − x21 )2 + (1 − x1 )2

À l'aide de tests appropriés, identier le véritable minimiseur.
Solution
Tout d'abord, calculons le gradient de f
 
−400x1 (x2 − x21 ) − 2(1 − x1 )
g(x) =  
2
200(x2 − x1 )
En remplaçant xa et xb dans le gradient on trouve que ces derniers ne sont pas des
points stationnaires.
Par contre, xc est un point stationnaire pour la fonction f .
Par la suite calculons la matrice héssienne au point xc .

   
1200x21 − 400x2 + 2 −400x1 802 −400
H(x) = ⇐⇒ H(xc ) =
−400x1 200 −400 200

Ainsi
∆1 = 200 > 0 et ∆2 = 400 > 0
Ce qui implique que H est D.P donc xc est un minimiseur pour f .

5
Exercice 8 Etudier la convexité des fonctions suivantes :
1. f (x) = x21 + 2x22 + 2x23 + x24 − x1 x2 + x1 x3 − 2x2 x4 + x1 x4
2. f (x) = x21 − 2x22 − 2x23 + x24 − x1 x2 + x1 x3 − 2x2 x4 + x1 x4
Solution
1. f (x) = x21 + 2x22 + 2x23 + x24 − x1 x2 + x1 x3 − 2x2 x4 + x1 x4
 
2x1 − x2 + x3 + x4
 4x2 − x1 − 2x4 
g(x) =  
 4x3 + x1 
2x4 − 2x2 + x1
Ici, x̄ = (0, 0, 0, 0) Et le hessien est donné par
 
2 −1 1 1
 −1 4 0 −2 
H(x) =   1

0 4 0 
1 −2 0 2

∆1 = 2 > 0 ; ∆2 = 8 > 0 ; ∆3 = 16 > 0 et ∆4 = 20 > 0.

Ainsi le hessien est D.P. donc la fonction f est strictement convexe.
2. f (x) = x21 − 2x22 − 2x23 + x24 − x1 x2 + x1 x3 − 2x2 x4 + x1 x4
 
2x1 − x2 + x3 + x4
 −4x2 − x1 − 2x4 
g(x) =  
 −4x3 + x1 
2x4 − 2x2 + x1
Ici, x̄ = (0, 0, 0, 0) Et le hessien est donné par
 
2 −1 1 1
 −1 −4 0 −2 
H(x) =  
 1 0 −4 0 
1 −2 0 2

∆1 = 2 > 0 ; ∆2 = −8 < 0 ; ∆3 = 48 > 0 et ∆4 = 84 > 0.

Ainsi le hessien est indéni donc la fonction f n'est ni concave ni convexe.