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: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|\mathrm{\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|\mathrm{\exists }x\in D_1\text{ so dass }f(x){\preccurlyeq }_{K}y\}$

Beispiele

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

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

und definiert $g:ℝ\mapsto {ℝ}^2$ durch

$g(x)=\left(\begin{array}{c}f(x)\\ 5x\end{array}\right)$

auf $D_0=ℝ$ mit dem Ordnungskegel $K={ℝ}_{+}\times \{0\}$. Für $x\in D_1=\{x\in ℝ|x\le 0\}$ ist jeder Punkt der Bildmenge von der Form $(-1,5x)$ und damit ist $g(D_1)=\{y\in {ℝ}^2|y_1=-1,y_2\le 0\}$. Analog folgt mit $D_2=\{x\in ℝ|x>0\}$, dass $g(D_2)=\{y\in {ℝ}^2|y_1=1,y_2>0\}$. Somit ist

$\begin{array}{c}g(D_1)+K=\{y\in {ℝ}^2|y_1\ge -1,y_2\le 0\}\\ g(D_2)+K=\{y\in {ℝ}^2|y_1\ge 1,y_2>0\}\end{array}$

Da aber $D_0=D_1\cup D_2$ ist, kann die Menge $g(D_0)+K=g(D_1\cup D_2)+K=(g(D_1)+K)\cup (g(D_2)+K)$ 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 $g(D_0)+K$ enthalten.

Eigenschaften

Jede konvexe Funktion ist fast konvex bezüglich des natürlichen Kegels $K={ℝ}_{+}$. 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

$\begin{array}{cc}\text{Minimiere }& f(x)\\ \text{unter den Nebenbedingungen }& g(x)\in -K\\ & x\in R\end{array}$

gegeben für einen Ordnungskegel $K$ mit nichtleerem Inneren und Abbildungen $f:V\mapsto ℝ$ und $g:V\mapsto Y$. Dabei sind $V,Y$ normierte reelle Vektorräume und die Funktion $K:V\mapsto ℝ\times Y$ definiert durch $K(x)=(f(x),g(x))$ ist fast konvex bezüglich des Kegels ${ℝ}_{+}\times K$. Weiter sei $R$ eine beliebige nichtleere Teilmenge von $V$.

Das Problem erfüllt nun die Slater-Bedingung, wenn es einen zulässigen Punkt $\tilde{x}$ gibt. Das heißt $\tilde{x}\in R,g(\tilde{x})\in -K$, so dass $g(\tilde{x})\in \mathrm{int}(-K)$ ist. Dabei bezeichnet $\mathrm{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.