Next PDF List

Optimisation convexeCh. DossalJanvier 2017IntroductionCe document est un support pour le cours d'optimisation.

Il n'a donc pasvocation a ^etre complet mais vient en appui aux seances de cours.L'objet de ce cours est de presenter des outils theoriques d'optimisation con-vexe ainsi que des algorithmes developpes ces dernieres annees pour resoudredes problemes lies plus particulierement au traitement des images et desstatistiques.

Comme ce cours traite a la fois de la theorie de l'optimisationconvexe et des algorithmes plus speciquement des algorithmes proximaux despliting, il ne pourra pas ^etre exhaustif.

Certains choix sont faits et certainesnotions ne sont donc pas approfondies et certains algorithmes ne sont pastraites.

L'objectif de ce cours aura ete rempli s'il permet aux personnes quile suivent d'avoir les outils pour appronfondir seules les notions abordees etd'^etre capable de mettre en oeuvre d'autres algorithmes de la grande familledes algorithmes proximaux qui forme aujourd'hui un vaste continent.L'optimisation continue, c'est a dire resoudre un probleme de la formeminx2EF(x)ouFest une fonction a valeur dansR[f+1get ouEest un ensemble inni,par exemple un espace de Hilbert, un espace euclidien, ou un sous ensemblede tels espaces, intervient dans de nombreux domaines des mathematiques(transport, traitement d'images, statistiques ).

Dans ce cours nous nousfocaliserons sur le cas particulier ouFest une fonction convexe et ouEest un ensemble convexe.

Non pas que les autres situations ne sont pasinteressantes ou utiles mais que c'est dans ce cadre plus simple ou il estpossible de developper le plus facilement des resultats et des algorithmes ef-caces.

Nous verrons qu'en pratique, certains algorithmes d'analyse convexepeuvent s'appliquer a des fonctionsFnon convexes mais que le resultat deces algorithmes ne fournit que rarement un optimum global au probleme.Ce cours se divise en deux grandes parties, la premiere est consacree al'optimisation de fonctions convexes dierentiables, la seconde de l'optimisationdes fonctions convexes non dierentiables, dites non lisses.

Avant de traiterces deux grandes parties nous presentons quelques exemples de problemesqui nous interesserons ainsi que les premieres denitions qui permettront deposer un cadre theorique clair dans lequel nous pourrons ensuite travailler.

1) Le plan de ce document est donc le suivant.Dans une premiere partie nous presentons des exemples, les premieresdenitions et le cadre theorique que nous allons etudier.

Dans une secondepartie, nous commencons par donner les denitions et les proprietes essen-tielles speciques au cas des fonctions dierentiables dont nous auront besoin.Nous introduirons par exemple la notion de dualite qui est une notion essen-tielle en optimisation convexe.Nous traiterons en premier lieu des problemes sans contraintes, puis desproblemes avec contraintes et plus speciquement des conditions d'optimalite(Lagrange conditions KKT).Dans un second temps nousevoquerons les algorithmes d'optimisation dierentiables,en commencant par les methodes de gradient et en passant par les methodesd'ordre superieure.

Nousevoquerons aussi les methodes de lissage, ou smooth-ing, qui permettent d'approcher des problemes non lisses par des problemesdierentiables.Dans une troisieme partie nous traiterons de l'optimisation non dierentiable.Nous introduirons les outils speciques a l'optimisation non lisse comme lesous dierentiel, et l'operateur proximal ainsi que des proprietes elementairesde ces derniers.

Nous etudierons ensuite les conditions d'optimalite dans lecadre non lisse. Puis nous detaillerons plusieurs algorithmes proximaux etleur cadre d'application.

Nous etudierons en priorite le Forward-Backward etsa version acceleree FISTA, l'algorithme Primal-Dual, l'algorithme Douglas-Rachford ainsi que l'ADMM.

Pour conclure cette partie nous verrons com-ment un m^eme probleme peut ^etre reecrit de plusieurs manieres et ainsi ^etreresolu via divers algorithmes.

La dualite jouera ici un r^ole crucial. 1) Motivation et denitions1.

1) Pourquoi resoudre un probleme d'optimisation ?Les problemes d'optimisation interviennent dans dierents domaines des mathematiques:Determiner les dimensions optimales d'un objet.Determiner la fonction d'une classe donnee la plus proche d'une fonc-tion ou d'un nuage de poinst donnees.Determiner la strategie optimale dans un jeu.Determiner un estimateur optimal pour une classe de fonction (seuillagepour un debruitage d'images par exemple), maximum de vraisemblanceou maximum a prosteriori en statitiques.Determiner le minimum d'un critere en restauration d'images.Transport optimal.

2) On peut ecrire beaucoup de ces problemes sous la forme :minx2EF(x)ouFest une fonction convexe denie sur un espaceHqui sera un espace deHilbert ou plus souvent un espace euclidien, typiquementRn, a valeur dansR[f+1get ouEpeut ^etre l'espaceHtout entier, un sous espace de dernierou un sous ensemble convexe deHdeni par un ensemble de contraintes.

Lespointsx2Esont dits admissibles.Ce probleme n'admet pas toujours de solution ou peut admettre des min-ima locaux.

On peut ramener les problemes de determination de maxima acelle de minima.

On peut aussi avoir a resoudre des problemes de points-sellec'est a dire des problemes de la forme :minx2E1maxy2E2G(x;y)Nous allons nous concentrer ici sur les problemes de minimisation de fonc-tionsFet des contraintesEconvexes.

Nous verrons que ce cadre est as-sez general et que les techniques utilisees peuvent parfois s'appliquer a desproblemes non convexes.

Nous verrons aussi que certains problemes nonconvexes peuvent ^etre convexies et que certains problemes de minimisationpeuvent ^etre reecrits sous forme de problemes de determination de points-selle via la theorie de la dualite.Nous allons maintenant rappeler certaines denitions et proprietes de basede calcul dierentiel qui seront utiles pour la suite.1.

2) Rappels de calcul dierentiel1.2.

1) Fonctions deRdansRSoitfune fonction denie de d'un intervalle ouvertIRa valeurs reelles.On rappelle quelques denitions classiques.On appelle point critique defsur un pointx2Itel quef0(x) = 0.On appelle minimiseur (respectivement maximiseur) local defsurIunpointx2Itel qu'il exister >0 tel que pour touty2I\]xr;x+r[,f(y)>f(x) (respectivementf(y)6f(x)).

On appelle minimum localou maximum local la valeurf(x).Une fonctionfest convexe surIsi et seulement si82[0;1];8(x;y)2I2; f(x+ (1)y)6f(x) + (1)f(y):Une fonctionfest strictement convexe surIsi et seulement si82[0;1];8(x;y)2I2; f(x+ (1)y)< f(x) + (1)f(y):On rappelle les quelques proprietes suivantes :3Sifest derivable au pointx2Ialorsf(x+h) =f(x)+hf0(x)+o(h).Sifest derivable deux fois enx2Ialorsf(x+h) =f(x) +hf0(x) +h22f00(x) +o(h2).Sifest derivable sur un ouvertIsifadmet un minimum ou maximumlocal enx2Ialorsf0(x) = 0.Sifest convexe et derivable surI, alorsf0est une fonction croissantesurI. (Reciproque ?)Sifest convexe et deux fois dierentiable surIalorsf00est une fonctionpositive surI.Sifest convexe, alors tout minimum local surIest un minimum globalsurIet tout minimiseur local et un minimiseur global.Sifest strictement convexe surI, elle admet au plus un minimiseur.La fonctionx7!exest strictement convexe surRet n'admet pas deminimum ni de minimiseur surR.1.2.

2) Optimisation de fonctions deRdansRSifest une fonction denie d'un intervalleIRet a valeurs dansR[f+1g,il existe plusieurs manieres d'en calculer un minimum local ou global suivantles hypotheses que l'on formule surf.Si la fonctionfest dierentiable, un point critiquex0est caracterise parle fait quef0(x0) = 0.

Ainsi, les minimieurs locaux sont contenus dansl'ensemble des pointsx0veriantx0.

Si on dispose d'un tel point, en analysantle comportement de la fonction au voisinage du point, on peut preciser s'ils'agit d'un minimiseur, d'un maximiseur ou d'un point d'inexion.1.

La methode par dichotomie permet d'approcher de maniere sequentielleune valeurx0telle queg(x0) = 0 ougest une fonction continue endenissant une suite d'intervalles emboites dont la taille tend vers 0 etqui contiennent tousx0.Dans la version classique de cet algorithme, dont il existe des variantes,on considere un intervalle borneI= [a;b] tel queg(a)g(b)<0.

Onpeut supposer par exemple queg(a)>0 etg(b)<0.

On posea0=aetb0=bpuis pour toutn>0 on denitm=an+bn2et sig(m)<0 onposebn+1=metan+1=anet sinon on posean+1=metbn+1=bn.Le theoreme des valeurs intermediaires asssure que pour toutn2N,l'intervalleIn= [an;bn] contient un elementx0tel queg(x0) = 0.2.

La methode de descente de gradient explicite a pas xe est denie parun point de departu02Iet un pas xehon construit alors la suiteundenie parun+1=unhf0(un).On peut montrer que sous certaines hypotheses de sur la fonctionf(telle que la convexite) et surh, cette methode converge vers un pointcritique def, independemment deu0.43.

Il existe une variante implicite de cete methode ou la suite (un)n2Nest denie parun+1=unhf0(un+1). Une telle methode necessitecependant de resoudre une equation a chaque etape.

Selon la formede la fonctionf, resoudre cette equation est plus ou moins couteux.Cette methode est plus stable que la methode de descente de gradientexplicite.4.

Si la fonctionfest deux fois derivable et que l'on sait calculer la deriveesecondef, on peut utiliser la methode dite deNewton.

Cette methodeest a l'origine une methode pour determiner lezerod'une fonctionderivable en utilisant la tangente de la fonction au pointunainsi pourapprocher lezerode la fonctiongon construit une suite de la manieresuivante :un+1=ung(un)g0(un).

Ainsi si on cherche un point critiqued'une fonctionf, on peut construire une suite (un)n2Nde la manieresuivante :un+1=unf0(un)f00(un).

On peut voir cette methode comme unemethode de descente de gradient a pas adaptatif.

Nous verrons par lasuite, dans le cadre plus general des fonctions convexes deRndansRdes conditions susantes de convergence de cette methode.1.2.

3) Fonctions deRndansROn peut generaliser la notion de derivee premiere et seconde aux cas desfontions denies d'un ouvert 2Rnet a valeur dansRen introduisant lanotion de gradient :Denition 1On dit quefest dierentiable en un pointx2, il existe unvecteuru2Rntel quef(x+h) =f(x) +hh;ui+o(khk):(1)S'il existe, ce vecteuruest unique et on le noterf(x).On peut noter que le gradient est un vecteur deRn.Dans le cas oun= 2, on peut representer la fonctionfpar une surfaced'equationz=f(x;y).

Le gradient defau point (x;y) est un vecteur quiest dirige dans la direction de plus forte pente de la surface au point (x;y)et dont la norme est proportionnellea la pente locale.Les composantes du gradient ne sont rien d'autre que les derivees par-tielles defpar rapport a chacune des variables (xi)16i6n.Denition 2Soitfune fonction denie d'un ouvertRnet a valeursreelles,i0un entier compris entre 1 etn, pour toutn1uplet(x1;;xi01;xi0+1;;xnon notegl'application partielle denie parg(x) =f(x1;;xi01;x;xi0+1;;xn).Si la fonctiongest derivable au pointx, on dit que la fonctionfadmetune derivee partielle d'indicei0au point(x1;;xi01;x;xi0+1;;xn).

Onnote@f@xi0cette derivee.

5) Proposition 1Si toutes les derivees partielles defexistent et sont contin-ues en tout point de, alors on dit quefestC1suret on arf=@f@x1;;@f@xntDenition 3Soitfune fonction denie d'un ouvert2RndansRdeclasseC1suret si l'applicationx7! rf(x)est elle m^emeC1, on dit quefest de classeC2, il existe alors une unique forme bilinaire'xtelle quef(x+h) =f(x) +hrf(x);hi+'x(h;h) +o(khk2):On appelle Hessienne la matriceHrepresentant cette application bilineaire.La matrice hessienne est la matrice symetrique reelle dont le terme d'indice(i;j)estHi;j=@2f@xi@xjRemarque :Nous avons fait l'hypothese que la fonction estC2et ainsi la matrice hessienneest symetrique ce que lon peut traduire que l'ordre de derivation n'importepas.Exemple :Quelle est la Hessienne au pointxde l'applicationx7!12kAxyk2, ouAest une matrice deMn;m(R) ety2Rm?Proposition 2Soitfest une fonction denie deRndansRetC2.Alorsfest convexe si et seulement si en tout pointx, la matrice hessienne estune matrice positive, c'est a dire que toute ses valeurs propres sont positives.Exercice :Justier que l'application denie dans l'exercice precedent est une applicationconvexe.

Est-elle necessairement strictement convexe ?Denition 4Soitfune fonction denie deEdansR=R[+1, on appelledomaine defet on notedom(f) =fx2Etels quef(x)6= +1g.Denition 5Une fonctionfdenie surEest dite coercive silimkxk!+1f(x) = +1:Denition 6On dire qu'une fonctionfdenie deEdansR[+1est semi-continue inferieurement (on notera sci) si pour toutx2E,liminfy!xf(y)>f(x):Remarque :6La semi-continuite inferieure est stable par somme.Toute fonction continue est sci.L'indicatrice d'un convexe ferme est sci (c'est a dire la fonction quivaut 0 en tout point du convexe et +1en dehors).Sifest sci, pour tout tout2R, les ensemblesfx2E; f(x)6getf(x;)2ERtels quef(x)6gsont fermes.Denition 7Une fonction deEdansR=R[f1gest dite propre si ellen'est pas identiquement egale a+1et si elle ne prend pas la valeur1.Proposition 3SiFest une fonction denie deEdansR, propre, coerciveet semi continue inferieurement, elle est minoree.Demonstration :Pour toutr2R, l'ensembleHr=fx2Etels queF(x)6rgest ferme carFest sci et borne carFest coercive.

Donc pour toutr2R, l'ensembleHrest compact.L'ensembleH=\r2RHrest une intersection de compacts emboites.

CommeFest propre,H=;donc il exister02Rtel queHr0est vide et doncr0estun minorant deF, ce qui conclut la demonstration de la proposition.Proposition 4SoitFune fonction denie surEa valeur dansR, convexe,propre, sci et coercive, alorsFadmet au moins un minimiseur.CommeFest propre, il existex02Etel queF(x0)<+1etF(x0)6=1.L'ensembleH=fx2Etels queF(x)6F(x0)gest ferme carFest sci etborne carFest coercive.Hest donc compact carEest de dimension nie.On a infx2EF(x) = infx2HF(x)>1carFest bornee inferieurement.

Soit(xn)n2Nune suite minimisante d'elements deHtels que limn!1F(xn) = infx2HF(x).Cette suite admet une sous-suite convergente vers un elementx1deH.CommeFest sci on aliminfn!1F(xn)>F(x1):Comme limn!1F(xn) = infx2HF(x) on en deduit queF(x1) = infx2HF(x) =infx2EF(x)72 Optimisation de fonctions dierentiablesDans cette partie on s'interesse au probleme generique suivant :minx2EF(x) (2)ouFest une fonction dierentiable denie sur un espace de HilbertHet avaleur dansR, convexe, coercive et queEest un ensemble convexe ferme.CommeFest dierentiable, elle est sci et propre par denition.

Ces hy-potheses assurent que ce probleme d'optimisation (2) admet au moins unesolution. Si de plusFest strictement convexe alors il existe une uniquesolution a (2).2.

1) Proprietes des fonctions dierentiablesLes fonctions convexes dierentiables ont la propriete d'^etre minorees parleurs approximations anes :Proposition 5Soitfune fonction convexe dierentiable denie deRndansRalors pour tout couple(x;y)2(Rn)2f(y)>f(x) +hrf(x);yxi(3)DemonstrationPar convexite on a pour tout2]0;1[,f(x+(yx))6(1)f(x) +f(y):ce qui peut s'ecriref(x+(yx))f(x)6f(y)f(x)en faisant tendrevers 0 on obtienthrf(x);yxi6f(y)f(x)On deduit de cette proposition, en l'appliquant aux pointsxetyle car-actere monotone du gradient :Denition 8Soitgune fonction denie deRndansRn, on dit quegestmonotone si pour tout couple(x;y)2(Rn)2,hg(x)g(y);xyi>0:Corollaire 1Soitfune fonction convexe dierentiable denie deRndansR, le gradient defest monotone.Il existe une notion de convexite, appelee forte convexite qui permet descontr^oles locaux de la fonction encore un peu plus ns.

8) Denition 9Soitfune fonction denie deEdansR[ f+1get soit >0, on dit que la fonctionfestfortement convexe (ouconvexe) si lafonctiongdenie parg(x) =f(x)2kxk2est convexe.On peut remarquer (exercice !) que s'il existex0tel que la fonctiongx0=f(x)kxx0k2est convexe alorsfestconvexe et bien s^ur qu'unefonction fortement convexe est strictement convexe et donc convexe.

Elleadmet en particulier un unique minimiseur.Par denition, sifest convexe et siyest un element deE, la fonctionx7!f(x) +12kxykest1-fortement convexe.Le lemme suivant montre que si on s'ecarte du minimiseur d'une fonctionnellefortement convexe, la valeur de la fonctionenlle croit au moins de manierequadratique.

Ce lemme sera utile par la suite.Lemma 1Soitfune foncionfortement convexe, et soitxle minimiseurdef, alors pour toutx2Eon af(x) +2kxxk26f(x) (4)Demonstration :On noteg, la fonctionx7!f(x)2kxk2qui est donc convexe par denition.Soit2]0;1[, par convexite degon ag(x+ (1)x)6g(x) + (1)g(x)f(x+ (1)x)2kx+ (1)xk26f(x)2kxk2+ (1)f(x)2kxk2(1)(f(x)f(x))62(2)kxk2+ 2(1)hx;xi (1)kxk2f(x)f(x)62kxxk2f(x) +2kxxk26f(x)ou on utilise a la troisieme ligne le fait quexest un minimiseur.

Ceci pourtout2]0;1[, ce qui conclut la preuve du Lemme.Nous aurons aussi besoin de la denition du caractere Lipschitz d'unefonction :Denition 10On dit qu'une fonctiongdenie deRndansRestLLipschitzsi pour tout couple(x;y)2(Rn)2on akg(x)g(y)k6LkxykSigest 1-Lipschitz on dit quegest non expansive et sigestLLipschitzavecL <1on dit quegestL-contractante ou contractante.Nous venons de voir que les fonctions convexes sont minorees par leursapproximations anes mais si le gradient defestLLipschitz, on peutobtenir un majorant defindependemment de la convexite en eet :9Lemma 2Soitfune fonction de denie deRndansR, dierentiable dontle gradient estLLipschitz, alors pour tout couple(y;z)2(Rn)2f(z)6f(y) +hrf(y);zyi+L2kzyk2:(5)Demonstration :Soitgune fonction derivable denie surRtelle queg0estKLipschitz,g(1) =g(0)+Z10g0(t)dt=g(0)+g0(0)+Z10(g0(t)g0(0))dt6g(0)+g0(0)+K2:Soit (y;z)2(Rn)2, pour toutt2[0;1] on posev=zy,yt=y+t(zy)etg(t) =f(yt).

La fonctiongest derivable etg0(t) =hrf(yt);vi.

D'apresles hypotheses surf,g0estK-Lipchitz avecK=Lkvk2.On en deduit que pour tout (y;z)2(Rn)2f(z)6f(y) +hrf(y);zyi+L2kzyk2:On peut egalement denir une notion plus stricte que la non-expansivite,la ferme non-expansivite (rmly non expansive en anglais) qui sera utile dansla suite :Denition 11On dit qu'une fonctionfest fermement non-expansive sipour tout couple(x;y)2(Rn)2kf(x)f(y)k2+kxf(x)y+f(y)k26kxyk2l'exemple classique d'une fonction fermement non-expansive est celui d'unprojecteur sur un convexe ferme mais nous verrons qu'il en existe d'autrestout aussi interessant.Proposition 6Soitfune fonction convexe denie surRndierentiable agradientLLipschitz.