Analyse convexe - Convex analysis

Un polytope convexe en 3 dimensions. L'analyse convexe comprend non seulement l'étude de sous-ensembles convexes d'espaces euclidiens, mais aussi l'étude des fonctions convexes sur des espaces abstraits.

L'analyse convexe est la branche des mathématiques consacrée à l'étude des propriétés des fonctions convexes et des ensembles convexes , souvent avec des applications en minimisation convexe , un sous-domaine de la théorie de l' optimisation .

Ensembles convexes

Un sous - ensemble d'un espace vectoriel est appelé convexe s'il satisfait à l'une des conditions équivalentes suivantes : ${\ displaystyle C \ subseteq X}$ ${\style d'affichage X}$

1. Si est réel et alors${\style d'affichage 0\leq r\leq 1}$${\style d'affichage x,y\en C}$${\ displaystyle rx + (1-r) y \ en C.}$
2. Si est réel et avec alors${\ displaystyle 0 <r <1}$${\style d'affichage x,y\en C}$${\style d'affichage x\neq y,}$${\ displaystyle rx + (1-r) y \ en C.}$
3. ${\ Displaystyle (r + s) C = rC + sC}$pour tout positif réel et${\style d'affichage r>0}$${\style d'affichage s>0.}$

Fonctions convexes

Fonction convexe sur un intervalle.

Tout au long, sera une carte valorisée dans les nombres réels étendus avec un domaine qui est un sous-ensemble convexe d'un espace vectoriel. La carte est une fonction convexe si ${\ displaystyle f: X \ to [- \ infty, \ infty]}$ ${\displaystyle [-\infty ,\infty ]=\mathbb {R} \cup \{\pm \infty \}}$ ${\displaystyle \operatorname {domain} f=X}$${\ displaystyle f: X \ to [- \ infty, \ infty]}$

${\style d'affichage f(rx+(1-r)y)\leq rf(x)+(1-r)f(y)}$

( Convexité ≤ )

est valable pour tout réel et tout avec Si cela reste vrai lorsque l'inégalité de définition ( Convexité ≤ ) est remplacée par l'inégalité stricte ${\ displaystyle 0 <r <1}$${\style d'affichage x,y\dans X}$${\ Displaystyle x \ neq y.}$${\style d'affichage f}$

${\style d'affichage f(rx+(1-r)y)<rf(x)+(1-r)f(y)}$

( Convexité < )

alors est dit strictement convexe . ${\style d'affichage f}$

Les fonctions convexes sont liées aux ensembles convexes. Plus précisément, la fonction est convexe si et seulement si son épigraphe${\style d'affichage f}$

Une fonction (en noir) est convexe si et seulement si son épigraphe, qui est la région au-dessus de son graphique (en vert), est un ensemble convexe .

Un graphique de la fonction convexe bivariée${\ displaystyle x ^ {2} + xy + y ^ {2}.}$

${\displaystyle \operatorname {epi} f:=\left\{(x,r)\in X\times \mathbb {R} ~:~f(x)\leq r\right\}}$

( Épigraphe déf. )

est un ensemble convexe. Les épigraphes de fonctions étendues à valeurs réelles jouent un rôle dans l'analyse convexe qui est analogue au rôle joué par les graphes de fonctions à valeurs réelles dans l'analyse réelle . Plus précisément, l'épigraphe d'une fonction étendue à valeur réelle fournit une intuition géométrique qui peut être utilisée pour aider à formuler ou prouver des conjectures.

Le domaine d'une fonction est noté alors que son domaine effectif est l'ensemble ${\ displaystyle f: X \ to [- \ infty, \ infty]}$${\displaystyle \operatorname {domain} f}$

${\displaystyle \operatorname {dom} f:=\{x\in X~:~f(x)<\infty \}.}$

( dom f déf. )

La fonction est dite propre si et pour tous Alternativement, cela signifie qu'il en existe dans le domaine de auquel et n'est d'ailleurs jamais égal à En mots, une fonction est propre si son domaine n'est pas vide, elle ne prend jamais la valeur et il n'est pas non plus identique à Si est une fonction convexe propre alors il existe un vecteur et certains tels que ${\ displaystyle f: X \ to [- \ infty, \ infty]}$${\displaystyle \operatorname {dom} f\neq \varnothing }$${\displaystyle f(x)>-\infty }$ ${\displaystyle x\in \operatorname {domain} f.}$${\style d'affichage x}$${\style d'affichage f}$${\displaystyle f(x)\in \mathbb {R} }$${\style d'affichage f}$${\displaystyle -\infty .}$${\displaystyle -\infty ,}$${\ displaystyle + \ infty.}$${\displaystyle f:\mathbb {R} ^{n}\to [-\infty ,\infty ]}$${\displaystyle b\in \mathbb {R} ^{n}}$${\displaystyle r\in \mathbb {R} }$

${\displaystyle f(x)\geq x\cdot br}$     pour chaque ${\style d'affichage x}$

où désigne le produit scalaire de ces vecteurs. ${\ displaystyle x \ cdot b}$

Conjugué convexe

Le conjugué convexe d'une fonction à valeur réelle étendue (pas nécessairement convexe) est la fonction de l' espace dual (continu) de et ${\ displaystyle f: X \ to [- \ infty, \ infty]}$${\displaystyle f^{*}:X^{*}\to [-\infty ,\infty ]}$ ${\displaystyle X^{*}}$${\style d'affichage X,}$

${\displaystyle f^{*}\left(x^{*}\right)=\sup _{z\in X}\left\{\left\langle x^{*},z\right\rangle -f (z)\droit\}}$

où les parenthèses désignent la dualité canonique Le biconjugué de est l'application définie par pour chaque Si désigne l'ensemble des fonctions valuées sur alors l'application définie par est appelée la transformée de Legendre-Fenchel . ${\displaystyle \left\langle \cdot ,\cdot \right\rangle }$ ${\displaystyle \left\langle x^{*},z\right\rangle :=x^{*}(z).}$${\style d'affichage f}$${\displaystyle f^{**}=\left(f^{*}\right)^{*}:X\to [-\infty ,\infty ]}$${\displaystyle f^{**}(x):=\sup _{z^{*}\in X^{*}}\left\{\left\langle x,z^{*}\right\rangle -f\gauche(z^{*}\droit)\droit\}}$${\style d'affichage x\dans X.}$${\ displaystyle \ operatorname {Func} (X; Y)}$${\style d'affichage Y}$${\style d'affichage X,}$${\displaystyle \operatorname {Func} (X;[-\infty ,\infty ])\to \operatorname {Func} \left(X^{*};[-\infty ,\infty ]\right)}$${\displaystyle f\mapsto f^{*}}$

Ensemble sous-différentiel et inégalité de Fenchel-Young

Si et alors l' ensemble sous-différentiel est ${\ displaystyle f: X \ to [- \ infty, \ infty]}$${\style d'affichage x\dans X}$

${\displaystyle {\begin{alignedat}{4}\partial f(x):&=\left\{x^{*}\in X^{*}~:~f(z)\geq f(x) +\left\langle x^{*},zx\right\rangle {\text{ pour tout }}z\in X\right\}&&({\text{“}}z\in X{\text{' '}} {\ text {peut être remplacé par:}} {\ text {"}} z \ in X {\ text {tel que}} z \ neq x {\ text {' '}}) \\ & = \left\{x^{*}\in X^{*}~:~\left\langle x^{*},x\right\rangle -f(x)\geq \left\langle x^{*} ,z\right\rangle -f(z){\text{ pour tout }}z\in X\right\}&&\\&=\left\{x^{*}\in X^{*}~ : ~\left\langle x^{*},x\right\rangle -f(x)\geq \sup _{z\in X}\left\langle x^{*},z\right\rangle -f( z)\right\}&&{\text{ Le côté droit est }}f^{*}\left(x^{*}\right)\\&=\left\{x^{*}\in X ^{*}~:~\left\langle x^{*},x\right\rangle -f(x)=f^{*}\left(x^{*}\right)\right\}&&{ \text{ Prenant }}z:=x{\text{ dans le }}\sup {}{\text{ donne l'inégalité }}\leq .\\\end{alignedat}}}$

Par exemple, dans le cas particulier important où est une norme sur , on peut montrer que si alors cette définition se réduit à : ${\displaystyle f=\|\cdot \|}$${\style d'affichage X}$${\style d'affichage 0\neq x\in X}$

${\displaystyle \partial f(x)=\left\{x^{*}\in X^{*}~:~\left\langle x^{*},x\right\rangle =\|x\| {\text{ et }}\left\|x^{*}\right\|=1\right\}}$     et     ${\displaystyle \partial f(0)=\left\{x^{*}\in X^{*}~:~\left\|x^{*}\right\|\leq 1\right\}. }$

Pour tout et que l'on appelle l' inégalité de Fenchel-Young . Cette inégalité est une égalité (ie ) si et seulement si C'est ainsi que l'ensemble sous-différentiel est directement lié au conjugué convexe${\style d'affichage x\dans X}$${\displaystyle x^{*}\in X^{*},}$ ${\displaystyle f(x)+f^{*}\left(x^{*}\right)\geq \left\langle x^{*},x\right\rangle ,}$${\displaystyle f(x)+f^{*}\left(x^{*}\right)=\left\langle x^{*},x\right\rangle }$${\displaystyle x^{*}\in \partial f(x).}$${\displaystyle \partial f(x)}$${\displaystyle f^{*}\left(x^{*}\right).}$

Biconjugué

Le biconjugué d'une fonction est le conjugué du conjugué, généralement écrit comme Le biconjugué est utile pour montrer quand une dualité forte ou faible est maintenue (via la fonction de perturbation ). ${\ displaystyle f: X \ to [- \ infty, \ infty]}$${\displaystyle f^{**}:X\to [-\infty ,\infty ].}$

Pour tout, l'inégalité découle de l'inégalité de Fenchel-Young . Pour les fonctions propres , si et seulement si est convexe et inférieur semi-continu par le théorème de Fenchel–Moreau . ${\style d'affichage x\dans X,}$${\displaystyle f^{**}(x)\leq f(x)}$${\displaystyle f=f^{**}}$ ${\style d'affichage f}$

Minimisation convexe

Un problème de minimisation convexe ( primal ) est de la forme

trouver lorsqu'on leur donne une fonction convexe et un sous-ensemble convexe${\displaystyle \inf _{x\in M}f(x)}$${\ displaystyle f: X \ to [- \ infty, \ infty]}$${\displaystyle M\subseteq X.}$

Double problème

Dans la théorie de l'optimisation, le principe de dualité énonce que les problèmes d'optimisation peuvent être envisagés sous deux angles, le problème primal ou le problème dual.

En général, étant donné deux paires doubles séparées localement des espaces convexes et ensuite, étant donné la fonction, nous pouvons définir le problème primal comme la recherche telle que ${\displaystyle \left(X,X^{*}\right)}$${\displaystyle \left(Y,Y^{*}\right).}$${\displaystyle f:X\to [-\infty ,\infty ],}$${\style d'affichage x}$

${\displaystyle \inf _{x\in X}f(x).}$

S'il y a des conditions de contrainte, celles-ci peuvent être intégrées à la fonction en laissant où se trouve la fonction d'indicateur . Soit alors une fonction de perturbation telle que${\style d'affichage f}$${\ displaystyle f = f + I _ {\ mathrm {contraintes}}}$${\ displaystyle I}$${\displaystyle F:X\times Y\to [-\infty ,\infty ]}$${\style d'affichage F(x,0)=f(x).}$

Le problème dual par rapport à la fonction de perturbation choisie est donné par

${\ displaystyle \ sup _ {y ^ {*} \ in Y ^ {*}} - F ^ {*} \ left (0, y ^ {*} \ right)}$

où est le conjugué convexe dans les deux variables de${\style d'affichage F^{*}}$${\style d'affichage F.}$

L' écart de dualité est la différence des côtés droit et gauche de l'inégalité

${\displaystyle \sup _{y^{*}\in Y^{*}}-F^{*}\left(0,y^{*}\right)\leq \inf _{x\in X} F(x,0).}$

Ce principe est le même que la dualité faible . Si les deux côtés sont égaux l'un à l'autre, on dit que le problème satisfait une dualité forte .

Il existe de nombreuses conditions pour que la dualité forte se maintienne telles que :

• ${\style d'affichage F=F^{**}}$où est la fonction de perturbation reliant les problèmes primaux et dual et est le biconjugué de ;${\style d'affichage F}$${\style d'affichage F^{**}}$${\style d'affichage F}$
• le problème primal est un problème d'optimisation linéaire ;
• Condition de Slater pour un problème d'optimisation convexe .

La dualité Lagrange

Pour un problème de minimisation convexe avec contraintes d'inégalité,

${\ displaystyle \ min {} _ {x} f (x)}$soumis à pour${\displaystyle g_{i}(x)\leq 0}$${\displaystyle i=1,\ldots ,m.}$

le problème dual lagrangien est

${\displaystyle \sup {}_{u}\inf {}_{x}L(x,u)}$soumis à pour${\style d'affichage u_{i}(x)\geq 0}$${\displaystyle i=1,\ldots ,m.}$

où la fonction objectif est la fonction duale de Lagrange définie comme suit : ${\style d'affichage L(x,u)}$

${\displaystyle L(x,u)=f(x)+\sum _{j=1}^{m}u_{j}g_{j}(x)}$

Voir également

• Convexité en économie
  • Non-convexité (économie)
• Liste des sujets de convexité  – article de liste Wikipedia
• Werner Fenchel

Remarques

Les références

• Bauschke, Heinz H .; Combettes, Patrick L. (28 février 2017). Analyse convexe et théorie des opérateurs monotones dans les espaces de Hilbert . CMS Livres en Mathématiques. Springer Science & Business Media . ISBN 978-3-319-48311-5. OCLC  1037059594 .
• Boyd, Stephen ; Vandenberghe, Lieven (8 mars 2004). Optimisation convexe . Série Cambridge en mathématiques statistiques et probabilistes. Cambridge, Royaume-Uni New York : Cambridge University Press . ISBN 978-0-521-83378-3. OCLC  53331084 .
• Hiriart-Urruty, J.-B. ; Lemaréchal, C. (2001). Fondamentaux de l'analyse convexe . Berlin : Springer-Verlag. ISBN 978-3-540-42205-1.
• Kusraev, AG; Kutateladze, Semen Samsonovich (1995). Sous-différentiels : théorie et applications . Dordrecht : Kluwer Academic Publishers. ISBN 978-94-011-0265-0.
• Rockafellar, R. Tyrrell ; Mouille, Roger J.-B. (26 juin 2009). Analyse variationnelle . Grundlehren der mathematischen Wissenschaften. 317 . Berlin New York: Springer Science & Business Media . ISBN 9783642024313. OCLC  883392544 .
• Rudin, Walter (1991). Analyse fonctionnelle . Série Internationale de Mathématiques Pures et Appliquées. 8 (Deuxième éd.). New York, NY: McGraw-Hill Science / Ingénierie / Math . ISBN 978-0-07-054236-5. OCLC  21163277 .
• Chanteur, Ivan (1997). Analyse convexe abstraite . Série de monographies et de textes avancés de la Société mathématique du Canada. New York : John Wiley & Sons, Inc. p. xxii+491. ISBN 0-471-16015-6. MR  1461544 .
• Stoer, J.; Witzgall, C. (1970). Convexité et optimisation en dimensions finies . 1 . Berlin : Springer. ISBN 978-0-387-04835-2.
• Zălinescu, Constantin (30 juillet 2002). Analyse convexe dans les espaces vectoriels généraux . River Edge, NJ Londres: World Scientific Publishing . ISBN 978-981-4488-15-0. MR  1921556 . OCLC  285163112 .

Liens externes

• Médias liés à l' analyse convexe sur Wikimedia Commons