Notes de cours - Préparation `a l'agrégation Introduction `a l ...

Description

• cours - matière potentielle : la préparation
• cours - matière potentielle : préparation

Notes de cours - Préparation à l'agrégation 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; 1

• longueur de la courbe
• vertu du théorèmede schwarz
• portion plane d'aire maximale
• problème d'optimisation
• dimension finie
• x0
• problèmes
• problème
• théorèmes
• théorème

Sujets

• cours

Informations

• Publié par: phios
• Nombre de lectures: 52
• Langue: Français

Extrait

Notesdecours-Préparationàl’agrégation
Introduction à l’optimisation
Première Partie : aspects théoriques
Univ.Rennes1,E.N.S.Rennes
∗YannickPrivat
∗ENS Cachan Bretagne, CNRS, Univ. Rennes 1, IRMAR, av. Robert Schuman, F-35170 Bruz, France;
[e-mail]
1TABLEDESMATIÈRES 2
Tabledesmatières
1 Introduction 3
1.1 Leprogrammedel’agrégation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Levocabulairedel’optimisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Quelquesrappelsdecalculdifférentiel . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.4 Détourversladimensionfinie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2 Questionsd’existenceetunicitédessolutions 8
2.1 Existenceendimensionfinie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.2 Unicitédel’optimum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.3 Existenceendimensioninfinie? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3 Conditionsd’optimalité-optimisationsanscontrainte 19
3.1 Conditionsd’optimalité-optimisationsanscontrainte . . . . . . . . . . . . . . . 20
3.2 Minimisationd’unefonctionnellequadratiquesanscontrainte . . . . . . . . . . . 22
3.3 Laméthodedesmoindrescarrés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
4 Conditionsd’optimalité-optimisationsouscontraintes 25
4.1 MultiplicateursdeLagrange,lethéorèmedesextremaliés . . . . . . . . . . . . . . 25
4.2 LesthéorèmesdeF.JohnetKarush-Kuhn-Tucker . . . . . . . . . . . . . . . . . . . 311 INTRODUCTION 3
1 Introduction
1.1 Leprogrammedel’agrégation
• Optimisationetapproximation
• InterpolationdeLagrange.
˝• ExtremumsdesfonctionsrOellesden variablesréelles:multiplicateursdeLagrange.
• Miseenœuvredel’algorithmedegradientàpasconstant.
• Méthodedesmoindrescarrésetapplications.
L’interpolation de Lagrange et les algorithmes de gradients seront étudiés ultérieurement, au
coursdelapréparation.
1.2 Levocabulairedel’optimisation
SoitV estunespacevectorielnormé,munidela normek·k.Danscecours,on s’intéresse
auproblèmesuivant
½
inff(x)
(1)
x∈K,
oùK ⊂V et f :K −→Restunefonction,appeléefonctioncoûtoucritère.
• SiK =V,onditque(1)estunproblèmed’optimisationsanscontrainte.
• SiK(V,onditque(1)estunproblèmed’optimisationsouscontrainte.
• Si dimK <+∞ (resp. dimK =+∞), on dit que (1) est un problème d’optimisation en
dimensionfinie(resp.infinie).
Remarquonsqueceformalismeenglobetouslesproblèmesd’optimisation,ycomprislespro-
blèmesdemaximisationpuisquemaximiserunequantitérevientàminimisersonopposé.
Dans le cadre de ce cours, on étudiera essentiellement l’optimisation en dimension finie,
conformémentauprogrammedel’agrégation.Nousadopteronslaconventionsuivante:sil’on
veutindiquerquelavaleurduminimumestatteinte,onécrira
½
minf(x)
x∈K,
tandisque l’on utilisera la notation “inf” quandon nesait pasapriorisi la valeur dela borne
inférieureest,ounonatteinte.Enfin,rappelonsquetoutepartieminoréenonvidedeRadmet
uneborneinférieure,caractériséedelafaçonsuivante:
Proposition 1.1. Suites minimisantes
Soit X, une partie minorée non vide de R.
Alors, les assertions suivantes sont équivalentes :
i m=inf{x,x∈X};
ii ∀ε>0, ∃x∈X|mÉx<m+ε;
Niii m est un minorant de X et il existe (x ) ∈X , appelée “suite minimisante”n n∈N
convergeant vers m.1 INTRODUCTION 4
Enconséquence,voicilesquestionsqu’ilseranatureldeseposerlorsquevousrencontrerezun
problèmed’optimisation:
• Ceproblèmepossèdet-ilunesolution?
er• 1 casdefigure.
Siceproblèmepossèdeunesolution,onchercheraàlacaractériser(parexemple,est-elle
unique?)ou mieux,àladéterminerlorsqueceserapossible. Onexploiterapourcela les
conditionsnécessairesd’optimalité(auxpremieretdeuxièmeordres).
ème• 2 casdefigure.
Siceproblèmenepossèdepasdesolution,onchercheraàexhiberunesuiteminimisante,
i.e.unesuited’élémentsdel’ensembleK convergeantversinf{f(x),x∈K}.
• Enfin,onseposeralaquestion,lorsquel’onnesaitpasdéterminerexplicitementlesso-
lutions du problème d’optimisation, du choix de méthodes numériques adaptées pour
déterminerleminimumetsesminimiseurs.
Terminonsceparagrapheenprésentantquelquesproblèmesd’optimisation.
• Problème1.(dimensionfinie)
,→Déterminerleparallélépipèderectangledevolumemaximalparmiceuxdontlasurface
extérieurevaut6.
En introduisant a, b et c, les longueurs des côtés du parallélépipède, on se ramène à la
résolutionduproblème 
supV(a,b,c)=abc
ab+ac+bc=3,

aÊ0, bÊ0, cÊ0.
3Ils’agitdoncd’unproblèmed’optimisationdansR souscontrainte.
• Problème2.(dimensioninfinie)
,→ProblèmedelareineDidon.
Le problème consiste à trouver la courbe plane de longueur ℓ fixée qui enclot avec le
segmentreliantsesdeuxextrémités,laportionplaned’airemaximale,autrementdit,on
résoutpourb>aÊ0,
 Zb sup y(x)dx aZ qb
′2 1+y (x)dx=ℓ, y(a)=y(b)=0, a
y∈Y,
où Y est un espace fonctionnel donné (choisi par exemple de sorte que ce problème
possèdeunesolution).
1.3 Quelquesrappelsdecalculdifférentiel
Commençonsparlanotiondedifférentiabilité.(voirparexemple[1,6])1 INTRODUCTION 5
Définition 1.2. Différentiabilité
Soient E et F, deux espaces vectoriels normés réels. SoitU, un ouvert de E et x ∈U.0
On dit qu’une application f :U −→F est différentiable en x ou admet undéve-0
loppementlimitéaupremierordreenx s’il existe df ∈L(E,F) (continue), telle0 x0
que
f(x +h)−f(x )=df (h)+ o (khk ).0 0 x E0
h→0
Quelquesremarquesimmédiates:
• En dimension infinie, la différentiabilité d’une fonction dépend de la norme dont sont
munislesespacesE etF.Çan’estbiensûrpaslecasendimensionfinie,étantdonnéque
touteslesnormessontéquivalentes.
• Par définition, l’application df est continue. Il n’en est pas nécessairement de mêmex0
1del’applicationdf : U −→ L(E,F) .Sic’estlecas,ondiraque f estdeclasseC au
x −→ df0 x0
voisinagedex .0
• Commentcalculerdefaçonpratiqueunedifférentielle?
Si l’on aau préalabledémontréque f est différentiableen x ,alors,on peutécrirepour0
touth∈E que
f(x +εh)−f(x )0 0df (h)=lim .x0
ε→0 ε
ε∈R
L’intérêt d’une telle écriture vient du fait que l’on s’est ainsi ramené au calcul d’une li-
mited’unefonctiond’unevariableréelle.Lalimiteprécédentes’appelleindifféremment
dérivéedirectionnellede f enx selonlevecteurh oudifférentielleausensdeGâteauxde0
f enx dansladirectionh.Notonsquesi f estdifférentiable,ilestaisédemontrerque f0
admet une dérivéedirectionnelle selon tout vecteurh,mais que la réciproque n’est pas
vraie.
Résumonssouslaformed’unschémalesrelationsd’implicationentrecesdifférentesproprié-
tés.
1 0f estC enx =⇒ f estdifférentiableenx =⇒ f estC enx0 0 0
⇓
f dérivableenx selontoutvecteurh0
Lesimplicationsnonécritessontapriorifausses,c’est-à-direquel’onpeuttrouverdescontre-
exemples.
Exemple 1.3 Quelques contre-exemples
• On peut aisément se convaincre à l’aide de la fonction
(
3x six =−y2 x+y(x,y)∈R →
0 sinon1 INTRODUCTION 6
qu’il est possible de trouver une fonction f dérivable selon tout vecteur en x =(0,0) qui0
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
½
2x six=y2(x,y)∈R →
0 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érentiable en (0,0).
Remarque 1.4 Différentiabilité d’ordre supérieur
Soit V, un espace de Hilbert et f :V −→R. Si f est supposée différentiable en x ∈V, à0
partir du développement
f(x +h)−f(x )=df (h)+ o (khk ),0 0 x V0
h→0
en utilisant le théorème de Riesz, on peut identifier df (h) à〈∇f(x ),h〉, où∇f(x )∈V. C’estx 0 00
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 que f est deux fois différentiable signifie qu’il existe une application
′linéaire L(x ):V −→V telle que0
′df =df +L(x )ξ+ o (kξk )∈V .x +ξ x 0 V0 0
ξ→0
2 ′La différentielle seconde de f,notée d f est alors l’application L(x ):V −→V . Elle estdifficilex 00
′à évaluer en pratique car L(x )ξ est un élément de V . Heureusement, en la faisant agir sur un0
2élément h∈V, on obtient une forme bilinéaire continue sur V×