[PDF] [PDF] Eléments danalyse et doptimisation convexe





Previous PDF Next PDF



Convex Optimization

This book is about convex optimization a special class of mathematical optimiza- tion problems



Optimisation convexe

convexe et des algorithmes plus spécifiquement des algorithmes proximaux de l'optimisation de fonctions convexes différentiables la seconde de l' ...



Eléments danalyse et doptimisation convexe.

Dans ce chapitre nous présentons quelques propriétés remarquables des fonctions convexes. Elle permettront de construire des algorithmes de minimisation dans 



Optimisation et analyse convexe

OPTIMISATION. ET. ANALYSE CONVEXE. Exercices et problèmes corrigés avec rappels de cours. Jean-Baptiste Hiriart-Urruty. Collection dirigée par Daniel Guin.



Convex Optimization

4 sept. 2009 Boyd & Vandenberghe Convex Optimization



Convex Optimization – Boyd and Vandenberghe

surprisingly many problems can be solved via convex optimization. Introduction. 1–8 convex and y is a random variable with log-concave pdf then.



Optimisation des fonctions convexes

Optimisation des fonctions convexes D7 : Une fonction réelle f définie sur C convexe est dite convexe si pour tout (a



Convex Optimization Basics

Is this convex? What is the criterion function? The inequality and equality constraints? Feasible set? Is the solution unique when: • n 



COURS OPTIMISATION Cours en Master M1 SITN Ionel Sorin

La fonction f est convexe (donc toute combinaison linéaire avec des coefficients stric- tement positifs de fonctions convexes est convexe). 2. Si au moins l'une 



Non-Parametric Discrete Registration with Convex Optimisation

sition of similarity and regularisation term into two convex optimisation steps. This approach enables non-parametric registration with billions.



[PDF] Optimisation convexe - Institut de Mathématiques de Bordeaux

Ce document est un support pour le cours d'optimisation Il n'a donc pas vocation `a être complet mais vient en appui aux séances de cours



[PDF] Eléments danalyse et doptimisation convexe

19 fév 2020 · 4 1 Méthodes optimales en optimisation convexe différentiable 45 4 1 1 Cas convexe différentiable



[PDF] Cours en Master M1 SITN

2 2 1 Fonctions convexes strictement convexes fortement convexes 11 4 2 3 Applications de la théorie du point selle à l'optimisation



[PDF] Optimisation convexe : géométrie modélisation et applications

19 nov 2009 · 1 Géométrie et analyse convexe 2 Optimisation : idées exemples convexité 3 Optimisation de la production électrique en France



[PDF] Optimisation convexe non-lisse - ENS Lyon

In our opinion convex optimization is a natural next topic after advanced linear algebra and linear programming (Stephen Boyd and Lieven Vandenberghe) 



[PDF] Optimisation linéaire & convexité

I 1 Introduction à la programmation linéaire 1 I 1 1 Un problème d'optimisation linéaire en dimension 2 II 2 4 Fonctions convexes



[PDF] Convexité en optimisation convexité forte

On dit que f est strictement convexe si l'inégalité ci-dessus est stricte pour x = y t ?]01[ Rappelons que toute fonction convexe possède une régularité 



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

16 oct 2015 · pdf pour la r`egle dite d'Armijo – Analyse théorique – Hypoth`eses pour résultat théorique simple : f deux fois dérivable convexe LI f (x)



[PDF] OPTIMISATION ET ANALYSE CONVEXE - Numilog

Pour les fonctions convexes différentiables on pourra consulter [12] Cha- pitre IV Section 4 par exemple * Exercice I 1 Soit f : Rn ?? R continûment 



[PDF] compléments danalyse : convexité et optimisation - ENS Rennes

1 1 1 Généralités 1 1 2 Convexité dans les espaces de Hilbert 5 1 3 Convexité et convergence faible 12 2 Fonctions convexes

  • Comment montrer qu'un problème est convexe ?

    Théorème 2.1 Un fonction f est convexe si et seulement si, pour tout (x, y) ? (dom(f))2 et ? ? 0 tels que y + ?(y ? x) ? dom(f), f satisfait : f(y + ?(y ? x)) ? f(y) + ?(f(y) ? f(x)).19 fév. 2020
  • Comment la convexité permet d'optimiser certains marchés économiques ?

    C'est un concept utile dans le cadre du trading sur obligations car la comparaison des durées des obligations peut permettre aux investisseurs d'anticiper le degré de variation du cours d'une obligation suite à un changement de taux d'intérêt.
  • Comment montrer qu'une fonction est fortement convexe ?

    Une fonction f : K ?? R est dite fortement convexe ou uniformément convexe ou ?-convexe ou ?-elliptique s'il existe ? > 0 tel que, pour tous (x, y) ? K2, t ? [0,1], f(tx + (1 ? t)y) ? tf(x) + (1 ? t)f(y) ? ? 2 t(1 ? t)x ? y2.
  • La fonction f est convexe sur I si sa dérivée f ' est croissante sur I, soit f ''(x) ? 0 pour tout x de I. La fonction f est concave sur I si sa dérivée f ' est décroissante sur I, soit f ''(x) ? 0 pour tout x de I. Soit la fonction f définie sur R par f (x) = 1 3 x3 ?9x2 + 4.
[PDF] Eléments danalyse et doptimisation convexe

Dernière mise à jour : 2015

Eléments d"analyse et d"optimisation convexe.

PierreWeiss

Table des matières

1 Introduction 5

2 Eléments d"analyse convexe 7

2.1 Définitions et propriétés géométriques élémentaires . . . . . . . . . . . . .

7

2.2 Opérations sur les fonctions convexes . . . . . . . . . . . . . . . . . . . . .

14

2.3 Continuité et différentiabilité . . . . . . . . . . . . . . . . . . . . . . . . . .

15

2.4 Théorèmes de séparation . . . . . . . . . . . . . . . . . . . . . . . . . . . .

17

2.5 Sous-différentiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

20

2.6 Règles de calcul sous-différentiel . . . . . . . . . . . . . . . . . . . . . . . .

22

2.7 Conjuguée convexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

25

2.8 Opérateurs proximaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

28

2.9 Eléments d"analyse pour l"algorithmie . . . . . . . . . . . . . . . . . . . . .

29

2.9.1 Fonctions à gradient Lipschitz . . . . . . . . . . . . . . . . . . . . .

30

2.9.2 Fonctions fortement convexes . . . . . . . . . . . . . . . . . . . . .

31

2.9.3 Conditionnement d"une fonction . . . . . . . . . . . . . . . . . . . .

33

3 Théorie de la complexité 35

3.1 Formalisation du problème . . . . . . . . . . . . . . . . . . . . . . . . . . .

35

3.2 Un exemple en optimisation non convexe . . . . . . . . . . . . . . . . . . .

36

3.3 Complexité en optimisation convexe différentiable . . . . . . . . . . . . . .

38

3.4 Complexité en optimisation fortement convexe différentiable . . . . . . . .

41

3.5 Complexité en optimisation convexe non différentiable . . . . . . . . . . . .

42

4 Méthodes d"optimisation convexe de premier ordre 45

4.1 Méthodes optimales en optimisation convexe différentiable . . . . . . . . .

45

4.1.1 Cas convexe différentiable . . . . . . . . . . . . . . . . . . . . . . .

45

4.1.2 Cas fortement convexe différentiable . . . . . . . . . . . . . . . . .

49

4.2 Méthodes optimales en optimisation convexe non différentiable . . . . . . .

52

4.3 Les descentes de gradient proximales . . . . . . . . . . . . . . . . . . . . .

54

4.3.1 Descente de gradient proximale . . . . . . . . . . . . . . . . . . . .

55

4.3.2 Descentes de gradient proximales accélérées . . . . . . . . . . . . .

56

4.3.3 Exemples d"application . . . . . . . . . . . . . . . . . . . . . . . . .

58

4.4 Dualité pour les problèmes fortement convexes . . . . . . . . . . . . . . . .

58
3

Chapitre 1

Introduction

Dans ce cours, nous nous intéressons essentiellement à la classe des fonctions convexes. Celles-ci apparaissent abondamment dans l"ingénierie et permettent de modéliser de nom-

breux phénomènes non linéaires (équations de la physique, traitement du signal, théorie

des jeux et de l"économie, statistiques...). Elles ont des propriétés remarquables qui per- mettent d"analyser plus facilement leurs propriétés et aussi de les minimiser efficacement. De nombreux problèmes non convexes irrésolvables peuvent être approchés par des pro- blèmes convexes qui eux sont presque systématiquement minimisés en des temps rapides. Pour conclure ce cours, nous indiquons quelques références utiles pour aller plus loin. Les

livres [3, 7] sont de très bonnes références pour découvrir les nombreux détails de l"analyse

convexe en dimension finie. La référence [1] propose est une très bonne introduction à l"analyse convexe dans des espaces de Hilbert. Enfin, indiquons une référence dans les espaces de Banach [8]. Notons que cette référence apporte des informations intéressante même pour des questions d"analyse numérique en dimension finie. Au niveau algorithmique, ce cours est essentiellement inspiré des références [6, 5]. Note importante :ces notes ont été rédigées rapidement sans relecture approfondie. Tous les commentaires sont donc les bienvenus. De plus, la partie finale du cours (points intérieurs et algorithme du simplexe) n"apparait pas encore ici par manque de temps. 5

Chapitre 2

Eléments d"analyse convexe

Dans ce chapitre, nous présentons quelques propriétés remarquables des fonctions convexes. Elle permettront de construire des algorithmes de minimisation dans la suite du cours. Dans toutes ces notes, on se place sur l"espace vectorielRn,n?N. On le munit d"un

produit scalaire?·,·?. La norme associée au produit scalaire est notée?·?2. Elle est définie

pour toutx?Rnpar?x?2=??x,x?.

2.1 Définitions et propriétés géométriques élémentaires

Une différence importante par rapport aux chapitres précédents est qu"on autorise ici

les fonctions à valoir+∞(mais pas-∞). Ainsi les fonctions considérées dans ce chapitres

seront de la forme : f:Rn→R? {+∞}.

Autoriser les fonctions à valoir+∞présente l"intérêt de pouvoir représenter les pro-

blèmes contraints sous une forme non contrainte. On a en effet : inf x?Rnf(x) = infx?dom(f)f(x) oùdom(f)est défini de la façon suivante : Définition 2.1 (Domaine d"une fonction)Le domaine d"une fonctionfest notédom(f).

Il est défini par

dom(f) ={x?Rn,f(x)<+∞}. Dans toute la suite de ce cours, on supposera (sans le préciser) que nos fonctions n"ont

pas un domaine vide :dom(f)?=∅.Définition 2.2 (Ensemble convexe)SoitX?Rnun ensemble. Ce dernier est

dit convexe si : ?(x1,x2)?X×X,?α?[0,1], αx1+ (1-α)x2?X.7

8 2.1. Définitions et propriétés géométriques élémentaires

Figure2.1 - En haut : quelques exemples d"ensembles convexes en 2 dimensions. En bas : quelques exemples d"ensembles non convexes (notez qu"il existe des segments dont les extrémités appartiennent à l"ensemble, qui ne sont pas entièrement contenus dans les ensembles).

La définition de la convexité reste identique pour les fonctions à valeur dansR?{+∞}.Définition 2.3 (Fonction convexe)Soitf:Rn→R?{+∞}.fest dite convexe

si :

convexe est convexe (exercice).Figure2.2 - Un exemple de fonction convexe. Un segment tracé entre deux points de

son graphe reste au dessus du graphe. Notez qu"une fonction convexe peut ne pas être dérivable. On peut cependant montrer qu"elle est dérivable presque partout.

Chapitre 2. Eléments d"analyse convexe 9

Définition 2.4 (Combinaison convexe)Soientx1,..,xm,méléments deRn. On dit quexest combinaison convexe de ces points s"il existe(α1,...,αm)tels que : -?i? {1,...,m}, αi?R+, -?mi=1αi= 1, -x=?mi=1αixi.Définition 2.5 (Enveloppe convexe)SoitX?Rnun ensemble. On appelle en- veloppe convexe deXet on noteconv(X)l"ensemble convexe le plus petit contenant X. En dimension finie, c"est aussi l"ensemble des combinaisons convexes d"éléments deX: conv(X) ={x?Rnpouvant s"écrirex=p i=1α ixioùxi?X, p?Netp i=1α

i= 1, αi≥0}.Figure2.3 - Exemples d"enveloppes convexes. A gauche : enveloppe convexe d"un ensemble

discret. A droite : enveloppe convexe d"un ensemble continu. La définition de la convexité permet d"obtenir un lemme souvent utile (notamment en probabilités) :Lemme 2.1 (Inégalité de Jensen)Soitf:Rn→R?{+∞}une fonction Soient x

1,x2,...,xm,mpoints appartenant àdom(f)etα1,...,αmdes coefficients réels po-

sitifs tels que?mi=1αi= 1. Alors f m? i=1α ixi? i=1α

if(xi)Preuve.Par récurrence, on vérifie d"abord que pourm= 2, l"inégalité n"est rien d"autre

que la définition de la convexité. Puis on suppose le résultat vrai au rangket on le montre au rangk+ 1en réutilisant l"inégalité de convexité.

10 2.1. Définitions et propriétés géométriques élémentaires

Preuve.

i=1α Théorème 2.1Un fonctionfest convexe si et seulement si, pour tout(x,y)?(dom(f))2 etβ≥0tels quey+β(y-x)?dom(f),fsatisfait : f(y+β(y-x))≥f(y) +β(f(y)-f(x)). Preuve.Soitfune fonction convexe. Notonsα=β1+βetu=y+β(y-x). Alors y=11 +β(u+βx) = (1-α)u+αx. Donc Réciproquement, supposons que la relationf(y+β(y-x))≥f(y) +β(f(y)-f(x))soit vraie. Soient(x,y)?dom(f)2etα?]0,1]. On noteβ=1-αα etu=αx+ (1-α)y. Alors x=1α (u-(1-α)y) =u+β(u-y).

On a donc

f(x)≥f(u) +β(f(u)-f(y)) =1α f(u)-1-αα f(y). Théorème 2.2fest convexe si et seulement si son épigraphe epi(f) ={(x,t)?dom(f)×R, t≥f(x)} est convexe. Preuve.Si(x1,t1)?epi(f)et(x2,t2)?epi(f)alors pour toutα?[0,1]on a αt

1+ (1-α)t2≥αf(x1) + (1-α)f(x2)≥f(αx1+ (1-α)x2).

Ainsi,(αx1+ (1-α)x2,αt1+ (1-α)t2)?epi(f). Réciproquement, siepi(f)est convexe, alors pourx1,x2dansdom(f), on a (x1,f(x1))?epi(f),(x2,f(x2))?epi(f).

Chapitre 2. Eléments d"analyse convexe 11

Figure2.4 - L"épigraphe de la fonction est la zone grisée au-dessus du graphe de la fonction (en noir). Ainsi,(αx1+ (1-α)x2,αt1+ (1-α)t2)?epi(f), soit encore Théorème 2.3Sifest convexe alors ses ensembles de niveaux L sont soit vides, soit convexes.Preuve.six1etx2appartiennent àLf(β), alors?α?[0,1], Remarque 2.1La réciproque est fausse! Une fonction dont les ensembles de niveaux sont convexes n"est pas convexe en général (exemple en 1D :f(x) =?|x|). Une telle fonction est appelée quasi-convexe. Un exemple de fonction quasi-convexe (non convexe) est donné sur la figure 2.1. Les fonctions convexes différentiables ont plusieurs caractérisations :

12 2.1. Définitions et propriétés géométriques élémentaires

Figure2.5 - Un exemple de fonction quasi-convexe. Ses lignes de niveaux sont des seg-

ments (donc des ensembles convexes), mais la fonction n"est pas convexe.Théorème 2.4 (Caractérisation différentielle de la convexité)

Soitf:Rn→Rune fonction différentiable. Les propositions suivantes sont équiva- lentes : (a)fest convexe. (b) Ses hyp erplanstange antssont des minor ants(voir figur e2.1). ?(x,y)?Rn×Rn, f(y)≥f(x) +??f(x),y-x?. (c)

L egr adientde fest un opérateur monotone :

?(x,y)?Rn×Rn,??f(y)- ?f(x),y-x? ≥0.Note : un opérateurF:Rn→Rnest dit monotone si ?(x,y)?Rn×Rn,?F(y)-F(x),y-x? ≥0. Cette notion généralise la notion de gradient des fonctions convexes. Elle apparaît abon- damment dans les EDP. Preuve.Nous nous contentons de la preuve(a)?(b)et laissons l"équivalence(b)?(c) en exercice. On montre d"abord(a)?(b).

Soitα?[0,1]et(x,y)?Rn×Rn. On a

lim

α→0+f(x+α(y-x))-f(x)α

=??f(x),y-x? par définition de la dérivée directionnelle. Par convexité def, on a de plus Donc f(x+α(y-x))-f(x)α

Chapitre 2. Eléments d"analyse convexe 13

Figure2.6 - Hyperplans tangents d"une fonction convexe (1D) et d"une fonction concave (2D). Notez que l"hyperplan tangent est un minorant pour la fonction convexe et un ma- jorant pour la fonction concave. En passant à la limite quandα→0+, on obtient l"inégalité annoncée. Montrons maintenant(b)?(a). Soient(x,y)?Rn×Rnetz=αx+(1-α)y. On peut

écrire :

f(x)≥f(z) +??f(z),x-z? f(y)≥f(z) +??f(z),y-z?

Soit encore :

f(x)≥f(αx+ (1-α)y) +??f(z),(1-α)(x-y)? f(y)≥f(αx+ (1-α)y) +??f(z),α(y-x)?

En multipliant la première inégalité parα, la seconde par(1-α)puis en additionnant les

deux, on obtient l"inégalité de convexité.

Les fonctionsC2convexes peuvent être caractérisées par leur hessienne.Proposition 2.1 (Caractérisation de second ordre de la convexité)

Soitf:Rn→Rune fonctionC2. Elle est convexe si et seulement si?x? R

n, H[f](x)?0(i.e. la hessienne defest semi-définie positive en tous points).De façon générale, une fonction convexe peut être très compliquée sur le bord de son

domaine. Par exemple, la fonction 2D f(x,y) =?0six2+y2<1

φ(x,y)six2+y2= 1avecφ(x,y)≥0(2.1)

est convexe. Cependant, son comportement sur le bord peut être arbitrairerement com- plexe. Minimiser de telles fonctions est en général impossible. Cette remarque nous mène à nous restreindre à la classe de fonctions semi-continues inférieurement : Définition 2.6Une fonction convexe est diteferméeousemi-continue inférieurement (s.c.i.) si son épigraphe est une ensemble fermé.

14 2.2. Opérations sur les fonctions convexes

Exemple 2.1.1La fonction définie par

f(x) =?0six?[0,1[ a≥0six= 1(2.2)

et illustrée sur la figure 2.1.1 n"est fermée que sia= 0.Figure2.7 - Un exemple de fonction convexe dont l"épigraphe est ouvert (voir équation

(2.2). Son épigraphe est fermé seulement sia= 0. Remarque 2.2On verra plus tard que les fonctions convexes sont continues sur l"intérieur de leur domaine. Toutes les fonctions convexes dont le domaine estRntout entier sont donc continues. Théorème 2.5Les ensembles de niveau des fonctions convexes s.c.i. sont fermés. Exemple 2.1.2Donnons quelques exemples de fonctions convexes fermées. 1. L esfonctions f:Rn→Rconvexes telles quedom(f) =Rnsont fermées. Voir théorème 2.8. 2. L esfonctions liné airessont c onvexeset fermé es. 3. L esfonctions c onvexes,différ entiablessur Rnsont convexes et fermées. 4. L afonction f(x) =?x?où?·?est une norme quelconque est convexe et fermée. En 5. L afonction (2.1) n "estc onvexeet fermé eque si φ(x,y) = 0,?(x,y)?R2.

2.2 Opérations sur les fonctions convexes

Chapitre 2. Eléments d"analyse convexe 15

Théorème 2.6Soientf1etf2deux fonctions convexes s.c.i. etβ >0. Les fonctions suivantes sont convexes s.c.i. :

1.f(x) =βf1(x).

2.f(x) = (f1+f2)(x)etdom(f) =dom(f1)∩dom(f2).

3.f(x) = max{f1(x),f2(x)}etdom(f) =dom(f1)∩dom(f2).Preuve.Exercice.Théorème 2.7Soitφ(y), y?Rmune fonction convexe s.c.i. SoitA:Rn→Rm

un opérateur linéaire etb?Rn. Alors la fonctionf(x) =φ(Ax+b)est convexe s.c.i.

etdom(f) ={x?Rn,Ax+b?dom(φ)}.Preuve.Soient(x1,x2)?dom(f)×dom(f). On notey1=Ax1+bety2=Ax2+b. Alors

pour toutα?[0,1]: f(αx1+ (1-α)x2) =φ(α(Ax1+b) + (1-α)(Ax2+b)) La fermeture de l"épigraphe est due à la continuité de l"opérateur affinex?→Ax+b.

2.3 Continuité et différentiabilité

Lemme 2.2Soitfune fonction convexe etx0?int(dom(f)). Alorsfest majorée loca- lement enx01. Preuve.Soit? >0tel que les pointsx0±?ei?int(dom(f)). D"après le corollaire 2.1 on

Remarque 2.3Dans ces notes de cours, nous énonçons en général les résultats surint(dom(f)).

En réalité, la grande majorité des résultats présentés sont valables sur l"intérieur relatif de

dom(f), c"est-à-dire l"intérieur par rapport à la topologie induite sur le plus petit sous- espace affine contenantdom(f). Par exemple, l"intérieur du simplexe surRnest vide alors que l"intérieur relatif du simplexe est l"ensemble{x?Rn,xi>0,?i? {1,...,n},n i=1x i= 1}. Le lemme 2.2 implique la continuité d"une fonction convexe sur l"intérieur de son do-

maine.1. Note : elle peut exploser au voisinage du bord. Il suffit par exemple de considérer la fonctionx?→1/x

sur]0,1]pour s"en convaincre.

16 2.3. Continuité et différentiabilité

Théorème 2.8Soitfune fonction convexe etx0?int(dom(f)). Alorsfest conti- B

2(x0,?). Soity?B2(x0,?)etz?∂B2(x0,?)un point de la frontière tel quez=x0+

1α (y-x0)avecα=1? defon a donc : =f(x0) +M-f(x0)? ?yα-x0?2. Pour obtenir l"inégalité inverse, on considère un pointy?B2(x0,?)et on poseu= x

0+1α

(x0-y). On a?u-x0?2=?ety=x0+α(x0-u). D"après le théorème 2.1 on a donc : f(y)≥f(x0) +α(f(x0)-f(u)) ≥f(x0)-α(M-f(x0)) =f(x0)-M-f(x0)? ?y-x0?2.

On a donc?y?B2(x0,?):

?y-x0?2. Définition 2.7 (Dérivée directionnelle)Soitx?dom(f). On appelle dérivée directionnelle au pointxdans la directionpla limite suivante : f ?(x,p) = limα→0+1α (f(x+αp)-f(x)).

Si cette limite existe, on dit quef?(x,p)est la dérivée directionnelle defenx.Théorème 2.9Une fonction convexe est différentiable dans toutes les directions sur

tous les points de l"intérieur de son domaine.Preuve.Soitx?int(dom(f)). On considère la fonction

φ(α) =1α

(f(x+αp)-f(x)),α >0. Soitβ?]0,1]etα?]0,?]avec?suffisamment petit pour quex+?p?dom(f). Alors :

Chapitre 2. Eléments d"analyse convexe 17

Ainsi

φ(αβ) =1αβ

(f(x+αp)-f(x)) =φ(α). La fonctionφest donc décroissante au voisinage de0+. Pourγ >0tel quex-γp?dom(f) on a d"après le théorème 2.1 :

φ(α)≥1γ

(f(x)-f(x-γp)).

La limite quandα→0+existe donc.

Rappelons que la dérivabilité selon toute direction enxn"implique pas nécessairement la différentiabilité defenx. Le contre-exemple typique est la fonctionx→ |x|. Cette fonction est bien dérivable à droite et à gauche de0, mais elle n"est pas dérivable en0. Lemme 2.3Soitfune fonction convexe etx?int(dom(f)). Alorsf?(x,p)est une fonc- tion convexe enp, homogène de degré1. Pour touty?dom(f)on a f(y)≥f(x) +f?(x,y-x).(2.3) Preuve.Démontrons d"abord l"homogénéité. Pour toutp?Rnetτ >0, on a f ?(x,τp) = limα→0+1α (f(x+ατp)-f(x)) =τlimβ→0+1β (f(x+βp)-f(x)) =τf?(x0,p).

De plus, pour toutp1,p2?Rnetβ?[0,1]on obtient

f ?(x,βp1+ (1-β)p2) = limα→0+1α [f(x+α(βp1+ (1-β)p2))-f(x)] {β[f(x+αp1)-f(x) + (1-β)[f(x+αp2)-f(x)]} =βf?(x,p1) + (1-β)f?(x,p2). La fonctionf?(x,p)est donc convexe enp. Pour finir, soitα?]0,1],y?dom(f)etyα= x+α(y-x). D"après le théorème 2.1 on a : f(y) =f(yα+1α (1-α)(yα-x))≥f(yα) +1α (1-α)[f(yα)-f(x)].

On obtient (2.3) en faisant tendreαvers0+.

2.4 Théorèmes de séparation

18 2.4. Théorèmes de séparation

Définition 2.8SoitQ?Rnun ensemble convexe. On dit que l"hyperplan

H(g,γ) ={x?Rn,?g,x?=γ},g?= 0

l"hyperplanH(g,γ)sépare un pointx0deQsi pour toutx?Q. Lorsque les inégalités dans(2.4)sont strictes, on parle de séparation stricte.Définition 2.9 (Projection)SoitQ?Rnun ensemble fermé etx0?Rn. L"opé- rateur de projection surQest notéπQet il est défini pour toutx0?Rnpar

Q(x0) = argmin

x?Q?x-x0?2.Théorème 2.10SiQest convexe et fermé, il existe une unique projectionπQ(x0).Preuve.Il suffit de remarquer queπQ(x0) = argmin

x?Q12 ?x-x0?22et que la fonction12 ?x- x

0?22+χQ(x)est strictement convexe.Théorème 2.11Soitf:Rn→Rune fonction convexe différentiable etQun

ensemble convexe, fermé deRn. Le pointx??Rnest solution du problème de mini- misation suivant minx?Qf(x)(2.5) si et seulement si ??f(x?),x-x?? ≥0,?x?Q.(2.6)Preuve.Si l"inégalité (2.6) est vraie, alors f(x)≥f(x?) +??f(x?),x-x?? ≥f(x?) pour toutx?Q. Réciproquement, soitx?une solution de (2.5). Supposons qu"il existe x?Qtel que ??f(x?),x-x??<0. On poseφ(α) =f(x?+α(x-x?)),α?[0,1]. Cette fonction satisfaitφ(0) =f(x?)etφ?(0) = ??f(x?),x-x??<0. Ainsi, pourαsuffisamment petit, on af(x?+α(x-x?)) =φ(α)< φ(0) =f(x?), ce qui rentre en contradiction avec l"optimalité dex?. Corollaire 2.2SoitQ?Rnun ensemble fermé etx0/?Q. Alors pour toutx?Qon a ?πQ(x0)-x0,x-πQ(x0)? ≥0.(2.7)

Chapitre 2. Eléments d"analyse convexe 19

Preuve.Il suffit de remarquer queπQ(x0) = argminx?Q12 ?x-x0?22et d"appliquer le théorème 2.11. Enfin, on peut donner une sorte d"inégalité triangulaire pour la projection. Lemme 2.4SoitQ?Rnun ensemble convexe fermé. Pour toutx?Qon a

Preuve.D"après (2.7), on a

?x-πQ(x0)?22- ?x-x0?22=?x0-πQ(x0),2x-πQ(x0)-x0? Théorème 2.12SoitQ?Rnun ensemble convexe fermé etx0/?Q. Alors il existe un hyperplanH(g,γ)qui sépare strictementx0deQ. Il suffit par exemple de prendre g=x0-πQ(x0), γ=?x0-πQ(x0),πQ(x0)?.Preuve.D"après (2.7), pour toutx?Q, on a =?x0-πQ(x0),x0? - ?x0-πQ(x0)?22. Nous avons maintenant tous les ingrédients pour montrer une version géométrique du théorème de Hahn-Banach. Théorème 2.13SoitQ?Rnun ensemble convexe fermé etx0?∂Q, un point de la frontière deQ. Alors il existe un hyperplan d"appui àQpassant parx0. Si cet hyperplan s"écritH(g,γ), le vecteurgest dit support àQenx0. Preuve.On considère une suite(yk)k?Ntelle queyk/?Qetlimk→+∞yk=x0. On note g D"après le théorème 2.12, on a pour toutx?Q

De plus, comme?gk?2= 1on a :

|γk|=|?gk,πQ(yk)-x0?+?gk,x0?| La suite(γk)k?Nest donc bornée. Ainsi, on peut extraire une sous-suite de(gk)telle qu"il

existeg?= limk→+∞gketγ?= limk→+∞γk. Il suffit ensuite de prendre la limite en 2.8.

20 2.5. Sous-différentiel

quotesdbs_dbs33.pdfusesText_39
[PDF] fonction convexe plusieurs variables

[PDF] modélisation et simulation d'un moteur ? courant continu matlab

[PDF] modélisation mcc

[PDF] simulation mcc simulink

[PDF] asservissement et regulation de vitesse d'un moteur a courant continu

[PDF] modélisation d'un moteur ? courant continu

[PDF] equation differentielle moteur courant continu

[PDF] schéma bloc moteur ? courant continu

[PDF] commande pid d'un moteur ? courant continu pdf

[PDF] modélisation machine asynchrone simulink

[PDF] onduleur triphasé matlab

[PDF] cours de modélisation financière sous excel

[PDF] modélisation financière pdf

[PDF] fiche de lecture les misérables victor hugo pdf

[PDF] modélisation financière exemple