theadaligncc

Corrigé devoir 2020 - Techniques d’optimisation

Questions de cours : (5 pts)

1) Quelles sont les conditions suffisantes pour un point d’inflexion d’une fonction à une seule
variable. Quelle est le signe de f 0 (x) et f 00 (x) au voisinage gauche et droite de ce point.
(1.5 pts)
f (n) (x∗ ) = 0 pour n = 1, · · · , k − 1 et f (k) (x∗ ) 6= 0 tel que k impair
f 0 (x) ne change pas de signe (+, +) ou bien (−, −)
f 00 (x) change de signe (−, +) ou bien (+, −)

2) Si on utilise la méthode Interval halving search pour minimiser une fonction f , donner (avec
explication) le nombre d’évaluations de f en fonction du nombre d’itérations n.(0.5 pts)
Trois 3 évaluations pour la première itération et 2 pour les autres itérations =⇒ 2n + 1

3) Quel est l’inconvénient principal de la méthode de la plus forte pente ? Expliquer la solution
proposée par la méthode des gradients conjugués ? (1 pts)
La vitesse de convergence est faible. Les directions sont orthogonales et la méthode fait des
”zigzag” dans l’espace de recherche. Dans la méthode des gradients conjugués, la direction dk
est égale à la somme du gradient ∇fk avec un multiple de la direction précédente.
4) Les méthodes Quasi-Newton proposent une solution à un problème éventuel lors de
l’utilisation de la méthode Newton dans le cas non-linéaire général à plusieurs variables.
Expliquer le problème rencontré et la solution proposée. (0.5 pts)
Le problème éventuel est la difficulté de calculer l’inverse de la Hessienne. Les méthodes Quasi-
Newton proposent d’utiliser une approximation de la Hessienne ou bien de son inverse.

5) Que représente le vecteur gradient d’une fonction en un point x par rapport à la fonction et
par rapport à l’iso-contour passant par ce point x? (1 pts)
Le gradient, qui est le taux de changement d’une fonction, est un vecteur qui pointe dans
la direction de la plus grande augmentation d’une fonction. Le gradient est nul aux maxima
et minima locaux car il n’y a pas de direction unique d’augmentation. Le gradient est
perpendiculaire à la tangente de l’iso-contour car il n’y a pas d’augmentation sur la direction
tangent à l’iso-contour

6) Expliquez pourquoi la méthode de Newton trouve le minimum local d’une fonction

quadratique après exactement une seule itération.(0.5 pts)
La méthode de Newton utilise une approximation de la fonction à minimiser en
développement de Taylor au degré 2. Pour es fonctions quadratiques, le développement de
Taylor au degré 2 représente la fonction exactement. Donc, l’approximation est égal a la
fonction.

1
Exercice 1 : (8 pts = 32/4)

1) Soit la fonction f1 , uni-modale sur son intervalle, suivante :

f1 (x) = (x − 1)3 − ln x , x ∈ [a, b] tel que a = 0.5 , b = 2.5

Utiliser la méthode de Fibonacci pour trouver la valeur du minimum. Localiser cette valeur
dans une plage de ε = 0.2. Prendre δ = 0.01 pour la dernière évaluation.

2) Soit la fonction f2 tel que :

x3 + x2 + 1
f2 (x) = , [x ∈ <, x 6= 1]
x−1
Utiliser la méthode de la sécante pour trouver un extremum local de la fonction en prenant
comme points initiaux x0 = 2 et x1 = 1.9. La précision requise est de ε = 0.01. Déterminer
la nature de cet extremum.
Pour chaque fonction, remplir le tableau des résultats des itérations ci-dessous.

Exercice 2 : 5pts

Détecter et classifier avec justification les points stationnaires des fonctions suivantes:

a. f1 : IR4 → IR avec f1 (x1 , x2 , x3 , x4 ) = x41 − 2x1 − cos(x2 ) + cos2 (x3 ) + 21 ex4 + 12 e−x4
 
4x31 − 2

 sin(x2 ) 

∇f1 (x1 , x2 , x3 , x4 ) = 
−2cos(x3 )sin(x3)

 1 
(ex4 − ex4 )
2
Le gradient s’annule pour :
r
3 1 π
x1 = , x2 = kπ, x3 = k‘ , x4 = 0
2 2
 
12x21 0 0 0
 0 cos(x2 ) 0 0 
 
H(f1 (x1 , x2 , x3 , x4 )) = 
 0 0 2(sin(x3 ) − cos(x3 )) 0


 1 x4 
0 0 0 (e + ex4 )
2
La matrice H est diagonale, donc les valeurs propres de la matrice H sont (1):

λ1 = 12x21 , λ2 = cos(x2 ),

1
λ3 = 2(sin(x3 ) − cos(x3 )), λ4 = (ex4 + ex4 )
2
1
b. f2 : IR2 → IR avec f2 (x, y) = x4 − x2 y + y 2 − 6y + 1
2
 
4x3 − xy
∇f2 (x, y) =  1 2 
− x + 2y − 6
2

2
 Le gradient s’annule pour :
r r
12 48 12 48
(x, y) = (0, 3) ou ( , ) ou (− , )
15 15 15 15

12x2 − y −x
 
H(f2 (x, y)) =
−x 2
Pour le point (0, 3) les r r de H sont λ1 = −3, λ2 = 2. (1)
valeurs propres
12 48 12 48
Pour les points ( , ), (− , ) les valeurs propres de H sont
√ 15 √15 15 15
21 + 141 21 − 141
λ1 = , λ2 = .
5 5

Pour chaque fonction, remplir le tableau récapitulatif des différents points stationnaires avec
leurs classifications.

f1 (Fibonacci)

Itérations a c d b fc fd

1 0.500 1.269 (1) 1.731 (1) 2.500 −0.219 (1) −0.158 (1)

2 (1) 0.500 0.962 (1) 1.269 1.731 0.039 (1) -0.219

3 (1) 0.962 1.269 1.423 (1) 1.731 -0.219 −0.277 (1)

4 (1) 1.269 1.423 1.577 (1) 1.731 -0.277 −0.263 (1)

5 (1) 1.269 1.423 1.433 (1) 1.577 -0.277 −0.279 (1)

optimal 1.423 (1) 1.577 (1)

... Fn > |b − a|/ε =⇒ n = 6 (1)

f2 (Sécante)

Itérations xk−1 xk f20 (xk−1 ) f20 (xk )

1 2.000 1.900 3.000 (1) 2.096 (1)

2 1.900 1.668 (2) 2.096 −1.386 (1)

3 1.668 1.760 (2) -1.386 0.332 (1)

4 1.760 1.743 (2) 0.332 0.044 (1)

optimal 1.740 (2)

3
 f1 (Exercice 2)
q q q q q
3 1 3 1 3 3 1 3 1
x1 = 2 (1) x1 = 2 x1 = 12 x1 = 2 x1 = 2
x2 = (2n)π(1) x2 = (2n)π(1) x2 = (2n)π(1) x2 = (2n)π(1) x2 = (2n + 1)π(1)
point π π π π π
x3 = (4n0 ) (1) x3 = (4n + 1) (1)x3 = (4n + 2) (1)x3 = (4n0 + 3) (1) x3 = (n0 ) (1)
0 0
2 2 2 2 2
x4 = 0(1) x4 = 0 x4 = 0 x4 = 0 x4 = 0

type Point de selle Minimum Point de selle(1) Minimum Point de selle(1)

(1) local(1) local(1)
f2 (Exercice 2)
r r
12 12
x = 0(1) x= (1) x=− (1)
point 15 15
y = 3(1) 48 48
y = (1) y=
15 15

type Point de selle(1) Minimum Minimum

local(1) local(1)

Exercice 3 : 5pts

1) Trouver un minimum local de f1 en utilisant la méthode des gradients conjugués à partir

du point x0 = (0, 0, 0) avec :

f1 : IR3 → IR avec f1 (x, y, z) = (x + y + z)2 + (x − y)2 + (y − z)2 + 2x − 3y + z 2

Remplir le tableau récapitulatif suivant:

Itérations Xk ∇f (Xk ) βk−1 dk αk

0
 
0

2
 -  
−2 0.1857(1)
0 −3(1)  3 (1)
0 0 0

1 0.07183(1) 0.29322(1)
     
−0.3714 0.5143 −0.6579
 0.5571 (1)  0.3428 (1) −0.1273(1)
0 −0.7428 0.7428

2 0.08314(1) 0.1530(1)
   
−0.5643
 
0.1782 −0.2329
 0.5198 (1) 0.1188(1) −0.12939(1)
0.2178 0.1782 −0.1164

3

−0.6
  
0 - - -
 0.5 (1) 0(1)
0.2 0

2) Trouver un minimum local de f2 en utilisant la méthode de Newton à partir du point

4
x0 = (0, 0) avec :

1
f2 : IR2 → IR avec f2 (x, y) = (x + y)2 + 3x − y(1 − y)
2
 
2x + 2y + 3 
2 2

∇f2 (x, y) =  1  et H(f2 (x, y)) =
3y + 2x − 2 3
2
    
 −1 3 3 3
d0 = −H −1 (f2 (x, y)) = −
2 2  1  = −  2 −1  1  (1pts)
2 3 − −1 3 −
2 2
   
−5 −5
d0 =  7  alors X1 = X0 + d0 =  7  (1pts)
2 2