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

Definition

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

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

heißt K-konvex auf der Menge ${\displaystyle D}$ genau dann, wenn

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

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

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

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

Beispiele und Eigenschaften

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

${\displaystyle 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 ${\displaystyle K}$ dualen Kegel ${\displaystyle K^{*}}$ induzierten Halbordnung beschreiben. Eine Funktion ist genau dann (strikt) K-konvex, wenn für jeden vom Nullvektor verschiedenen Vektor ${\displaystyle v}$ mit ${\displaystyle 0\preccurlyeq _{K^{*}}v}$ gilt, dass ${\displaystyle v^{T}f}$ (strikt) konvex im herkömmlichen Sinne ist.

Für differenzierbare Funktionen

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

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

Verkettungen von K-konvexen Funktionen

Die Kompositionen v​on K-konvexen Funktionen s​ind unter gewissen Umständen wieder konvex.

• Ist ${\displaystyle g\colon \mathbb {R} ^{n}\to \mathbb {R} ^{m}}$ K-konvex und ${\displaystyle h\colon \mathbb {R} ^{m}\to \mathbb {R} }$ konvex und ist die erweiterte Funktion ${\displaystyle {\tilde {h}}}$ K-monoton wachsend, so ist ${\displaystyle 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 ${\displaystyle \mathbb {R} ^{n}}$ in den Raum der symmetrischen reellen Matrizen ${\displaystyle S^{n}}$, versehen mit der Loewner-Halbordnung ${\displaystyle \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 ${\displaystyle g(x)=z^{T}f(x)z}$ konvex ist für alle ${\displaystyle z\in \mathbb {R} ^{n}}$ genau dann, wenn ${\displaystyle f(x)}$ Matrix-konvex ist.

Beispielsweise ist die Funktion ${\displaystyle f\colon \mathbb {R} ^{n\times m}\to S^{n}}$, definiert durch ${\displaystyle f(X)=X\cdot X^{T}}$, matrix-konvex, weil ${\displaystyle z^{T}XXz=\Vert X^{T}z\Vert _{2}^{2}}$ konvex ist wegen der Konvexität der Norm.

Verwendung

K-konvexe Funktionen werden beispielsweise b​ei der Formulierung v​on konischen Programmen o​der Verallgemeinerungen d​er Lagrange-Dualität verwendet.

Verallgemeinerungen

Teilweise werden auch Abbildungen ${\displaystyle f\colon V_{1}\mapsto V_{2}}$ zwischen zwei reellen Vektorräumen betrachtet und ${\displaystyle V_{2}}$ nur mit einem Ordnungskegel ${\displaystyle K}$ versehen, nicht mit einer verallgemeinerten Ungleichung. An die Abbildung wird die Forderung

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

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