Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Ecole Nationale Supérieure de Techniques Avancées (ENSTA) - http://www.ensta.fr

Ecole Nationale Supérieure de Techniques Avancées (ENSTA) - http://www.ensta.fr Ce document est mis à votre disposition par l'ENSTA sous couvert de la licence "Creative Commons" Travaux dirig´ es. 1 Optimisation & Analyse convexe S´ eance 1 : Existence d’un minimum. Convexit´ e Exercice 1 Soit A ∈I Rn×n une matrice sym´ etrique, et b un vecteur de I Rn. On consid` ere la fonction : f : x ∈I Rn 7− →1 2(x, Ax) −(b, x). 1. Soient λmin et λmax la plus petite et la plus grande valeur propre de A. Montrer que ∀x ∈I Rn λmin∥x∥2 2 ≤(Ax, x) ≤λmax∥x∥2 2. 2. Montrer que f est d´ erivable sur I Rn. Calculer d f(x) et ∇f(x), pour x ∈I Rn. 3. Supposons maintenant que A est sym´ etrique positive. Montrer que dans ce cas, A est inversible si et seulement A est d´ eﬁnie positive. Corrig´ e 1 1. La matice A est sym´ etrique, toutes ses valeurs propres λi sont r´ eelles (eventuellement nulles), et elle admet une base de vecteurs propres orthonorm´ es B = {v1, v2, · · · , vn} : Avi = λivi pour i = 1, 2, · · · , n et (vi, vj) = δij pour i, j = 1, 2, · · · , n. Pour tout vecteur x ∈I Rn, on a donc x = n X i=1 xivi, Ax = n X i=1 xiAvi = n X i=1 λixivi et (Ax, x) = n X i=1 λix2 i soit ﬁnalement min i λi n X i=1 x2 i ≤(Ax, x) ≤max i λi n X i=1 x2 i . 2. Pour tout h ∈I Rn, on a f(x + h) = 1 2(A(x + h), x + h) −(b, x + h) = 1 2(Ax, x) + (Ax, h) + 1 2(Ah, h) −(b, x) −(b, h) = f(x) + (Ax −b, h) + 1 2(Ah, h). Si on pose ε(h) = 1 2(Ah, h)/∥h∥2, alors |(Ah, h)| ≤∥A∥∥h∥2 2 ⇒lim h→0 |ε(h)| = 0. Soit d f(x).h = (Ax −b, h) et ∇f(x) = Ax −b. Commentaire : Dans le cas g´ en´ eral (A non sym´ etrique) : f(x) = 1 2(x, (A + AT ) 2 x) −(b, x); d f(x).h = (1 2(A + AT )x −b, h) et ∇f(x) = 1 2(A + AT )x −b. Ecole Nationale Supérieure de Techniques Avancées (ENSTA) - http://www.ensta.fr Ce document est mis à votre disposition par l'ENSTA sous couvert de la licence "Creative Commons" 2 Travaux dirig´ es. 3. Supposons que A soit inversible. Soit w tel que (Aw, w) = 0. On va montrer que w est en fait ´ egal ` a z´ ero. Soient d ∈I Rn (d ̸= 0) et λ > 0. Comme A est positive et sym´ etrique : 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 c’est valable pour toute direction (d ∈I Rn), on en d´ eduit que Aw = 0, ce qui conduit enﬁn ` a w = 0 par hypoth` ese sur A. La r´ eciproque est ais´ ee et classique. En eﬀet, si A est d´ eﬁnie-positive, Aw = 0 entraˆ ıne que (Aw, w) = 0, et donc que w = 0 : par cons´ equent, A est inversible. Exercice 2 Soit f : I Rn →I R , f(x) = 1 2(x, Ax) −(b, x) + c avec A une matrice n × n sym´ etrique, b ∈I Rn, c ∈I R. 1. Montrer que f admet un minimum sur tout compact K de I Rn. 2. Montrer que f est convexe ssi A est positive1. 3. Montrer que f est stritement convexe ssi A est d´ eﬁnie positive. 4. Montrer que si A est d´ eﬁnie positive, alors f est “inﬁnie ` a l’inﬁni”et admet un minimum unique sur tout ferm´ e convexe K ⊂I Rn. 5. Montrer que, s’ils existent, les minima de f v´ eriﬁent la relation Ax = b. En d´ eduire que si A est non positive, alors f n’admet pas de minimum sur I Rn. Corrig´ e 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 ∈I Rn, (∇f(y) −∇f(x), y −x) ≥0. D’autre part, on a ∇f(x) = Ax −b. Il vient alors : f est convexe ⇔ ((Ay −b) −(Ax −b), y −x) ≥0 ∀y, x ∈I Rn ⇔ (A(y −x), y −x) ≥0 ∀y, x ∈I Rn ⇔ (Az, z) ≥0 ∀z ∈I Rn ⇔ A est positive. 3. La stricte convexit´ e de f est equivalente ` a : ∀x ̸= y ∈I Rn, (∇f(y) −∇f(x), y −x) > 0. 4. Supposons que la matrice A est sym´ etrique d´ eﬁnie positive. Donc d’apr` es l’exercice 1, on peut minorer la foncion f par : f(x) ≥1 2λmin(A)∥x∥2 2 −∥b∥2∥x∥2 + c, avec λmin(A) > 0 et lim z→+∞ 1 2λmin(A)z2 −∥b∥2z + c = +∞. On en d´ eduit alors que : lim x∈K,∥x∥→+∞f(x) = +∞; pour tout ensemble ferm´ e K de I Rn. f est alors “inﬁnie ` a l’inﬁni” et strictement convexe, elle admet donc un minimum unique sur tout ferm´ e convexe K. 1c’est ` a dire (Av, v) ≥0 pour tout v ∈I Rn. On parle aussi dans certains livres de semi-d´ eﬁnie positive Ecole Nationale Supérieure de Techniques Avancées (ENSTA) - http://www.ensta.fr Ce document est mis à votre disposition par l'ENSTA sous couvert de la licence "Creative Commons" Travaux dirig´ es. 3 5. Supposons que f atteint le minimum en x ∈I Rn, 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 ∈I Rn et pour tout λ > 0 assez petit tel que x + λd ∈V . En divisant par λ et en faisant tendre λ vers 0 par valeurs sup´ erieures, on en d´ eduit que x satisfait : ∇f(x).d = (Ax −b, d) ≥0, ∀d ∈I Rn. Ou encore, puisque d parcourt I Rn, Ax = b. D’autre 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 ∈I Rn (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 compos´ ee 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β (β ∈I N), ℓ(x) = |x|β (β > 1)? 3. Soit ∥·∥une norme de I Rn. Montrer que x ∈I Rn 7− →∥x∥et x ∈I Rn 7− →∥x∥2 sont convexes. Corrig´ e 3 1. La compos´ ee de deux fonctions convexes n’est pas forc´ ement convexe. En eﬀet, les fonctions g : x 7− →e−x et f : x 7− →x2 sont bien convexes sur R, et pourtant g ◦f : x 7− →e−x2 n’est pas convexe sur I R ! Par contre, on peut facilement v´ eriﬁer le r´ esultat suivant : Soit K une partie convexe de I R. Soient f : I Rn − →K une fonction convexe et g : K − →I R une fonction convexe croissante. Alors g ◦f est convexe. 2. La fonction f est strictement convexe (sur I R∗ +), mais n’est pas α−convexe. La fonction g n’est pas convexe sur I R, mais est convexe sur les intervalles ] −∞, − √ 6 6 ] et [ √ 6 6 , +∞[. Pour β ∈{0, 1}, la fonction h est convexe. Pour β ≥2, h n’est convexe sur I R que si β est paire. Dans le cas β = 2, h est α-convexe avec α = 2. La fonction ℓse d´ ecompose en s ◦r o` u s et r sont d´ eﬁnies par : s : x ∈I R+ 7− →xβ, r : x ∈I R 7− →|x|. Il est facile de v´ eriﬁer que r est strictement convexe, et s est strictement convexe et croissante sur I R+. On conclut alors que pour β > 1, ℓest strictement convexe sur I R. Ecole Nationale Supérieure de Techniques Avancées (ENSTA) - http://www.ensta.fr Ce document est mis à votre disposition par l'ENSTA sous couvert de la licence "Creative Commons" 4 Travaux dirig´ es. Exercice 4 Soit f de I R2 dans I R2 d´ eﬁnie par : f(x, y) =    xy p x2 + y2 si (x, y) ̸= (0, 0) 0 sinon. 1. Montrer que f est continue en (0, 0). 2. Montrer que f n’est pas diﬀ´ erentiable en (0, 0). 3. Est-elle uploads/Litterature/ corrige-optimisation.pdf