Exercice 2 : (algorithme du gradient à pas constant dans l’optimisation sans contraintes)
On cherche à minimiser une fonction donnée f : Rn → R et on propose l’algorithme suivant dont l’idée est de choisir successivement les points x0, x1, . . . en espérant que cette suite converge vers un minimum local de f. Pour construire xi+1, on part de xi dans la direction opposée au gradient de f qui est la direction dans la quelle la fonction est censée de décroître.
Algorithme 2 : gradient à pas constant
Entrées0 ∈Rn,unnombre(lepas)ρ>0etlatolérancetol>0 pour i = 0,1,... faire
xi+1 = xi − ρ∇f(xi) si ||∇f(xi+1)|| ≤ tol
ou on a perdu l’espoir que l’algorithme aboutisse jamais à quelque chose intéressant
alors
poser xmin = xi+1, fmin = f(xmin) et sortir de la boucle fin
fin
Sorties : xmin, fmin
On verra dans le cours que cet algorithme converge sous certaines hypothèses sur f si ρ est assez petit.
1. Implémentez l’algorithme du gradient à pas constant sous scilab.
2. Testez l’algorithme sur quelques fonctions quadratiques, comme, par exemple,
f ( x 1 , x 2 ) = 2 x 21 − x 1 x 2 + x 2 2 + 1 .
Visualisez le déroulement de l’algorithme en dessinant les lignes de niveau de f et itérations
x0, x1, . . . la-dessus.
3. Testez l’algorithme sur les exos du TP no 2.