Verallgemeinerte Konvexität

Die Verallgemeinerte Konvexität (engl. 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 Y nach $\R$

$F(X) = \{ \varphi | \varphi : Y \mapsto \R \}$

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

1. $\forall \varphi \in \Phi, \lambda \ge 0 : \lambda \varphi \in \Phi$
2. $\forall \varphi \in \Phi, c \in \R : \varphi + c \in \Phi$

Φ-konvexe Funktion

Eine (erweiterte) reellwertige Funktion $f: X \mapsto \overline{\R}$ heißt Φ-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 Φ-konvex genau dann, wenn es eine Menge $\Phi_0 \subseteq \Phi$ gibt und zu jedem $\varphi \in \Phi_0$ ein a_φ 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) = <v,x> + c, v \in \R^n, c \in \R\}$, dann stimmt die Φ-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 \R\}$ Φ-konvex.

Literatur

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

Siehe auch

• Konvexe Funktion
• Konvexe Menge
• Konvexe Optimierung