[PDF] COURS DOPTIMISATION [.2pc] ISIMA – F4 3ème année – Master

View - Download COURS DOPTIMISATION [.2pc] ISIMA – F4 3ème année – Master

Previous PDF

Next PDF

Motivations

Ensembles convexes

Fonctions convexes

Dualité

AlgorithmesCOURS D"OPTIMISATION

ISIMA - F4 3ème année - Master Recherche Maths

Jonas Koko

ISIMA

J. KokoCours d"Optimisation Convexe

Motivations

Ensembles convexes

Fonctions convexes

Dualité

AlgorithmesPlan

1Ensembles convexes

2Fonctions convexes

3Dualité

4Algorithmes

J. KokoCours d"Optimisation Convexe

Motivations

Ensembles convexes

Fonctions convexes

Dualité

AlgorithmesMotivations

Régularisations de problèmes de type "moindres carrés"

Applications :

Programmation quadratique

Restauration d"images

least absolute deviationskAxbk1`

1Loss minimization minl(x) +kxk1LASSOkAxbk22+kxk1...

J. KokoCours d"Optimisation Convexe

Motivations

Ensembles convexes

Fonctions convexes

Dualité

AlgorithmesNormek k2

f(x) =kxk2

J. KokoCours d"Optimisation Convexe

Motivations

Ensembles convexes

Fonctions convexes

Dualité

AlgorithmesNormek k1

f(x) =kxk1

J. KokoCours d"Optimisation Convexe

Motivations

Ensembles convexes

Fonctions convexes

Dualité

AlgorithmesQuelques Rappels

Définition (Boule unité)

B=fx2Rnjkxk1gDéfinition

C un ensemble

Fermeture :cl(C) =\

>0(C+B)Intérieur :int(C) =fx2Cj 9" >0;x+BCgCest un cône si8x2C,x2C,80.J. KokoCours d"Optimisation Convexe

Motivations

Ensembles convexes

Fonctions convexes

Dualité

AlgorithmesRappels II

Définition (Hyperplan)

DansRn, un sous-espace de dimensionn1. Par exemple, x i=X j6=ia jxjDéfinition (Opérateur monotone)

Aest monotone si

hA(u)A(v);uvi 0;8u;v

SiAest linéaire

hA(u);ui 0;8u SiAest une matrice()Asémi-définie positive.J. KokoCours d"Optimisation Convexe

Motivations

Ensembles convexes

Fonctions convexes

Dualité

AlgorithmesEnsemble convexe

Définition (Ensemble convexe)

Cest convexe six+ (1)y2C,8x;y2Cet82(0;1).Exemples :

Les boulesB(x0;r) =fx:kxx0krgCônes

Sous-espaces vectoriels, sous-espaces affines

Propriétes :C

1,C2convexes, alorsC1\C2convexeC

1,C2convexes, alors1C1+1C2convexe,81;2Définition (Combinaison convexe)

m X i=1 ixi; i0;mX i=1 i=1:J. KokoCours d"Optimisation Convexe

Motivations

Ensembles convexes

Fonctions convexes

Dualité

AlgorithmesEnsembles convexes II

Définition (Enveloppe convexe)

Sensemble convexe

conv(S) =( x2Rn;:x=mX i=1 iai; i0;mX i=1 i=1;ai2S) conv(S)est convexe.J. KokoCours d"Optimisation Convexe

Motivations

Ensembles convexes

Fonctions convexes

Dualité

AlgorithmesProjection

Définition (Projection)

Censemble convexe deRn,u2Rn. Le vecteurpest meilleure approximation deusurCsi kupk2=minx2Ckuxk2Théorème Cconvex fermé non vide.u2Rnpossède un uniqueptel que kupk2=minx2Ckuxk2 hpu;pxi 0;8x2C:J. KokoCours d"Optimisation Convexe

Motivations

Ensembles convexes

Fonctions convexes

Dualité

AlgorithmesProjection II

Théorème (monotonie)

Cprojection surCalors

h'C(u)'C(v);uvi 0;8u;v2C(monotone) k'C(u)'C(v)k kuvk;8u;v2C(non-expansive)J. KokoCours d"Optimisation Convexe

Motivations

Ensembles convexes

Fonctions convexes

Dualité

AlgorithmesFonctions convexes

Définition

Domaine : Dom(f) =fxjf(x)<+1gfpropre si Dom(f)6=;etf(x)>1Epigraphe epi(f) =f(x;z)2Rn+1jf(x)zgDéfinition (Fonction convexe)

f:C!Rconvexe si82(0;1) f(x+ (1)y)f(x) + (1)f(y);8x;y2C: ffortement convexe si9 >0 f(x+(1)y)f(x)+(1)f(y)2(1)kxyk2;8x;y2C:J. KokoCours d"Optimisation Convexe

Motivations

Ensembles convexes

Fonctions convexes

Dualité

AlgorithmesExemples de fonctions convexes

Remarque

Sifconvexe, la fonctiong=fest concaveFonctions affines (linéaires)

f(x) = (1=2x>Qxb>x,Qsemi-définie positivef(x) =x2f(x) =exf(x) =log(x),x>0f(x) =px,x0f(x) =1=x,x>0f(x) =jxjJ. KokoCours d"Optimisation Convexe

Motivations

Ensembles convexes

Fonctions convexes

Dualité

AlgorithmesPropriétés

Théorème (caractérisation fondamentale)

fest convexe si, et seulement si, epi(f)est convexe.f

1,f2convexes et Dom(f1)[Dom(f2)6=;f

1+f2convexeaf

1convexe,8a0supff1;f2gconvexef

1f2(x) :=infzf1(z) +f2(xz)(inf-convolution) est convexefconvexe etAaffine,(fA)(x) =f(Ax)convexef

i(i2I)affines,f(x) =supi2Ifi(x)convexe.J. KokoCours d"Optimisation Convexe

Motivations

Ensembles convexes

Fonctions convexes

Dualité

AlgorithmesContinuité

Définition (Continuité)

Cconvexe ouvert deRn,f:C!R.fsemi-continue inférieurement (sci) en x2Csi8fxkg C,xk!x f(x)limxk!xinff(xk):Définition (Dérivée directionnelle) f:C!R, La dérivée directionnell defenx2Cdans la direction d2Rn(si elle existe) est f

0(x;d) =limt!01t

(f(x+td)f(x))) fdifférentiable enxsif0(x;d)existe dans toutes les directions.J. KokoCours d"Optimisation Convexe

Motivations

Ensembles convexes

Fonctions convexes

Dualité

AlgorithmesPropriétés

Théorème

Couvert convexe etfdiférentiable surC, alors les affirmations suivantes sont équivalentes fconvexe surC

8x;y2C;hrf(x);yxi f(y)f(x)

8x;y2C;hrf(x) rf(y);yxi 0:Théorème

ffortement convexe surCconvexe ouvert deRn, alors

8x;y2C;hrf(x) rf(y);yxi kxyk22:r2f(x)semi-définie positiveJ. KokoCours d"Optimisation Convexe

Motivations

Ensembles convexes

Fonctions convexes

Dualité

AlgorithmesFonction conjuguée

Définition (Fonction support)

Csous-ensemble deRn,

C(y) =sup

x2Chy;xiLa fonctionCest convexe sci.Définition (Fonction conjuguée)

La conjuguée d"une fonctionfdeRndansRest

f (y) =sup x2Dom(f)hx;yi f(x)Inégalité de Fenchel f(x) hx;yi f(y);8y2Dom(f)et8x2Dom(f)J. KokoCours d"Optimisation Convexe

Motivations

Ensembles convexes

Fonctions convexes

Dualité

AlgorithmesFonction conjuquée : exemple de calcul f(x) =jxj xy jxjjyj )yxjxj (jyj1)jj )f(y) =0 sijyj 1 +1sinonf(x) =C,Cconvexe f (y) =suphx;yi C(x) =sup x2Chx;yi=C(y)J. KokoCours d"Optimisation Convexe

Motivations

Ensembles convexes

Fonctions convexes

Dualité

AlgorithmesSous-différentiabilité

Définition (Sous-gradient)

2Rnsous-gradient defenx0si

f(x)f(x0) +h ;xx0i;8x2Dom(f): @f(x0)ensemble des sous-gradient enx0(sous-différentiel).Conditions équivalentes y

02@f(x0)

x

02@f(y0)

f(x0) +f(y0) =hx0;y0ifdifférentiable enx0,@f(x0) =frf(x0)gJ. KokoCours d"Optimisation Convexe

Motivations

Ensembles convexes

Fonctions convexes

Dualité

AlgorithmesDualité de Fenchel

X,YR-espaces vectoriels normés complets de dualX,Y

2L(X;Y),2L(Y;X)(adjoint)

F:X!Rconvexe,G:Y!Rconvexe

F ,GconjuguéesDéfinition (Problème primal) (P)infx2XF(x) +G(x)Définition (Problème dual) (P)sup y

2YF(y)G(y)J. KokoCours d"Optimisation Convexe

Motivations

Ensembles convexes

Fonctions convexes

Dualité

AlgorithmesConditions d"optimalités

Theorem (Fenchel)

F,Gconvexes sci propres

9x02X,F(x0<+1,G(x0)<+1,Gcontinue enx0.

Alors(P)et(P)admettent au moins une solutionxety

=infx2XF(x) +G(x) =sup y

2YF(y)G(y)Theorem

Sijj<+1alors

y2@F(x) y2@G(x) xsolution de(P),ysolution de(P)J. KokoCours d"Optimisation Convexe

Motivations

Ensembles convexes

Fonctions convexes

Dualité

AlgorithmesDescente du gradient

Gradient Descent (GD)

1Fork=0;:::;K1

g k2@f(xk) x k+1=xktkgk2ReturnxKorxm= (x0+xK1)=KMarche aussi pour le cas avec contrainte,x2C: x k+1=ProjC(xktkgk)J. KokoCours d"Optimisation Convexe

Motivations

Ensembles convexes

Fonctions convexes

Dualité

AlgorithmesDescente du Gradient 2

Hypothèse (HL) (Lipschitz)

9L>0;8x;g2@f(x)tel quekgkLThéorème

Si (HL) ettk=R=(LpK)alors

f 1K K1X k=0x k! f(x)RLpK Rem : Pour une précision",K=R2L2="2J. KokoCours d"Optimisation Convexe

Motivations

Ensembles convexes

Fonctions convexes

Dualité

AlgorithmesDescente du Gradient 3

Hypothèse (L) (-Lipschitz)

8x;y;k rf(x) rf(y)kkxykThéorème

Si (L) ettk=1=alors

f(xK)f(x)2kx0xk2K+4Rem : Pour une précision",K=2="J. KokoCours d"Optimisation Convexe

Motivations

Ensembles convexes

Fonctions convexes

Dualité

AlgorithmesDescente du Gradient 4

Hypothèse (C)ffortement convexe

8x;y;gx2@f(x);f(y)f(x) +hg;yxi+2

kyxk2Théorème

Si (L), (C) ettk=1=((k+1))alors

f 1K K1X k=0x k!quotesdbs_dbs32.pdfusesText_38

[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

[PDF] programme daeu a

[PDF] cours physique daeu b pdf