Verallgemeinerte Ungleichung

Eine verallgemeinerte Ungleichung (engl. generalized inequality) ist eine Halbordnung auf dem , die mittels eines Kegels definiert wird und die den 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.

DefinitionBearbeiten

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

 

eine Halbordnung auf  . Der Kegel enthält also alle "positiven" Elemente, also diejenigen, für die   gilt. Analog lässt sich durch

 

eine strikte Halbordnung auf   definieren. Dabei ist   das Innere des Kegels.

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

Ist   der zu   duale Kegel, so heißt   ( ) die zu   (  ) duale (strikte) Halbordnung oder duale verallgemeinerte Ungleichung.

EigenschaftenBearbeiten

Die verallgemeinerte Ungleichung   hat folgende Eigenschaften:

  • Sie ist abgeschlossen bezüglich Addition: Ist   und  , so ist  .
  • Sie ist abgeschlossen bezüglich der Multiplikation mit positiven Skalaren: Ist   und  , so ist  .
  • Sie ist transitiv, das heißt ist   und  , so ist auch  .
  • Sie ist reflexiv, das heißt es ist stets  .
  • Sie ist antisymmetrisch, das heißt ist   und  , so ist  .

Die strikte verallgemeinerte Ungleichung   hat folgende Eigenschaften:

  • Sie ist abgeschlossen bezüglich der Multiplikation mit echt positiven Skalaren, das heißt ist   und   , so ist  
  • Sie ist abgeschlossen bezüglich Addition: Ist   und  , so ist  .
  • Sie ist nicht reflexiv, das heißt es gilt nicht  .

Die duale (strikte) verallgemeinerte Ungleichung   ( ) hat folgende Eigenschaften:

  •   genau dann, wenn für alle   gilt, dass  .
  •   genau dann, wenn für alle   gilt, dass  .

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

Minimale Elemente und MinimumBearbeiten

Ein Element   einer Menge   heißt ein Minimum von   , wenn für alle   gilt, dass  . Äquivalent hierzu ist, dass  .

Ein Element   der Menge   heißt ein minimales Element von   , wenn aus   mit   folgt, dass  . Äquivalent hierzu ist, dass  .

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.

BeispieleBearbeiten

  • Sei in   der Kegel   gegeben. Dann stimmt die von diesem Kegel induzierte Ordnung mit der Ordnung auf   überein und die Null ist sowohl Minimum als auch minimales Element der Menge  
  • 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  , bei denen alle n Komponenten positiv sind. Die von diesem Kegel erzeugte verallgemeinerte Ungleichung ist genau das komponentenweise Vergleichen:
 .
  • Nicht alle Punkte   sind miteinander vergleichbar. So ist der Punkt   weder größer noch kleiner als die   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  -Matrizen, versehen mit dem Kegel   der positiv semidefiniten Matrizen, so ist die entsprechende verallgemeinerte Ungleichung die Loewner-Halbordnung  , wie sie zum Beispiel in der semidefiniten Programmierung verwendet wird.

VerwendungBearbeiten

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 NotationenBearbeiten

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   ein Kegel, setzt dann   und definiert die Funktion  , so ist   genau dann, wenn   und  . 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

 

die Notation

 ,

was äquivalent ist, wenn   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.

LiteraturBearbeiten

  • 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.