Verallgemeinerte Ungleichung

Eine verallgemeinerte Ungleichung (engl. generalized inequality) ist eine Halbordnung auf dem $\mathbb {R} ^{n}$, die mittels eines Kegels definiert wird und die den $\mathbb {R} ^{n}$ zu einem geordneten Vektorraum macht. Verallgemeinerte Ungleichungen werden in der Optimierung verwendet, um auch noch in höheren Dimensionen Punkte sinnvoll miteinander vergleichen zu können. Außerdem kann man mit verallgemeinerten Ungleichungen den Begriff der konvexen Funktionen auf vektorwertige Funktionen verallgemeinern.

Definition

Gegeben sei ein abgeschlossener, spitzer und konvexer Kegel $K$, der ein nichtleeres Inneres besitzt. Dann definiert

$x\preccurlyeq _{K}y{\text{ genau dann, wenn }}y-x\in K$

eine Halbordnung auf $\mathbb {R} ^{n}$. Der Kegel enthält also alle „positiven“ Elemente, also diejenigen, für die $0_{n}\preccurlyeq _{K}y$ gilt. Analog lässt sich durch

$x\prec _{K}y{\text{ genau dann, wenn }}y-x\in K^{\circ }$

eine strikte Halbordnung auf $\mathbb {R} ^{n}$ definieren. Dabei ist $K^{\circ }$ das Innere des Kegels.

Die Ungleichungen bezüglich dieser Halbordnung werden verallgemeinerte Ungleichungen (bezüglich der von dem Kegel $K$ induzierten Halbordnung) genannt.

Ist $K^{*}$ der zu $K$ duale Kegel, so heißt $\preccurlyeq _{K^{*}}$ ($\prec _{K^{*}}$) die zu $\preccurlyeq _{K}$ ( $\prec _{K}$) duale (strikte) Halbordnung oder duale verallgemeinerte Ungleichung.

Eigenschaften

Die verallgemeinerte Ungleichung $\preccurlyeq _{K}$ hat folgende Eigenschaften:

• Sie ist abgeschlossen bezüglich Addition: Ist $a\preccurlyeq _{K}b$ und $c\preccurlyeq _{K}d$, so ist $a+c\preccurlyeq _{K}b+d$.
• Sie ist abgeschlossen bezüglich der Multiplikation mit positiven Skalaren: Ist $\lambda \in [0,\infty )$ und $a\preccurlyeq _{K}b$, so ist $\lambda a\preccurlyeq _{K}\lambda b$.
• Sie ist transitiv, das heißt, ist $a\preccurlyeq _{K}b$ und $b\preccurlyeq _{K}c$, so ist auch $a\preccurlyeq _{K}c$.
• Sie ist reflexiv, das heißt, es ist stets $a\preccurlyeq _{K}a$.
• Sie ist antisymmetrisch, das heißt, ist $a\preccurlyeq _{K}b$ und $b\preccurlyeq _{K}a$, so ist $a=b$.

Die strikte verallgemeinerte Ungleichung $\prec _{K}$ hat folgende Eigenschaften:

• Sie ist abgeschlossen bezüglich der Multiplikation mit echt positiven Skalaren, das heißt, ist $\lambda >0$ und $a\prec _{K}b$ , so ist $\lambda a\prec _{K}\lambda b$
• Sie ist abgeschlossen bezüglich Addition: Ist $a\prec _{K}b$ und $c\preccurlyeq _{K}d$, so ist $a+c\prec _{K}b+d$.
• Sie ist nicht reflexiv, das heißt, es gilt nicht $a\prec _{K}a$.

Die duale (strikte) verallgemeinerte Ungleichung $\preccurlyeq _{K^{*}}$ ($\prec _{K^{*}}$) hat folgende Eigenschaften:

• $a\preccurlyeq _{K}b$ genau dann, wenn für alle $y\succcurlyeq _{K^{*}}0$ gilt, dass $\langle y;a\rangle \leq \langle y;b\rangle$.
• $a\prec _{K}b$ genau dann, wenn für alle $y\succ _{K^{*}}0\,,y\neq 0$ gilt, dass $\langle y;a\rangle <\langle y;b\rangle$.

Alle diese Eigenschaften folgen direkt aus den Eigenschaften der definierenden Kegel.

Minimale Elemente und Minimum

Ein Element $x$ einer Menge $S$ heißt ein Minimum von $S$ , wenn für alle $y\in S$ gilt, dass $x\preccurlyeq _{K}y$. Äquivalent hierzu ist, dass $S\subset x+K$.

Ein Element $x$ der Menge $S$ heißt ein minimales Element von $S$ , wenn aus $y\preccurlyeq _{K}x$ mit $y\in S$ folgt, dass $y=x$. Äquivalent hierzu ist, dass $(x-K)\cap S=\{x\}$.

Analog lassen sich auch die Begriffe Maximum und maximales Element definieren. Die Begriffe können zusammenfallen, tun dies aber im Allgemeinen nicht! Ein Beispiel für ein minimales oder maximales Element einer Menge ist das Pareto-Optimum.

Beispiele

• Sei in $\mathbb {R} ^{1}$ der Kegel $K=\{x\geq 0\}$ gegeben. Dann stimmt die von diesem Kegel induzierte Ordnung mit der Ordnung auf $\mathbb {R}$ überein und die Null ist sowohl Minimum als auch minimales Element der Menge $[0,1]$
• Betrachtet man die n Einheitsvektoren und die von ihnen aufgespannte konvexe Hülle, so lässt sich ein kleinster Kegel konstruieren, der diese Menge enthält. Dieser Kegel enthält dann alle Punkte des $\mathbb {R} ^{n}$, bei denen alle n Komponenten positiv sind. Die von diesem Kegel erzeugte verallgemeinerte Ungleichung ist genau das komponentenweise Vergleichen:

$x\preccurlyeq _{K}y{\text{ genau dann wenn }}x_{i}\leq y_{i}\,{\text{ für alle }}i=1,\dots ,n$.

• Nicht alle Punkte $x,y$ sind miteinander vergleichbar. So ist der Punkt $(1,-1)$ weder größer noch kleiner als die $0_{\mathbb {R} ^{2}}$ bezüglich der oben definierten Halbordnung. Dies folgt daraus, dass es sich im Allgemeinen um keine Totalordnung handelt.
• Betrachtet man den Vektorraum der reellen symmetrischen $n\times n$-Matrizen, versehen mit dem Kegel $S_{+}^{n}$ der positiv semidefiniten Matrizen, so ist die entsprechende verallgemeinerte Ungleichung die Loewner-Halbordnung $\preccurlyeq _{S_{+}^{n}}$, wie sie zum Beispiel in der semidefiniten Programmierung verwendet wird.

Verwendung

Verallgemeinerte Ungleichungen spielen eine wichtige Rolle in der Vektoroptimierung, um eine Vergleichbarkeit von Vektoren zu garantieren. Außerdem erlauben verallgemeinerte Ungleichungen die Verallgemeinerung von konvexen Funktionen auf vektorwertige Funktionen, die sogenannten K-konvexen Funktionen. Diese Finden zum Beispiel bei der Formulierung von konischen Programmen eine Rolle.

Abwandlungen und alternative Notationen

In der Optimierung werden teilweise Kegel zur Definition von Ordnungen verwendet, deren Inneres leer ist. Dies hat den Vorteil, dass man Gleichungs- und Ungleichungsrestriktionen komponentenweise in eine Funktion schreiben kann. Ist zum Beispiel $K=\{0\}\times \mathbb {R} _{\geq 0}\subset \mathbb {R} ^{2}$ ein Kegel, setzt dann $x\leq _{K}y\iff y-x\in K$ und definiert die Funktion $f(x)=(g(x),h(x))^{T}$, so ist $f(x)\leq _{K}0$ genau dann, wenn $g(x)=0$ und $h(x)\leq 0$. Nachteil ist, dass sich die zugehörige strikte Ungleichung nicht mehr definieren lässt und damit einige Aussagen wie zum Beispiel die Slater-Bedingung umständlich zu formulieren werden.

Gelegentlich findet man auch anstelle der Formulierung

$g(x)\preccurlyeq _{K}0$

die Notation

$g(x)\in -K$,

was äquivalent ist, wenn $K$ ein echter Kegel ist. Meist handelt es sich jedoch nur um einen Ordnungskegel. Die zweite Notationsweise wird bevorzugt dann genutzt, wenn man schwächere Voraussetzungen an den Kegel stellt und/oder sich in unendlichdimensionalen Vektorräumen bewegt.

Literatur

• Boyd, Stephen; Vandenberghe, Lieven (2004). Convex Optimization. Cambridge University Press. ISBN 978-0-521-83378-3. ( online )
• Johannes Jahn: Introduction to the Theory of Nonlinear Optimization. 3. Auflage. Springer, Berlin 2007, ISBN 978-3-540-49378-5.