uiz-fpo : smi-s6 Nom et Prénom : ....................................
Modélisation CNE : ................................
Examen SP 2022 Salle : ..........
————————————————————————————————————-
Exercice 1:
Soit X ∈ Rn est un ensemble convexe et si la fonction f : X −→ R est strictement
convexe sur X. On pose qu’il existe un point minimum local x∗ .
1. Démontrer que x∗ est un minimum global.
Corrigé : La preuve se fait par contradiction en supposant qu’il existe un point
x̂ ∈ X tel que f (x̂) < f (x̄). Puisque f est convexe, f (θx̂ + (1 − θ)x̄) ≤ θf (x̂) +
(1 − θ)f (x̄) < θf (x̄) + (1 − θ)f (x̄) = f (x̄) pour tout θ ∈ (0, 1]. Or pour θ > 0
suffisamment petit, x(θ) = θx̂ + (1 − θ)x̄ ∈ B (x̄) ∩ X. Ainsi f (x(θ)) < f (x̄) où
x(θ) ∈ B (x̄) ∩ X, contredisant que x̄ est un minimum local de f sur X.
2. Démontrer que le minimum est unique.
Corrigé : Soit donc x∗ ∈ K tel que f (x∗ ) ≤ f (x), ∀x ∈ K. Supposons qu’il existe
y ∗ 6= x∗ tel que f (y ∗ ) ≤ f (x), ∀x ∈ K. Formons pour λ ∈ ] 0, 1 [ le vecteur
u = λy ∗ + (1 − λ)x∗ . D’après la stricte convexité de f et puisque nécessairement
f (y ∗ ) = f (x∗ ) on a f (u) < λf (y ∗ ) + (1 − λ)f (x∗ ) = f (x∗ ), ce qui contredit le
fait que x∗ soit un minimum. On a donc x∗ = y ∗ .
Exercice 2:
x41 α
Soit (P) le problème de minimisation suivant : min f (x1 , x2 ) = 4
+ x22 0
et X =
0
(α 6= 0 quelconque) le point initial.
1. Calculer le gradient de la fonction f
Corrigé : ∇f (x1 , x2 ) = (x31 , 2x2 )t
2. Calculer le Hessienne dela fonctionf
2
3x 1 0
Corrigé : ∇2 f (x1 , x2 ) =
0 2
3. Appliquer la méthode de Newton en partant de X 0 pour calculer X 1 pour
résoudre (P).
2
Corrigé : X 1 = ( α, 0)T
3
2
4. Démontrer que X k = (( )k α, 0)T .
3
2 2 2 T
X = (( ) α, 0)
3
5. En déduire que en partant du point X 0 , la méthode de Newton converge.
2 k→∞
Corrigé : X k = (( )k α, 0)T −−−→ 0
3
6. Donner l’itération de la méthode de Newton avec le pas optimale.
1
Corrigé : X 1 (t) = X 0 − t( α, 0)T
3
7. Calculer le pas optimale en partant de X 0 .
t
(α − α)4
Corrigé : g(t) = f (X(t)) = 3 ≥ 0 donc g(t) atteint son minimum en
4
t=3
8. En déduire X 1 par la méthode de Newton avec le pas optimale en partant de
X 0.
Corrigé : X 1 = X(3) = (0, 0)T minimum atteint.
1
Exercice 3: Modèle statistique multiple
Considérer le problème d’estimer les paramètres de la régression
Y = α1 X1 + α2 X2 + α3
qui approche le mieux les n triples (X1i , X2i , Y i ).
1. Quelle méthode que on peut utiliser ?
Corrigé : La méthode des moindres carrés.
2. Formuler ce problème comme un problème d’optimisation.
n
Corrigé : F (α1 , α2 , α3 ) = min (yi − (α1 x1i + α2 x2i + α3 x3i ))2 .
P
i=1
3. Écrire les conditions d’optimalité pour ce problème.
∂F (α)
Corrigé : = 0, i = 1, 2, 3.
∂αi
4. Donner l’itération de l’algorithme de gradient pour ce problème.
Corrigé : On pose α = (α1 , α2 , α3 )t donc αk+1 = αk − θk ∇F (αk )
Exercice 4: : Programmation sous Python
1. Écrire une fonction [Link] qui permet d’optimiser une fonction
f : R −→ R par la méthode de Newton.
Corrigé :
import numpy as np
# f : la fonction objective
# grad f : le gradient de f
# hes f : le Hessienne de f
def Newton1(X,eps=0.0001) :
normg = grad f(X)
k = 1 # itération
while [Link](normg) > eps :
..... H = [Link](hes f(X))
..... M = [Link](H)
..... V = [Link](grad f(X))
..... X = X - [Link](M,V)
..... print(’iteration :’, k)
..... print(’X = ’, X)
..... print(’f(X) =’, f(X))
..... normg = grad f(X)
..... k += 1
return X
2. Écrire un programme qui résoudre (P) de l’exercice 2 par la fonction [Link]
Corrigé :
f = lambda X : X[1]ˆ4/4 + X[2]ˆ2
grad f lambda X : [X[1]ˆ3 , 2*X[2]]
hes f lambda X : [[3*X[1]ˆ2 0] , [0 2]]
X0 = [1, 1]
X = Newton1(X0)
print(’Solution optimal X*= ’, X)
print(’Valeur optimal f*= ’, f(X))
