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
reelle Vektorräume und
ein Ordnungskegel auf
sowie
eine nichtleere Teilmenge von
. Dann heißt eine Abbildung
fast konvex, wenn die Menge
![{\displaystyle M:=f(D_{1})+K}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a78622041d1d4a415f16e37bed522c6f8ffd75b5)
konvex ist. Die Menge
lässt sich äquivalent beschreiben als
![{\displaystyle M=\{y\in V_{2}\,|\,\exists x\in D_{1}{\text{ so dass }}f(x)-y\in -K\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ad69fcfb7ed56e158776711cd3c23bdb3813712b)
Ist der Kegel ein echter Kegel und definiert damit eine verallgemeinerte Ungleichung
, so lautet diese Menge
![{\displaystyle M=\{y\in V_{2}\,|\,\exists x\in D_{1}{\text{ so dass }}f(x)\preccurlyeq _{K}y\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b74918afceac7b39fa377df622b25a788cd4c391)
Beispiele
Betrachtet man die Funktion
mit
und den echten Kegel
sowie
, so ist
. Damit ist
. Diese Menge ist konvex und damit ist die Sinusfunktion fast konvex.
Betrachtet man die Funktion
und definiert
durch
![{\displaystyle g(x)={\begin{pmatrix}f(x)\\5x\end{pmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fa6675b49cfbd702ce0e8fe147668cc7584bc6f3)
auf
mit dem Ordnungskegel
. Für
ist jeder Punkt der Bildmenge von der Form
und damit ist
. Analog folgt mit
, dass
. Somit ist
![{\displaystyle {\begin{aligned}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{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/151df4d219995f9a16ec13ba426da8f30d2fbbb6)
Da aber
ist, kann die Menge
nicht konvex sein, da zum Beispiel die Punkte
und
in
enthalten sind, aber keiner der Punkte auf der Strecke zwischen ihnen. Zum Beispiel ist
der Mittelpunkt dieser Strecke, aber nicht in
enthalten.
Eigenschaften
Jede konvexe Funktion ist fast konvex bezüglich des natürlichen Kegels
. 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
![{\displaystyle {\begin{aligned}{\text{Minimiere }}&f(x)\\{\text{unter den Nebenbedingungen }}&g(x)\in -K\\&x\in R\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7f259bc60a4cd09a0ce62b0a8a248e2e12bcb36b)
gegeben für einen Ordnungskegel
mit nichtleerem Inneren und Abbildungen
und
. Dabei sind
normierte reelle Vektorräume und die Funktion
definiert durch
ist fast konvex bezüglich des Kegels
. Weiter sei
eine beliebige nichtleere Teilmenge von
.
Das Problem erfüllt nun die Slater-Bedingung, wenn es einen zulässigen Punkt
gibt. Das heißt
, so dass
ist. Dabei bezeichnet
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.