Fast-konvexe Funktion

Die fast konvexen Funktionen (englisch convex-like functions) bilden eine Verallgemeinerung der konvexen Funktionen und werden in der mathematischen Optimierung verwendet, da für sie einfache Regularitätsvoraussetzungen wie die Slater-Bedingung gelten, unter denen starke Dualität gilt und damit auch die Karush-Kuhn-Tucker-Bedingungen gelten.

Definition

Seien $V_{1},V_{2}$ reelle Vektorräume und $K\,$ ein Ordnungskegel auf $V_{2}$ sowie $D_{1}$ eine nichtleere Teilmenge von $V_{1}$. Dann heißt eine Abbildung $f\colon D_{1}\mapsto V_{2}$ fast konvex, wenn die Menge

$M:=f(D_{1})+K$

konvex ist. Die Menge $M$ lässt sich äquivalent beschreiben als

$M=\{y\in V_{2}\,|\,\exists x\in D_{1}{\text{ so dass }}f(x)-y\in -K\}$

Ist der Kegel ein echter Kegel und definiert damit eine verallgemeinerte Ungleichung $\preccurlyeq _{K}$, so lautet diese Menge

$M=\{y\in V_{2}\,|\,\exists x\in D_{1}{\text{ so dass }}f(x)\preccurlyeq _{K}y\}$

Beispiele

Betrachtet man die Funktion $f\colon \mathbb {R} \mapsto \mathbb {R}$ mit $f(x)=\sin(x)$ und den echten Kegel $K=\mathbb {R} _{+}=\{x\in \mathbb {R} \,|\,x\geq 0\}$ sowie $D_{1}=[0,2\pi ]$, so ist $\sin(D_{1})=[-1,1]$. Damit ist $M=[-1;1]+\mathbb {R} _{+}=\{x\in \mathbb {R} \,|\,x\geq -1\}$. Diese Menge ist konvex und damit ist die Sinusfunktion fast konvex.

Betrachtet man die Funktion $f(x)={\begin{cases}-1&{\text{ falls }}x\leq 0\\1&{\text{ falls }}x>0\end{cases}}$

und definiert $g\colon \mathbb {R} \mapsto \mathbb {R} ^{2}$ durch

$g(x)={\begin{pmatrix}f(x)\\5x\end{pmatrix}}$

auf $D_{0}=\mathbb {R}$ mit dem Ordnungskegel $K=\mathbb {R} _{+}\times \{0\}$. Für $x\in D_{1}=\{x\in \mathbb {R} \,|\,x\leq 0\}$ ist jeder Punkt der Bildmenge von der Form $(-1,5x)$ und damit ist $g(D_{1})=\{y\in \mathbb {R} ^{2}\,|\,y_{1}=-1,y_{2}\leq 0\}$. Analog folgt mit $D_{2}=\{x\in \mathbb {R} \,|\,x>0\}$, dass $g(D_{2})=\{y\in \mathbb {R} ^{2}\,|\,y_{1}=1,y_{2}>0\}$. Somit ist

${\begin{aligned}g(D_{1})+K=\{y\in \mathbb {R} ^{2}\,|\,y_{1}\geq -1,y_{2}\leq 0\}\\g(D_{2})+K=\{y\in \mathbb {R} ^{2}\,|\,y_{1}\geq 1,y_{2}>0\}\end{aligned}}$

Da aber $D_{0}=D_{1}\cup D_{2}$ ist, kann die Menge $g(D_{0})+K=g(D_{1}\cup D_{2})+K=\left(g(D_{1})+K\right)\cup \left(g(D_{2})+K\right)$ nicht konvex sein, da zum Beispiel die Punkte $(-1,0)^{T}$ und $(1,1)^{T}$ in $g(D_{0})+K$ enthalten sind, aber keiner der Punkte auf der Strecke zwischen ihnen. Zum Beispiel ist $(0,0{,}5)$ der Mittelpunkt dieser Strecke, aber nicht in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g(D_0)+K } enthalten.

Eigenschaften

Jede konvexe Funktion ist fast konvex bezüglich des natürlichen Kegels Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle K= \mathbb{R}_+ } . Dies folgt direkt aus der Konvexität des Epigraphs. Genauso ist auch jede K-konvexe Funktion fast konvex bezüglich ihres Kegels.

Verwendung

Die fast konvexen Funktionen sind eine Funktionenklasse, die so definiert ist, dass wenn sie die Slater-Bedingung erfüllt, die starke Dualität gilt. Sei also ein Optimierungsproblem der Form

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \begin{align} \text{Minimiere } & f(x) \\ \text{unter den Nebenbedingungen } & g(x) \in -K \\ & x \in R \end{align} }

gegeben für einen Ordnungskegel Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle K\,} mit nichtleerem Inneren und Abbildungen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f\colon V \mapsto \mathbb{R} } und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g\colon V \mapsto Y } . Dabei sind Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle V, Y } normierte reelle Vektorräume und die Funktion Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle K\colon V \mapsto \mathbb{R} \times Y } definiert durch Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle K(x)=(f(x), g(x)) } ist fast konvex bezüglich des Kegels Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathbb{R}_+ \times K } . Weiter sei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle R } eine beliebige nichtleere Teilmenge von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle V } .

Das Problem erfüllt nun die Slater-Bedingung, wenn es einen zulässigen Punkt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \tilde x } gibt. Das heißt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \tilde x \in R, \, g(\tilde x) \in -K } , so dass Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g( \tilde x) \in \operatorname{int}(-K) } ist. Dabei bezeichnet Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \operatorname{int}(M) } das Innere einer Menge.

Erfüllt solch ein Problem mit fast konvexen Funktionen nun die Slater-Bedingung, so gilt starke Dualität und damit zum Beispiel auch die Karush-Kuhn-Tucker-Bedingungen. Der Begriff der fast konvexen Funktion erweitert also die Dualitätstheorie der konvexen Funktionen auf Probleme, die nicht notwendigerweise konvex sein müssen. Dies hat den Vorteil, dass die Slater-Bedingung im Gegensatz zu vielen anderen Regularitätsbedingungen oder „constraint qualifications“ die Regularität des gesamten Problemes liefert, und nicht nur die Regularität in einem Punkt.

Literatur

• Johannes Jahn: Introduction to the Theory of Nonlinear Optimization. 3. Auflage. Springer, Berlin 2007, ISBN 978-3-540-49378-5.