Part I
Exercices
Exercise 1 Soit A l’ensemble des u = (x; y) 2 R2 tel que :
8
>
> 3 x+2y 1;
>
>
>
>
>
> 2 x+3y 0;
>
<
5x+2y 7;
>
>
>
>
>
> 7 x 4y 2;
>
>
>
: 2 x+9y 1:
Calculer puis dessiner les cônes contingent et normal à A au point (1; 1) :
Exercise 2 Répondre par vrai ou faux.
1. L’application x 7 ! kxk1 est convexe sur R2 :
2. L’application x 7 ! kxk1 est strictement convexe sur R2 :
3. L’application f : R2 ! R dé…nie par f (x; y) = x2 2xy + 3y 2 + y admet un unique minimum.
4. Soit A 2 Mn;m (R) et b 2 Rn : L’application g : Rm ! R dé…nie par g (x) = kAx bk2 admet
un unique minimum.
Exercise 3 Soit f 2 C 1 (Rn ; R) : On suppose qu’il existe > 0 tel que:
hrf (x) rf (y) ; x yi jx yj2 ; 8 (x; y) 2 Rn Rn :
1. Montrer que f est strictement convexe.
2. Montrer que f est coercive.
3. Que peut-on en déduire ?
Exercise 4 On considère la fonction f : R2 ! R dé…nie par
f (x; y) = 2x2 + y 2 xy 3x y + 4:
1. Montrer que f admet un minimum global unique u = (x; y) 2 R2 à calculer.
1
2. En partant du point u0 = (0; 0) ; calculer le premier itéré u1 donné par l’algorithme du gradient
à pas optimal.
Exercise 5 On considère le problème d’optimisation avec contraintes :
8
>
> x2 + y 2 2;
>
>
>
>
< xy 1
minimiser f (x; y) = ln (x) y 4 + 2xy 4x sujet à :
>
> x 1;
>
>
>
> 1
: y :
2
L’hypothèse de quali…cation des contraintes est-elle véri…ée en (1; 1) ? A-t-on un optimum local en
(1; 1) ?
Part II
Exercices similaires
Exercise 6 On considère l’ensemble X des points (x1 ; x2 ) 2 R2 véri…ants :
8
>
> x1 + x2 8;
>
>
>
>
>
> 2 x1 + 3 x2 8;
>
<
6 x1 5 x2 30;
>
>
>
>
>
> 4 x1 + 5 x2 1=2;
>
>
>
: x1 ; x2 0:
1. Déterminer le cône normal et le cône tangent à X en x = (7=4; 3=2) :
2. x est-elle une solution optimale de f (x1 ; x2 ) = 4x21 + 16x22 16x1 x2 sur X ?
Exercise 7 On considère l’ensemble X des points (x1 ; x2 ) 2 R2 véri…ants :
8
>
> 3 x1 2 x2 6;
>
>
>
>
>
> x 2 x2 4;
>
< 1
3 x1 + 2 x2 12;
>
>
>
>
>
> x1 6;
>
>
>
: x ;x
1 2 0:
2
1. Déterminer le cône normal et le cône tangent à X en x = (3; 3=2) :
2. Dessiner l’ensemble X; le cône normal et le cône tangent à X en x = (3; 3=2) :
3. x peut elle être une solution optimale de f (x1 ; x2 ) = x21 + 3x22 x1 x2 sur X ?
Exercise 8 On considère l’ensemble X des points (x1 ; x2 ) 2 R2 véri…ants :
8
>
> x1 + 2 x2 10;
>
>
>
>
>
> 4x 3 x2 0;
>
< 1
2 x1 x2 4;
>
>
>
>
>
> x1 + x2 4;
>
>
>
: x1 ; x2 0:
1. Déterminer le cône normal et le cône tangent à X en x = (8=3; 4=3) :
2. x peut elle être une solution optimale de f (x1 ; x2 ) = 4x21 + 9x22 sur X ?
3. x = (3=2; 3) peut elle être une solution optimale de f sur X ?
Exercise 9 On considère le problème d’optimisation avec contraintes :
8p
>
> 4 + 3x + sin y2 2;
>
<
minimiser f (x; y) = 3x 2y + ex sujet à :
>
>
>
: log (1 + x) y:
L’hypothèse de quali…cation des contraintes est-elle véri…ée en (0; 0) ? A-t-on un optimum local en
(0; 0) ?
Exercise 10 On considère le problème d’optimisation sans contraintes :
minimiser f (x1 ; x2 ) = x21 2x1 x1 x2 x22 :
1. Montrez que ce problème admet une solution et une seule.
2. Partant de x0 = (0; 0) ; déterminer la solution optimale du problème en utilisant la méthode
du gradient conjugué.
Exercise 11 Soit a 2 R et soit (Pa ) le problème d’optimisation sans contraintes :
(Pa ) : minimiser fa (x; y) = x2 + y 2 + axy 2x 2y:
3
1. Pour quelles valeures de a; la fonction fa est elle convexe ? strictement convexe ?
2. Soit A l’ensemble des réels a tel que fa est strictement convexe.
(a) Montrer que, pour tout a 2 A; la fonction fa est coercive sur R2 :
(b) Que peut-on en déduire ?
3. Partant de x0 = (0; 0) déterminer si c’est possible, la solution optimale du problème (Pa ) en
utilisant la méthode du gradient conjugué.
4
Part I
Corrigés
Solution 1 Les contraintes actives au point u = (1; 1) sont la première et la troisième contrainte.
L’ensemble P étant convêxe, on a :
8 0 1 0 1 9
< 3 5 =
Nu (P ) = @ A+ @ A: ; 0
: 2 2 ;
et
Tu (P ) = fd 2 Rn : 3d1 + 2d2 0 et 5d1 2d2 0g :
Solution 2 Répondre par vrai ou faux.
1. Vrai
2. Faux. L’application est convexe, mais pas strictement convexe. Si on …xe v1 (1; 0) et v2 (1; 1) ;
alors pour tout t 2 [0; 1] :
ktv1 + (1 t) v2 k1 = k(1; 1 t)k1 = 1 = t kv1 k1 + (1 t) kv2 k1 :
3. Vrai. Posons X = (x; y)t ; on reconnait la fonctionnelle quadratique
1
f (x; y) = hAX; Xi hb; Xi
2
avec 0 1 0 1
1 1 0
A=@ A et b = @ A :
1 3 1
p
La matrice A est une une matrice symétrique dé…nie positive (ses valeures propres 1 = 2+ 2
p
et 2 = 2 2 sont toutes strictement positives). Donc, f admet un unique minimum.
0 1 0 1
1 0 0
4. Faux. Contre-exemple. Pour A = @ A et b = @ A ; on a g (x) = kAx bk = x21
2
0 0 0
et toute la droite x1 = 0 réalise le minimum de g:
Solution 3 Soit f 2 C 1 (Rn ; R) : On suppose qu’il existe > 0 tel que:
hrf (x) rf (y) ; x yi kx yk2 ; 8 (x; y) 2 Rn Rn :
1
1. Soient (x; y) 2 Rn Rn et t 2 [0; 1] : Soit ' : R ! Rn la fonction dé…nie par
' (t) = f (x + t (y x)) :
Alors
Z 1
f (y) f (x) = ' (1) ' (0) = rf (x + t (y x)) (y x) dt:
0
On en déduit que
Z 1
f (y) f (x) rf (x) (y x) = rf (x + t (y x)) (y x) rf (x) (y x) dt:
0
c’est-à-dire :
Z 1 Z 1
f (y) f (x) rf (x) (y x) = rf (x + t (y x)) (y x) rf (x) (y x) dt t kx yk2 dt:
0 | {z } 0
kx yk2
Ceci entraîne :
kx yk2
f (y) f (x) rf (x) (y x) > 0 si x 6= y: (1)
2
On a donc, pour tout (x; y) 2 Rn Rn
f (y) > f (x) + rf (x) (y x)
D’après la première caractérisation de la convexité, on déduit que f est strictement convexe.
2. En posant x = 0 dans (1) ; on a
kyk2
f (y) f (0) + rf (0) y + :
2
Comme
rf (0) y krf (0)k kyk
on a
kyk2
f (y) f (0) krf (0)k kyk + :
2
Donc,
kyk
f (y) f (0) + kyk krf (0)k :
2
Ainsi
lim f (y) = +1:
kyk!+1
2
3. On déduit que f admet un minimum unique.
Solution 4 On considère la fonction f : R2 ! R dé…nie par
f (x; y) = 2x2 + y 2 xy 3x y + 4:
1. On a 0 1 0 1
4x y 3 4 x 1
rf (x; y) = @ A et Hf (x; y) = @ A:
2y x 1 1 2 x
Puisque la matrice hessienne de f est symétrique dé…nie positive (ses valeures propres 1 =
p p
3 2 et 2 = 3 2 sont toutes strictement positives), alors f admet un minimum global
unique u = (x; y) 2 R2 : Ce minimum est obtenu pour
0 1 0 1
4x y 3 0
rf (x; y) = 0 () @ A = @ A () x = 1 et y = 1:
2y x 1 0
La valeure de ce minimum est v = f (1; 1) = 2:
2. Puisque u0 = (0; 0) ; alors 0 1
3
d0 = rf (u0 ) = @ A :
1
On pose
g ( ) = f (u0 + d0 ) :
f (x; y) = 2x2 + y 2 xy 3x y + 4:
Alors 0 1
3
g( ) = f @ A = 18 2
+ 2
3 2
9 + 4 = 16 2
10 + 4:
Puisque g 0 ( ) = 32 10; alors
10 5
g 0 ( ) = 0 () = = :
32 16
Donc 0 1
15
5 @ 16 A
= et u1 = u0 + d0 = :
16 5
16
Remarquons que f (u1 ) = 2; 4375 est plus proche de 2 que f (u0 ) = 4:
3
Solution 5 On considère le problème d’optimisation avec contraintes :
8
>
> x2 + y 2 2;
>
>
>
>
< xy 1
minimiser f (x; y) = ln (x) y 4 + 2xy 4x sujet à :
>
> x 1;
>
>
>
> 1
: y
2
L’hypothèse de quali…cation des contraintes est-elle véri…ée en (1; 1) : En e¤ et,
R (1; 1) = G (1; 1) :
On pose :
1
g1 (x; y) = x2 + y 2 2; g2 (x; y) = xy 1; g3 (x; y) = x 1 et g4 (x; y) = y+ :
2
Puisque les contraintes saturées sont C1 ; C2 et C3 ; on est interessé par :
0 1 0 1 0 1
2x y 1
rg1 (x; y) = @ A ; rg2 (x; y) = @ A et rg3 (x; y) = @ A :
2y x 0
Donc, 0 1 0 1 0 1
2 1 1
rg1 (1; 1) = @ A ; rg2 (1; 1) = @ A et rg3 (1; 1) = @ A :
2 1 0
– On a :
G (1; 1) = d = (d1 ; d2 ) 2 R2 : 2d1 + 2d2 0; d1 + d2 0; d1 0 :
Par conséquent,
G (1; 1) = d = (d1 ; d2 ) 2 R2 : d1 + d2 0; d1 0 :
– On a :
8 9
>
> d = (d1 ; d2 ) 2 R2 : 9 > 0 tel que pour tout ! 0; >
>
>
> >
>
>
> >
>
< (1 + d1 )2 + (1 + d2 )2 2; =
R (1; 1) = :
>
> (1 + d1 ) (1 + d2 ) 1; >
>
>
> >
>
>
> >
>
: (1 + d1 ) 1: ;
Donc, pour assez petite, à l’aide d’un développement limité au voisinage de 0; on
trouve:
R (1; 1) = d = (d1 ; d2 ) 2 R2 : d1 + d2 0; d1 0 :
4
Non. Par l’absurde, supposons que (1; 1) est un optimum local. Puisque l’hypothèse de
quali…cation des contraintes est-elle véri…ée en (1; 1) ; alors il existe
2; 1;
3 0 tel que:
0 1
0
rf (1; 1) + 1 rg1 (1; 1) + 2 rg2 (1; 1) + 3 rg3 (1; 1) = @ A ;
0
avec 0 1
1
+ 2y 4
rf (x; y) = @x A:
4y 3 + 2x
Ainsi, 0 1
0 1 0 1 0 1 0 1
1 2 1 1 0
@ A+ 1@ A+ 2@ A+ 3@ A = @ A:
2 2 1 0 0
Donc, 8
< 1 + 2 1 + 2 + 3 = 0;
: 2 + 2 1 + 2 = 0:
On obtient 3 = 1 < 0; absurde.
