Optimisation et analyse convexe
OPTIMISATION. ET. ANALYSE CONVEXE. Exercices et problèmes corrigés avec rappels de cours. Jean-Baptiste Hiriart-Urruty. Collection dirigée par Daniel Guin.
Exercices corrigés
La fonction f est une somme de fonctions convexes elle est par conséquent convexe sur Df . Exercice 14.4. On consid`ere la fonction f définie sur R2 par f(x
Devoir Maison dOptimisation Numérique – Corrigé
Corrigé. Exercice 1 (6 points). Soit C ? R2 l'ensemble donné par Il n'est pas convexe parce que les point A0 = (1
Exercices corrigés Fonctions de deux variables Fonctions convexes
Pour optimiser f sous la contrainte de façon géométrique il faut déterminer les plus petit et plus grand k ? R tels que la courbe de niveau k de f coupe l'
QUELQUES EXERCICES CORRIGÉS DOPTIMISATION EXERCICE
1. 3y2 ? 1. ) . Rappelons que f est convexe sur R2 si et seulement si sa matrice hessienne est semi-définie positive en tout point. Or
Convexité et Optimisation
28 janv. 2009 3.8 Projection sur les convexes dans les espaces de Hilbert et séparation des convexes . ... Corrigé de l'Exercice 2.10 On note d'abord que.
Partiel du 26 Mars 2015—Corrigé “Optimisation et programmation
26 mars 2015 “Optimisation et programmation dynamique” ... convexe fermé non vide K de Rn. Si y = (yi)i=1...
ANALYSE RÉELLE OPTIMISATION LIBRE ET SOUS CONTRAINTE
Le but de l'UE est d'optimiser une fonction de deux variables : optimisation libre ou sous doivent être préparés : écouter le corrigé d'un exercice ...
Travaux dirigés. 1 Optimisation & Analyse convexe Séance 6
Séance 6 : Algorithmes pour l'optimisation avec contraintes. Exercice 1 (Algorithme d'Uzawa : Cas de contraintes d'égalité et inégalité). Corrigé 2 .
MS41 Optimisation I
29 juil. 2014 On a inclus dans ce texte nombreux exercices corrigés. ... Soit D un sous-ensemble convexe de R2 et f : D ? R une fonction.
[PDF] quelques exercices corrigés doptimisation
La fonction f est-elle convexe sur R2 ? 3 Déterminer les points critiques de f et préciser leur nature (minimum local maximum local point-selle
[PDF] OPTIMISATION ET ANALYSE CONVEXE - Numilog
OPTIMISATION ET ANALYSE CONVEXE Exercices et problèmes corrigés avec rappels de cours Jean-Baptiste Hiriart-Urruty Collection dirigée par Daniel Guin
[PDF] Exercices corrigés
(a) Montrer que D est un sous-ensemble convexe de R2 (b) Montrer que la fonction h = ln ?f est bien définie sur D et étudier la convexité ou la concavité de h
[PDF] 4GMM Lundi 12/01/2015 Analyse convexe & optimisation Durée
12 jan 2015 · Exercice 1 Pour les ensembles X suivants dites si l'ensemble est convexe et détermi- nez l'opérateur de projection ?X par la méthode de
[PDF] CC2 - Optimisation
6 jan 2014 · 4ème année CC2 - Optimisation Durée : 2h30 Seuls le polycopié de cours et les notes personnelles de cours sont autorisés Exercice 1
[PDF] Partiel du 26 Mars 2015—Corrigé “Optimisation et - Ceremade
26 mar 2015 · “Optimisation et programmation dynamique” convexe fermé non vide K de Rn Si y = (yi)i=1 m et z = (zi)i=1 m sont Exercice 1
[PDF] Travaux dirigés 1 Optimisation & Analyse convexe Séance 6
Séance 6 : Algorithmes pour l'optimisation avec contraintes Exercice 1 (Algorithme d'Uzawa : Cas de contraintes d'égalité et inégalité) Corrigé 2
[PDF] Exercices doptimisation et quelques corrigés - Laurent Lafleche
(4) Trouver le minimum et le maximum de f sur T Solution 1) La fonction f n'est ni convexe ni concave puisque elle est C2 et sa matrice
[PDF] Devoir Maison dOptimisation Numérique – Corrigé
Devoir Maison d'Optimisation Numérique – Corrigé Exercice 1 (6 points) Il n'est pas convexe parce que les point A0 = (12) et A1 = (?12)
[PDF] Optimisation Examen du mercredi 5 mai 2021 Corrigé
b) Montrer que U est un ensemble convexe et compact 2 c) Introduire deux fonctions g1 et g2 pour décrire U comme un ensemble de contraintes inégalités et
![[PDF] Devoir Maison dOptimisation Numérique – Corrigé [PDF] Devoir Maison dOptimisation Numérique – Corrigé](https://pdfprof.com/Listes/17/48730-17DMopti2012-corrig.pdf.pdf.jpg)
Devoir Maison d"Optimisation Numérique
-Corrigé Exercice 1(6 points).SoitC?R2l"ensemble donné par 1.Dessiner l"ensem bleC.
2.S"agit-il d"un ensem blecompact ?
3.S"agit-il d"un ensem blecon vexe?
4. Considérer la fonction fdonnée parf(x,y) =xy. Admet-elle un minimum et un maximum surC? 5. Calculer inf{f(x,y) : (x,y)?C}etsup{f(x,y) : (x,y)?C}.Solution⎷3-
⎷3⎷3 ⎷3C•A0•A
1•A
1/2L"ensembleCest bien compact, puisqu"il est fermé (à cause de l"inégalité large dans la définition) et borné
Il n"est pas convexe, parce que les pointA0= (1,2)etA1= (-1,2)appartiennent àCmais leur point intermédiaireA1/2= (0,2)n"y appartient pas puisque22+ (02-1)2= 5>4. La fonctionfest continue et elle admet donc in minimum et un maximum surCpar le théorème deWeierstrass.
et?g(x,y) = (4x(x2-1),2y). Les deux fontionsfetgsont bien dérivables partout (elles sontC1). Lafonctiongpermet d"appliquer le théorème des multiplicatuers des Lagrange parce que?g= 0seulement
en(0,0),(1,0)et(-1,0), qui n"appartiennent pas à l"ensemble oùg= 0(le bord deC). Les points candidats à la minimisation et à la maximisation sont donc les p ointsoù ?f= 0, c"est-à-dire juste(0,0) les p ointsoù le sys tèmedonné par le m ultiplicateurde Lagrange est satisfait ??y= 4λx(x2-1), x= 2λy, y2+ (x2-1)2= 4.
Pour résoudre le système remarquons d"abord queλne peut pas être nul (sinon on auraitx=y= 0mais
la troisième équation n"est pas satisfaite). Nous pouvons ensuite multiplier les deux premières équations
entre elles après avoir réécrit la deuxième comme2λy=xet nous obtenons2λy2= 4λx2(x2-1).
Avec la troisième équation, et en divisant par2λ?= 0, cela donne4-(x2-1)2= 2x2(x2-1).
Posonst=x2-1. On at≥ -1et
4-t2= 2t(t+ 1),
qui est une équation d"ordre deux dont les solutions sont t=-1±⎷13 3 mais seulementt= (-1 +⎷13)/3satisfaitt≥ -1. On trouve alorsx=±⎷t+ 1 =±?(2 + ⎷13)/3. En correspondance de cela, on trouvey=±⎷4-t2=±?22 + 2 ⎷13/3. Les point sur les bords qui sont candidats à l"optimisation sont donc (x,y) =(±?2 +
⎷13 3 ,±?22 + 2 ⎷13 3Il est évident que les deux choix oùxetyont le même signe donnent une valeur defégale et positive,
les deux avec signes opposés égale et négative, et on compare cela avecf(0,0) = 0.On a donc
maxCf=?2 +
⎷13 3·?22 + 2
⎷13 3 minCf=-?2 + ⎷13 3·?22 + 2
⎷13 3 Exercice 2(5 points).Soitf:R3→Rla fonction définie parf(x1,x2,x3) =|x1|+|x2|2+|x3|3.S"agiti-il d"une fonction convexe? strictement convexe? écrire son sous-différentiel∂f(x)en tout point
x= (x1,x2,x3).Solution
La fonctionfest convexe en tant que somme de fonctions convexes d"une variable. Pourtant, elle n"estpas strictement convexe parce que la partie qui porte surx1ne l"est pas, et elle est indépendante des deux
autres. Par exemple, en prenantf(1,0,0),f(3,0,0)etf(2,0,0)on trouve une contradiction à la stricte
convexité.En tout point(x1,x2,x3)avecx1?= 0la fonctionfest différentiable et son gradient vaut?f(x1,x2,x3) =
(signe(x1),2x2,3x23signe(x3)). Si on prend un point du type(0,x2,x3)on ap= (p1,p2,p3)?∂f(0,x2,x3)si et seulement si ?(h1,h2,h3)|h1|+|x2+h2|2+|x3+h3|3≥0 +|x2|2+|x3|3+h1p1+h2p2+h3p3. En prenanth1=h2= 0eth3→0on trouve forcémentp3= 3x23signe(x3), et en prenanth1=h3= 0et h2→0on trouve forcémentp2= 2x2. En prenanth2=h3= 0on a ensuite
|h1| ≥p1h1On sait donc que tout élément de∂f(0,x2,x3)est de la forme(t,2x2,3x23signe(x3))pourt?[-1,1].
D"autre part, ce n"est pas difficile de vérifier, en utilisant la convexité dex2?→ |x2|2etx3?→ |x3|3, et
l"inégalité|h1| ≥p1h1pour touth1?Ret toutp1?[-1,1], que tout vecteur de cette forme appartient
bien à∂f(0,x2,x3).Nous avons finalement
∂f(x1,x2,x3) =?{(signe(x1),2x2,3x23signe(x3))}six1?= 0 {(t,2x2,3x23signe(x3)) :t?[-1,1]}six1= 0. 2Exercice 3(4 points).Suggérer et décrire une méthode numérique itérative efficace pour résoudre le
problème de projection min||x-a||:x?E oùa= (a1,a2,...,an)?Rnest fixé etPour que la réponse soit satisfaisante, il faut expliquer à chaque étape les calculs qu"on doit faire et
comment les faire. Il pourrait éventuellement être utile de reformuler le problème de manière équivalente
(changer variables, minimiser une fonction différente mais avec les mêmes minimiseurs...).Solution
Il y a plusieurs possibilités qu"on ne détaillera pas complètement. Dans tous les cas, il vaut mieux remplacer
||x-a||avec12 ||x-a||2. Une possibilité est d"utiliser l"algorithme d"Uzawa pour résoudre min xsup i≥012 ||x-a||2+n-1? i=1λ i(xi-xi+1). Ceci donne lieu à une suite calculée comme suit x k= argminx12 ||x-a||2+n-1? i=1λki(xi-xi+1), c"est-à-dire ??x k1=a1-λk1, x ki=ai-λki+λki-1, x kn=an+λkn-1;et ensuite on définitλk+1i= (λki+ρ(xki-xki+1)+, pour un petit paramètreρ. La suite desxkci-obtenue
converge alors vers le miniseur.D"autres possibilité : réécrire le problème comme un problème de minimisation sur(x1,y2,y3,...,yn)avec
x1?R,yi≥0etxi=x1+?ij=2yj, du coup cela donne
min x1?R,yi≥0n
i=1( x1+ (i? j=2y j)-ai) )2Dans ce problème l"expression de la fonctionnelle est plus difficile (mais toujours quadratique) mais la
contrainte est plus simple. On peut envisager un algorithme de gradient projeté. Troisième possibilité : méthode pénalisation min x12 ||x-a||2+1ε n-1? i=1(xi-xi+1)2+. Pour une réponse complète il serait bien d"indiquer comment calculer lexεoptimal. Exercice 4(5 points).SoitK?Rnun sous-ensemble fermé. Pourx?Rnon définitd(x,K) = inf{|x-y|: y?K}. 1. P eut-ondire que la b orneinférieure dans la définition de d(x,K)est atteinte? pourquoi? 2. Donner un exemple d"ensem bleKet de pointxtelle que cette borne est atteinte mais en plusieurs pointsy?K(un dessin pourrait suffire). 3.La fonction x?→d(x,K)est-elle continue?
4. Donner un exemple où la fonction x?→d(x,K)n"est pas convexe. 35.P eut-ondire qu"elle con vexe,si on ra joutel"h ypothèseque Ksoit convexe?
Solution
La borne est atteinte même siKn"est pas borné (auquel cas il serait compact) parce que la fonction que
l"on minimise est coercive, et la minimisation peut se faire sur un compact, donc. SiK={A,B}avecA?=Ble point(A+B)/2est à distance égale deAet deB, il a donc deux projections. Pour toutyla fonctionx?→ |x-y|est Lipschitzienne de constante1. Par conséquent, la fonction d(x,K) = inf{|x-y|:y?K}l"est aussi (commeinfd"une famille de fonctions Lipschitizienne avec la même distance). SiK={A,B}avecA?=B, le point(A+B)/2on adK(A) =dK(B) = 0alors quedK((A+B)/2) = |A-B|/2>0, ce qui démontre quedKn"est pas convexe. Par contre, siKest convexe, considéronsx0,x1?Rnety0,y1?Kleurs projections respectives. Soit t?[0,1]. Le pointyt= (1-t)y0+ty1appartient àKparce queKest convexe. Or, soitxt:= (1-t)x0+tx1 d ce qui montre la convexité dedK. Exercice 5(5 points).Considérer la fonctionnelleFsuivanteF(u) :=?
1 0? 12 u?(t)2+ 64|u(t)|7/4? dt et le problème de minimisation minF(u) :u?C1([0,1]), u(1) = 16?
1.Écrire l"é quationd"Euler-Lagrange corresp ondanteà ce problème de minimisation, a vecles condi-
tions au bord opportunes. 2. T rouverune solution ¯ude cette équation, en la cherchant de la forme¯u(t) =Atα. 3.Justifier qu e¯uest solution du problème de minimisation, qu"elle est la seule solution du problème
de minimisation et aussi la seule solution de l"équation avec ses conditions au bord.Solution
Nous utilisons la fonctionL(t,x,v) =12
|v|2+ 64|x|7/4. On a ∂L∂x (t,x,v) = 16·7|x|3/4signe(x),∂L∂v (t,x,v) =v,ce qui nous permet d"obtenir l"équation d"Euler-Lagrange et la condition de transversalité au pointt= 0
(ent= 1la valeur est fixée), et donc le système ??u ??(t) = 16·7|u(t)|3/4signe(u(t)), u ?(0) = 0, u(1) = 16.Si on cherche une solution du typeu(t) =Atαon doit choisirA= 16pour satisfaire la dernière équation
etα >1suffit pour la deuxième. Pour satisfaire la première il faut imposerα(α-1)Atα-2= 16·7·A3/4t34
(le signe est positif), qui impose en particulierα-2 =34 α,d"oùα= 8. On peut alors vérifier que la fonctionu(t) = 16t8est bien solution de l"équation, puisqueu??(t) = 16·8·7t6et|u(t)|3/4signe(u(t)) = 8t6.
La fonctionLétant convexe, minimiser et résoudre le système sont deux notions équivalentes;Létant
également strictement convexe, la solution du problème de minimisation est unique. On en déduit queu
est la seule solution du système aussi (attention, les calculs qu"on a fait auparavant nous avaient juste dit
qu"elle étaient la seule solutionde la formeu(t) =Atα). 4quotesdbs_dbs29.pdfusesText_35[PDF] cours doptimisation pour économistes
[PDF] cours optimisation sans contrainte
[PDF] resume cours optique geometrique
[PDF] cours de physique optique cours et exercices corrigés pdf
[PDF] examen corrigé optique ondulatoire
[PDF] résumé cours optique ondulatoire
[PDF] physique optique cours complet
[PDF] controle optique 1ere s
[PDF] orientation scolaire et professionnelle définition
[PDF] oxydoréduction cours bac pro
[PDF] programme daeu b physique
[PDF] programme daeu a
[PDF] cours physique daeu b pdf
[PDF] cours chimie daeu b