Notes de cours - CEREMADE

Le calcul diﬀ´erentiel (CD) ou inﬁnit´esimal, invent´e par Newton (1642-1727) et Leibniz ( 1646-1716) `a la ﬁn du 17`eme si`ecle, est souvent consid´er´e comme une des grandes d´ecouvertes de l’humanit´e Cette invention est en fait double : un concept math´ematique (la diﬀ´erentielle d’une fonction), et une notation (dx)

Calcul Sous-Differentiel et Optimisation

Calcul Sous-Differentiel et Optimisation JEAN-PAUL PENOT Universite’ de Pm, Fact& des Sciences Exactes, 604010 Paw Universite’, France Communicated by J L Lions Received October 12, 1976 L’objectif de ce travail est de donner une theorie, aussi simple et naturelle

Introduction au Calcul Différentiel et Intégral

de base de calculs, une introduction au calcul différentiel et intégral en dimensions un, ainsi qu’une introduction au calcul différentiel et l’optimisation des fonctions de plusieurs variables De plus, ce document apporte un nombre signiﬁcatif d’exemples et de problèmes, visant à améliorer la

Calculdiﬀérentieletoptimisation: Cours

On étudie le calcul diﬀérentiel dans l’espace de dimension ﬁnie Rn Le cours se compose detroisgrandesparties: —Topologieetcontinuité(chapitres1à3), —Diﬀérentiabilité(chapitres4à6), —Applications(chapitres7à9) Table des matières 1 NormessurRn 5 2 TopologiedeRn 11 3 Fonctionscontinues 17 4 Diﬀérentiabilité

Optimisation (MT2AM050) Notes de cours

pels de calcul différentiel, conditions d’optimalité, convexité, etc ), une part importante est don-née à l’exposition des différents algorithmes classiques d’optimisation, l’étude théorique de leur convergence, ainsi que leur mise en œuvre pratique Le langage Python sera utilisé en séance de Travaux Pratiques (TP)

X Algorithmes d’optimisation

Pour trouver les maximums et les minimums d’une fonction, on utilise le calcul différentiel, et là ou la dérivée de la fonction s’annule, on trouve soit un maximum ou un minimum Un minimum local est facile à trouver, mais il est difficile de trouver un minimum absolu

Notes de cours - CEREMADE

Pour les parties Calcul di er entiel et Optimisation, je me suis tr es large-ment inspir e des notes d’un cours tr es complet que J Blot enseignait en premi ere ann ee de l’ENSAE dans les ann ees 90, qu’il en soit sinc erement remerci e ici Cesnotesdecoursnevousserontpro tablesquesivouspr eparez r eguli ere-

CQP 208 - Chapitre 5 Optimisation - Université de Sherbrooke

CQP 208 Chapitre 5 Optimisation Olivier Godin Université de Sherbrooke 20 novembre 2015 Optimisation 1 / 50

Calculus Cheat Sheet - Lamar University

UFRMath

ematiquesdelad ecision

Notesdecours

CALCULDIFFERENTIELET

OPTIMISATION

GuillaumeCARLIER

L3,ann

ee2008-2009 2 d'egaliteetd'inegalite(KKT). remercieici. unebonnelecture.

G.CARLIER

3 4

Tabledesmatieres

ITopologie7

1Espacesmetriques8

4EspacesdeHilbert46

IICalculdierentiel58

5Quelquesrappels59

6Accroissementsnis,formulesdeTaylor70

7Inversionlocale,fonctionsimplicites87

IIIOptimisation92

8Resultatsd'existenceetrappels93

9Optimisationsouscontraintesd'egalite100

Premierepartie

Topologie

Chapitre1

Espacesmetriques

1.1Denitionspremieres

2.d(x;y)=0,x=y

EEE. surE. tout(x;y;z)2EEE. d

1(x;y):=nX

i=1jxiyij;d1(x;y):=maxi=1;::;njxiyij etladistanceeuclidienne: d

2(x;y):=(nX

i=1(xiyi)2)1 2: 8 vectorielsnormes.

1.2Topologiedesespacesmetriques

etderayonr:

B(x;r):=fy2E:d(x;y) et decentrexetderayonr0:
B(x;r):=fy2E:d(x;y)rg:
d
B(0;1)
bornee ssiilexistex2Eetr>0telsqueAB(x;r).
SiAestunepartiedeE,ondenitsondiametre
diam(A)par: diam(A):=supfd(x;y);(x;y)2A2g:
Onpeutmaintenantdenirlesensemblesouverts
de(E;d): que:
1.Aestouvert
ssipourtoutx2A,9r>0telqueB(x;r)A,
2.Aestferme
ssiEnAestouvert.
3.Aestunvoisinage
dex2Essi9r>0telqueB(x;r)A. ouverte(resp.fermee). 9
1.Eet;sontouverts,

3.uneintersectionFINIE
d'ouvertsestouverte. ainsiasefamiliariseraveclesdenitions... fermes:
1.Eet;sontfermes,

2.unereunionFINIE
defermesestfermee, niferme. onditque:
1.xestunpointinterieur
aAssi9r>0telqueB(x;r)A(autrement ditAestunvoisinagedex),
2.xestunpointadherent
aAssi8r>0,B(x;r)rencontreA.
3.xestunpointfrontiere
deAssi8r>0,B(x;r)rencontreAetEnA. deA.OnappelleadherencedeAetl'onnote
A,l'ensembledespoints
A=E.
Onaclairementlesinclusions:
int(A)A A; @A=
Anint(A):
10
Onaaussilesproprietesimportantes:
2.
Preuve:
2
Aouvert,A=int(A);
et
Aferme,A=
A: que:
A=Enint(EnA);int(A)=EnEnA:
l'adherencedeB(x;r)etl'interieurde
B(x;r).
limite: quandxtendversx1cequel'onnote: lim x!x1;x6=x1f(x)=l d
2(f(x);l)".
11 setraduirepardesproprietessequentielles (i.e.enutilisantdessuites): cequ'estunesuiteconvergente: (xn)estconvergentesielleadmetunelimite.
0ded(xn;x)(dansR).
sontsepares
Preuve:

0i.e.x=yd'oul'unicite.2

1.soitx2E,x2

Assixestlimited'unesuited'elementsdeA,
limitedecettesuiteappartientaA.
Preuve:

2)decoulede1)etdufaitqueAestfermessiA=

A.Supposonsx2A,alors

A.Soitr>0,

Finalementr>0etantarbitraireonabienx2
A. 2 d'elementsdeEnA. 12
Pourtoutx2EondenitladistancedexaApar:
d(x;A):=inffd(x;a)a2Ag
1.Montrerquex2

Assid(x;A)=0.
(n2N).
3.Determiner\n2NAn.
tersectiondenombrabled'ouverts.
1.3SuitesdeCauchy,espacesmetriquescom-
plets (p;q)2N2avecpNetqNona:d(xp;xq)".
Cauchyssi
sup pN;qNd(xp;xq)!0quandN!+1: cettereciproqueestvraiesontditscomplets: derationnelsdenieparxn:=Pn k=01=(k!)estdeCauchy,onmontrepar chapitressuivants. 13 sectiondesFnestnonvide.
Preuve:
F 2
1.4Compacite
valeurd'adherence. N. deE.Onditquexestvaleurd'adherence de(xn)ssil'unedesassertions equivalentessuivantesestsatisfaite:
2.8">0,8N2N,9nNt.q.d(xn;x)",

3.8">0l'ensemblefn2N:d(xn;x)"gestinni.
npourtoutn. ssitoute admetunesous-suiteconvergentedansA. 14 pactedeEalorsAestfermeeetborne.
Preuve:
montrequeAestfermee. lim nd(xn;yn)=+1:(1.1) cequicontredit(1.1). 2 l'occasionderevenirsurcepoint. puisque:
Preuve:
2
Preuve:
15 2 precedentenousavonsetablileresultat: d'adherence. compact.
Preuve:
decompose[0;1]en2psegmentsdelongueur2p: [0;1]=2 p1[ k=0I p k;Ip k:=[k2p;(k+1)2p]: J 1=[ k2f0;::;4g:I2kJ1I 2k l'onnoteraJ2verie: J
2J1,etl'ensemblefn2Nt.q.xn2J2gestinni:
J fn2N:xn2Jpgestinni. 16 2 denition)suivante: peutextraireunrecouvrementni.
1.5Continuite
enxssi8">0, E
1ssifestcontinueenchacundesespoints.

1.festcontinuesurE1,

4.pourtoutesuite(xn)d'elementsdeE1ona:
lim nxn=xdansE1)limnf(xn)=f(x)dansE2: 17
Preuve:

Onvamontrer1))2))3))4))1).
doncf1(F)=E1nf1(O),ainsif1(F)estferme. tq8N2N,9nNNtq d
2(f(xnN);f(x))":(1.2)
x cequiestabsurde. d d 2 partiecompactedeE2.
Preuve:
compact. 2 18
Preuve:
sontniesetappartiennentaf(E).2 d'optimisation: supff(x),x2Egetinfff(x),x2Eg estunmax.(resp.min.). lim jxj!+1f(x)=+1 montrerquel'inmumdefsurRestatteint. denit: d
A(x):=inffd(x;a),a2Ag:
E. surE1ssi uniformementcontinue. k-Lipschitzienne. 19 x7!dA(x):=inffd(x;a),a2Ag est1-Lipschitzienne. estuniformementcontinue. dent: formementcontinuesurE1.
Preuve:
d cequiestabsurde. 2
1.6Pointsxesdecontractions
completude. 20 que: d(f(x);f(y))kd(x;y),8(x;y)2EE:
Preuve:
x
1=x2d'oul'unicite.
d(xn+1;xn)knd(x1;x0)(1.3)
PourqpNonadonc:
d(x1;x0)kN 1k x n+1=f(xn)convergeversf(x)onadoncx=f(x).2 x 21

1.7Connexite
sontequivalentes:
1.(E;d)estconnexe,
muniparexempledeladistancenaturelledeR).
Preuve:
A A constant. quimontreque(E;d)estconnexe. 2 surB1et0surB2). arccontinu: ssipourtout(x1;x2)2E2,ilexiste
2C0([0;1];E)telque
(0)=x1et (1)=x2.
Onaalors
22

Preuve:

2C0([0;1];E)telque
(0)=x1et (1)=x2.Pourtoutt2[0;1]on denitalorsg(t):=f( g(t0)=1=2,or,g(t0)=f( (t0))2f0;1g,d'oulacontradictionvoulue.2 etdoncconnexes. estconnexe. l'imagef(E1)estconnexe.
Preuve:
2 23

Chapitre2

Espacesvectorielsnormes,
espacesdeBanach
2.1Denitionspremieres

Denition2.1Onappellenorme
surEtouteapplication:k:k:E!R+ veriant:
1.kxk=0,x=0,

2.kx+ykkxk+kyk,8(x;y)2E2,

3.kxk=jjkxk,8(;x)2RE.
descompacts...)donneepar: d(x;y):=kxyk,8(x;y)2E2: l'exempledeladistancegrossiere).
Notonsaussiquekxk=kxketjkxkkykjkxyk.
24
kxk1:=max(jx1j;::;jxnj);kxk1:=nX i=1jxij;kxk2:=(nX i=1jxij2)1=2
Nousverronsparlasuite,quepourtoutp1:
kxkp:=(nX i=1jxikp)1=p(2.1) estencoreunenorme).
Exemple2.2E=C0([a;b];R)muniedelanorme
kfk1:=maxfjf(t)j,t2[a;b]g:
SurEonpeutaussiconsidererlesnormes:
kfk1:=Z b a jfj;kfk2:=(Z b a f2)1=2 ouplusgeneralementpourtoutp1: kfkp:=(Z b a jfjp)1=p: kxk1:=supjxnj,n2N: cesdeuxnormessontequivalentes ssiilexistedeuxconstantesstrictement positivesaetbtellesquepourtoutx2Eonait: akxk1kxk2bkxk1: 25
equivalentes. tellequekfnk1akfnk1pourtoutn2N.
Denition2.3OnappelleespacedeBanach
toutevnquimunideladis- tanceassocieeasanormeestcomplet
2.2SeriesavaleursdansunespacedeBanach
generalxn(notation:(P suiteformeesparsessommespartielles:Sn:=P knxk.
Denition2.4Soit(E;k:k)unevnet(P
nxn)nuneserieavaleursdans
E.Onditque(P
partiellesqu'onnotesimplementP+1 n=0xn.Onditque(P nxn)nestnorma- lementconvergentessilaserie(P nkxnk)nestconvergentedansR.
Onrappellequelaserie(atermespositifs)(P
nkxnk)nconvergessila suitedesessommespartiellesestdeCauchy:
8">0;9N2Ntq8pqN,pX
k=q+1kxkk"(2.2) danscecaslasuitedesrestesP+1 k=nkxkktendvers0quandn!+1. nxn)uneserie avaleursdansE,si(P nxn)estnormalementconvergentealors(P nxn) convergedansE. 26

Preuve:
knxkestde
Cauchy,oronapourpq:
kSpSqkpX k=q+1kxkk+1X k=q+1kxkk(2.3) 2 lumentconvergente. nn) nnfn)
2.3Espacesvectorielsnormesdedimension
nie sanspreciserlanorme. convergente.
Preuve:

M>0tellequeF

B(0;M)=[M;M]k.Soit(xn)n2FN([M;M]k)N,
27
lim nkx'(n)xk1=0: preuve. 2 alors touteslesnormessurEsontequivalentes.
Preuve:
x2Rnquel'onecritdanscettebasex=Pn i=1xiei,ona:
N(x)=N(nX
i=1x iei)nX i=1jxijN(ei)(nX i=1N(ei))kxk1 x,y: jN(x)N(y)jjN(xy)jCkxyk1(2.4) donc: N(x kxk1))kxk1N(x): queNetk:k1sontequivalentes.2 lapreuveestlaisseeaulecteur: lecteur... 28
compactesicedernierestdedimensioninnie). equivalences:
1.(xn)nconvergeversxpourk:k1,

2.(xn)nconvergeversxpourN,

2.4InegalitesdeHolderetdeMinkowski

Onaainsiq>1etq=p=(p1).Onad'abord:

Lemme2.1Soitxetydeuxreelspositifsona:
xyxp p+yqq(2.5)
Preuve:
exp(u p+vq)1pexp(u)+1qexp(v)(2.6) xyxp p+yqq: 2
Cecipermetd'etablirl'inegalitedeHolder:
29
n X i=1jaibij(nX i=1jaijp)1=p(nX i=1jbijq)1=q:(2.7)
Preuve:
reelsstrictementpositifs
S:=(nX
i=1jaijp)1=p;T:=(nX i=1jbijq)1=q: jaibij
STjaijppSp+jbijqqTq(2.8)
ensommantcesinegalites,onobtient: n X i=1jaibij
ST1pSpn
X i=1jaijp+1qTqn X i=1jbijq:(2.9) donc:nX i=1jaibijST cequiprouve(2.7).2
Onpeutendeduirel'inegalitedeMinkowski:
nX i=1jxi+yijp)1=p(nX i=1jxijp)1=p+(nX i=1jyijp)1=p:(2.10)
Preuve:

Remarquonsd'abord:
nquotesdbs_dbs47.pdfusesText_47

[PDF] Notes de cours - CEREMADE

UFRMath

Notesdecours

CALCULDIFFERENTIELET

OPTIMISATION

GuillaumeCARLIER

L3,ann

G.CARLIER

Tabledesmatieres

ITopologie7

1Espacesmetriques8

4EspacesdeHilbert46

IICalculdierentiel58

5Quelquesrappels59

6Accroissementsnis,formulesdeTaylor70

7Inversionlocale,fonctionsimplicites87

IIIOptimisation92

8Resultatsd'existenceetrappels93

9Optimisationsouscontraintesd'egalite100

Premierepartie

Topologie

Chapitre1

Espacesmetriques

1.1Denitionspremieres

2.d(x;y)=0,x=y

1(x;y):=nX

2(x;y):=(nX

1.2Topologiedesespacesmetriques

B(x;r):=fy2E:d(x;y)rg:

B(0;1)

SiAestunepartiedeE,ondenitsondiametre

Onpeutmaintenantdenirlesensemblesouverts

1.Aestouvert

2.Aestferme

3.Aestunvoisinage

1.Eet;sontouverts,

3.uneintersectionFINIE

1.Eet;sontfermes,

2.unereunionFINIE

1.xestunpointinterieur

2.xestunpointadherent

3.xestunpointfrontiere

A,l'ensembledespoints

Onaclairementlesinclusions:

Anint(A):

Onaaussilesproprietesimportantes:

Preuve:

Aouvert,A=int(A);

Aferme,A=

A=Enint(EnA);int(A)=EnEnA:

B(x;r).

2(f(x);l)".

0ded(xn;x)(dansR).

Preuve:

0i.e.x=yd'oul'unicite.2

1.soitx2E,x2

Assixestlimited'unesuited'elementsdeA,

Preuve:

2)decoulede1)etdufaitqueAestfermessiA=

A.Supposonsx2A,alors

A.Soitr>0,

Finalementr>0etantarbitraireonabienx2

Pourtoutx2EondenitladistancedexaApar:

1.Montrerquex2

Assid(x;A)=0.

3.Determiner\n2NAn.

1.3SuitesdeCauchy,espacesmetriquescom-

Cauchyssi

Preuve:

1.4Compacite

2.8">0,8N2N,9nNt.q.d(xn;x)",

3.8">0l'ensemblefn2N:d(xn;x)"gestinni.

Preuve:

Preuve:

Preuve:

Preuve:

2J1,etl'ensemblefn2Nt.q.xn2J2gestinni:

1.5Continuite

1ssifestcontinueenchacundesespoints.

1.festcontinuesurE1,