Optimisation TP2 - Optimisation sans contraintes
TRAVAUX PRATIQUES : OPTIMISATION SANS CONTRAINTES
Les conditions suivantes sont equivalentes :
A est semi-definie positive,
Toutes les valeurs propres de A sont positives,
P
le polynome caracteristique de A, pA () = nk=0 (1)k ak k , avec k, ak > 0,
Pour tout k = 1, 2, . . . , n, tous les mineurs principaux dordre k de A sont positifs.
(seulement lorsque n = 2), tr(A) 0 et det(A) 0.
pe
Pr
au
x
Faits : Soit A Mn (R) une matrice symetrique ; A = (ai,j )i,j=1,...,n .
Les conditions suivantes sont equivalentes :
A est definie positive,
Toutes les valeurs propres de A sont strictement
Pn positives,
le polynome caracteristique de A, pA () = k=0 (1)k ak k , avec k, ak > 0,
det Ak > 0, pour tout k = 1, 2, . . . , n, o`
u Ak = (ai,j )i,j=1,...,k .
(seulement lorsque n = 2), tr(A) > 0 et det(A) > 0.
Ph
ilip
Exercice 1
Soient f, g les fonctions definies sur R2 par :
f (x, y) = x3 + y 3 9xy + 27
g(x, y) = x4 + y 4 (x + y)2
n-
1 - a ) - Determiner les extremas locaux et globaux de f sur R2 .
b ) - Determiner les extremas locaux et globaux de g sur R2 .
Je
a
2 ) Retrouvez les minima de f et g sous Matlab en utilisant la fonction fminunc. En guise
dexemple, pour la fonction f , le calcul de f ainsi que de son gradient sont fournis `a Matlab
dans le fichier F1.m :
gh
t:
function [f,gradf]=F1(x)
f=x(1)^3+x(2)^3-9*x(1)*x(2)+27;
if nargout > 1
gradf(1)=3*x(1)^2-9*x(2);
gradf(2)=3*x(2)^2-9*x(1);
end
yri
On definira les options suivantes pour lalgorithme de minimisation :
options=optimset(LargeScale,on,GradObj,on);
Co
p
On utilisera les commandes suivantes, la signification des param`etres employes se trouve dans
laide sur la fonction fminunc :
x0=[1,1];
[x,fval,exitflag,output,grad,hessian]=fminunc(@F1,x0,options)
On essaiera plusieurs points initiaux, loption de sortie output permet de voir linfluence de ce
choix.
Optimisation TP2 - Optimisation sans contraintes
Exercice 2
f est la fonction definie sur R3 par :
f (x1 , x2 , x3 ) = x21 + x22 + x23 x1 x2 x2 x3 + 3x1 x2 + 2x3
pe
Pr
au
x
1) Justifier de lexistence dun extremum global que lon caracterisera `a laide dun syst`eme
dequations lineaires.
2) Determiner les extrema globaux de f sous matlab sans utiliser la toolbox doptimisation.
3) Retrouver ce resultat en appliquant la fonction quadprog de la toolbox doptimisation. Il
faut alors ecrire f sous la forme :
1
f (x) = xt H x + b x
2
Exercice 3
Soit t R ; on consid`ere la fonction quadratique definie sur R2 :
Ph
ilip
t
ft (x, y) = (x2 + y 2 ) + xy + x y
2
[X,Y]=meshgrid([-10:0.5:10]);
graphf0=X.*Y+X-Y;
surf(X,Y,graphf0)
n-
1) Determiner tous les extrema de (x, y) g(x, y) = exp(ft (x, y)) ; on discutera en fonction
du param`etre t.
2) On se restreint `a t = 0, 1 et 2. Tracer la surface representative de f0 , f1 , f2 sur le
carre [10, 10] [10, 10]. Par exemple le trace pour f0 sobtient par :
Co
p
yri
gh
t:
Je
a
3) Que donne la fonction fminunc de Matlab appliquee `a f0 ? On lui demandera de nous fournir
le gradient et la matrice hessienne.
Optimisation TP2 - Optimisation sans contraintes
Correction
Exercice 1
au
x
1 - a) Le gradient et la matrice hessienne de f valent :
2
3x 9y
6x 9
2
f (x, y) =
,
f=
9x + 3y 2
9 6y
pe
Pr
Les points critiques de f sont les points O(0, 0) et A(3, 3). En O, la matrice hessienne de f nest
pas semi-definie positive (le determinant est negatif et la trace est nulle). Donc lorigine O nest
pas un minimum pour f .
En A, la matrice hessienne de f est definie positive (le determinant et la trace sont strictement
positifs). Le point critique A de f est donc lunique minimum local de f sur R2 .
Il ny a pas dextremum global puisque limx+ f (x, 0) = + et limx f (x, 0) =
1 - b) Le gradient et la matrice hessienne de g valent :
3
4x 2x 2y
12x2 2
2
2
g(x, y) =
,
g(x, y) =
4y 3 2x 2y
2
12y 2 2
n-
Ph
ilip
Les points critiques de g sont les points O(0, 0), A(1, 1) et B(1, 1). La matrice Hessienne de g
est definie positive en A et B (determinant et trace > 0). Ainsi A et B sont des minima locaux.
La matrice Hessienne est semi-definie negative en 0 (trace < 0 et determinant nul). Cependant
O nest pas un extremum local comme on peut sen apercevoir en comparant g(0, 0) avec g(x, x)
et g(x, x) lorsque x est dans un voisinage de 0.
g est coercive et admet donc un minimum global et aucun maximum global. Les points A et B
sont les deux minima globaux de g (g(A) = g(B)).
Exercice 2
Je
a
1) La matrice hessienne H de f est :
2 1 0
H = 1 2 1
0 1 2
gh
t:
Elle est definie positive (det H1 = 2, det H2 = 3, det H3 = 4) et la fonction f est donc strictement
convexe et admet un unique minimum global u solution du syst`eme lineaire H.u = b o`
u
t b = (3, 1, 2).
2) Il suffit de resoudre ce syst`eme sous matlab :
yri
H=[2 -1 0;-1 2 -1;0 -1 2]
b=[3;-1;2]
u=inv(H)*(-b)
fmin=1/2*u*H*u+b*u
Co
p
Le minimum se trouve en u = (2.2500, 1.5000, 1.7500) en lequel la fonction vaut 4.3750.
3) La fonction quadprog donne ce minimum en 1 iteration.
options=optimset(LargeScale,off);
H=[2 -1 0;-1 2 -1;0 -1 2];
b=[3 -1 2];
[x,fval,exitflag,output]=quadprog(H,b,[],[],[],[],[],[],x0,options)
% les 2 premiers champs d
efinissent f(x)=1/2*x*H*x+b*x
% les suivants sont analogues `
a linprog
Optimisation TP2 - Optimisation sans contraintes
Exercice 3
au
x
1) Puisque la fonction exp est strictement croissante tout extremum de g(x, y) est extremum de
ft et reciproquement. La matrice Hessienne de ft est :
t 1
Ht =
1 t
pe
Pr
elle a pour determinant t2 1 et pour trace 2t. Ainsi :
pour t > 1 elle est definie positive: ft a pour unique minimum ((1+t)/(1t2 ), (1+t)/(1t2 )),
pour t = 1 elle est semi-definie positive, et ft na aucun extremum,
pour 1 < t < 1 elle est non semi-definie (negative ou positive) et ft na pas dextremum
pour t = 1 elle est semi-definie negative, ft a une infinite de maxima sur la droite y = x 1
pour t < 1 elle est definie negative : ft a un unique maximum ((1+t)/(1t2 ), (1+t)/(1t2 )).
Ph
ilip
2) Traces des surfaces representatives :
Figure 3: f2
Je
a
3) On tape dans un fichier F0.m :
n-
Figure 2: f1
Figure 1: f0
t:
function [f,gradf]=F0(x)
f=x(1)*x(2)+x(1)-x(2);
if nargout >1
gradf(1)=x(2)+1;
gradf(2)=x(2)-1;
end
gh
puis :
yri
options=optimset(LargeScale,on,GradObj,on);
x0=[0,0];
[x,fval,exitflag,output,grad,hessian]=fminunc(@F0,x0,options)
Co
p
fminunc retourne pour resultat :
x =
-10.0073
3.7297
en lequel le vecteur gradient est non nul. Loption exitflag est strictement positive, elle vaut
2 (matlab pense avoir trouve une solution optimale). Le resultat est pourtant evidemment
aberrant.
