Ecole Nationale Suprieure de Techniques Avances (ENSTA) - [Link]

fr
1

Travaux diriges.

Optimisation & Analyse convexe

S
eance 1 : Existence dun minimum. Convexit
e
Exercice 1
fonction :

Soit A IRnn une matrice symetrique, et b un vecteur de IR n . On consid`ere la

1. Soient min et max

1
f : x IRn 7 (x, Ax) (b, x).
2
la plus petite et la plus grande valeur propre de A. Montrer que
min kxk22 (Ax, x) max kxk22 .

x IRn

2. Montrer que f est derivable sur IR n . Calculer df (x) et f (x), pour x IR n .

3. Supposons maintenant que A est symetrique positive. Montrer que dans ce cas, A est
inversible si et seulement A est definie positive.

Corrig
e1
1. La matice A est symetrique, toutes ses valeurs propres i sont reelles (eventuellement
nulles), et elle admet une base de vecteurs propres orthonormes B = {v 1 , v2 , , vn } :
Avi = i vi

pour i = 1, 2, , n

et

(vi , vj ) = ij

pour i, j = 1, 2, , n.

Pour tout vecteur x IRn , on a donc

n
X

x=

xi vi ,

Ax =

i=1

n
X

xi Avi =

n
X

x2i (Ax, x) max i

i=1

soit finalement
min i
i

i=1

n
X

i xi vi

et

(Ax, x) =

i=1

n
X

i x2i

i=1

n
X

x2i .

i=1

2. Pour tout h IR , on a
1
(A(x + h), x + h) (b, x + h)
2
1
1
=
(Ax, x) + (Ax, h) + (Ah, h) (b, x) (b, h)
2
2
1
= f (x) + (Ax b, h) + (Ah, h).
2

f (x + h) =

Si on pose (h) = 21 (Ah, h)/khk2 , alors

|(Ah, h)| kAkkhk22 lim |(h)| = 0.
h0

Soit
df (x).h = (Ax b, h)

et

f (x) = Ax b.

Commentaire : Dans le cas general (A non symetrique) :

(A + AT )
1
x) (b, x);
f (x) = (x,
2
2
1
df (x).h = ( (A + AT )x b, h) et
2

f (x) =

1
(A + AT )x b.
2

Ce document est mis votre disposition par l'ENSTA sous couvert de la licence "Creative Commons"

Ecole Nationale Suprieure de Techniques Avances (ENSTA) - [Link]

2

Travaux diriges.

3. Supposons que A soit inversible. Soit w tel que (Aw, w) = 0. On va montrer que w est en
fait egal a` zero. Soient d IRn (d 6= 0) et > 0. Comme A est positive et symetrique :
0 (A{w + d}, w + d) = 2(Aw, d) + 2 (Ad, d).
En mettant en facteur, puis en faisant tendre vers 0 dans le facteur restant, on obtient
(Aw, d) 0. Comme cest valable pour toute direction (d IR n ), on en deduit que Aw = 0,
ce qui conduit enfin a` w = 0 par hypoth`ese sur A.
La reciproque est aisee et classique. En effet, si A est definie-positive, Aw = 0 entrane
que (Aw, w) = 0, et donc que w = 0 : par consequent, A est inversible.
1
Exercice 2
Soit f : IRn IR , f (x) = (x, Ax) (b, x) + c avec A une matrice n n
2
symetrique, b IRn , c IR.
1. Montrer que f admet un minimum sur tout compact K de IR n .
2. Montrer que f est convexe ssi A est positive 1 .
3. Montrer que f est stritement convexe ssi A est definie positive.
4. Montrer que si A est definie positive, alors f est infinie a
` linfiniet admet un minimum
n
unique sur tout ferme convexe K IR .
5. Montrer que, sils existent, les minima de f verifient la relation Ax = b.
En deduire que si A est non positive, alors f nadmet pas de minimum sur IR n .
Corrig
e2
1. f etant continue, elle atteint ses minima sur tout compact K.
2. Rappelons que la fonction f est convexe si et seulement si :
x, y IRn , (f (y) f (x), y x) 0.
Dautre part, on a f (x) = Ax b. Il vient alors :
f est convexe

((Ay b) (Ax b), y x) 0

(A(y x), y x) 0
(Az, z) 0

z IRn

y, x IRn

y, x IR n

A est positive.

3. La stricte convexite de f est equivalente a` :

x 6= y IRn , (f (y) f (x), y x) > 0.
4. Supposons que la matrice A est symetrique definie positive. Donc dapr`es lexercice 1, on
peut minorer la foncion f par :
1
f (x) min (A)kxk22 kbk2 kxk2 + c,
2
1
avec min (A) > 0 et lim min (A)z 2 kbk2 z + c = +. On en deduit alors que :
z+ 2
lim

xK,kxk+

f (x) = +;

pour tout ensemble ferme K de IRn . f est alors infinie a` linfini et strictement convexe,
elle admet donc un minimum unique sur tout ferme convexe K.
1

cest a
` dire (Av, v) 0 pour tout v IRn . On parle aussi dans certains livres de semi-definie positive

Ce document est mis votre disposition par l'ENSTA sous couvert de la licence "Creative Commons"

Ecole Nationale Suprieure de Techniques Avances (ENSTA) - [Link]

3

Travaux diriges.

5. Supposons que f atteint le minimum en x IR n , alors il existe V un voisinage de x tel

que :
f (y) f (x), y V.

En particulier, f (x + d) f (x) 0 pour tout d IR n et pour tout > 0 assez petit tel
que x + d V . En divisant par et en faisant tendre vers 0 par valeurs superieures,
on en deduit que x satisfait :
f (x).d = (Ax b, d) 0,

d IRn .

Ou encore, puisque d parcourt IRn ,

Ax = b.
Dautre part, si x existe alors
f (x + d) f (x) = (Ax b, d) +

2
2
(Ad, d) =
(Ad, d) 0,
2
2

pour tout d IRn (et pour tout > 0, assez petit tel que x + d reste dans le voisinage V
de x). Donc A est necessairement positive.
Exercice 3
1. La composee de deux fonctions convexes est-elle convexe ?
2. Examiner, parmi les fonctions suivantes, lesquelles sont convexes, strictement convexes,
convexes :
f (x) = ln(x), g(x) = x4 x2 , h(x) = x ( IN), `(x) = |x| ( > 1)?
3. Soit kk une norme de IRn . Montrer que x IRn 7 kxk et x IRn 7 kxk2 sont convexes.
Corrig
e3
1. La composee de deux fonctions convexes nest pas forcement convexe. En effet, les fonctions
2
g : x 7 ex et f : x 7 x2 sont bien convexes sur R, et pourtant g f : x 7 e x nest
pas convexe sur IR !
Par contre, on peut facilement verifier le resultat suivant : Soit K une partie convexe de
IR.
Soient f : IRn K une fonction convexe et g : K IR une fonction convexe
croissante. Alors g f est convexe.

2. La fonction f est strictement convexe (sur IR + ), mais nest pas convexe.

6
La
fonction
g
nest
pas
convexe
sur
I
R
,
mais
est
convexe
sur
les
intervalles
]

6 ] et

[ 66 , +[.
Pour {0, 1}, la fonction h est convexe. Pour 2, h nest convexe sur IR que si est
paire. Dans le cas = 2, h est -convexe avec = 2.
La fonction ` se decompose en s r o`
u s et r sont definies par :
s : x IR+ 7 x ,

r : x IR 7 |x|.

Il est facile de verifier que r est strictement convexe, et s est strictement convexe et
croissante sur IR+ . On conclut alors que pour > 1, ` est strictement convexe sur IR.

Ce document est mis votre disposition par l'ENSTA sous couvert de la licence "Creative Commons"

Ecole Nationale Suprieure de Techniques Avances (ENSTA) - [Link]

4

Travaux diriges.

Exercice 4 Soit f de IR2 dans IR2 definie par :

p xy
x2 + y 2
f (x, y) =
0

si (x, y) 6= (0, 0)
sinon.

1. Montrer que f est continue en (0, 0).

2. Montrer que f nest pas differentiable en (0, 0).

3. Est-elle Gateaux-differentiable ?
Corrig
e4
1. De linegalite 2|xy| x2 + y 2 , on obtient la majoration de |f (x, y)| par :
|f (x, y)|

1p 2
x + y2 ,
2

x, y IR.

On en deduit alors que

lim f (x, y) = 0 = f (0, 0)

(x,y)0

ce qui prouve la continuite de f en (0, 0).

2. Pour que f soit differentiable en (0, 0) il faut et il suffit quil existe une forme lineaire
df (0, 0) tel que :
f (x, y) = f (0, 0) + df (0, 0).(x, y) + k(x, y)k(x, y);

avec

lim

(x,y)(0,0)

(x, y) = 0.

Or si on fixe y = 0, on obient :
f (x, 0) = 0 = f (0, 0) + 0,

x IR.

Donc si f est differentiable en (0, 0), alors df (0, 0).(x, 0) = 0 pour tout x IR, et de meme
on pourrait etablir que df (0, 0).(0, y) = 0. Ce qui entranerait que df (0, 0) 0.
Maintenant, si on prend x = y 6= 0, alors on obtient :
|x|
x2
= ,
f (x, x) =
2
2
2x
et

f (x, x) f (0, 0) 0.(x, x)

6= 0.
k(x, x)k
(x,x)0
lim

Donc la forme lineaire nulle nest pas la differentielle de f en (0, 0) et f nest pas differentiable
en ce point.
3. Pour tout t > 0 et tout (x, y) 6= (0, 0), on a :

donc

f (tx, ty) f (0, 0)

xy
=p
.
t
x2 + y 2
lim

t0+

xy
f (tx, ty) f (0, 0)
.
=p
t
x2 + y 2

Cette limite netant pas une forme lineaire, on conclut que f nest pas Gateaux-differentiable.

Ce document est mis votre disposition par l'ENSTA sous couvert de la licence "Creative Commons"

Ecole Nationale Suprieure de Techniques Avances (ENSTA) - [Link]

5

Travaux diriges.

Exercice 5 Montrer que :

1. Lapplication f : x IRn 7 kxk nest jamais differentiable a` lorigine.

2. Lapplication f : x IRn 7 kxk2 (la norme euclidienne) est differentiable au sens de

Frechet en tout point x 6= 0, et
df (x).h =

hx, hi
,
kxk2

h IRn .

3. Lapplication f : x IRn 7 kxk est derivable en un point a IRn , si et seulement si il

existe un indice i0 , tel que
i 6= i0 , |ai0 | > |ai |.
Corrig
e5
1. On suppose que lapplication f : x IR n 7 kxk est differentiable en 0 ; alors on peut
ecrire
f (0 + h) = f (0) + (f (0), h) + khk(h), avec lim k(h)k = 0;
h0

soit encore
1=

khk
h
= 0 + (f (0),
) + (h),
khk
khk

avec lim k(h)k = 0.

h0

En changeant h par h, on aussi :

1=

h
khk
= 0 (f (0),
) + (h).
khk
khk

Par addition, on obtient la contradiction

2 = (h) + (h)

avec lim k(h)k = lim k(h)k = 0.

h0

h0

2. Pour la norme euclidienne, on ecrit pour tout x 6= 0

kx + hk22 kxk22 = 2(x, h) + khk22 .
On obtient
kx + hk2 kxk2 =

2(x, h) + khk22
.
kx + hk2 + kxk2

Reecrivons tout dabord la partie en khk 22 , sous la forme khk2 1 (h), avec
1 (h) =

khk2
;
kx + hk2 + kxk2

on a 0 1 (h)

khk2
, et lim |1 (h)| = 0.
h0
kxk2

Si maintenant on extrait la partie lineaire de ce qui reste, on trouve

(x, h) (x, h){kxk2 kx + hk2 }
2(x, h)
=
+
.
kx + hk2 + kxk2
kxk2
kxk2 {kx + hk2 + kxk2 }
Ecrivons le second terme sous la forme khk 2 2 (h), avec
2 (h) =

(x, h){kxk2 kx + hk2 }

.
khk2 kxk2 {kx + hk2 + kxk2 }

Ce document est mis votre disposition par l'ENSTA sous couvert de la licence "Creative Commons"

Ecole Nationale Suprieure de Techniques Avances (ENSTA) - [Link]

6

Travaux diriges.

Dapr`es linegalite de Cauchy-Schwartz, on a |(x, h)| khk 2 kxk2 , et dapr`es linegalite

triangulaire, on a egalement |kxk 2 kx + hk2 | khk2 . Ainsi
0 |2 (h)|

khk2
, et lim |2 (h)| = 0.
h0
kxk2

Remarque. Un
raisonnement plus rapide consiste a` exprimer f sous la forme f = g f 2 ,
avec g : t 7 t et f2 : x 7 kxk22 . Des que x 6= 0, on deduit du theor`eme de composition
des differentielles que f est bien differentiable, et on a :
df (x).h = dg(f2 (x)).(df2 (x).h),
Or on a

1
dg(s).y = y, s IR+ ,
2 s

h IRn .

df2 (x).h = 2(x, h), h IRn .

On en deduit finalement que, pour x 6= 0, on a :

df (x).h =

2(x, h)
,
kxk2

et f (x) ==

2
x.
kxk2

3. On consid`re dabord le cas o`

u il existe un indice i 0 tel que |ai0 | > |ai | pour tout i 6= i0 . On
pose = |ai0 | maxi6=i0 |ai | ; > 0 et pour tout h IRn tel que khk /2, on a
f (a + h) f (a) = ka + hk kak = |ai0 + hi0 | |ai0 | = hi0 sign(ai0 ).
ainsi lapplication f est differentiable en a et
df (a).h = (f (a), h) = hi0 sign(ai0 ).
On consid`ere maintenant le cas o`
u il existe (au moins) deux indices i 0 et j0 , tels que :
kak = |ai0 | = |aj0 |
et a 6= 0 (aucune norme nest derivable en 0, voir plus haut). Alors pour tout h IR n tel
que |hi0 | < |ai0 |, et hi = 0 pour tout i 6= i0 , on ecrit
ka + hk kak = max |ai + hi | |ai0 |.
i

a partir de l`a, on a maxi |ai + hi | = |ai0 + hi0 | = kak + khk si hi0 et ai0 sont de meme
signe, et maxi |ai + hi | = |ai0 = kak sinon. On trouve donc

khk si sign(hi0 ) = sign(ai0 ),
ka + hk kak =
0
si sign(hi0 ) = sign(ai0 ).
Lapplication f nest donc pas differentiable en a.

Ce document est mis votre disposition par l'ENSTA sous couvert de la licence "Creative Commons"