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 <math> V_1, V_2 </math> reelle Vektorräume und <math>K\,</math> ein Ordnungskegel auf <math> V_2 </math> sowie <math> D_1 </math> eine nichtleere Teilmenge von <math> V_1 </math>. Dann heißt eine Abbildung <math> f\colon D_1 \mapsto V_2 </math> fast konvex, wenn die Menge

<math> M:=f(D_1)+K </math>

konvex ist. Die Menge <math> M </math> lässt sich äquivalent beschreiben als

<math> M= \{ y \in V_2 \, | \, \exists x \in D_1 \text{ so dass } f(x)-y \in -K\} </math>

Ist der Kegel ein echter Kegel und definiert damit eine verallgemeinerte Ungleichung <math> \preccurlyeq_K </math>, so lautet diese Menge

<math> M= \{ y \in V_2 \, | \, \exists x \in D_1 \text{ so dass } f(x) \preccurlyeq_K y \} </math>

Beispiele

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

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

und definiert <math> g\colon \mathbb{R} \mapsto \mathbb{R}^2 </math> durch

<math> g(x)=

\begin{pmatrix} f(x) \\ 5x \end{pmatrix} </math>

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

<math> \begin{align}

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{align}</math> Da aber <math> D_0=D_1 \cup D_2 </math> ist, kann die Menge <math> g(D_0)+K=g(D_1 \cup D_2)+K = \left( g(D_1) +K \right) \cup \left( g(D_2) +K \right)</math> nicht konvex sein, da zum Beispiel die Punkte <math> (-1,0)^T </math> und <math> (1,1)^T </math> in <math> g(D_0)+K </math> enthalten sind, aber keiner der Punkte auf der Strecke zwischen ihnen. Zum Beispiel ist <math> (0, 0 {,}5) </math> der Mittelpunkt dieser Strecke, aber nicht in <math> g(D_0)+K </math> enthalten.

Eigenschaften

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

<math> \begin{align}

\text{Minimiere } & f(x) \\ \text{unter den Nebenbedingungen } & g(x) \in -K \\

& x \in R

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

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