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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle K } , der ein nichtleeres Inneres besitzt. Dann definiert

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x \preccurlyeq_K y \text{ genau dann, wenn } y-x \in K }

eine Halbordnung auf Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \R^n } . Der Kegel enthält also alle "positiven" Elemente, also diejenigen, für die Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 0_n \preccurlyeq_K y } gilt. Analog lässt sich durch

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S \subset x+K } .

Ein Element Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x } der Menge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S } heißt ein minimales Element von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S } , wenn aus Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle y \preccurlyeq_K x } mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle y \in S } folgt, dass Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle y=x } . Äquivalent hierzu ist, dass Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathbb{R}^1 } der Kegel Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle K=\{x \geq 0\} } gegeben. Dann stimmt die von diesem Kegel induzierte Ordnung mit der Ordnung auf Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathbb{R} } überein und die Null ist sowohl Minimum als auch minimales Element der Menge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle [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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathbb{R}^n } , bei denen alle n Komponenten positiv sind. Die von diesem Kegel erzeugte verallgemeinerte Ungleichung ist genau das komponentenweise Vergleichen:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x \preccurlyeq_K y \text{ genau dann wenn } x_i \leq y_i \, \text{ für alle } i=1, \dots, n } .

• Nicht alle Punkte Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x,y } sind miteinander vergleichbar. So ist der Punkt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (1,-1) } weder größer noch kleiner als die Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n \times n } -Matrizen, versehen mit dem Kegel $S_{+}^{n}$ der positiv semidefiniten Matrizen, so ist die entsprechende verallgemeinerte Ungleichung die Loewner-Halbordnung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle K=\{0\}\times \mathbb{R}_{\geq 0} \subset \mathbb{R}^2 } ein Kegel, setzt dann Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x \leq_K y \iff y-x \in K } und definiert die Funktion Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f(x)=(g(x),h(x))^T } , so ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f(x) \leq_K 0 } genau dann, wenn Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g(x) = 0 } und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g(x) \preccurlyeq_{K} 0 }

die Notation

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g(x)\in -K } ,

was äquivalent ist, wenn Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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.