[PDF] Résumé du cours doptimisation.

View - Download Résumé du cours doptimisation.

Previous PDF

Next PDF

Résuméducoursd'optimisation.

L.HALPERN

13septembre2005

2

Tabledesmatières

IRésultatsthéoriques5

1Résultatsd'existence7

2Caractérisationdesextrema11

3Lagrangienetpointselle15

IIAlgorithmes19

3 4

Premièrepartie

Résultatsthéoriques

5 6

Chapitre1

Résultatsd'existence

Sommaire

UdeudansKtelque

8v2U;J(u)J(v)(1.1)

(u2K;

J(u)=infv2KJ(v)(1.2)

problèmesdeminimisation.

1.1ThéorèmedeWeierstrass

sation(1.2)admetunesolution. 7

1.2Casconvexe

Onrappellequ'unepartieKdeVestconvexesi

8(x;y)2K;82[0;1];x+(1)y2K(1.3)

-convexesi -strictementconvexesi -convexesi

8(x;y)2K;82[0;1];J(x+(1)y)6J(x)+(1)J(y)

2(1)jjxyjj2:(1.6)

malesestconvexe. unesolution. plustoutesuiteminimisanteconvergeversu.

1.3Rappelsdecalculdifférentiel

1.3.1Dérivéespremières

dansV0telleque, l deVnotérJ(u)telquepourtoutvdansVonait J

0(u)v=(rJ(u);v)

8

Exemplesdebase

(c;v),rJ(u)=c.

3.SiV=Rn,J0(u)=(@J

@x1(u);;@J@xn(u))etJ0(u):v=Pn i=1@J @xi(u)vi.

1.3.2Dérivéessecondes

Exemplesdebase

1.J(u)=(c;u),J"(u)=0.

2a(v;w).SiV=Rn,J(u)=1

pourtoutu. @xi@xj(u).

1.3.3FormulesdeTaylor

]u;v[,ilexiste2]0;1[telque

J(v)=J(u)+J0(u+(vu))(vu)

sur]u;v[,ilexiste2]0;1[telque

J(v)=J(u)+J0(u)(vu)+1

2J00(u+(vu))(vu)(vu)

différentiabledansunvoisinagedeu,

J(v)=J(u)+J0(u)(vu)+(vu)kvuk;lim!0(vu)=0

desconditionssuivantesestvérifiée:

8u;v2V;J(v)>J(u)+J0(u)(vu)(1.8)

8u;v2V;(J0(v)J0(u))(vu)>0(1.9)

8u;w2V;J00(u)w:w>0(1.10)

9

Pourunefonction-convexe,ona:

1.SiJestdifférentiable,

8u;v2V;J(v)>J(u)+J0(u)(vu)+

2kvuk2;(1.11)

2.SiJestdifférentiable,

8u;v2V;(J0(v)J0(u))(vu)>kvuk2;(1.12)

3.SiJestdeuxfoisdifférentiable,

8u;w2V;J00(u)w:w>kwk2:(1.13)

8u2V;2a(w;w)>kwk2

Sil'onestdansRn,avecJ(u)=1

2(Au;u),cecirevientà

8u2V;(Aw;w)>kwk2

(Aw;w)=nX i=1d i((Pw)i)2>(min1indi)nX i=1((Pw)i)2 (Aw;w)>(min1indi)kPwk2=(min1indi)kwk2 min

1indi-convexe.

10

Chapitre2

Caractérisationdesextrema

Sommaire

2.1Equationd'Euler,casgénéral

1.SiJestdifférentiable,J0(u)=0,

VtelqueJ0(u)=0.

deutel que8v2

8w2V;J00(u)w:w>kwk2;

alorsuestminimumlocalstrictpourJ.

2.2Inéquationd'Euler,casconvexe

u2K

8v2K;J0(u):(vu)>0:(2.1)

optimale. 11 pointdeK,notéPKwtelque (PKw2K; kwPKwk=infv2Kkwvk(2.2)

Ilestcaractérisépar

8v2K;(PKww;vPKw)>0(2.3)

Lescasparticulierssonttrèsimportants.

1.K=VOnale

seulementsiJ0(u)=0. caractériséeparJ0(u)=0. alors (2:1),( u2K

8w2K;J0(u):w=0(2.4)

(2:1),8 :u2K

91;::;m;rJ(u)+mX

i=1 iai=0(2.5)

V;Fi(w)=0g,et(2.5)seréécrit

(2:1),8 :u2K

91;::;m;rJ(u)+mX

i=1 iF0i=0:(2.6) Alors (2:1),8 :u2K J

0(u):(u0u)=0

8w2K0;J0(u):w>0:(2.7)

M ?=fc2V;8v2M;(c;v)>0g(2.8)

Théorème2.5(LemmedeFarkas).

c=mX i=1 iai. 12 estdansK?0,etdonc(??)seréécrit (2:1),8 :u2K J

0(u):(u0u)=0

9(1;;m)>0;rJ(u)+Pm

i=1iai=0(2.9)

0;16i6mg,et(2.9)s'écrit

(2:1),8 :u2K J

0(u):(u0u)=0

9(1;;m)>0;rJ(u)+Pm

i=1iF0i=0(2.10) lecasgénéral.

K(v)=f0g[fw2V;

kv jjvkvjj=wjjwjjg(2.11)

K(u)?.

2.3.1contrainteségalités

K=fv2V;F(v)=0g(2.12)

K(u)=fw2V;F0i(u):w=0;1img(2.13)

que J

0(u)+mX

i=1p iF0i(u)=0:(2.14) 13

L(v;q)J(v)+mX

i=1q iFi(v);(2.15) alors L 0 v(v;q)@L @v(v;q)=J0(v)+mX i=1q iF0i(v) L 0 q(v;q)@L @q(v;q)=F(v)(2.16) et u2K,8q2Rm;L0 v(u;q)=0 uminimumlocal,9p2Rm;L0 q(u;p)=0(2.17)

2.3.2contraintesinégalités

K=fv2V;F(v)0g(2.18)

K(u)=fw2V;8i2I(u);F0i(u):w0g(2.20)

LelemmedeFarkaspermetalorsd'établirle

mréelsp1;::;pm>0telsque J

0(u)+mX

i=1p iF0i(u)=0 m X i=1p iFi(u)=0(2.21) +,etl'onpeutécrire u2Ksolutionoptimale)9p2Rm L 0 v(u;p)=L0 q(u;p):p=0:(2.22) 14

Chapitre3

Lagrangienetpointselle

Sommaire

3.1Pointselle

(u2K;

J(u)=infv2KJ(v)(3.1)

K=fv;F(v)0g;L:KRm

+!R

K=fv;F(v)=0g;L:KRm!R(3.2)

oùF:V!Rm,et

L(v;q)=J(v)+(F(v);q)(3.3)

(.,.)désigneleproduitscalairedansRm.

Lemme3.1.

sup q2Pinfv2UL(v;q)infv2Usup q2PL(v;q)(3.4) sup q2PL(u;q)=L(u;p)=infv2UL(v;p)(3.5) 15 sup q2Pinfv2UL(v;q)=L(u;p)=infv2Usup q2PL(v;q)(3.6) partKetJpar

K=fv2U;sup

q2PL(v;q)<+1g; etpourvdansK,

J(v)=sup

q2PL(v;q):

Leproblèmeprimalassociés'écrit:

(P)Trouveru2KtelqueJ(u)=infv2KJ(v) (P)Trouverp2KtelqueG(p)=sup q2KG(q) solutionde(P),etJ(u)=G(p).

3.2ThéoriedeKuhnetTucker

K=fv2V;F(v)0g(3.7)

convexeetondéfinitlelagrangiensurVRm +par

L(v;q)=J(v)+(F(v);q)(3.8)

Remarque3.1.

affines,ellesignifiequeK6=;. 16 définition2.2duchapitre2. ilexistepdansRm +telque(u;p)soitpointselledulagrangien.

3.2,onaleschémasuivant:

usolutionoptimalede(1.2)(Th2.8)=)9p2Rm +8 :J

0(u)+mX

i=1p iF0i(u)=0 m X i=1p iFi(u)=0

K=fv;Fi(v)0;1img:

+telque 8 :J

0(u)+mX

i=1p iF0i(u)=0 m X i=1p iFi(u)=0(3.10)

Depluspestsolutionduproblèmedual(P).

17 18

Deuxièmepartie

Algorithmes

19 20

Chapitre4

Méthodesdedescente.Problèmessans

contraintes

4.1Principe

n'estpasforcémentunique)telque

8y2V;J(x)6J(y)(4.1)

x k+1=xkkdk(4.2) d

4.2Méthodederelaxation

21

1.xk;1estdéfinipar

J(xk;1)=inf2RJ(xke1)

ouencore x k;1=(xk 11;xk

2;::;xk

n)

Onnotexk+11=xk

11

2.àl'étapeiona

x k;i=(xk+11;::;xk+1i;xk i;::;xk n) x k;i+1estmaintenantdéfinipar

J(xk;i+1)=infJ(xk;iei+1)

3.xk+1=xk;n

convergeversla solutionoptimale.

2(Av;v)(b;v),onretrouve

4.3Méthodedugradient

Icionchoisitàchaqueétapedk=rJ(xk).

4.3.1Méthodeàpasvariable

solution optimalepour04.3.2Méthodeàpasoptimal

J(xkkrJ(xk))=inf2RJ(xkrJ(xk))(4.3)

la solutionoptimale. rJ(xk):rJ(xk+1)=0: 22

IcilafonctionnelleJestquadratiquesurRn:

J(v)=1

2(Av;v)(b;v)

4.4.1Méthodeàpasoptimal

k=(rk;dk) (Adk;dk)(4.4) etl'ona(rk+1;dk)=0.

NotonsE(v)=1

2(A(vu);vu),onaalors

E(xk+1)=(1

k)E(xk)(4.5) avec k=1

2(rk;dk)2(Adk;dk)(A1rk;rk):(4.6)

Puisquelaquantité

kestparconstructiontelleque0 k1,onal'estimationsuivante: siladirectiondedescenteesttelleque rk jjrkjj;dkjjdkjj

2>>0(4.7)

alors k>

E(xk+1)(1

)E(xk)(4.8)

écrire

E(xk)K(A)1

K(A)+1

2kE(x0)(4.9)

lente. 23

4.4.2Méthodedegradientàpasconstant

jjxkxjj2max1inj1ijkjjx0xjj2(4.10) noùnestlaplusgrande

4.5Méthodedugradientconjugué

2(Av;v)

vérifieAx=b.

4.5.1Principedelaméthode

lesgradientsprécédents.On note L k=vectfrJ(x0);::;rJ(xk)g(4.11) etondéfinitxk+1par:

J(xk+1)=inf2LkJ(xk+)(4.12)

4.5.2Ecriturecommealgorithmededescente

8 :x k+1=xkkdk d k=rJ(xk)+jjrJ(xk)jj2 jjrJ(xk1)jj2dk1 k=jjrJ(xk)jj2 (Adk;dk) (rk+1;dk)=0(4.13) 24

Ilsuffitdesedonnerd0=rJ(x0).

Cholewski(N3

4.5.3Analysedeconvergence

Onintroduitl'espacedeKrylov

K k=vectfr0;Ar0;::;Akr0g(4.14) etonale

Théorème4.7

oùlesisontlesvaleurspropresdeA.

Corollaire4.1.Onal'estimationd'erreur

E(xk)4p

K(A)1pK(A)+1

2kE(x0)(4.16)

E(xk)K(A)1

K(A)+1

2kE(x0)

25
26

Chapitre5

Méthodespourlesproblèmesavec

contraintes (u2K;

J(u)=infv2KJ(v)(5.1)

tiablepar(2.1,PartieI): u2K

8v2K;J0(u):(vu)>0:(5.2)

u k+1=PK(ukkrk)(5.3) ferméK(PartieI,2.1). so- lutionoptimalepour0M2.Deplusilexisteuneconstante<1telle que kukukkku0uk(5.4) 27

K=fv2V;8i;1in;vi>0g;(5.5)

auquelcas (PKw)i=max(wi;0);1in:(5.6)

SiKestlepavéQn

i=1[ai;bi],alors (PKw)i=8 :a isiwiai w isiaiwibi b isiwi>bi(5.7)

5.2Algorithmed'Uzawa

K=fv;F(v)0g(5.8)

oùF:V!Rm.Onadéfiniunlagrangien

L(v;q)=J(v)+(F(v);q);L:KRm

+!R(5.9) etleproblèmedual: K =fq2P;infv2UL(v;q)>1g(5.10) (P)Trouverp2KtelqueG(p)=sup q2KG(q) +(cequiestlecaspourdescontraintesaf- inf v2VL(v;q)=L(uq;q)(5.11)

L'algorithmesedécritalorscommesuit:

p k!uk=upk!pk+1=PK(pk+rG(pk))(5.12) +etuk!u, 28
quotesdbs_dbs32.pdfusesText_38

[PDF] optimisation mathematiques pdf exercices

[PDF] cours optimisation master

[PDF] exercices corrigés de convexité et optimisation

[PDF] exercices corrigés doptimisation pdf

[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