Einführung in die Mathematische Optimierung: Die Geometrie der Linearen Optimierung

Die äußere Darstellung "P = {x ∈ Rⁿ | Ax ≤ b}" definiert ein Polyeder durch die Schnittmenge von Halbräumen. Die innere Darstellung "P = conv V + ccone U" beschreibt das Polyeder als Kombination von konvexen und konischen Hüllen. Der Dekompositionssatz verknüpft diese beiden Darstellungen und bildet die Grundlage für viele weitere Untersuchungen. Die Äquivalenz beider Darstellungen ermöglicht es, zwischen ihnen zu wechseln, je nachdem, welche für das jeweilige Problem günstiger ist. Die rationale Darstellbarkeit spielt eine wichtige Rolle für die algorithmische Behandlung von Polyedern.

Die innere Darstellung erlaubt eine einfache Charakterisierung von Unzulässigkeit und Unbeschränktheit linearer Optimierungsprobleme. Existiert eine Optimallösung, so kann diese direkt aus der endlichen Menge V bestimmt werden. Die Polynomialität der Kodierungslängen hat wichtige Implikationen für die Komplexität linearer Optimierungsprobleme. Polynomiale Zertifikate für Optimalität können konstruiert werden. Die Existenz rationaler Optimallösungen mit polynomial beschränkter Kodierungslänge ist eine wichtige Konsequenz. Das Entscheidungsproblem der Lösbarkeit linearer Ungleichungssysteme liegt in NP ∩ coNP.

Der charakteristische Kegel char(P) eines Polyeders P enthält alle Richtungsvektoren, die zu jedem Punkt in P addiert werden können, ohne P zu verlassen. Er ist selbst ein polyedrischer Kegel. Polytope sind genau die beschränkten Polyeder, was äquivalent zu einem trivialen charakteristischen Kegel ist (Bemerkung 5.9). Die Darstellung "P = Q + K" als Summe eines Polytops Q und eines polyedrischen Kegels K verdeutlicht die Bedeutung des charakteristischen Kegels.

Der Linealitätsraum lineal(P) ist der größte lineare Unterraum, der in P enthalten ist. Er charakterisiert die Richtungen, in denen sich P unbeschränkt ausdehnt. Die affine Hülle aff(P) ist der kleinste affine Raum, der P enthält. Die Dimension dim(P) ist die Dimension von aff(P). Diese Begriffe sind eng miteinander verbunden und liefern wichtige Informationen über die geometrische Struktur von P.

Seiten von Polyedern sind wiederum Polyeder. Sie entstehen durch die Restriktion des Polyeders durch zusätzliche Gleichungen. Die Menge der Optimallösungen eines linearen Optimierungsproblems ist eine Seite des zugehörigen Polyeders. Gültige Ungleichungen für ein Polyeder lassen sich durch Linearkombinationen der definierenden Ungleichungen darstellen (Satz 5.15). Die äußere Darstellung von Seiten erfolgt durch Gleichungen (Satz 5.16).

Facetten sind die inklusionsmaximalen nicht-trivialen Seiten eines Polyeders. Ihre Dimension ist um eins kleiner als die Dimension des Polyeders (Satz 5.21). Irredundante Darstellungen (sowohl äußere als auch innere) vermeiden redundante Informationen. Eine irredundante äußere Darstellung besteht aus Gleichungen für die affine Hülle und Ungleichungen für die Facetten (Satz 5.22).