[PDF] FONCTIONS CONVEXES - ISIMA

Fonctions convexes - Claude Bernard University Lyon 1

Proposition 33 2 Soit f une fonction convexe d´efinie sur un intervalle I La fonction f est strictement convexe si et seulement si il n’existe aucun intervalle de longueur non nulle sur lequel f co¨ıncide avec une fonction affine Preuve Supposons que la restriction de f a [x,y], x 6= y, co¨ıncide avec une fonction affine ϕ

Fonctions convexes 1 Dimension 1 - Institut de Mathématiques

et la fonction fnulle sur ]0;1] et qui vaut 1 en 0, on a bien une fonction convexe non continue en 0 —Une fonction convexe n’est pas nécessairement dérivable On peut penser à la fonction f(x) = jxjsur R par exemple —Si fest deux fois dérivable sur I, alors elle est convexe (resp strictement convexe) si et seulement

Fonctions convexes 1 Dimension 1 - Institut de Mathématiques

fonction fnulle sur ]0;1] et qui vaut 1 en 0, on a bien une fonction convexe non continue en 0 –Une fonction convexe n’est pas nécessairement dérivable On peut penser à la fonction f(x) = jxjsur R par exemple –Si fest deux fois dérivable sur I, alors elle est convexe (resp strictement convexe) si et seulement si f00 0 (resp f00>0

etiennemiquey[at]ens-lyonfr Fonctions convexes

En revanche, une fonction convexe n’est pas n´ecessairement d´erivable, mais si elle l’est, on peut en d´eduire certaines propri´et´es Th´eor`eme 8 Soit f convexe sur [a,b] Alors f est continue sur ]a,b[ Il est a noter que la continuit´e est bien sur l’intervalle ouvert, il peut se passer des choses bizarres au bord sinon : 0 1

FONCTIONS CONVEXES - ISIMA

En général, la composition de deux fonctions convexes n’est pas convexe On a par contre le résultat suivant : Lemme 3 1 Soit f une fonction convexe sur le sous-ensemble C de IRn, et φ une fonction convexe non décroissante de f(C) dans IR Alors h = φ f est convexe sur C Démonstration : Exercice Composition par une transformation

Analyse 20 – Fonctions convexes d’une variable r´eelle

convexe si f > 0 et logf est convexe Exemple: Γ(x) = R +∞ 0 e−ttx−1dt Une fonction log-convexe est convexe Th´eor`eme 9 L’ensemble des fonc-tions log-convexes sur I est stable par +, ×, et passage a la limite si celle-ci existe et est strictement po-sitive 5 Fonctions midconvexes D´efinition 3 Une fonction f : I → R est dite

Fonctions convexes dune variable réelle Applications

Fonctions convexes d’une variable r eelle Applications 2 Convexit e et d erivation Proposition 2 1 Soit fune fonction convexe sur I Alors : (i) fadmet une d eriv ee a gauche et a droite en tout point aint erieur a Iet f0

Leçon 74 : Fonctions convexes d’une variable réelle

− Une fonction affine est convexe sur R − La fonction :x x est convexe sur R − Une fonction continue et affine par morceaux formée de plusieurs graphes de fonctions affines de pentes de plus en plus grandes lorsque n varie de a à b (a

f mid-convexe

Une fonction convexe est trivialement mid-convexe, et il n’est pas difficile de d´emontrer qu’une fonction mid-convexe et continue est convexe Il est alors l´egitime de se demander s’il existe des fonctions mid-convexes r´eelles qui ne sont pas convexes? La r´eponse a cette question n’est pas ´evidente

Optimisation - Examen en pr esentiel du 04/01/2021

n;n(R) une matrice bien choisie 2 Soient ˚: R +R une fonction convexe et croissante, et h: RnR + une fonction convexe Montrer alors que ˚ hest convexe 3 Montrer que g: x2Rn 7 q kDxk2 2 + "est convexe (On pourra consid erer la fonction t2R + 7 p t2 + ") 4 Montrer que fest 1-fortement convexe 5 Justi er que fadmet un unique

[PDF] dérivabilité d'une fonction exercices corrigés

[PDF] montrer que f est dérivable sur r

[PDF] montrer qu'une fonction n'est pas dérivable en un point

[PDF] fonction continue sur un compact atteint ses bornes

[PDF] majoré minoré suite

[PDF] matrice diagonalisable exercice corrigé

[PDF] exemple dossier de synthèse bac pro sen tr

[PDF] rapport de stage terminal bac pro eleec pdf

[PDF] rapport de synthèse bac pro sen

[PDF] rapport de synthèse bac pro sen avm

[PDF] endomorphisme nilpotent exercice corrigé

[PDF] endomorphisme nilpotent problème

[PDF] etude de cas rapport de stage bac pro sen

[PDF] matrice nilpotente pdf

[PDF] dossier de synthèse bac pro sen ed

Chapitre 3FONCTIONS CONVEXES3.1 Notations et définitions préliminaires L"étude des fonctions convexes montrera que celles ci sont continues sur tout l"intérieur

de leur domaine de définition et qu"elles sont presque partout différentiables. Une propriété

suffisante pour étudier les fonctions convexes est lasemi-continuité inférieure: Définition 3.1Soit une fonction:, oùest un ouvert de IR.est dite semi-continue inférieurement (sci) ensi, pour toute suite convergente vers, on a liminf()(). Une notion fondamentale est celle de ladérivée directionnelledont on rappelle les définitions : Définition 3.2Soit une fonction:, oùest un ouvert de IR. La dérivée directionnelle deendans la directionIRest définie par la limite quand elle existe de : (;) = lim0(+)?()

La fonctionsera ditedifférentiableen

si elle possède des dérivées directionnelles dans toutes les directions et siest linéaire par rapport à, i.e. s"il existe un vecteur ()appelé legradientdeentel que : Les composantes du gradient sont alors les dérivées partielles depar rapport à chaque variable= 1notées(). Si= [1]est un vecteur de fonctions:= 1différentiables, leJacobiende la fonction vectorielle deIRdansIRest la matrice()delignes et colonnes dont les lignes sont les gradients()= 1. Si une fonctionest deux fois différentiable en, leHessienest la matrice symétrique ()dont les éléments sont les dérivées secondes partielles parrapport aux variables etnotées2= 1. 1

2CHAPITRE 3. FONCTIONS CONVEXES

(1(1))=1+ (1?)2(2(2)) ()(1) + (1?)(2)

Figure3.1 - Fonction convexe

3.2 Définitions et propriétés

On décrit dans ce chapitre les propriétés des fonctions convexes deIR. Définition 3.3: Soit une fonction:, oùest un ensemble convexe non vide de IR .est dite convexe sursi : (1+ (1?)2)(1) + (1?)(2)1et2 (01) est ditestrictement convexesi l"inégalité précédente est stricte pour1=2. Définition 3.4:estfortement convexede constante 0si : (1+ (1?)2)(1) + (1?)(2)?

2(1?)1?22

On montre facilement qu"une fonction fortement convexe eststrictement convexe. On a aussi la caractérisation suivante : Proposition 3.1Soitun convexe de IRetIR. La fonction:IRest fortement convexe sursi et seulement si la fonctiondéfinie ci-dessous est convexe : 2?2

Démonstration : Exercice

Siest convexe, la fonction:telle que=?est diteconcavesur. Les fonctions affines deIRsont bien sûr convexes (elles sont aussi concaves). Comme on le vérifiera plus loin, les fonctions quadratiques convexes deIRsont celles qui sont associées à une matrice semi-définie positive. DansIR, des exemples courants de fonctions convexes sont : () =2 () =?log, sur 0 sur0 () = 1sur 0

3.2. DÉFINITIONS ET PROPRIÉTÉS3

Figure3.2 - Fonction quasiconvexe

Ledomainede définition desera noté Dom(), c.a.d. :

Dom() =IR()+

On appellepropresles fonctions qui ne prennent jamais la valeur?et qui ne sont pas identiques à+. Par convention, la fonction convexeprendra la valeur+en dehors de Dom()et l"opération ? est interdite. On utilisera deux outils de représentation des fonctions deIR: L"épigraphequi décritdansIR+1et lesensembles de niveauxqui sont des surfaces de IR Définition 3.5: L"épigraphe d"une fonctionde IRest noté epi()et est défini par : epi() =?

IR+1()

L"ensemble de niveauest l"ensemble des x de IRtels que() =. On lui associe lasection, notée: =IR()

L"épigraphe sera particulièrement utile pour transférer les propriétés des fonctions sur les

ensembles deIR+1. Par exemple, un épigraphe fermé signifie que la fonction estsemi- continue inférieurement (sci). On a la caractérisation fondamentale suivante : Une fonction est convexe si et seulement si son épigraphe estconvexe. Par contre, s"il est vrai qu"une fonction convexe possède des sections convexes (par convention, l"ensemble vide est convexe), il existe des fonctions non convexes dont toutes les sections sont convexes. Définition 3.6: Une fonction dont toutes les sections sont convexes est ditequasiconvexe (Fig. 3.2). Une fonction convexe est donc quasiconvexe.

4CHAPITRE 3. FONCTIONS CONVEXES

Proposition 3.2est quasiconvexe sur un ensemble convexesi et seulement si : (1+ (1?)2)max(1)(2)12et(01)

Propriétés des fonctions convexes:

Soient1et2deux fonctions convexes telles que Dom(1)Dom(2)=. Alors : i)1+2est convexe ii)1est convexe0 iii)sup12est convexe iv)inf1() +2(?)est convexe

Démonstration:

i) et ii) sont des conséquences immédiates de la définition. iii) équivaut à epi(1)epi(2)est un ensemble convexe deIR+1. iv) équivaut à epi(1) +epi(2)est un ensemble convexe deIR+1. Cette dernière opé- ration est appelée l"inf-convolutionde1et2, notée1?2.

1?2() = inf1() +2(?)

En général, la composition de deux fonctions convexes n"estpas convexe. On a par contre le résultat suivant : Lemme 3.1Soitune fonction convexe sur le sous-ensemblede IR, etune fonction convexe non décroissante de()dans IR. Alors=est convexe sur.

Démonstration : Exercice.

Composition par une transformation affine:

Soitune transformation affine deIRdansIRetune fonction convexe deIRdans

IR. Alors la fonction:

est convexe. En effet, l"épigraphe deest l"image réciproque de l"épigraphe depar la transformation affine deIR+1dansIR+1:()(). De même, siest une fonction convexe surIR, alors la fonctiondéfinie par : ()() = inf()= est convexe surIR. Cette fois-ci, l"épigraphe deest l"image directe de l"épigraphe de par la transformation affine précédente. Application: Soit une fonctiondeIRIR, convexe en()IRIR().

Alors la fonction

() = inf IRp() est convexe surIR. En effet, elle s"écritoùest l"opérateur de projection deIRIR surIR.

3.3. CONTINUITÉ ET DIFFÉRENTIABILITÉ5

3.3 Continuité et différentiabilité

Dans la suiteest une fonction convexe propre définie sur un ouvert convexedeIR Lemme 3.2 (Monotonie des accroissements)Soitetune direction de IR.

Alors, la fonction() =(+)()

, définie pour des réelssuffisamment petits, est une fonction croissante de. DémonstrationPrenons un intervalle[]avec0 . On a :+= (1?)+ (+)avec=

1. La convexité implique(+)(1?)() +(+)

qui s"écrit : Le même raisonnement s"applique pour des pas négatifs.? Ce résultat implique, en étudiant les limites à gauche et à droite de()quandtend vers

0, l"existence de dérivées directionnelles en tout point de, définies par :

(;) = lim0() = inf0() Observez que l"infimum est borné car,étant un ouvert, il existe 0tel que(;) Théorème 3.1: Une fonction convexe est continue sur rint(Dom()), c"est-à-dire en tout point de l"intérieur de Dom()relativement à la topologie induite dans affDom(). Démonstration et résultats connexes: cf. Rockafellar, Convex Analysis, chap. 10. En résumé, une fonction convexe est continue et différentiable presque partout sur l"intérieur de son domaine. Siest différentiable en, on a : En effet, la dérivée directionnelle satisfait(;?)()?()grâce à la relation de monotonie précédente et, dans le cas différentiable(;) =(). La réciproque est vraie comme l"indique le théorème suivant : Théorème 3.2Siest différentiable sur l"ouvert convexe, alors les 3 affirmations suivantes sont équivalentes : convexe sur ()? ()?()(3.1) ()? ()? 0(3.2) DémonstrationMontrons que (3.1) implique queest convexe. Cette inégalité peut s"écrire : sup qui est en fait une égalité car on peut échanger les rôles deet. Donc,est convexe en tant que supremum d"une famille de fonctions affines.

6CHAPITRE 3. FONCTIONS CONVEXES

Montrons maintenant que (3.2) implique (3.1) par l"absurde. Supposons un segment[] tel que()? ()?(). Grâce au théorème de Rolle, il existe un= (1?)+[01], satisfaisant() =() +()?. On en déduit : ()? ()?=()? ()(?)0 ce qui contredit (3.2) pour le couple().

Les autres implications sont immédiates.?

Monotonie de l"opérateur Gradient: la relation (3.2) signifie que l"opérateur Gradient :IRest monotone sur.

Fonctions fortement convexes différentiable:

Proposition 3.3: Soit une fonctionde IRdans IRfortement convexede constante sur un ensemble convexeet différentiable sur; alors : ()? ()? ?2 Corollaire 3.1 (Fonctions convexes deux fois différentiables)Siest deux fois diffé- rentiable sur,est convexe si et seulement si le Hessien2()est semi-définie positif sur.

Démonstration : Exercice.

Exercice : Montrer le résultat suivant :

Siest deux fois différentiable et fortement convexe (de paramètre), alors la matrice

2()?est définie positive.

3.4 Supports affines et fonctions conjuguées

On noteΓ0l"ensemble des fonctions convexes propres et sci. Ce sont les fonctions dont l"épigraphe est un ensemble convexe fermé. D"aprés la représentation externe de ces ensembles abordée au chapitre 1, ces épigraphes coïncidentavec l"intersection de tous les demi-espaces qui les contiennent. On peut remarquer sur la figure 3.3 ci-dessus qu"un tel demi-espace (associé à un hyperplan non vertical) est l"épigraphe d"une fonction affine qui minore. On a d"ailleurs le théorème fondamental suivant : Théorème 3.3: Une fonctionappartient àΓ0si et seulement siest l"enveloppe su- périeure des fonctions affines qui la minorent. DémonstrationIl est clair qu"une fonction qui est l"enveloppe supérieurede fonctions affines deIRest dansΓ0. SoitΓ0; puisqueest propre, il existe au moins untel que()est fini. On en déduit que le point? avec ()n"appartient pas à epi(). On peut donc le séparer par un hyperplan qui est clairement non vertical. Ilcorrespond donc à l"épigraphe d"une fonction affine qui minore. Supposons quene soit pas l"enveloppe supérieure de ses minorantes affines. Cela implique qu"il existe¯Dom()tel que(¯)¯, où ¯= sup¯+,représentant ici les indices des fonctions affines qui minorent

3.4. SUPPORTS AFFINES ET FONCTIONS CONJUGUÉES7

epi() i i+i() Figure3.3 - Fonctions affines minorantes d"une fonction convexe . A nouveau, on peut séparer?¯ et l"épigraphe depour obtenir une minorante de contredisant la définition de¯.? SiΓ0, cette enveloppe supérieure notée cl(conv)est la plus grande fonction convexe sci qui minore. On remarque que ces demi-espaces définissent des hyperplansfrontières non verticaux à condition de se placer à l"intérieur du domaine; on va maintenant les construire en utilisant l"outil suivant : Définition 3.7: On appelle fonction support d"un ensemblede IRla fonction définie par : () = sup Remarquons queest convexe et semi-continue inférieurement, en tant que supremum d"une famille de fonctions linéaires.est aussi positivement homogène, c"est-à-dire() = ()0. Observez que son épigraphe est un cône convexe. On citera deplus deux propriétés remarquables dont les démonstrations sont laissées en exercice :

1.12=1()2()

2.=conv=cl(conv())

Considérons pour une certaine fonctiondeΓ0le calcul deepi()dansIR+1pour la direction (non horizontale)= (0?1). Supposons queDom(epi()); il existe alors0Dom()tel que : epi()() =00 ?(0) Cette correspondance définit une fonction deIRappeléefonction conjuguéede: Définition 3.8: On appelle fonction conjuguée d"une fonctionde IRla fonction définie par : () = sup

Dom() ?()

8CHAPITRE 3. FONCTIONS CONVEXES

epi() ??(0) 0 0 Figure3.4 - Conjuguée et support de l"épigraphe

Donc,epi()() =00 ?(0) =(0)(Fig. 3.4).

Pour chaqueDom(), ?()définit une fonction affine de la variable. On

en déduit queΓ0. La dualité inhérente à la propriété de convexité consiste àidentifier

les fonctions telles que()=:

Théorème 3.4:Γ0si et seulement si=

DémonstrationOn doit seulement démontrer l"implication directe : l"hyperplan associé au calcul de(),0, est un hyperplan support de l"épigraphe de: 0=?

0 ?=00 ?(0)

Donc,(0) 0 ?()Dom().

Cette inégalité, appelée inégalité de Fenchel peut s"écrire : () ?()Dom()etDom() En prenant le supremum des termes de droite, on trouve que=cl(conv). Donc, d"après le théorème précédent, siΓ0=.?

Exemples de fonctions conjuguées

a) Soitla fonction indicatrice d"un ensembledeIRdéfinie par : () =?0si +sinon est convexe si et seulement siest convexe. ()() = sup ?()= sup La fonction support est la conjuguée de l"indicatrice.

3.5. SOUS-DIFFÉRENTIABILITÉ9

epi() epi(?)[?1274] [?2?34]=?2+ 34 =?12?74

Figure3.5 - Exemple e)

b)() = 1?() = 1, où1 +1= 1 c) DansIR,() =+=() =?+() d) Soient1et2deux fonctions convexes deIRet soit=1?2. Alors =1+2

En effet,

(1?2)() = sup ?inf1(1) +2(2)1+2= = sup sup ?1(1)?2(2)1+2= = sup1+2 ?1(1)?2(2)12 =1() +2() e) DansIR,() =2?+ 1 =() = sup?2+?1= 14(+ 1)2?1

3.5 Sous-différentiabilité

Si on reprend l"équation de l"hyperplan support0, on a la relation :

Dom()0 ?() 00 ?(0)

On dit alors que0est un sous-gradient deen0.

Définition 3.9On appelle sous-gradient d"une fonction convexeen0tout vecteur de IR tel que :

Dom()()(0) +?0

L"ensemble des sous-gradients en0est le sous-différentiel deen0, noté(0)et on dira queest sous-différentiable en0s"il existe au moins un sous-gradient.

Exemple:

DansIR,() = max++où 0et 0.

On notera0=

le point qui minimise, et0=(0)(Figure 3.6) L"ensemble des sous-gradients est le segment[]

Des résultats précédents, on tire donc que les 3 conditions suivantes sont équivalentes :

10CHAPITRE 3. FONCTIONS CONVEXES

?1? ?1? ?1?epi() 0

Figure3.6 - Support affine et sous-gradient :[]

i)0(0) ii)0(0) iii)(0) +(0) =00 On va voir maintenant que ces sous-gradients généralisent le concept de gradient dans certains cas non différentiables. On a vu plus haut que les dérivées directionnelles existent en tout point intérieur au domaine et dans toute direction. Observons que(;)est une fonction positivement homogène et sous-additive, i.e. : (;) =(;)si0 Elle est donc la fonction support d"un ensemble qui n"est autre que le sous-différentiel. En effet, soit(0). On a donc(0+)(0) +, ce qui implique : (0;) (0)etaffDom() ? 0 Le sous-différentiel est donc l"ensemble (convexe compact)dont la fonction support est la dérivée directionnelle, soit : (0;) = max (0) Une conséquence importante est que, siest différentiable en0, le sous-différentiel(0) se réduit à un élément, le gradient deen0. différentiable en0(0) =(0)

On rejoint alors l"inégalité (3.1) trouvée à la section 3.2 qui exprime que la tangente se

situe au dessous du graphe.

Exemples de calcul du sous-différentiel:

a) Soit un ensembleconvexe fermé deIRet soitsa fonction indicatrice. On a alors : si() =IR() ==(), le cône normal àen. b) DansIR,() =?2si 0 2si0

3.6. OPTIMALITÉ11

n"est pas différentiable en 0 et(0) = [02]. c) Soit() = max+ une fonction affine par morceaux qui est bien convexe et sci. On se propose de calculer le sous-différentiel en un point0et soit(0) = (0) =0+. On peut alors réécrirecomme : () =(0) + max?0 ? où=(0)?0?0(donc= 0(0)). On en déduit, poursuffisamment petit : (0+) =(0) +max (0) Donc(0;) = max(0)et d"après les résultats précédents sur la dérivée direc- tionnelle et le fait quei(0)=convi(0), on obtient : (0) =conv(0) On peut généraliser ce résultat au cas d"une fonction "max" comme() = max() où lessont convexes, différentiables. En0?

Dom(), on a :

(0) =conv(0)(0) Ce dernier exemple est un cas particulier du théorème suivant, dû à Danskin : Théorème 3.5Soitun sous-ensemble compact de IRetΦ :IRIR une fonction continue, différentiable et convexe par rapport à son premier argumentIRet ce, pour tout. Soit : () = maxΦ() et soit()l"ensemble desqui maximisentΦ()sur. Alors : i)est convexe et(;) = max()Φ(;) ii)() =convΦ()() Démonstration : cf. Hiriart-Urruty et Lemarechal, 1993

3.6 Optimalité

Quand on cherche à minimiser une fonction deIR, on distingue minimum global de minimum local : un minimum global deest un pointDom()tel que() ()Dom(); pour définir un minimum local, on remplaceDom()par Dom()(), où()est un voisinage dede rayon, i.e.() = ? pour un 0. Théorème 3.6Soitune fonction convexe de IRetun point oùest sous-différentiable. Une condition nécessaire et suffisante pour qu"un pointsoit un minimum global d"une fonction convexe est0().

12CHAPITRE 3. FONCTIONS CONVEXES

DémonstrationConséquence immédiate de la définition d"un sous-gradient. ()()()() +0? On retrouve dans le cas différentiable la condition nécessaire d"optimalité du premier ordre : siminimise, le gradient deenest nul. Cette relation est locale, alors que tout minimum local d"une fonction convexe est un minimum global. Dans le cas convexe, la condition d"optimalité du premier ordre est nécessaire et suffisante (Observez que la condition du deuxième ordre est satisfaite en tout point car le Hessien d"une fonction convexe deux fois différentiable est semi-défini positif).

3.6. OPTIMALITÉ13

Références:

C. Berge et A. Ghouila-Houri, Programmes, Jeux et Transport,Dunod, 1962 J.B. Hiriart-Urruty et C. Lemarechal, Convex Analysis and Minimization Algorithms,

Springer V., 1993

P.J. Laurent, Approximation et Optimisation, Hermann, 1972 R.T Rockafellar, Convex Analysis, Princeton U. , 1970 J. Stoer et C. Witzgall, Convexity and Optimization, Springer V., 1970quotesdbs_dbs22.pdfusesText_28