Sujet Et Corrigé Optimisation Sans Contraintes

Université Abou Bekr Belkaid Tlemcen
Département de mathématiques
L3 mathématiques 2021/2022
Solution de l’examen final

Optimisation sans contraintes
Exercice 1 (6 points):
On définit la fonction J : Rn → R par
1
J(x) := ⟨Ax, x⟩ − ⟨b, x⟩,
2
où A ∈ Mn (R) est une matrice symétrique définie positive et b ∈ Rn . On
considère la méthode du gradient à pas optimal pour la minimisation de J.
- Donner l’expression de xk+1 obtenu par cette méthode.
- Montrer que le pas θk s’écrit dans ce cas:
||dk ||2
θk = .
⟨Adk , dk ⟩
- Rappelons que le problème de minimisation de J admet une unique solution
x̄ ∈ Rn caractérisée comme étant l’unique solution de l’équation d’Euler
∇J(x) = 0. Montrer que
⟨A−1 dk , dk ⟩ = 2(J(xk ) − J(x̄)).
Solution:
- L’algorithme de la méthode du gradient à pas optimal s’écrit:


 xk+1 = xk + θk dk
dk = −Axk + b


θk est tel que J(xk + θk dk ) = minθ∈R J(xk + θdk )
(1 point).
- Dans l’algorithme du gradient à pas optimal, deux directions successives
sont orthogonales:
⟨dk+1 , dk ⟩ = 0.
En utilisant la formule de xk+1 et de dk on obtient:
0 = ⟨−Axk+1 + b, dk ⟩
= ⟨−A(xk + θk dk ) + b, dk ⟩
= ⟨−Axk + b − θk Adk , dk ⟩
= ⟨dk − θk Adk , dk ⟩
= ||dk ||2 − θk ⟨Adk , dk ⟩
on suppose que dk ̸= 0 et donc ⟨Adk , dk ⟩ =
̸ 0 (car A est définie positive).
Ainsi, θk s’exprime
||dk ||2
θk = .
⟨Adk , dk ⟩
(2 points)
- La solution du problème de minimisation de J est x̄ = A−1 b. Un simple
calcul montre que
⟨A−1 dk , dk ⟩ = ⟨A−1 (Axk − b), Axk − b⟩

= ⟨xk − A−1 b, Axk − b⟩
−1 −1
= ⟨Ax
k , xk ⟩ − ⟨b, xk ⟩ − ⟨A b, Axk ⟩ +⟨A b, b⟩
= 2 12 ⟨Axk , xk ⟩ − ⟨b, xk ⟩ + 21 ⟨A−1 b, b⟩
= 2(J(xk ) − J(x̄))
car
J(x̄) = 21 ⟨Ax̄, x̄⟩ − ⟨b, x̄⟩
= 12 ⟨b, x̄⟩ − ⟨b, x̄⟩
= − 21 ⟨b, x̄⟩
= − 21 ⟨b, A−1 b⟩.
(3 points)
On considère le problème minR2 f (x) où f (x) = 21 ⟨Ax, x⟩ avec
!
2 −1
A=
−1 2
- Donner la solution de ce problème (qu’on note x̄).

Soit α > 0 et soit la suite (xk )k∈N définie par xk+1 = xk − αAxk .
- Pour quelles valeurs de α la suite (xk ) converge vers x̄ pour tout x0 ∈ R2 ?
- Quel est le pas optimal ᾱ?
Solution :
- Les valeurs propres de la matrice A sont λ1 = 1 et λ2 = 3. La forme
quadratique f est strictement convexe et coercive, elle admet alors un unique
minimum qui est solution de
∇f (x) = 0 ⇔ Ax = 0.
Comme A est inversible, on obtient x̄ = (0, 0)T . (2 points)

- Il s’agit de la suite engendrée par la méthode du gradient à pas fixe, elle
2
converge pour toute valeur de α ∈]0, 23 [. (1.5 point)
- Le pas optimal de cette méthode est donné par:
2 1
ᾱ = = (1.5 point)
λ1 + λ2 2
Déterminer et préciser la nature des points critiques des fonctions suivantes:
f (x, y) = x3 + y 3 − 3axy, a ∈ R
g(x, y) = x2 − cos(y)
h(x, y) = y 2 + xy ln(x).
Solution:
1) le gradient le hessien de f sont donnés par:
! !
3x2 − 3ay 2 6x −3a
∇f (x, y) := ∇ f (x, y) =
3y 2 − 3ax −3a 6y
Soit a ̸= 0, la fonction f admet deux points critiques p0 = (0, 0) et pa = (a, a).

La matrice hessienne de f au point p0 admet deux valeurs propres de signe
différent. Le point p0 est donc un point selle. La hessienne calculée au point
pa admet deux valeurs propres λ1 = 3a et λ2 = 9a. On déduit que si a > 0,
pa est un minimum et si a < 0, pa est un maximum (3 points).
2) le gradient et le hessien de g sont donnés par:
! !
2x 2 2 0
∇g(x, y) := ∇ g(x, y) =
sin(y) 0 cos(y)
Les points critiques de g sont de la forme pk = (0, kπ), k ∈ Z. Le calcul de

∇2 g au point pk donne
!
2 2 0
∇ g(pk ) =
0 (−1)k
donc pk est un minimum si k est pair et c’est un point selle si k est impair
(3 points).
3) la fonction h est définie pour tout x > 0 et elle est de classe C 2 sur son
domaine de définition. le gradient le hessien de h sont donnés par:
y
! !
y ln(x) + y 2 ln(x) + 1
∇h(x, y) := ∇ h(x, y) = x
2y + x ln(x) ln(x) + 1 2
Il existe deux points critiques (1, 0) et ( 1e , 2e

1
). Le premier est un point selle
et le deuxième est un minimum (3 points).

Sujet Et Corrigé Optimisation Sans Contraintes

Transféré par

Droits d'auteur :

Formats disponibles

Sujet Et Corrigé Optimisation Sans Contraintes

Transféré par

Informations du document

Titre original

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

Sujet Et Corrigé Optimisation Sans Contraintes

Transféré par

Droits d'auteur :

Formats disponibles

Université Abou Bekr Belkaid Tlemcen

Solution de l’examen final

⟨A−1 dk , dk ⟩ = ⟨A−1 (Axk − b), Axk − b⟩

- Donner la solution de ce problème (qu’on note x̄).

Comme A est inversible, on obtient x̄ = (0, 0)T . (2 points)

Soit a ̸= 0, la fonction f admet deux points critiques p0 = (0, 0) et pa = (a, a).

Les points critiques de g sont de la forme pk = (0, kπ), k ∈ Z. Le calcul de

Il existe deux points critiques (1, 0) et ( 1e , 2e

Vous aimerez peut-être aussi