Conditions doptimalité en optimisation avec contraintes
ède un minimum global sur lorsque le vecteur de multiplicateur . Si. 0 . 0 et. 0 pour tout 1
MAT 2410: Optimisation
Chapitre 4. Optimisation différentiable avec contraintes Si U = Rn on retrouve la condition d'optimalité sans contrainte: ?f (a) = 0.
Optimisation sans contrainte : conditions doptimalité
Optimisation sans contrainte : conditions d'optimalité. Michel Bierlaire michel.bierlaire@epfl.ch. EPFL - Laboratoire Transport et Mobilit´e - ENAC.
COURS DOPTIMISATION AVEC CONTRAINTES [.2pc] Polytch
Problème d'optimisation avec contraintes p contrainte d'inégalité' du problème ... Théorème (Conditions (nécessaires) d'optimalité du 1er ordre).
IFT 3515 Fonctions `a plusieurs variables Optimisation avec
Optimisation avec contraintes. Conditions d'optimalité. Fabian Bastin. DIRO. Université de Montréal Multiplicateurs de Lagrange : contraintes d'égalité.
Introduction à loptimisation
4 Conditions d'optimalité - optimisation sous contraintes. 25. 4.1 Multiplicateurs de Lagrange Formule de Taylor avec reste de Lagrange.
Présentation PowerPoint
1.2 Contraintes linéaires. 1.3 Contraintes non linéaires. 1.4 Conditions d'optimalité. 2. Optimisation sans contraintes. 3. Optimisation avec contraintes.
Université Paris Dauphine Optimisation et programmation dynamique
l'optimisation avec contraintes d'une part
Optimisation
7. feb. 2019 5 Optimisation sous contraintes d'inégalité. Généralités. Conditions d'optimalité. 6 Algorithmes d'optimisation avec contraintes.
Contrôle optimal déquations différentielles avec - ou sans - mémoire
5. des. 2013 naires les conditions d'optimalité standards sont renforcées en ne ... with therapeutic optimization as a medical application in view.
Introduction à l"optimisation
Première Partie : aspects théoriques
Univ. Rennes 1, E.N.S. Rennes
Yannick Privat?
?ENS Cachan Bretagne, CNRS, Univ. Rennes 1, IRMAR, av. Robert Schuman, F-35170 Bruz, France; yannick.privat@bretagne.ens-cachan.fr 1TABLE DES MATIÈRES2
Tabledes matières
1 Introduction3
1.1 Le programme de l"agrégation . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . 3
1.2 Le vocabulaire de l"optimisation . . . . . . . . . . . . . . . . . . .. . . . . . . . . . 3
1.3 Quelques rappels de calcul différentiel . . . . . . . . . . . . .. . . . . . . . . . . . 4
1.4 Détour vers la dimension finie . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . 6
2 Questions d"existence et unicité des solutions8
2.1 Existence en dimension finie . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . 8
2.2 Unicité de l"optimum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . 11
2.3 Existence en dimension infinie? . . . . . . . . . . . . . . . . . . . . .. . . . . . . . 14
3 Conditions d"optimalité - optimisation sans contrainte 19
3.1 Conditions d"optimalité - optimisation sans contrainte . . . . . . . . . . . . . . . 20
3.2 Minimisation d"une fonctionnelle quadratique sans contrainte . . . . . . . . . . . 22
3.3 La méthode des moindres carrés . . . . . . . . . . . . . . . . . . . . . .. . . . . . . 23
4 Conditions d"optimalité - optimisation souscontraintes25
4.1 Multiplicateurs de Lagrange, le théorème des extrema liés . . . . . . . . . . . . . . 25
4.2 Les théorèmes de F. John et Karush-Kuhn-Tucker . . . . . . . .. . . . . . . . . . . 31
1 INTRODUCTION3
1 Introduction
1.1 Le programme de l"agrégation
• Optimisation et approximation • Interpolation de Lagrange. • Extremums des fonctions r Oelles denvariables réelles : multiplicateurs de Lagrange. • Mise en oeuvre de l"algorithme de gradient à pas constant. • Méthode des moindres carrés et applications.L"interpolation de Lagrange et les algorithmes de gradients seront étudiés ultérieurement, au
cours de la préparation.1.2 Le vocabulaire de l"optimisation
SoitVest un espace vectoriel normé, muni de la norme?·?. Dans ce cours, on s"intéresse au problème suivant?inff(x) x?K,(1) oùK?Vetf:K-→Rest une fonction, appeléefonction coûtoucritère. • SiK=V, on dit que (1) est un problème d"optimisationsans contrainte. • SiK?V, on dit que (1) est un problème d"optimisationsous contrainte. • Si dimK< +∞(resp. dimK= +∞), on dit que (1) est un problème d"optimisation en dimension finie (resp. infinie). Remarquons que ce formalisme englobe tous les problèmes d"optimisation, y compris les pro- blèmes de maximisation puisque maximiser une quantité revient à minimiser son opposé. Dans le cadre de ce cours, on étudiera essentiellement l"optimisation en dimension finie, conformémentauprogramme del"agrégation. Nousadopteronslaconventionsuivante:sil"on veut indiquer que la valeur du minimum est atteinte, on écrira ?minf(x) x?K, tandis que l"on utilisera la notation inf" quand on ne sait pasa priorisi la valeur de la borne inférieure est, ou non atteinte. Enfin, rappelons que toute partie minorée non vide deRadmet une borne inférieure, caractérisée de la façon suivante :Proposition 1.1. Suites minimisantes
SoitX, une partie minorée non vide deR.
Alors, les assertions suivantes sont équivalentes : im=inf{x,x?X}; ii?ε>0,?x?X|m?xProblème 1.(dimension finie)
?→Déterminerleparallélépipèderectanglede volumemaximalparmiceuxdontlasurface extérieure vaut 6.En introduisanta,betc, les longueurs des côtés du parallélépipède, on se ramène à la
résolution du problème???supV(a,b,c)=abc ab+ac+bc=3, a?0,b?0,c?0. Il s"agit donc d"un problème d"optimisation dansR3sous contrainte.Problème 2.(dimension infinie)
?→Problème de la reine Didon. Le problème consiste à trouver la courbe plane de longueur?fixée qui enclot avec le segment reliant ses deux extrémités, la portion plane d"aire maximale, autrement dit, on résout pourb>a?0, ?sup b a y(x)dx b a?1+y?2(x)dx=?,y(a)=y(b)=0,
y?Y, oùYest un espace fonctionnel donné (choisi par exemple de sorteque ce problème possède une solution).1.3 Quelques rappels de calcul différentiel
Commençons par la notion dedifférentiabilité. (voir par exemple [1, 6])1 INTRODUCTION5
Définition 1.2. Différentiabilité
SoientEetF, deux espaces vectoriels normés réels. SoitU, un ouvert deEetx0?U. On dit qu"une applicationf:U-→Festdifférentiable enx0ou admet un déve- loppement limité au premier ordre enx0 s"il existed fx0?L(E,F)(continue), telle que f(x0+h)-f(x0)=d fx0(h)+oh→0(?h?E).Quelques remarques immédiates :
• En dimension infinie, la différentiabilité d"une fonctiondépend de la norme dont sont
munis les espacesEetF. Ça n"est bien sûr pas le cas en dimension finie, étantdonné que toutes les normes sont équivalentes.• Par définition, l"applicationd fx0est continue. Il n"en est pas nécessairement de même
de l"applicationd f:U-→L(E,F) x0?-→d fx0. Si c"est le cas, on dira quefest de classeC1au
voisinage dex0. Comment calculer de façon pratique une différentielle?Si l"on a au préalable démontré quefest différentiable enx0, alors, on peut écrire pour
touth?Eque d fL"intérêt d"une telle écriture vient du fait que l"on s"est ainsi ramené au calcul d"une li-
mite d"une fonction d"une variable réelle. La limite précédente s"appelle indifféremment dérivée directionnelle de f en x0selon le vecteur houdifférentielle au sens de Gâteaux de
f en x0dans la directionh. Notons que sifest différentiable, il est aisé de montrer quef
admet une dérivée directionnelle selon tout vecteurh, mais que la réciproque n"est pas vraie.Résumons sous la forme d"un schéma les relations d"implication entre ces différentes proprié-
tés. festC1enx0=?fest différentiable enx0=?festC0enx0 fdérivable enx0selon tout vecteurhLes implications non écrites sonta priorifausses, c"est-à-dire que l"on peuttrouver des contre-
exemples.Exemple 1.3Quelques contre-exemples
• On peut aisément se convaincre à l"aide de la fonction (x,y)?R2?→? x3 x+ysix?=-y0 sinon
1 INTRODUCTION6
qu"il est possible de trouver une fonctionfdérivable selon tout vecteur enx0=(0,0)qui n"est cependant pas continue en ce point.• De même, il existe des fonctions continues non différentiables ayant cependant des déri-
vées dans toutes les directions. C"est par exemple le cas de l"application (x,y)?R2?→?xsix=y20 sinon.
Cette fonction est bien continue en(0,0), dérivable dans toutes les directions en(0,0)(de dérivées directionnelles nulles), mais pas différentiableen(0,0). Remarque 1.4Différentiabilité d"ordre supérieur SoitV, un espace de Hilbert etf:V-→R. Sifest supposée différentiable enx0?V, à partir du développement f(x0+h)-f(x0)=d fx0(h)+oh→0(?h?V),en utilisant le théorème de Riesz, on peut identifierd fx0(h)à??f(x0),h?, où?f(x0)?V. C"est
ainsi que l"on généralise la notion de gradient que nous détaillerons ci-après, dans le cadre de
la dimension finie. Dire quefest deux fois différentiable signifie qu"il existe une application linéaireL(x0):V-→V?telle que d f x0+ξ=d fx0+L(x0)ξ+oξ→0(?ξ?V)?V?.La différentielle seconde def, notéed2fx0est alors l"applicationL(x0):V-→V?. Elle est difficile
à évaluer en pratique carL(x0)ξest un élément deV?. Heureusement, en la faisant agir sur un
élémenth?V, on obtient une forme bilinéaire continue surV×V, que l"on notera?d2fx0ξ,h?.
Il est alors aisé de montrer que
f(x0+h)-f(x0)=d fx0(h)+12?d2fx0h,h?+oh→0(?h?2).
Dans le cas de la dimension finie (V=Rn), ces formules revêtent un aspect particulièrement sympathique puisque la différentielle seconde s"identifie àla matrice hessienne lorsquefest deux fois différentiable (voir paragraphe suivant).1.4 Détour versla dimension finie
Le programme de l"agrégation en optimisation s"intéresse essentiellement à la dimension finie. On va compléter les notions que nous venons d"aborder dans ce cas particulier. Dans ce quisuit, onnote (e1,···,en)la base canoniquedeRneton munitRndesastructureeuclidienne usuelle.1 INTRODUCTION7
Définition 1.5. Fonctions de classeCk
Soiti?{1,···n}etk?2. On dit qu"une fonctionf:U?Rn-→R i admet une dérivée partielle d"indiceienx0si elle est dérivable enx0selon le vecteurei; ii est de classeCksi toutes ses dérivées partielles jusqu"à l"ordrekexistent et sont continues surU. On se placera dorénavant dansle cas particulier d"une fonctionf:U?Rn-→R, avecUouvert deRn. Soitx0?K. • Supposons quefest différentiable enx0. Alors, pour touth?Rn, f(x0+h)-f(x0)=??f(x0),h?+oh→0(?h?)où?f(x0) est le gradient defenx0, i.e. le vecteur (∂f∂x1(x0),···,∂f∂xn(x0)).
La notion de gradient n"est bien sûr pas intrinsèque, elle dépend du produit scalairechoisi : la définition générale de?f(x) résulte du théorème de représentation de Riesz
appliqué à la différentielle defenx. Toutefois, en dimension finie, on fixe le plus sou- vent le produit scalaire canonique et les formules ci-dessus définissent le gradient et la hessienne tout aussi bien. • Supposons quefest deux fois différentiable enx0. Alors, pour touth?Rn,où Hessf(x0) est la matrice de taillen×ndes dérivées secondes defévaluées enx0, i.e.
Hessf(x0)=?∂2f
∂xi∂xj(x0)?1?i,j?n
est symétrique (réelle) (garder également en tête le contre-exemple de Peano lorsque la fonction n"est pas deux fois différentiable, cf [6]) Pour rappel, refaisons le point sur les différentes formules de Taylor et les hypothèses mi-nimales de régularité qu"elles nécessitent. Nous les écrivons ici à l"ordre deux seulement, car
cela s"inscrit dansla logique dece cours, maisces formuless"étendentbiensûràtouslesordres avec des hypothèses ad hoc.FormuledeTaylor avec reste intégral.
Supposons quefest de classeC2dans un ouvertUdeRndansR. Si le segment [a,a+h] est contenu dansU, alors f(x0+h)-f(x0)=??f(x0),h?+1 2? 10(1-t)kk!?Hessf(x0+th)h,h?dt
2 QUESTIONS D"EXISTENCE ET UNICITÉ DES SOLUTIONS8
FormuledeTaylor avec reste deLagrange.
Supposons quefest deux fois différentiable dans un ouvertUdeRnà valeurs dansR. Si le segment [a,a+h] est contenu dansUet supposons qu"il existe une constanteC>0 telle que ?t?[0,1],???Hessf(x0+th)h,h????C?h?2.Alors,
|f(x0+h)-f(x0)-??f(x0),h?|?C2?h?2.
2 Questions d"existence et unicité des solutions d"un problème d"op-
timisation Onpeutretenir comme principegénéralque la compacité fournitdes résultatsd"existence, et la convexité un cadre favorable pour l"unicité. Dans cette section, nous avons fait le choix de présenter la notion de convexité pour desfonctions définies sur un espace de dimension finie (excepté dans la section 2.3). Néanmoins,
on peut sans difficulté étendre ces notions à un espace de HilbertV. (voir par exemple [1])2.1 Existence en dimension finie
Dans cette partie, on suppose quef:K?Rn-→Rest continue,Kdésignant une partie quelconque deRn. On considère le problème d"optimisation ?minf(x) x?K.(2) Remarquons que l"existence n"est pas toujours assurée, comme le montre l"exemple de la mi- nimisation dex?→exsurR, mais nécessite en général peu d"hypothèses.Théorème 2.1. Existence en dimension finie
On suppose qu"il existex0?Rntel que l"ensemble{f?f(x0)}1soit borné. Alors, le problème(2)a au moins une solution globalex?. Démonstration.Le problème (2) équivaut à minimiserfsur l"ensemble compact˜K:={f? f(x0)}. Or, une fonction continue sur un compact atteint sa borneinférieure. Redonnons unedémonstration de ce résultat élémentaire en utilisant les suites minimisantes, ce qui est tout
à fait dans l"esprit de ce cours. Posonsm=inf{f(x),x?˜K}?[-∞,+∞[. Soit (xn)n?N, une suite
minimisante pour le problème (2), i.e.xn?Kpour toutn?Netf(xn)-----→n→+∞m. D"après le
théorème de Bolzano-Weierstrass, quitte à extraire, il existex??˜K(fermé) tel que (xn)n?N
converge versx?. Par continuité def, (f(xn))n?Nconverge versf(x?) ce qui implique que m=f(x?)>-∞, autrement dit quex?réalise le minimum defsur˜K, puis surK.1. On rappelle que {f?f(x0)} est l"écriture abrégée de {x?Rn,f(x)?f(x0)}
2 QUESTIONS D"EXISTENCE ET UNICITÉ DES SOLUTIONS9
Deux remarques très utiles en pratique...
Voici comment on utilise en général le théorème précédent. Rappelons cependant qu"il estes-
sentielque l"on se soit placé en dimension finie pour pouvoir utiliser ce théorème. Dans le cas
contraire, il est aisé de construire des contre-exemples. • SiKest compact, alors, on obtient immédiatement l"existence en utilisant la continuité def. • Sifestcoercive(on dit aussiinfinie à l"infini), c"est-à-diref(x)------→?x?→+∞+∞1etKest
fermé, alors on est dans les conditions d"utilisation du théorème précédent.Remarque 2.2Semi continuité inférieure
Le théorème précédent reste vrai si l"on suppose seulement quefestsemi-continue inférieu-
rement , i.e. ?α?R, {f?α} est fermé dansRn. Cela peut également s"écrire "pour toutε>0, il existe un voisinageVdex0tel quef(x)? f(x0)+ε" ou encoref(x0)?liminfx→x0f(x)=limε→0infx?[x0-ε,x0+ε]f(x).Pour se convaincre de la généralisation du théorème précédent aux hypothèses ci-dessus,
il suffit d"adapter sa preuve en écrivant quef(x?)?liminfn→+∞f(xn)=mpour obtenir le même
résultat. ?→Par exemple, soitI, un sous-ensemble quelconque deR,(fj)j?I, une famille de fonctions linéaires deRndansRet f(x)=sup{fj(x),j?I} pour toutxdansRn. Alorsfest semi-continue inférieurement. En effet, pour tout réelα, l"ensembleUα={x?Rn,f(x)>α}est la réunion des ensemblesUα,j={x?Rn,fj(x)>α}: c"est une réunion d"ouverts, il est donc lui-même ouvert. FIGURE1 - Une fonction semi-continue inférieurement enx0.1. Cette condition signifie :?A>0,?η>0,?x? ?η=?f(x)?Aou encore quelle que soit la suite (xn)n?N
d"éléments deKtelle que limn→+∞?xn?=+∞, on a limn→+∞f(xn)=+∞.2 QUESTIONS D"EXISTENCE ET UNICITÉ DES SOLUTIONS10
Exemple 2.3
Considérons le problème
?minf(x,y)=x4+y4-x2 (x,y)?K={(x,y)?R2,x+y?4}. Montrons quefest "infinie à l"infini". Pour tous(X,Y)?R2, on sait que|XY|?12(X2+Y2). En
remplaçantXparx2etYpar 1, on obtientx4?2x2-1et par conséquent,fest donc "infinie à l"infini" etKest fermé (image réciproque d"un fermé par une application
continue...), et on en déduit que le problème d"optimisation a (au moins) une solution.Exemple 2.4Un peu plus difficile...
On définit la famille des{ui}i?{0,...,N+1}parui=ih, avech=1N+1. On se donne un nuage de points deR2(ui,xi)i?{0,···,N+1}, avecN?N?donné. On suppose par ailleurs quex0=0et x N+1=1. Posonsx=(x1,···,xN). On appellef(x), la longueur de la courbe affine par morceaux passant par les points(ui,xi). On montre aisément que f(x)=N? i=0? (ui+1-ui)2+(xi+1-xi)2 =hN? i=0?1+?xi+1-xih?
2. On considère le problème d"optimisation suivant : "minimiser la somme des longueursf(x) parmi tous lesx?RN", autrement dit ?inff(x) x?RN.(3)Il est très aisé de caractériser géométriquement la solution d"un tel problème. En effet, on se
convainc aisément que la meilleure façon de minimiser la longueurf(x)est de choisir tous lesxisur la droite d"équationx=u, ce qui caractérise de façon unique les pointsxi. Ainsi, x i=ihpour touti?{1,...,N}. Cela dit, oublions provisoirement l"interprétation géométrique et concentrons-nous sur le problème(3). La simple question de l"existence d"un minimiseur (et à plus forte raison sa caractérisation) ne semblent alors pas triviales. Montrons-là.On va montrer quefest en réalité infinie à l"infini ce qui, en vertu du théorème 2.1, fournira
le résultat. De?1+x2?|x|pour toutx?R, on déduit pourk?{1,...,N}que
f(x)?k-1? i=0|xi+1-xi|??????k-1? i=0(xi+1-xi)????? =|xk|. Par conséquent,f(x)??x?∞pour toutx?RNet l"existence d"un minimiseur pour le problème (3)s"ensuit.2 QUESTIONS D"EXISTENCE ET UNICITÉ DES SOLUTIONS11
2.2 Unicité de l"optimum
L"unicité repose en général sur des arguments de convexité.Rappelons les notions d"en- semble convexe et de fonction convexe. Définition 2.5. Ensembles et fonctions convexes i On dit qu"un ensembleK?Rnest convexe si, et seulement si pour tous(x1,x2)? K2ett?[0,1],tx1+(1-t)x2?K.
ii SoitK, un convexe inclus dansRn. La fonctionf:K-→Rest diteconvexesi, et seulement si ?(x1,x2)?K2,?t?[0,1],f(tx1+(1-t)x2)?t f(x1)+(1-t)f(x2). On dit quefeststrictement convexesi l"inégalité ci-dessus est stricte pour x?=y,t?]0,1[. Rappelons que toute fonction convexe possède une régularité minimaleen dimension finie. • Sifest une fonction convexe définie sur un ouvertconvexeΩdeRn, alorsfest continue surΩet lipschitzienne sur tout compact deΩ. (voir par exemple [7] pour la preuve dans R net [9] pour le casn=1)• De la propriété de Lipschitz découle, en utilisant le théorème de Rademacher, que toute
fonction convexe définie surΩ?Rnest différentiable presque partout(au sens de la me- sure de Lebesgue) sur son domaine. À présent, nous allons rappeler un fait bien connu mais néanmoins fort utile en pratique.On peut caractériser assez facilement une fonction convexedansle cas où celle-ci est régulière
(différentiable partout ou deux fois différentiable partout) . Théorème 2.6. Caractérisation des fonctions convexes dansle cas régulier i Sif:Rn-→Rest différentiable, on a les équivalences entre (i)fest convexe surRn; (ii)f(y)?f(x)+??f(x),y-x?,?(x,y)?[Rn]2; (iii)??f(y)-?f(x),y-x??0,?(x,y)?[Rn]2.ii On a équivalence entre convexité stricte et les inégalités(ii)et(iii)précédentes
rendues strictes, pourx?=y. iii Sif:Rn-→Rest deux fois différentiable, on a les équivalences entre (i)fest convexe; (ii)pour toutx?Rn,Hessf(x)est semi-définie positive. Démonstration.i • (i)=?(ii).Soitt?[0,1],(x,y)?[Rn]2.Alors,parconvexitédef,f(tx+2 QUESTIONS D"EXISTENCE ET UNICITÉ DES SOLUTIONS12
(1-t)y)?(1-t)f(x)+t f(y), d"oùf(x+t(y-x))?t[f(y)-f(x)], puis on divise part et on fait tendretvers 0. • (ii)=?(iii). On écrit (ii) avec (x,y), puis (y,x) et on somme. • (iii)=?(ii). On utilise la formule de Taylor Mac-Laurin à l"ordre 12, appliquée à la fonctiont?[0,1]?→f(x+t(y-x)). Il existet?[0,1] tel que f(y)=f(x)+??f(x+t(y-x)),y-x? et ce dernier terme est positif par (iii), donc on a (ii). • (ii)=?(i). On posext=(1-t)x+ty=x+t(y-x) et on écrit (ii) avecx=xt,y=xou y. On a : f(x)?f(xt)+??f(xt),x-xt? f(y)?f(xt)+??f(xt),y-xt?, respectivement par 1-tett, puis on les somme : (1-t)f(x)+t f(y)?(1-t+t)f(xt)=f(xt).ii Il s"agit d"adapter avec beaucoup de précaution la démonstration précédente. Cet exer-
cice est laissé au lecteur. Attention cependant à être prudent lors des passages à la limite
quotesdbs_dbs9.pdfusesText_15[PDF] Conditions tarifaires de location de Véhicules RENT A CAR au 1er
[PDF] Exemple conducteur emission
[PDF] conducteurs en equilibre electrostatique - usthb
[PDF] Travaux dirigés : Conductance et Conductivité - Lycée Gustave
[PDF] Ch3 - EXERCICES Courant électrique dans les solutions aqueuses
[PDF] TRANSFERTS DE CHALEUR - Exercices de références - Doc 'INSA
[PDF] Vapeur - ThermExcel
[PDF] La Conductivité thermique de quelques matériau de construction
[PDF] Propriétés thermiques des matériaux et références métrologiques
[PDF] fimo / fco - Pardessuslahaie
[PDF] Conduire en France avec un permis étranger et son échange I
[PDF] conduite ? tenir devant une femme ayant une cytologie - Aly Abbara
[PDF] Scorpion - Centre AntiPoison et de Pharmacovigilance du Maroc
[PDF] PDF 241 ko Gestion de projet - FOAD
