Scribd
Importer
5 vues6 pages

TD2 Optimisation

Le document présente une série d'exercices d'optimisation mathématique, incluant des problèmes sur la détermination des points critiques, la convexité des fonctions, et l'application de théorèmes d'optimisation comme celui de Weierstrass. Il aborde également des algorithmes d'optimisation, tels que la dichotomie et la section dorée, en détaillant leur convergence et leur vitesse. Enfin, il traite de la convexité de divers ensembles et de la recherche de minima et maxima sous contraintes.

Transféré par

Dieudonné Zongo
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF ou lisez en ligne sur Scribd
5 vues6 pages

TD2 Optimisation

Le document présente une série d'exercices d'optimisation mathématique, incluant des problèmes sur la détermination des points critiques, la convexité des fonctions, et l'application de théorèmes d'optimisation comme celui de Weierstrass. Il aborde également des algorithmes d'optimisation, tels que la dichotomie et la section dorée, en détaillant leur convergence et leur vitesse. Enfin, il traite de la convexité de divers ensembles et de la recherche de minima et maxima sous contraintes.

Transféré par

Dieudonné Zongo
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF ou lisez en ligne sur Scribd
Exercices d’optimisation et quelques corrigés 1. Optimisation DE FONCTIONS, HnsSIENNE, CONVEXITE, Exercice 1. Soit l'application f : R? —> IR définie par Flog) = eye) Déterminer les points critiques de f ainsi que leur nature : maximum ou minimum local, point-selle, maximum ou minimum global. Exercice 2, Soit les fonctions f, g et h définies sur ? par f(x,y) = 2' + y! g(x,y) = (e-y)Peth= f-2g. (1) Montrer que les fonctions f et g sont convexes sur nest ni convexe ni concave sur (2) La fonction h admet-elle un minimum ow un maximum sur? (3) Déterminer les points critiques de h, et préciser leur nature. mais que hh = f —29 Exercice 3. Soit f la fonction définie sur R° par f(x,y,2) = x¢ —22y + 2y? Qyz+22— A245, (1) Déterminer les points critiques de f sur R® (2) Montrer que l'expression f(r, y, 2) peut s’écrire sous forme d'une somme de carrés. (3) En déduire les extrema de f sur RS. Exercice 4. Soit f : RS + R donnée par f( maximale et la valeur minimale de f sur By aprés avoir démontré qu’ elles existent. .Y,2) = ry +y2+ 22, Trouver la valeur {(2,y,2) RS a? ty? +2 <1}, Exercice 5. Soit TC R? l'ensemble T= { (ey) eR: 220y202+ys1} Soit f la fonction donnée par f(x,y) = —z — 2y — 2zy + 52? + (1) fest-elle convexe ? concave ? (2) Démontrer que tout minimum ou maximum local de f sur 7’ se trouve sur la frontiére de T. (3) Démontrer que f admet bien un minimum et un maximum sur T. (4) Trouver le minimum et le maximum de f sur 7. Solution. 1) La fonction f n’est ni convexe ni concave, puisque elle est C? et samatrice Hessienne est Fey) 1-2 Piste =(_5 t): t 2 de déterminant det(D?f) = —3 < 0, ce qui implique que ses valeurs propres sont de signe opposé. 2) Siily avait un minimum ou maximum local 8 intérieur il devrait annuler Vf. Or, Vi (x,y) = (-1—2y +2, -2— 24 + y) = 0 seulement pour (x, y) = )¢e donc il n'est pas possible que f ait un minimum ou un maximum local 3 I'intérieur. 3) La fonction f est continue et C’ est fermé (par les inégalités larges) et borné (T. est inclus dans la boule unité), donc compact. On peut done utiliser le théoreme de Weierstrass, 4) On fait une liste de candidats & optimisation : il n'y a pas de points & Vintérieur, ils sont donc sur la frontiére. Cette frontitre est composée de 6 parties : les trois sommets (0,0), (1, 0) et (0, 1), etles trois c6tés (0, y) avec y €]0, 1], (x, 0) avec €]0, 1[ et (x,y) avec x,y €]0, I[eta + y = 1, Sur ce demier c6té nous pouvons appliquer le multiplicateur de Lagrange, en imposant Vf = A (1,1), of (1, 1) est le gradient de la fonction « + y. On trouve alors —1 — 2y A= -2— 20 + y, ce qui donne le systéme -1-2yt2=-2-2ty rty-l 4,3). Pour les autres cétés il n’est pas nécessaire de qui a pour solution (x,y) = ( faire de multiplicateurs de Lagrange, il suffit d’étudier (0,y) = —2y + 4y?, dont la dérivée s'annule pour y = 2, c’est-a-dire hors de l'intervalle qui nous intéresse, et f(x, 0) ax + $2, dont la dérivée s’annule pour x = 1, ce qui est aussi hors de Vintervalle d’intérét (c'est sur son bord). Les points intéressants sont done (0,0), (1,0), (0, 1) et (3,3) etona (0,0) = FO, =-}, fO0=-3, fGH= Le minimum est done réalisé en ( et vaut 0, 3 Exercice 6, Déterminer les extrema locaux des fonctions suivantes sur R? A(zy) =284+32y?—152-12y A(z,y) =325+2y?-3ary fsley) = 24 +y9/3—4y 2 Ailzy) =o +ay— xy? Pour chaque fonction, montrer que les extrema locaux ne sont pas globaux. Exercice 7. Les sous-ensembles de IR? suivants sont-ils convexes ? A= { (zu) €R? :2y>0} Az = { (,y) €R? eeypaoty+lfi 4. 3) La fonction f est continue sur un ensemble compact et elle admet donc un minimum et un maximum sur C' par le théoréme de Weierstrass. 4) Sioncalcule Vf on obtient V f(x, y) = (y, x). La contrainte peut s’écrire sous la forme g(x, y) < O avec g(x,y) — y? +(x? —1)? —4et Vg(x, y) — (4 (2? — 1), 2y) Les deux fonctions f et g sont bien dérivables partout (elles sont C), La fonction g 4 permet d’appliquer le théor&me des multiplicateurs de Lagrange parce que Vg = 0 seulement en (0,0), (1, 0) et (—1, 0), qui n’appartiennent pas ensemble od g = 0 (le bord de C). Les points candidats & la minimisation et & la maximisation sont done # les points od Vf = 0, c'est-dedire juste (0,0), « les points od le systéme donné par le multiplicateur de Lagrange est satisfait y=4X2(2?~1), Ay, 24 (421)? w+ (e?-1) Pour résoudre le systéme on remarque d’abord que A ne peut pas étre nul (sinon on aurait x = y = 0 mais la troisiéme équation n'est pas satisfaite). En multipliant les deux premiéres équations entre elles aprés avoir réécrit la deuxiéme comme 2. y = x. on obtient 2dy? = 4 Az? (2? 1) Avec la troisiéme équation, et en divisant par 2. # 0, cela donne 4— (a? — 1)? = 22°(2? - 1). En posant t = 2? — 1, onat > —Let 4—-P=2t(t+)) qui est une équation d’ordre deux dont les solutions sont -ltvB 3 mais seulement ¢ = (—1+ YT3)/3 satisfait > —1. On trouve done z = +4 42+ V13)/3. Grace a la troisigme équation du systéme des multiplicateurs de Lagrange, on obtient y = +V4 +22 + 2V113/3. Les point sur les bords qui sont candidats & l'optimisation sont done + VI3 wees) t 3 3 Les deux choix ot x et y ont le méme signe donnent une valeur de f égale et positive, les deux avec signes opposés égale et négative, et on compare cela avec (0,0) = 0. On en déduit que 22 + 2vT3 ae mins 3 3 [22-4 2v73 3 Exercice 9. Soit Cc IR? l'ensemble donné par cm {ener (2-1) +his4} (1) Dessiner l'ensemble C. (2) S’agit-il d’un ensemble compact ? S’agit-il d’un ensemble convexe ? (3) Considérer la fonction f donnée par f(r, y)=27+y. Admet-elle un minimum et un maximum sur C'? (4) Calculer inf { f(x,y) : (x,y) € C }etsup { f(x,y) : (x,y) © C} Exercice 10, Optimiser les fonctions suivantes sur leurs domaines Flx,yy2) = at + 2y? +32? — ys By t4e—5 g(21,---,tn) j An...) = I] 2 Exercice 11. Soit / : R — B strictement convexe, c € Ret n € N. Sous la contrainte Ly # = 6 trouver infimum et le supremum de She) 2. ALGORITHMES D’ OPTIMISATION ET VITESSE DE CONVERGENCE Exercice 12 (Dichotomie). Soit f € C"(Ja, |, B) qui ne posséde qu'un seul optimum. (1) Montrer qu'il existe (a9, bo) €]a, b tels que ay < by et f"(ao) et f"(bo) sont de signes différents (2) On suppose que /’(ao) < 0 < f"(bo) et que optimum est le seul point critique et on effectue I’algorithme par récurrence suivant. Pour tout n > 0, on définit Gn = 4 (a + bn), puis on pose (ann) si f'(en) > 0 (Qnst, bret) =} (Garb) Si f'(en) <0 (caen) si f'(en) =0 Montrer que I’algorithme converge vers le minimum global de . (3) Calculer la vitesse de convergence de l'algorithme, (4) Proposer un algorithme dans le cas od "(bo) < 0 < f"(a0). Exercice 13 (Algorithme de la section dorée). Soit f € C({a, b], R) dont le minimum. est le seul extremum local dans Ja, 6/. On définit pour n = 0, Jy, = [a6]. On choisit ensuite 7 €]0, 1[ et on effectue Ialgorithme suivant. On définit c = a +7 (b—a) puis d = +7 (bc). Si f(c) < f(d), on définit Jn = {a,d], sinon on définit Jy... Tt (1) Pour optimiser ’algorithme, on fait en sorte que les deux possibilités d’intervalle a chaque pas sont de méme taille. Trouver alors la valeur de 7. (2) Montrer que ’algorithme converge vers le minimum de f et calculer sa vitesse de convergence = (c,8]. On recommence alors I'algorithme sur 6 Exercice 14. Soit ¢ > 0 et By = {2 ERY, |r|? =a} +a}+---+23 <1}. Cae culer le vitesse de convergence de l’algorithme de gradient a pas fixe pour trouver Je minimum de la fonction f : B, + R définie par f(r) = |x|?** avec un pas a <1/(24 6). On pourra regarder la suite 1/ |x|" ow x) est la n-iéme valeur donnée par l’algorithme. Solution. Pour obtenir une expression explicite des pas de I’ algorithme, on commence par calculer le gradient de f. On peut écrire f = goh avec h: R* > R. définie par h(x) = |x|? = 2-2 et g: Ry > R définie par g(r) = r'*/?, Comme Vh(x) = Var- x = 2, onen déduit que c+2 2 V(t) = g(h(e)) Vax) = (jeP)? 22 = (c+2)[al* Sion écrit x“) le n-idme point calculé par l’algorithme, on a donc 2) — 20) 0,0 < tint S tty < Let vérific tiger = (1a (6 +.2) uf) ty Done la suite est bornée et décroissante. En particulier, elle admet une limite € € [0, 1 qui vérifie £ = [1 — a (c +2) |, ce qui donne ¢ = 0. On regarde maintenant sa vitesse de convergence. On regarde 1 11 1 /1-(-a(e+2) ut)" wy wm wu \l-ale ug \ (=a(e+2) ug) En utilisant le fait que 1 — (1 ~ 2)" ~ ex et (1~sr)° ~ 1 lorsque x + 0, on en déduit que 11 1 facle+2) us bE (seer) _ gefes9), Wa eG lorsque n + oo. En utilisant le fait que l’équivalence de suites positives associées & des séries divergentes entraine I’équivalence des sommes partielles, on en déduit que 1 1 1 << f, --l- -4+~Saclc+2)=acle+2)n, mm “ak ce qui entraine que 1 (ae(e+2)n)*

Vous aimerez peut-être aussi