Verallgemeinerte Konvexität

Die verallgemeinerte Konvexität (englisch generalized convexity) ist eine Verallgemeinerung des gewöhnlichen Konvexitätsbegriff für Funktionen und Mengen, die sich insbesondere bei der Behandlung nicht-konvexer Optimierungsprobleme als nützlich erweist.

Φ-Konvexität

Gegeben sei eine Menge $X\neq \emptyset$ und die Menge aller Abbildungen von $X$ nach $\mathbb {R}$

F(X)=\{\varphi \mid \varphi \colon X\to \mathbb {R} \}

Eine Menge $\Phi \subseteq F(X)$ heißt Referenzsystem für $X$ genau dann, wenn gilt:

$\forall \varphi \in \Phi ,\lambda \geq 0:\lambda \varphi \in \Phi$
$\forall \varphi \in \Phi ,c\in \mathbb {R} :\varphi +c\in \Phi$

Φ-konvexe Funktion

Eine (erweiterte) reellwertige Funktion $f\colon X\mapsto {\overline {\mathbb {R} }}$ heißt $\Phi$ -konvex genau dann, wenn eine Menge $\Phi _{0}\subset \Phi$ existiert, so dass

f(x)=\sup _{\varphi \in \Phi _{0}}\varphi (x)

gilt.

Φ-konvexe Menge

Eine Menge $A\subseteq X$ heißt $\Phi$ -konvex genau dann, wenn es eine Menge $\Phi _{0}\subseteq \Phi$ gibt und zu jedem $\varphi \in \Phi _{0}$ ein $a_{\varphi }$ existiert, so dass

A=\bigcap _{\varphi \in \Phi _{0}}\{x\in X:\varphi (x)\leq a_{\phi }\}

Beispiele

Nimmt man zum Beispiel als Referenzsystem die affinen Funktionen, also $\Phi =\{\varphi \,|\,\varphi (x)=\langle v,x\rangle +c,v\in \mathbb {R} ^{n},c\in \mathbb {R} \}$ , dann stimmt die $\Phi$ -Konvexität mit der gewöhnlichen Konvexität überein.

Die Lipschitz-stetigen Funktionen sind zum Referenzsystem der peak-Funktionen $\Phi =\{\varphi \,|\,\varphi (x)=-k\cdot d(x,x_{0})+c,x_{0}\in X,c\in \mathbb {R} \}$ $\Phi$ -konvex.

Siehe auch

Literatur

Szymon Dolecki, Stanisl Aw Kurcyusz: On $\Phi$ -Convexity in Extremal Problems. In: SIAM Journal on Control and Optimization. Band 16, Nr. 2, 1978, S. 277–300, doi:10.1137/0316018 (aip.org).
Diethard Pallaschke, Rolewicz, S.: Foundations of Mathematical Optimization: Convex Analysis Without Linearity. Kluwer Academic Publishers, 1997, ISBN 0-7923-4424-3.