[PDF] Cours Apprentissage - ENS Math/Info Analyse Convexe

View - Download Cours Apprentissage - ENS Math/Info Analyse Convexe

Previous PDF

Next PDF

Cours Apprentissage - ENS Math/Info

Analyse Convexe

Francis Bach

17 octobre 2014

Ce cours s'appuie sur le livre \Convex Optimization" de Stephen Boyd et Lieven Vandenberghe (disponible gratuitement :http://www.stanford.edu/~boyd/cvxbook/). La convexite intervient dans de nombreuses branches des mathematiques et de l'informatique. Deux aspects seront vus dans le cours d'apprentissage : l'analyseconvexe (proprietes des fonctions et problemes d'optimisation convexes) et l'optimisationconvexe (algorithmes de resolution). Exemple classique en apprentissage : minimisation du risque empirique regularise min f2F1n n X i=1`(yi;f(xi)) + (f); avec ( xi;yi)2 X Y,i= 1;:::;ndonnees d'apprentissage |F: ensemble convexe de predicteursf:X !R |u7!`(y;u) perte convexe pour touty2 Y p enalitecon vexe.

1 Ensembles convexes

On ne considere dans ce cours que la convexite dans un espace Euclidien de dimension nie (le plus generalementRn). |Denition:KRnest convexe si et seulement si, pour toutx;y2K, le segment [x;y] est inclus dansK, i.e.,82[0;1],x+ (1)y2K. |Exemples classiques: hyperplana>x=b(a2Rn,a6= 0,b2R), demi-espacea>x>b, sous-espace aneAx=b, boulesfkxk61g Rn, conefkxk6tg Rn+1. |Proprietes: l'intersection d'une famille (non necessairement denombrables) de convexes est convexe; la convexite est preservee par les applications anes (image et image inverse). |Enveloppe convexe: Etant donne un ensembleA, l'enveloppe convexe est le plus petit ensemble convexe contenantA. Elle est egale a l'intersection de tous les convexes contenant A. Elle est egale a l'ensemble des barycentres a coecients positifs ou nuls de familles nies de points deA(i.e.,Pp i=1ixi, pourxi2A,i>0 etPp i=1i= 1). 1 |Separation des convexes: SiCetDsont deux ensemble convexes disjoints (C\D=?), il existe un hyperplan separantCetD, i.e.,9a6= 0 etb2Rtels queC fa>x>bget D fa>x6bg(forme geometrique du theoreme de Hahn-Banach). SiCetDsont compacts, alors il existe une separation stricte, i.e.,C fa>x > bgetD fa>x < bg. Exercice: Montrer le theoreme de separation stricte quandCetDsont compacts (indication : on utilisera la paire (x;y) minimisantkxyk2pour (x;y)2CDet la mediatrice des pointsxety).

2 Fonctions convexes

|Denition: Une fonctionfdenie surDRnest convexe ssi (a)Dest convexe et (b) pour toutx;y2D, et2[0;1], alorsf(x+ (1)y)6f(x) + (1)f(y). |Convexite stricte: m^eme denition sauf : si2(0;1),f(x+(1)y)< f(x)+(1)f(y) |Convexite forte: m^eme denition sauf :f(x+(1)y)6f(x)+(1)f(y)2 (1 )kxyk2 |Exemples classiques en une dimension:x,x2,logx,ex, log(1+ex),jxjppourp>1, xppourp <1 etx>0. |Exemples classiques en dimension superieure: fonctions lineairesa>x, fonctions qua- dratiques 12 x>QxpourQsymmetrique semidenie positive, normes. |Caracterisation pourfderivable:8x;y2D; f(x)>f(y) +f0(y)>(xy). |Caracterisation pourfdeux fois derivable:8x2D; f00(x) semidenie positive. |Operations preservant la convexite: supremum d'une famille de fonctions convexes sup i2Ifi(x), combinaison lineaires positives, minimisation partielle infx2Cf(x;y) (sifest convexe surCD). |Proprietes:fest continue sur l'interieur deD. |Inegalite de Jensen:f(Pn i=1ixi)6Pn i=1if(xi) etf(EX)6Ef(X). |Fonctions convexes etendues(a valeurs dansR[ f+1g) :~f:Rn7!Rnie sur son domaine, innie sur son complement. Permet de gerer simplement les fonctions a domaine

D6=Rn.

3 Problemes d'optimisation non-contraints

On supposefconvexe et nie surRn. Alors, les trois cas exclusifs suivants sont possibles : inf x2Rnf(x) =1: pas de minimum (exempleflineaire) inf x2Rnf(x)>1non atteint (exemple log(1 +ex)) inf x2Rnf(x)>1atteint (exemple le plus classique) :fest ditecoercive(limkxk!+1f(x) = +1) Minimas locaux vs. minimas globaux:xest minimum local ssi il existe un voisinageVdex tel quexest le minimum defsurV. Lorsquefest convexe, tout minimum local est global. 2 Stricte convexite et minimum unique: sifest strictement convexe, alors il y a au plus un minimum. Condition necessaire et susante d'optimalite (cas derivable): Sifest convexe et derivable, xest un minimum defsurRnsi et seulement sif0(x) = 0.

4 Problemes d'optimisation contraints

On supposefconvexe et nie surDRn. On cherche a minimiserfsur un convexeCD. L'ensemble de contraintesCpeut ^etre specie par une intersection d'ensembleshi(x) = 0 etgj(x)60 (voir section suivante). Minimisation d'une fonction lineaire sur une enveloppe convexe: SoitAun compact de R neta2Rn,a6= 0. Alors min x2Aa>x= minx2Enveloppe convexe(A)a>x Exemple classique du probleme d'aectation: on apemployes etpt^aches, et a chaque paire em- ploye/t^ache (i;j), on a un co^utcij, le but est de trouver une permutation:f1;:::;pg 7! f1;:::;pg telle quePp i=1ci(i)est minimum. On aPp i=1ci(i)=hc;MiouMest la matrice de permutation associee. L'enveloppe convexe des matrices de permutations est l'ensemble des matrices double- ment stochastiques (theoreme de Birkho), qui correspond a un probleme d'optimisation comvexe contraint.

5 Dualite Lagrangienne

On s'interesse au probleme d'optimisation suivant (dit problemeprimal) : min x2Df(x) tel que8i2 f1;:::;mg;hi(x) = 0 et8j2 f1;:::;rg;gj(x)60:

On noteDl'ensemble desx2Dveriant les contraintes.

|Denition du Lagrangien: on appelle Lagrangien la fonctionL:RmRr+denie par

L(x;;) =f(x) +>h(x) +>g(x):

etsont appeles multiplicateurs de Lagrange (ou variables duales). |Probleme primal comme supremum du Lagrangien par rapport aux variables duales: pour toutx2D, sup (;)2RmRr+L(x;;) =f(x) six2D +1sinon

Le probleme primal est donc equivalent a

p = infx2Dsup (;)2RmRr+L(x;;): 3 |Fonction duale:q:RmRr+!Rdenie parq(;) = infx2DL(x;;). Le probleme dual est la minimisation deqsurRmRr+, equivalent a d = sup (;)2RmRr+infx2DL(x;;): |Concavite du probleme dual: sans aucune hypotheses surD,f;g;h, la fonction dualeq est concave. |Dualite faible: sans aucune hypotheses surD,f;g;h, pour tout (;)2RmRr+, et x2 D, infx02DL(x0;;)6L(x;;)6sup (0;0)2RmRr+L(x;0;0) ce qui impliqueq(;)6f(x). Ceci impliqued6p. |Problemes non faisables, non-bornes Interpretation geometrique: probleme a une contrainte d'inegalite |Conditions de Slater: sifetDsont convexes,hianes etgjconvexes et il existe un point strictement faisable (9x2Dtel que8j,gj(x)<0), alorsd=p(dualite forte). |Conditions de Karush-Kuhn-Tucker (KKT): Si il y a dualite forte, alorsxest une variable primale optimale et (;) une paire duale optimale si et seulement si |stationarite primale:xminimisex7! L(x;;). |faisabilite:xet (;) sont faisables |conditions de complementarite:8j;gj(x) = 0 Preuv ep ourles conditi onsde KKT : soit x2Dfaisable(i.e.,x2D) et (;)2RmRr+. Alors q(;) = infx2Df(x) + ()>h(x) + ()>g(x)

6f(x) + ()>h(x) + ()>g(x)

6f(x):

La paire (x;;) est alors optimale si et seulement si il y a egalite dans les deux inegalites precedentes, ce qui aboutit aux conditions de KKT. Remarques : (a) le dual du d ualest le dual, (b) plusieurs probl emesduaux, dualit ef ortepas toujours vraie. |Exemple (Programmation lineaire): minAx=b;x>0c>x= maxA>y6cb>y |Exemple (Probleme quadratique avec contrainte d'egalite): mina>x=b12 x>Qxq>x |Exemple (Relaxation Lagrangienne de probleme combinatoire - Max Cut): minx2f1;1gnx>Wx |Exemple (Dualite forte pour probleme non convexe): minx>x6112 x>Qxq>x |Exemple (Fenchel): maxAx=bf(x) = minyb>y+f(A>y) avecf(x) =1p P n i=1xp i, f(x) =Pn i=1exi,f(x) = logPn i=1exi. 4quotesdbs_dbs33.pdfusesText_39

[PDF] nombre dérivé 1ere sti2d

[PDF] primitive terminale sti2d

[PDF] tableau dérivée sti2d

[PDF] calcul primitive ti 82

[PDF] ti 89 probabilité

[PDF] loi normale ti 89

[PDF] equation differentielle t.i 89

[PDF] règle de dérivation

[PDF] fonction valeur absolue dérivable en 0

[PDF] primitive valeur absolue

[PDF] dérivation linguistique

[PDF] dérivation définition

[PDF] le dernier jour d'un condamné analyse chapitre par chapitre

[PDF] le dernier jour dun condamné résumé chapitre par chapitre en arabe

[PDF] le dernier jour dun condamné séquence pédagogique pdf