BE d’optimisation
Exercice 1 (1) Ecrire un programme Scilab de l’algorithme des gradients conjugués. On
prendra comme entrées une dimension n, une matrice Q symétrique définie positive de
taille n × n, un vecteur b ∈ Rn , un point initial x1 ∈ Rn et une tolérance ε > 0 (pour
définir le critère d’arrêt).
(2) Tester le programme avec les éléments suivants :
(a) n = 4, ε = 10−4 ,
1 1 1 1 −4 5
1 2 2 2 −7 5
Q=
1 2 3 3
,
−9 ,
b=
5 .
x1 =
1 2 3 4 −10 5
(b) n = 4, ε = 10−3 , Q = [Qjk ] avec Qjk = 1/(j + k − 1), b = (1, 2, −1, −2)> et
x1 = (1, 2, 3, 4)> .
Exercice 2 On cherche à minimiser sur R3 la fonction f définie par
f (x, y, z) = x2 + y 4 + z 2 + ch (x + y + z).
(1) Vérifier que f est strictement convexe, de classe C 2 (R3 ) et 1-coercive.
(2) Ecrire un simulateur pour la fonction f , c’est-à-dire, un sous-programme prenant en entrée
un vecteur (x, y, z) et donnant en sortie f (x, y, z) et ∇f (x, y, z).
(3) Ecrire un programme Scilab de l’algorithme de Fletcher-Lemaréchal utilisant le simulateur
de la question (2). On prendra comme entrée un pas initial α0 > 0, deux paramètres β1 , β2
tels que 0 < β1 < β2 < 1, un parmètre λ > 1, un vecteur (x, y, z) (l’itéré courant) et une
direction de descente d = (dx , dy , dz ).
(4) Ecrire un programme Scilab de l’algorithme de plus forte pente avec recherche linéaire de
Wolfe, utilisant le simulateur de la question (2) et l’algorithme de Fletcher-Lemaréchal.
On prendra comme entrée un itéré initial x0 et une tolérance ε > 0.
(5) Minimiser la fonction f , en utilisant par exemple les valeurs suivantes :
(a) α0 = 0, 1; 1; 10.
(b) β1 = 0, 1; 0, 5.
(c) β2 = 0, 1(β1 − 1).
1
Rappelons les conditions de Wolfe : si xk , dk , αk sont respectivement l’itéré courant, la direction
de recherche et le pas, alors xk+1 := xk + αk dk satisfait la première condition de Wolfe si
(W1) f (xk+1 ) ≤ f (xk ) + αk β1 h∇f (xk ), dk i ;
et la deuxième condition de Wolfe si
(W2) h∇f (xk+1 ), dk i ≥ β2 h∇f (xk ), dk i.
L’algorithme de Fletcher-Lemaréchal peut s’écrire de la manière suivante :
Entrées :
f : Rn → R, fonction de classe C 1 (Rn ) ;
∇f : Rn → Rn ;
x ∈ Rn et d ∈ Rn \ {0} tels que h∇f (x), di < 0 ;
α0 > 0, pas initial ;
β1 , β2 tels que 0 < β1 < β2 < 0 ;
λ > 1.
Sortie : ᾱ, un pas tel que x + ᾱd satisfasse (W1) et (W2).
Initialisation : k = 0, αl = 0, αu = ∞.
Itérations :
(1) Si αk est tel que (W1) et (W2) sont satisfaites, alors ᾱ ← αk ; FIN.
(2) Si αk ne satisfait pas (W1) (le pas est trop long), alors
αu ← αk ,
αl + αu
αk+1 = .
2
(3) Si αk satisfait (W1) mais pas (W2) (le pas est trop court), alors
αl ← αk ,
( α +α
l u
si αu < ∞,
αk+1 = 2
λαk si αu = ∞.
(4) k ← k + 1, puis retourner en (1).
L’algorithme de la plus forte pente peut s’écrire de la manière suivante :
Entrées :
f : Rn → R, fonction de classe C 1 (Rn ) ;
∇f : Rn → Rn ;
x0 ∈ Rn , point initial ;
ε > 0, paramètre proche de zéro.
Sortie : x̂, approximation de x̄, minimiseur de f sur Rn ;
Initialisation : k = 0.
Itérations :
(1) Si k∇f (xk )k ≤ ε, alors x̂ = xk ; FIN.
(2) Si k∇f (xk )k > ε, alors
(i) Calculer dk = −∇f (xk ) ;
(ii) Calculer αk à l’aide de l’algorithme de Fletcher-Lemaréchal ;
(iii) Calculer xk+1 = xk + αk dk ;
(iv) k ← k + 1, puis retourner en (1).
2
Les scripts ci-dessous sont donnés à titre indicatif. Leur efficacité numérique pourrait être
améliorée de manière non négligeable en évitant certains tests.
Exercice 1 :
1) Gradients conjugués :
function [x] = gradConj(Q,b,x1,epsilon)
// initialisation
k=1;
betak=0;
xk=x1;
yk=Q*xk+b;
// itérations
while(norm(yk)>epsilon)
if(k==1)
betak = 0;
dk=-yk;
else
betak = norm(yk)^2/norm(ykmoins1)^2;
dk=-yk+betak*dkmoins1
end;
alphak = - (dk’*yk)/(dk’*(Q*dk));
xkplus1 = xk + alphak*dk;
k=k+1;
ykmoins1=yk;
dkmoins1=dk;
xk=xkplus1;
yk=Q*xk+b;
end;
x= xk;
// affichage
disp("nombre iterations");
disp(k-1);
disp("minimiseur");
disp(x);
disp("valeur du minimum");
disp(0.5*x’*Q*x + b’*x);
endfunction;
3
2) Exemple de séquence d’appel :
epsilon = 0.0001;
Q= [1 1 1 1
1 2 2 2
1 2 3 3
1 2 3 4];
b= [-4 -7 -9 -10]’;
x1 =[5 5 5 5]’;
x = gradConj(Q,b,x1,epsilon);
Exercice 2 :
1) Simulateur :
function [f, gradf] = fgradf(x)
//calcul de f(x)
f= x(1)^2+x(2)^4+ x(3)^2 + cosh(x(1)+x(2)+x(3));
//Calcul de gradiant f(x)
gradf(1)=2*x(1)+sinh(x(1)+x(2)+x(3));
gradf(2)=4*x(2)^3 +sinh(x(1)+x(2)+x(3));
gradf(3)=2*x(3)+sinh(x(1)+x(2)+x(3));
endfunction
4
2) Recherche linéaire :
function alpha = rlinFL(alpha0, beta1, beta2, lambda, x, d)
alphag=0
alphad = %inf;
alpha = alpha0;
[fx , gradfx] = fgradf(x);
xd = x+ alpha*d;
[fxd, gradfxd] = fgradf(xd);
w1 = (fxd<= fx+ alpha *beta1*(gradfx’*d));
w2 = (gradfxd’*d>=beta2*(gradfx’*d));
while(~w1 | ~w2)
if(~w1) //le pas est trop long
alphad = alpha;
alpha = (alphag+alphad)/2;
else //le pas est trop petit
alphag = alpha;
if(~isinf(alphad))
alpha = (alphag+alphad)/2;
else
alpha = lambda*alpha
end;
end;
xd = x+ alpha*d;
[fxd, gradfxd] = fgradf(xd);
w1 = (fxd<= fx+ alpha *beta1*(gradfx’*d));
w2 = (gradfxd’*d>=beta2*(gradfx’*d));
end;
endfunction
5
3) Plus profonde descente :
function [x] = algopfp(x0,epsilon)
//parametres a utiliser dans la l’algo de Fletcher-Lemaréchal
alpha0= 10;
beta1 = 0.2;
beta2 = 0.7;
lambda = 4;
// initialisation
k=0;
x=x0;
[fx, gradfx] = fgradf(x);
suiteNormegrad = [norm(gradfx)];
suitef =[fx];
// itérations
while(norm(gradfx) >epsilon)
d = -gradfx;
alpha = rlinFL(alpha0, beta1, beta2, lambda, x, d);
x = x + alpha*d;
[fx, gradfx] = fgradf(x);
suiteNormegrad = [suiteNormegrad norm(gradfx)];
suitef =[suitef fx];
k=k+1;
end;
// affichage
disp("nombre iteration")
disp(k);
disp("minimiseur");
disp(x);
disp("optimum");
disp(fx);
xbasc();
plot((0:k),log(suiteNormegrad),’+’);
endfunction