Corrige optimisation

8/10/2019 Corrige optimisation

1/6

Ecole Nationale Suprieure de Techniques Avances (ENSTA) - http://www.ensta.fr

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

Travaux diriges. 1

Optimisation & Analyse convexeSeance 1 : Existence dun minimum. Convexite

Exercice 1 Soit A IRn n une matrice symetrique, et b un vecteur de IR n . On considere lafonction :f : x IRn 12(x,Ax ) (b, x).

1. Soient min et max la plus petite et la plus grande valeur propre de A. Montrer que

x IRn min x 22 (Ax,x ) max x 22 .

2. Montrer que f est derivable sur IR n . Calculer df (x) et f (x), pour x IRn .3. Supposons maintenant que A est symetrique positive. Montrer que dans ce cas, A est

inversible si et seulement A est denie positive.

Corrige 1

1. La matice A est symetrique, toutes ses valeurs propres i sont reelles (eventuellementnulles), et elle admet une base de vecteurs propres orthonormes B = {v1, v2, , vn } :Av i = i vi pour i = 1, 2, , n et (vi , v j ) = ij pour i, j = 1 , 2, , n.

Pour tout vecteur x IRn , on a donc

x =n

i=1

x i vi , Ax =n

i=1

x i Av i =n

i=1

i x i vi et (Ax,x ) =n

i=1

i x2i

soit nalement

mini

in

i=1

x2i (Ax,x ) maxi in

i=1

x2i .

2. Pour tout h IRn , on af (x + h) =

12

(A(x + h), x + h) (b, x + h)=

12

(Ax,x ) + ( Ax,h ) + 12

(Ah,h ) (b, x) (b, h)= f (x) + ( Ax b, h) +

12

(Ah,h ).

Si on pose (h) = 12 (Ah,h )/ h 2 , alors

|(Ah,h )

| A h 22

limh0 |

(h)

| = 0.

Soitdf (x).h = ( Ax b, h) et f (x) = Ax b.

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

f (x) = 12

(x, (A + AT )

2 x) (b, x);

df (x).h = (12

(A + AT )x b, h) et f (x) = 12

(A + AT )x b.


2/6



2 Travaux diriges.

3. Supposons que A soit inversible. Soit w tel que (Aw,w ) = 0. On va montrer que w est enfait egal a zero. Soient d IRn (d = 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 IRn ), on en deduit que Aw = 0,ce qui conduit enn à w = 0 par hypothese sur A.La reciproque est aisee et classique. En effet, si A est denie-positive, Aw = 0 entraneque (Aw,w ) = 0, et donc que w = 0 : par consequent, A est inversible.

Exercice 2 Soit f : IRn IR , f (x) = 12

(x,Ax ) (b, x) + c avec A une matrice n nsymetrique, b IRn , c IR.

1. Montrer que f admet un minimum sur tout compact K de IRn .2. Montrer que f est convexe ssi A est positive 1 .3. Montrer que f est stritement convexe ssi A est denie positive.4. Montrer que si A est denie positive, alors f est innie à linni et admet un minimum

unique sur tout ferme convexe K IRn

.5. Montrer que, sils existent, les minima de f verient la relation Ax = b.

En deduire que si A est non positive, alors f nadmet pas de minimum sur IR n .

Corrige 2

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

y, x

IRn

(A(y x), y x) 0 y, x IRn (Az,z ) 0 z IRn A est positive .

3. La stricte convexite de f est equivalente à :

x = y IRn , (f (y) f (x), y x) > 0.4. Supposons que la matrice A est symetrique denie positive. Donc dapres lexercice 1, on

peut minorer la foncion f par :

f (x) 12min (A) x

22 b 2 x 2 + c,

avec min (A) > 0 et limz+

12

min (A)z2 b 2z + c = + . On en deduit alors que :lim

xK, x + f (x) = + ;

pour tout ensemble ferme K de IRn . f est alors innie a linni et strictement convexe,elle admet donc un minimum unique sur tout ferme convexe K .

1 cest a dire ( Av,v ) 0 pour tout v IR n . On parle aussi dans certains livres de semi-denie positive


3/6



Travaux diriges. 3

5. Supposons que f atteint le minimum en x IRn , alors il existe V un voisinage de x telque :f (y) f (x),y V.

En particulier, f (x + d) f (x) 0 pour tout d IRn et pour tout > 0 assez petit telque 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 IR n ,

Ax = b.

Dautre part, si x existe alors

f (x + d) f (x) = (Ax b, d) + 2

2 (Ad,d) =

2

2 (Ad,d) 0,

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 une norme de IR n . Montrer que x IRn x et x IRn x 2 sont convexes.Corrige 3

1. La composee de deux fonctions convexes nest pas forcement convexe. En effet, les fonctionsg : x ex et f : x x2 sont bien convexes sur R, et pourtant g f : x ex

2nest

pas convexe sur IR !Par contre, on peut facilement verier le resultat suivant : Soit K une partie convexe deIR.

Soient f : IRn K une fonction convexe et g : K IR une fonction convexecroissante. Alors g f est convexe.2. La fonction f est strictement convexe (sur IR + ), mais nest pas convexe.

La fonction g nest pas convexe sur IR, mais est convexe sur les intervalles ]

,

66 ] et

[ 66 , + [.Pour {0, 1}, la fonction h est convexe. Pour 2, h nest convexe sur IR que si estpaire. Dans le cas = 2, h est -convexe avec = 2.La fonction se decompose en s r ou s et r sont denies par :

s : x IR+ x , r : x IR |x|.Il est facile de verier que r est strictement convexe, et s est strictement convexe etcroissante sur IR + . On conclut alors que pour > 1, est strictement convexe sur IR.


4/6



4 Travaux diriges.

Exercice 4 Soit f de IR2 dans IR 2 denie par :

f (x, y) =xy

x2 + y2si (x, y) = (0 , 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 ?

Corrige 4

1. De linegalite 2 |xy| x2 + y2, on obtient la majoration de |f (x, y)| par :

|f (x, y)| 12 x2 + y2, x, y IR.

On en deduit alors quelim

(x,y )0f (x, y) = 0 = f (0, 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) + (x, y) (x, y); avec lim(x,y )(0 ,0)

(x, y ) = 0 .

Or si on xe 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 memeon pourrait etablir que df (0, 0).(0, y) = 0. Ce qui entranerait que df (0, 0) 0.Maintenant, si on prend x = y = 0, alors on obtient :

f (x, x ) = x2

2x2 = |x| 2,

etlim

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

(x, x ) = 0 .Donc la forme lineaire nulle nest pas la differentielle de f en (0, 0) et f nest pas differentiableen ce point.

3. Pour tout t > 0 et tout ( x, y ) = (0 , 0), on a :f (tx,ty ) f (0, 0)

t =

xy

x2 + y2.

donclim

t0+f (tx,ty ) f (0, 0)

t =

xy

x2 + y2.

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


5/6



Travaux diriges. 5

Exercice 5 Montrer que :1. Lapplication f : x IRn x nest jamais differentiable ` a lorigine.2. Lapplication f : x IRn x 2 (la norme euclidienne) est differentiable au sens deFrechet en tout point x = 0, et

df (x).h = x, hx 2 , h IRn .

3. Lapplication f : x IRn x est derivable en un point a IRn , si et seulement si ilexiste un indice i0, tel quei = i0, |a i 0 | > |a i |.

Corrige 5

1. On suppose que lapplication f : x IRn x est differentiable en 0 ; alors on peutecriref (0 + h) = f (0) + (f (0), h) + h (h), avec limh

0

(h) = 0;

soit encore

1 = hh

= 0 + (f (0), hh

) + (h), avec limh 0

(h) = 0 .

En changeant h par h, on aussi :1 = h

h = 0 (f (0) ,

hh

) + (h).Par addition, on obtient la contradiction

2 = (h) + (

h) avec lim

h0(h) = lim

h0(

h) = 0 .

2. Pour la norme euclidienne, on ecrit pour tout x = 0x + h 22 x 22 = 2( x, h ) + h 22 .

On obtientx + h 2 x 2 =

2(x, h ) + h 22x + h 2 + x 2

.

Reecrivons tout dabord la partie en h 22 , sous la forme h 21(h), avec1(h) = h 2

x + h 2 + x 2; on a 0

1(h)

h 2

x 2, et lim

h

0 |1(h)

| = 0 .

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

2(x, h )x + h 2 + x 2

= (x, h )

x 2+

(x, h ){ x 2 x + h 2}x 2{ x + h 2 + x 2}

.

Ecrivons le second terme sous la forme h 22(h), avec2(h) =

(x, h ){ x 2 x + h 2}h 2 x 2{ x + h 2 + x 2}

.


6/6


6 Travaux diriges.

Dapres linegalite de Cauchy-Schwartz, on a |(x, h )| h 2 x 2, et dapres linegalitetriangulaire, on a egalement | x 2 x + h 2| h 2. Ainsi0 |2(h)|

h 2x 2

, et limh 0 |2(h)| = 0.

Remarque. Un raisonnement plus rapide consiste ` a exprimer f sous la forme f = g f 2,avec g : t t et f 2 : x x 22 . Des que x = 0, on deduit du theoreme de compositiondes differentielles que f est bien differentiable, et on a :df (x).h = dg(f 2(x)).(df 2(x).h), h IRn .

Or on adg(s).y =

12 s y, s IR+ , df 2(x).h = 2( x, h ), h IR

n .

On en deduit nalement que, pour x = 0, on a :df (x).h =

2(x, h )

x 2, et

f (x) ==

2

x 2x.

3. On considre dabord le cas o`u il existe un indice i0 tel que |a i 0 | > |a i | pour tout i = i0. Onpose = |a i 0 | max i= i 0 |a i | ; > 0 et pour tout h IRn tel que h / 2, on af (a + h) f (a) = a + h a = |a i 0 + hi 0 | |a i 0 | = hi 0 sign(a i 0 ).

ainsi lapplication f est differentiable en a et

df (a).h = (f (a), h) = h i 0 sign(a i 0 ).

On considere maintenant le cas o` u il existe (au moins) deux indices i 0 et j0, tels que :

a = |a i 0 | = |a j 0 |et a = 0 (aucune norme nest derivable en 0, voir plus haut). Alors pour tout h IR n telque |h i 0 | < |a i 0 |, et h i = 0 pour tout i = i0, on ecrit

a + h a = maxi |a i + hi | |a i 0 |.a partir de l`a, on a max i |a i + hi | = |a i 0 + hi 0 | = a + h si hi 0 et ai 0 sont de memesigne, et max i |a i + hi | = |a i 0 = a sinon. On trouve donc

a + h

a

= h si sign(h i 0 ) = sign( a i 0 ),

0 si sign(h i 0 ) = sign(a i 0 ).Lapplication f nest donc pas differentiable en a.

Documents

Corrige optimisation