Feuilles d’exercices d’Optimisation - Free

1 Feuilles d exercices d OptimisationAlexandre Marino11 Existence et Unicit semi-continuit e inf erieure La semi-continuit e inf erieure s exprime d une mani`ere analytique ou g eom etriquecomme suit tout pointx IRn, on a lim infx xf(x ) f(x).( in egalit e dansR {+ }). tout IR, la coupe `a hauteur {x IRn, f(x) }estferm epigraphe def, c est `a dire ce qui est au dessus du graphe def :{(x, r) IRn IR, f(x) r}est ferm erifier l equivalence des trois d efinitions pr ec les propri et es fonction caract eristique d un ouvert (resp ferm e) est semi-continueinf erieurement ( resp sup erieurement). fonction `a valeur dans IR est continue si et seulement si elle est `ala fois semi-continue inf erieurement et sup bornesupd une famille de fonctions semi-continues inf erieurementest semi-continue inf 0- coercivit e Exercice que sifest continue 0-coercive ( limx K, x + f(x) =+ ) alors l image r eciproque d un compact est un d un minimum :On consid`ere le probl`eme :minx Kf(x)( )D emontrer le th eor`eme suivant :Th eor`eme suppose dans le probl`eme ( ) que ferm e et il existe un point deKen lequelfest semi-continue inf erieurement sur K, x + f(x) = +.

2 (f0-coercive )Alorsfest born ee inf erieurement surKet il existe x Ktel quef( x) =infx Kf(x). Th eor`eme de Weierstrass et convexit e Exercice fonctionf:O IRn IR convexe sur un ouvert convexeOy est fonction convexe etKun ensemble convexe ferm edans IRn. Alors le probl`eme ( ) admet au moins une solution si l une desdeux conditions suivantes est satisfaite |x| + f(x) = + born ces hypoth`eses, montrer que l ensemble des solutions optimales duprobl`eme ( ) est un ensemble convexe et born e. Montrer que le probl`eme( ) admet une unique solution si la fonctionfest strictement ApplicationsExercice e de IRn,a IRnetf:x a x alors il existe xtel que a x a x .Exercice :x IRn f(x) :=12< Ax, x >+< b, x >+ etrique d efinie positive. Pour tout ferm eeKde IRn, il existe alorsun unique x Condition de minimalit Condition de minima local du premier ordreExercice :O IRn IR (Oouvert de IRn), Si xest un minimumlocal ( ou maximum ) defet sifest diff erentiable en x, alors : f( x) = 0 Caract erisation de la convexit e en termes du gradient :Dans le cas o`u la fonctionfn est suppos ee qu une fois diff erentiable, on a ler esultat suivant :Exercice :K IRn Rune fonction une fois diff erentiable,alorsfest convexe si et seulement sif(y) f(x) + f(x)(y x) x, y K2, x6=yOn voit bien l interpr etation g eom etrique de ce dernier resultat quandn= 1 : le graphe d une fonction convexefse trouve toujours au-dessus dela tangente en un point donn les r esultats xun point tq f( x) = 0.

3 Alors pour tout >0, xest un minimumlocal strict de la fonctionx f(x) + x x . :O IRn IR convexe et diff erentiable sur l ouvert les conditions suivantes sont equivalentes : xest un minimum (global ) defsurO. xest minimum local def. xest tq f( x) = :f:x IRn f(x) :=12< Ax, x >+< b, x >+ l absence de convexit eExercice x Oun point en lequelfest continue et supposonsqu il existe un voisinage ouvertVde xtel que diff erentiable surV\{ x}2.< f(x), x x > 0 ( resp.>0) pour toutx V\{ x}.Alors xest un minimum local ( resp. minimum local strict ) (x1, x2) :=x2/31+x4/52+ (x1, x2) := (x1 x2)4+(x1 1)4+10, on remarque que le second ordrene suffit Condition de minimalit e global du premier ordreExercice : IRn IR une fonction-objectif diff erentiable sur x IRnest un minimum global defsur IRnsi et seulement si :1. f( x) = 02.(convf)( x) =f( x). Condition de minimalit e du second ordreExercice xest un minimum local defet sifest deux fois diff erentiableen x, alors : f( x) = 0, et 2f( x) semi-d efinie xest un minimum local defet sifest deux fois diff erentiableen x, et si : f( x) = 0, et 2f( x) d efinie positive, alors : xest un minimum local strict il n y a pas que pourf(x1, x2) := 3x41 4x21x2+x22(0,0) est unpoint critique semi-d efinie positif qui n est pas un extremum Convexit e et Diff erentiabilit eExercice : IR IR est 2 fois contin ument d erivable sur K convexealorsfest convexe si et seulement sif (x) 0 x Ket strictementconvexe si et seulement sif (x)>0 x K(sauf eventuellement en despoints isol es).

4 Ce r esultat se g en eralise pourn >1 :le r esultat suivant fait le lien entre le hessien et la propri et e de convexit e :Exercice :K IRn Rune fonction deux fois diff erentiable,alorsfest convexe si et seulement si 2f(x) 0 x K, et strictementconvexe si et seulement si 2f(x)>0 x ExercicesExercice ensemble convexe ferm e. On consid`ere la fonction :p(x) :=12 x P x 2O`uPd esigne le projecteur surK. Montrer que cette fonction est d erivableet calculer son gradient. En d eduire quepest consid`ere l application d efinie sur IR2par :f(x, y) :=14x4 xy+ quefest 0- coercive. En d eduire l existence d un le gradient en tout point. Determiner les points d eduire le minimum global consid`ere l application d efinie sur IR3par :f(x, y, z) :=x2y xln(y) +z(z 1)(z+ 1)2 Calculer le gradient et la matrice hessienne defaux pointsA= (1/e2, e2, 1)etB= (0,1, 1). V erifier siAetBsont des extrema locaux les extrema globaux def(x, y, z) =x2+y2+z2sousla contraintex+y+z= 1 en se ramenant `a un probl`eme d optimisation sanscontrainte dans IR2.

5 Faites une interpr etation g eom les extrema globaux def(x, y, z) =x2+y2+z2sousla contraintex+y2= 1 en se ramenant `a un probl`eme d optimisation sanscontrainte dans IR2. Faites une interpr etation g eom les extrema globaux def(x, y, z) = 5x2+y2 2xysous la contraintex2+y2= 1 en se ramenant `a un probl`eme d optimisationsans contrainte dans IR2. Faites une interpr etation g eom consid`ere la fonctionJpd efinie dans IR3(p etant unparam`etre r eel).Jp(x, y, z) :=x4+y4+z4 p(x2+y2+z2 1) emontrer que la fonctionJpest d eduire que la proposition (P) suivante est vraie :Il existe (x0, y0, z0) IR3tel que (x, y, z) IR3, Jp(x0, y0, z0) Jp(x, y, z). s interesse aux points critiques deJp. Montrer qu il existe une valeurp0telle que :(a)Pourp p0,Jpadmet un seul point critique.(b)Pourp > p0,Jpadmet 27 points pr ecisera la valeur depainsi que celle des 27 points les minima globaux deJplorsquep suppose maintenantp > p0 Calculer le Hessien deJpet etudier la nature des points critiques.

6 End eduire que la fonctionJpadmet 8 minima globaux que l on pr matrice sym etrique d efinie positive de taillen consid`ere la fonctionJy( param`etrey IRn) d efinie dans IRnparJy(x) :=< x, y > 12< Ax, x > le maximum deJysur d eduire qu il existe une matriceBtelle que x, y IRn2< x, y > < Ax, x >+< By, y >Exercice la fonction d efinie sur IR2parf(x, y) =x4+y4 erifier quefest deux fois d erivable sur erifier que l ensemble ={(x, y) (IR+)2, xy >1}est un ouvertconvexe de erifier quefest strictement convexe sur . erifier quefest eterminer les minima globaux sur IR2?Exercice consid`ere la fonction d efinie sur IR2parf(x, y) = 3x2 2xy+ 2y2+sup(x,1) erifier qu il existe un r eel strictement positif tel que x, y IR2f(x, y) 1 + (x2+y2) d eduire quefest erifier quefest strictement convexe sur d eduire quefadmet un minimum global unique sur l ensemble :={(x, y) IR2, x6= 1}Montrer que est un ouvert de quefest d erivable sur.

7 Le gradient defsur . les points critiques defsur . le minimum global quefn est pas d erivable au point (1, t) avect C ones tangent et Notion de C one tangentD efinition :SoitK IRn, eta K. Alors le c one tangent `aKenaest :T(K, a) :={y IRn, xk K, k>0, k INtel que:xk a et k(xk a) y}Propri et es queT(K, a) :={d IRn, dk d, tk>0 0, telles que: k IN, a+tkdk K} (K, a) est un c one contenant l K1 K2, alorsT(K1, a) T(K2, a). ( ki=1Ki, a) = ki=1T(Ki, a) avecKi Ki+ esigne la fonction-distance `aK,d T(K, a) liminft 0+dK(a+td)/t= toutr >0,K IRneta Kon a :T(K, a) =T(K B(a, r), a)O`uB(a, r) est la boule de centreaet de dansKouvert, alorsT(K, a) = dans l int erieur deK, alorsT(K, a) = (K, a) est ferm one,Kest convexe si et seulement siK+K convexe ferm e, alors pour touta K, on a : K a T(K, a)De plus,T(K, a) est convexe, ferm e (c est l enveloppe c onique ferm e deK a).

8 Exercices :Exercice fonction d efinie sur IRn`a valeur dans IRp, de classeC . On note :Graph(f) ={(x, y) IRn IRp, y=f(x)}etJac(f, x) le jacobien defau pointxrepr esent e par la matrice des d eriv que :T(Graph(f),(x, y)) =Graph(Jac(f, x))Exercice reprenant l enonc e de l exercice pr ec edent avecp= 1, onnoteEpigraph(f) ={(x, y) IRn IR/y f(x)}.Montrer que :T(Epigraph(f),(x, f(x))) =Epigraph(Jac(f, x))(On rappelle queEpigraph(Jac(f, x)) ={(u, v) IRn IR/v ni=1 f xi(x)ui}Retrouver la propri et e suivante : sifest de classeC , si xest un minimumdef, alorsJac(f, x) est nul.)Exercice erons l applicationf(x1, x2) :=x21+x22. V erifier qu entout point, le c one tangent au graphe defest le translat e passant par l originedu plan tangent le c one tangent du graphe de l applicationf(x1, x2) :=|x1|+|x2|en (0,0) et calculer le c one normal.(N(K, a) :={w= (w1, w2) IR2, < w, v > 0, v T(K, a)}).

9 Exercice IR3, on consid`ere l ensembleKd efini parK:={(x, y, z) IR3, x2+y2 1, z 0, x+y+z 2}Calculez le c one tangent `aKau point (1,0,1).Motivation :Exercice x O Kest un minimum local defsurKet sifdiff erentiable en x, alors pour toutd T(K, x) :< f( x), d > 0 Exercice que l on retrouve la condition n ecessaire de minimalit edu premier ordre siKest un efinition :SiKest un c one, on appelle c one polaire deKl ensemble suivant :Ko:={s IRn/ < s, d > 0, d K}D efinition :On appelle c one normal deKena, l ensemble suivant :N(K, a) := (T(K, a))oExercice un c one convexe ferm e ayant les propri et es suivantes :1.(K1 K2) (Ko2 Ko1). un convexe ferm e,Koo= un sous espace vectoriel, alorsHo=H .Exercice le c one convexe engendr e par lesvi, c est `a direK={n j=1 jvj/ j 0, j}AlorsKest ferm e etKo={s/ < s, vj> 0, j}Exercice {d/ < d, ai>= 0, < d, sj> 0, j, i}AlorsK={m i=1 iai+k j=1 jsj/ j 0, j}=(sous-espace vectoriel engendr e par lesai)+(c one convexe engendr e par lessj)Exercice et repr esenter les c ones tangents et normaux en(0,0) et (1,1) des :={(x, y) IR2/|x|+|y| 1} :={(x, y) IR2/max(|x|,|y|) 1} :={(x, y) IR2/x 0, y 0, y (1 x)3}104 Introduction `a l Dans le lin eaire :Un cas tr`es simple : fonction lin eaire et contraintes lin esolution avec l algorithme du Dans le convexeDans cette section on suppose queKest (K, a) est exactement l adh erence du c one engendr e parK a:T(K, a) =IR+(K a)Exercice directionsest dans [T(K, a)]osi et seulement si, pourtoutx K.

10 < s, x a > 0(sfait un angle optus avec toute direction rentrant dansK`a partir dea)Exercice et diff erentiable sur l ouvertO`a valeurdans IR, etKconvexe. Alors les minima defsurO Ksont exactement les x Kpour lesquels f( x) N(K, x). Introduction dans le diff erentiable :Sans aucune hypoth`ese on cherche une expression du premier ordre pourle c one :={x IRn/hi(x) = 0, i [1, .. , m], gj(x) 0, j [1, .. , p]}.O`u les poseJ( x) le sous ensemble de [1, .. , p] tqgj( x) = x K. Alors (K, x) {d/ < hi( x), d >= 0, i= 1, .. , m,;< gj( x), d > 0, i J( x)}2.[T(K, x)]o (sous espace vectoriel engendr e par les hi( x))+(c oneconvexe engendr e par les gj( x),j J( x))115 Optimisation sous contraintes d egalit eOn suppose les fonctionshide classeC1sur la suite nous posonsK:={x/hi(x) = 0, i= 1, .. , m}. Calcul du c one tangentOn poseA( x) :={d IRn/ < hi( x), d >= 0, i= 1.}