UNIVERSITE HASSAN II DE CASABLANCA
FACULTE DES SCIENCES BEN M’SIK
DEPARTEMENT DE MATHEMATIQUES INFORMATIQUE
TP 3 Module Algorithmes d’optimisation
Exercice 1 :
Soit les fonctions suivantes :
a) f (x, y) = x2 − 5xy + y4 − 25x − 8y
b) g(x, y) = (x4 − 3) + y4
c) h (x, y) = x4 − 4y3 + 6 (x2 + y2) − 4 (x + y) .
d) t(x,y)= y2 - cos(x+1)
Pour chacune des fonctions :
1) Chercher les points critiques
2) Utiliser l’algorithme du Gradient à pas fixe puis le gradient à pas optimal pour trouver le minimum local
de la fonction
3) faites une étude de sensibilité sur le point de départ (initialisation) et le pas (points initiaux = [[0, 0], [1,
2], [-1, 3], [5, -5]], alphas = [0.001, 0.01, 0.1, 0.7, 0.9].
4) faites une comparaison numérique des deux méthodes surtout en termes de vitesse de convergence en
nombre d'itérations et temps CPU.
5) Comparer avec les point critiques obtenus analytiquement et tracer les courbes de niveau et l’évolution
du gradient.
Exercice 2:
4 1 1
Soit le système linéaire suivant : A= ( ), b=( ) , On veut résoudre l’équation Ax=b .
1 3 2
1) Vérifiez que A est symétrique définie positive.
2) Implémentez la méthode du gradient conjugué manuellement sur 2 itérations.
3) Comparez avec la solution exacte x=A−1b.
Exercice 3 :
1 0
Considérer les fonctions quadratiques : f(x,y)=2(2x2+y2)−x−y avec x0=( ), g(x,y,z)=
0
1
(x,y,z)=x2+2y2+3z2+2xy−z , avec x0=(1). Pour chacune des fonctions faites :
1
1
1) Trouver la forme quadratique de la fonction : f(x)= 2xTAx−bTx+c. Identifier la matrice A et le vecteur b
et c.
2) Trouver les point critiques de la fonction analytiquement en résolvant ∇f(x,y)=0.
3) En utilisant le x0 proposé, implémenter la méthode du gradient conjugué et utiliser le mode verbose pour
afficher les détails de chaque itération.
4) Comparez les points critiques avec la solution numérique.
5) Combien d'itérations faudrait-il théoriquement pour converger vers la solution exacte pour une fonction
quadratique 2D ?
6) Tracer les courbes de niveau et la trajectoire du gradient.
Exercice 4 :
1 є 0
Soit la fonction quadratique suivante : f(x,y)= 2xTAx où A=( ) et є = 10−6
0 1
1) Trouver les points critiques
2) En prenant le point initial x0=(2,1), et en variant la tolérance et le nombre d’itération trouver le minimum
avec la méthode du gradient à pas optimal et enregistrer la trajectoire.
3) Tracez les courbes de niveau de f et la trajectoire de l'algorithme.
4) Afficher le nombre d'itérations nécessaires pour atteindre une convergence. Observez la forme des
courbes de niveau et la direction des pas de l'algorithme.
5) Refaire la même chose en utilisant le gradient conjugué et comparer sous les mêmes condition (tolérance)
le nombre d’itérations et la trajectoire.
6) Refaites la même chose en prenant є = 0,1.
Exercice 5 :
Soit la fonction f(x,y)=x2+xy+y2−6x−9y
1) Calculer le gradient ∇f(x,y) et trouver les points critiques.
2) Utiliser la méthode de Newton pour trouver le minimum en utilisant différents nombre d’itérations et un
critère d'arrêt sur la norme du gradient ∥∇f∥<ε avec une limite du nombre d’itération.
3) Vérifier que la Hessienne est définie positive au point trouvé.
4) Tracer les courbes de niveau ainsi que l’évolution de f(x,y) à chaque itération
Exercice 6 :
Soit la fonction de Rosenbrock définie comme suit :
f (X) = f (x1, x2) = 100(y − x2)2+ (1 − x)2
1) Calculer le gradient et la matrice Hessienne de la fonction f.
2) Vérifier que x∗ = (1 1)t est un minimum local de f.
3) Calculer les 5 premiers itérés de la méthode de Newton pour minimiser f en commençant par x0 = (−1
−2)t.
4) Calculer la norme de l'erreur ∥x − x∗∥ à chaque itération et déterminer si le taux de convergence est
quadratique.
Exercice 7 :
Soit f(x)= f(x,y)= ex+y +(x − y).2
1) Trouver les points critiques de f
2) Implémenter Newton et BFGS et DFP pour cette fonction.
3) Comparer le nombre d’itérations et les performances en termes CPU.
2
4) Tracer les courbes de niveau et les points générés par les deux méthodes.
5) Comparer la valeur approchée avec les points critiques.
Exercice 8 :*
Pour comparer les méthodes d'optimisation on utilise souvent un ensemble classique de fonctions tests. Ces
fonctions sont choisies pour leurs caractéristiques particulières : convexité, non-linéarité, plateau, ...). Voici
quelques-unes :
Comparer les différentes méthodes de descente en utilisant ces fonctions, en fonction de .
a) Nombre d’itérations
b) Temps de calcul (CPU time)
c) Précision de la solution
d) Sensibilité au point du départ.