École Supérieure Privée d’Ingénierie et de Technologies
TP optimisation sans contrainte en di-
mension quelconque
Classes : 4DS Semestre : 1 Année universitaire: 2019/2020
L’objectif de ce TP est d’utiliser différentes méthodes d’optimisation afin d’approcher la
solution du problème:
(P) min J(X),
X∈Rn
où J : Rn → R fonction objective continue definie par:
1
∀X ∈ Rn , J(X) = < AX, X > − < b, X >,
2
où b ∈ Rn et A ∈ Mn (R) est une matrice symétrique définie positive.
2 −1 0 . . . ... 0
−1 2 −1 . . . ... .
0 −1 2 −1 . . ... .
.
0 −1 2 −1 . ... . 1
.
. 0 −1 2 −1 ... .
1
A= . . . . . . ... . , et b =
. .
. . . . . . ... . .
. . . . . . ... . 1
. . . . . . ... .
. . . . . −1 2 −1
0 . −. . . 0 −1 2
Remarque 1 Il est important d’exploiter le format creux de la matrice A afin de diminuer
les temps de calcul
1. Programmer en python la fonction J et la représenter dans le cas n = 2 sur le pavé
[−20, 20] × [−20, 20].
2. Programmer en python le gradient de J.
1
1 Partie 1: Algorithme de gradient à pas fixe
Le schéma général de l’algorithme de gradient à pas fixe est donné par la suite (Xk )k∈N
d’élément de Rn telle que:
X0 ∈ Rn quelconque
Xk+1 = Xk − ρ∇J(Xk ) ∀k ∈ N
où ρ est un réel positif.
1. Ecrire une fonction python prenant en argument ρ > 0 un pas fixe et X0 ∈ Rn , un
vecteur d’initialisation, et ε > 0 la précision afin de mettre en oeuvre l’algorithme du
gradient à pas fixe.
2. Tester l’algorithme sur la fonction J pour différentes valeurs de n, n = 2, 10, 15, 20, 30, 40, 50
pour un ρ = 0.5, ρ = 1 et ρ = 2.
3. Tracer la courbe représentant le nombre d’itération en fonction de la valeur de n.
4. Tester l’algorithme du gradient à pas fixe on changant le critère d’arrêt. Ces critère
sont:
(a) ||∇J(Xk )|| ≤ ε ⇒ Xk solution. (Condition nécessaire d’optimalité du premier
ordre).
(b) En pratique, le test d’optimalité n’est pas toujours satisfait et on devra faire
appel à d’autres critères.
• ||Xk+1 − Xk || ≤ ε||Xk || stagnation de la solution.
• |J(Xk+1 ) − J(Xk )| ≤ ε|J(Xk )| stagnation de la fonction.
• Nombre d’itération dépassont un seuil fixe à l’avance k < IterM ax.
Analyser les résultats et commenter.
2 Partie 2: Algorithme de gradient à pas optimal
Le schéma général de l’algorithme de gradient à pas optimal est donné par la suite (Xk )k∈N
d’élément de R3 telle que:
X0 ∈ Rn quelconque
Xk+1 = Xk − ρk ∇J(Xk ) ∀k ∈ N
où ρk est un réel positif.
2
1. Soit X ∈ Rn et d ∈ Rn , écrire une fonction python permettant de minimiser la
fonction ϕ(t) = J(X + td).
2. Programmer l’algorithme de gradient à pas optimal pour différentes valeurs de n,
n = 2, 10, 15, 20, 30, 40, 50, 100.
3. Tracer la courbe représentant le nombre d’itération en fonction de la valeur de n.
4. Analyser les résultats et commenter.
3 Partie 3: Méthode du gradient conjugué
Le schéma général de l’algorithme du gradient conjugué est donné par la suite (Xk )k∈N
d’élément de Rn telle que:
X0 ∈ Rn quelconque, r0 = AX0 − b etd0 = −r0
< rk , dk >
Xk+1 = Xk + ρk dk , ρk = −
< Adk , dk >
rk+1 = AXk+1 − b
||rk+1 ||2
dk+1 = −rk+1 + βk dk , βk :=
||rk ||2
1. Faire une étude bibliographique sur l’algorithme du gradient conjugué.
2. Programmer l’algorithme du gradient conjugué pour différentes valeurs de n, n =
2, 10, 15, 20, 30, 40, 50, 100 pour un ρ = 0.5.
3. Tracer la courbe représentant le nombre d’itération en fonction de la valeur de n.
4. Analyser les résultats et commenter.
Comparer à l’aide d’un tableau ou d’une figure la rapidité de convergence de chacune des
deux algorithmes, ainsi le temps de calcul par python suivant les différentes valeurs prises
par n.
4 Partie 4: Régrassion linéaire
Dans cette partie la fonction J est définie par:
N
1X
J(a, b) = (yi − (axi + b))2
2 i=1
Avec (xi , yi ), i = 1, ..N un nuage de point donner par le fichier univariatel inearr egressiond [Link].
Appliquer les algorithmes de gradient à pas fixe , pas optimal et du gradient conjugué pour
déterminer le minimum de J.
