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 $\mathbb {R}$ abgeschwächt und es wird mit Halbordnungen auf $\mathbb {R} ^{m}$ gearbeitet, den sogenannten verallgemeinerten Ungleichungen.

Definition

Gegeben sei ein abgeschlossener, spitzer und konvexer Kegel $K\subset \mathbb {R} ^{m}$ mit nichtleerem Inneren und $\preccurlyeq _{K}$ bzw. $\prec _{K}$ die von diesem Kegel induzierte Halbordnung bzw. strikte Halbordnung. Des Weiteren sei $D$ eine konvexe Teilmenge des $\mathbb {R} ^{n}$. Die Funktion

$f\colon D\to \mathbb {R} ^{m}$

heißt K-konvex auf der Menge $D$ genau dann, wenn

$f(\lambda x+(1-\lambda )y)\preccurlyeq _{K}\lambda f(x)+(1-\lambda )f(y)$

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

$f(\lambda x+(1-\lambda )y)\prec _{K}\lambda f(x)+(1-\lambda )f(y)$

für alle $\lambda \in (0,1)$ und alle $x\neq y$ in $D$ gilt.

Beispiele und Eigenschaften

• Setzt man $m=1$, ist die Funktion also reellwertig, und wählt als Kegel die Menge $K=\{x\geq 0\}$, 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 $K=\{x\leq 0\}$, 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

$K=\{x\in \mathbb {R} ^{m}\,|\,x_{i}\geq 0\,{\text{ für alle }}\,i=1,\dots ,n\}$, 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 $K$ dualen Kegel $K^{*}$ induzierten Halbordnung beschreiben. Eine Funktion ist genau dann (strikt) K-konvex, wenn für jeden vom Nullvektor verschiedenen Vektor $v$ mit $0\preccurlyeq _{K^{*}}v$ gilt, dass $v^{T}f$ (strikt) konvex im herkömmlichen Sinne ist.

Für differenzierbare Funktionen

Ist $f$ eine differenzierbare Funktion, so ist diese genau dann K-konvex, wenn

$f(x)+Df(x)(y-x)\preccurlyeq _{K}f(y)$ für alle $x,y$. Hierbei ist $D$ die Jacobi-Matrix.

Verkettungen von K-konvexen Funktionen

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

• Ist $g\colon \mathbb {R} ^{n}\to \mathbb {R} ^{m}$ K-konvex und $h\colon \mathbb {R} ^{m}\to \mathbb {R}$ konvex und ist die erweiterte Funktion ${\tilde {h}}$ K-monoton wachsend, so ist $h(g(x))$ 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 $\mathbb {R} ^{n}$ in den Raum der symmetrischen reellen Matrizen $S^{n}$, versehen mit der Loewner-Halbordnung $\succcurlyeq _{S_{+}^{n}}$, so heißen die entsprechenden K-konvexen Funktionen auch Matrix-konvexe Funktionen. Eine äquivalente Charakterisierung der Matrix-Konvexität ist, dass die Funktion $g(x)=z^{T}f(x)z$ konvex ist für alle $z\in \mathbb {R} ^{n}$ genau dann, wenn $f(x)$ Matrix-konvex ist.

Beispielsweise ist die Funktion $f\colon \mathbb {R} ^{n\times m}\to S^{n}$, definiert durch $f(X)=X\cdot X^{T}$, matrix-konvex, weil $z^{T}XXz=\Vert X^{T}z\Vert _{2}^{2}$ 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 $f\colon V_{1}\mapsto V_{2}$ zwischen zwei reellen Vektorräumen betrachtet und $V_{2}$ nur mit einem Ordnungskegel $K$ versehen, nicht mit einer verallgemeinerten Ungleichung. An die Abbildung wird die Forderung

$\lambda f(x)+(1-\lambda )f(y)-f(\lambda x+(1-\lambda )y)\in K$

für alle $\lambda \in [0,1]$ und $x,y$ aus der konvexen Menge $M$ gestellt. Dann wird die Abbildung $f$ 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).