K-konvexe Funktion

Eine K-konvexe Funktion ist einer Verallgemeinerung des Begriffes der Konvexität einer Funktion auf reell-vektorwertige Funktionen. Dazu wird die strikte Ordnung auf <math> \mathbb{R} </math> abgeschwächt und es wird mit Halbordnungen auf <math> \mathbb{R}^m </math> gearbeitet, den sogenannten verallgemeinerten Ungleichungen.

Definition

Gegeben sei ein abgeschlossener, spitzer und konvexer Kegel <math> K \subset \mathbb{R}^m </math> mit nichtleerem Inneren und <math> \preccurlyeq_K </math> bzw. <math> \prec_K </math> die von diesem Kegel induzierte Halbordnung bzw. strikte Halbordnung. Des Weiteren sei <math>D</math> eine konvexe Teilmenge des <math> \R^n </math>. Die Funktion

<math> f\colon D \to \mathbb{R}^m </math>

heißt K-konvex auf der Menge <math> D </math> genau dann, wenn

<math> f(\lambda x + (1- \lambda)y) \preccurlyeq_K \lambda f(x)+ (1- \lambda) f(y) </math>

gilt für alle <math> \lambda \in [0,1]</math> und alle <math> x,y \in D </math>. Die Funktion <math> f </math> heißt strikt K-konvex auf der Menge <math> D </math>, wenn

<math> f(\lambda x + (1- \lambda)y) \prec_K \lambda f(x)+ (1- \lambda) f(y) </math>

für alle <math> \lambda \in (0,1) </math> und alle <math> x \neq y </math> in <math> D </math> gilt.

Beispiele und Eigenschaften

• Setzt man <math> m=1 </math>, ist die Funktion also reellwertig, und wählt als Kegel die Menge <math> K=\{x \geq 0\} </math>, so sind die K-konvexen Funktionen genau die konvexen Funktionen. Dies liegt daran, dass die von dem Kegel induzierte Ordnung die gewöhnliche Ordnung auf den reellen Zahlen ist.
• Wählt man hingegen als Kegel die Menge <math> K=\{x \leq 0\} </math>, so sind die K-konvexen Funktionen genau die konkaven Funktionen, da der Kegel die Ordnung auf den reellen Zahlen umkehrt.
• Ist der Kegel die Menge

<math> K=\{x \in \mathbb{R}^m \, | \, x_i \geq 0 \, \text{ für alle } \, i=1, \dots, n \} </math>, so ist die induzierte allgemeine Ungleichung das komponentenweise kleinergleich. Die K-konvexen Funktionen sind dann die Funktionen, deren Komponenten alle konvex sind.

• Affine Funktionen sind immer K-Konvex, unabhängig vom verwendeten Kegel. Dies folgt direkt aus der Linearität der Funktion und der Reflexivität der verallgemeinerten Ungleichung.
• Die Subniveaumenge einer K-konvexen Funktion ist eine konvexe Menge.
• Eine Funktion ist genau dann K-konvex, wenn ihr Epigraph eine konvexe Menge ist. Der Epigraph wird in diesem Fall mittels der verallgemeinerten Ungleichung und nicht mit dem herkömmlichen kleinergleich definiert.

Alternative Charakterisierungen

Über Dualität

Die K-Konvexität einer Funktion lässt sich auch gut mittels der von dem zu <math> K </math> dualen Kegel <math> K^* </math> induzierten Halbordnung beschreiben. Eine Funktion ist genau dann (strikt) K-konvex, wenn für jeden vom Nullvektor verschiedenen Vektor <math> v </math> mit <math> 0 \preccurlyeq_{K^*}v </math> gilt, dass <math> v^Tf </math> (strikt) konvex im herkömmlichen Sinne ist.

Für differenzierbare Funktionen

Ist <math> f </math> eine differenzierbare Funktion, so ist diese genau dann K-konvex, wenn

<math> f(x)+Df(x)(y-x) \preccurlyeq_{K} f(y) </math> für alle <math> x,y </math>. Hierbei ist <math> D </math> die Jacobi-Matrix.

Verkettungen von K-konvexen Funktionen

Die Kompositionen von K-konvexen Funktionen sind unter gewissen Umständen wieder konvex.

• Ist <math> g\colon \R^n \to \R^m </math> K-konvex und <math> h\colon \R^m \to \R </math> konvex und ist die erweiterte Funktion <math> \tilde h </math> K-monoton wachsend, so ist <math> h(g(x)) </math> konvex. Insbesondere müssen die beiden Kegel, welche die K-Konvexität und die K-Monotonie definieren, übereinstimmen.

Matrix-konvexe Funktionen

Betrachtet man Abbildungen vom <math> \R^n </math> in den Raum der symmetrischen reellen Matrizen <math> S^n </math>, versehen mit der Loewner-Halbordnung <math> \succcurlyeq_{S^n_+} </math>, so heißen die entsprechenden K-konvexen Funktionen auch Matrix-konvexe Funktionen. Eine äquivalente Charakterisierung der Matrix-Konvexität ist, dass die Funktion <math> g(x)=z^T f(x) z </math> konvex ist für alle <math> z \in \R^n</math> genau dann, wenn <math> f(x) </math> Matrix-konvex ist.

Beispielsweise ist die Funktion <math> f\colon \R^{n \times m} \to S^n </math>, definiert durch <math> f(X)=X\cdot X^T </math>, matrix-konvex, weil <math> z^TXXz=\Vert X^Tz\Vert_2^2 </math> konvex ist wegen der Konvexität der Norm.

Verwendung

K-konvexe Funktionen werden beispielsweise bei der Formulierung von konischen Programmen oder Verallgemeinerungen der Lagrange-Dualität verwendet.

Verallgemeinerungen

Teilweise werden auch Abbildungen <math> f\colon V_1 \mapsto V_2 </math> zwischen zwei reellen Vektorräumen betrachtet und <math> V_2 </math> nur mit einem Ordnungskegel <math> K </math> versehen, nicht mit einer verallgemeinerten Ungleichung. An die Abbildung wird die Forderung

<math> \lambda f(x) + (1-\lambda) f(y)-f(\lambda x + (1-\lambda)y) \in K</math>

für alle <math> \lambda \in [0,1] </math> und <math> x,y </math> aus der konvexen Menge <math> M </math> gestellt. Dann wird die Abbildung <math> f </math> wieder eine konvexe Abbildung genannt.

Literatur

• Stephen Boyd, Lieven Vandenberghe: Convex Optimization. Cambridge University Press, Cambridge, New York, Melbourne 2004, ISBN 978-0-521-83378-3 (online).