Polyeder und Kombinatorische Optimierung

[n***@strunk-online.net]

Hallo Leute!

Ich arbeite gerade mein Skript aus der Uni zum Thema Polyeder und
Kombinatorische Optimierung durch. Jetzt wollte ich mal fragen, ob meine
Anschauung so richtig ist. Also:

Polyeder sind ja Schnitte von endlich vielen Halbräumen der Form {x in R^n |
a^T x <= b} mit a in R^n. (a^T ist der transponierte Vektor). a^T x = b
wäre die zugehörige Hyperebene.

Wenn ich jetzt den Polyeder beschreiben will, dann nehme ich doch alle
Ungleichungen der Halbräume zusammen und erhalte daraus meine Beschreibung
für mein Polyeder: P = {x in R^n | Ax <= b} mit A in R^(m x n) und b in
R^m. Stimmt das soweit?

Ich möchte jetzt die Seiten/Ecken des Polyeders bestimmen. Dazu muß ich doch
die Schnitte der Hyperebenen betrachten, oder? Also wähle ich einige Zeilen
von A aus und erhalte daraus ein Gleichungssystem A'x = b' (kein < mehr,
sondern nur =, weil ich die Hyperebenen schneiden will). Das löse ich und
bekomme entweder eine Ecke (bei Dimension = 0) oder eine Seite, wenn die
Dimension der Lösung um eins kleiner ist als Dimension des Polyeders.

Stimmt das soweit? Oder hab ich da irgendwo einen Denkfehler?




Und jetzt habe ich noch eine Definition in meinem Skript, die ich nicht ganz
verstehe:

Sei P ein Polyeder.

(i) x in P heisst innerer Punkt von P (im topologischen Sinne), falls Ax <
b ist

(ii) x in P heißt algebraisch-innerer Punkt, falls a_i^T x < b_i für alle
I\I_0 gilt. mit I = {1..n} und I_0 := {i in {1..n}} | a_t^T = b_i für alle
x in P}

Beides sehe ich ein. Aber was ist der (anschauliche) Unterschied zwischen
einem inneren Punkt und einem algebraisch-inneren Punkt? Kann mir
vielleicht jemand dabei helfen?

Vielen Dank und schönen Tag noch!

Karsten

[Horst Kraemer]

Post by n***@strunk-online.net
Ich arbeite gerade mein Skript aus der Uni zum Thema Polyeder und
Kombinatorische Optimierung durch. Jetzt wollte ich mal fragen, ob meine
Polyeder sind ja Schnitte von endlich vielen Halbräumen der Form {x in R^n |
a^T x <= b} mit a in R^n. (a^T ist der transponierte Vektor). a^T x = b
wäre die zugehörige Hyperebene.
Wenn ich jetzt den Polyeder beschreiben will, dann nehme ich doch alle
Ungleichungen der Halbräume zusammen und erhalte daraus meine Beschreibung
für mein Polyeder: P = {x in R^n | Ax <= b} mit A in R^(m x n) und b in
R^m. Stimmt das soweit?

Der Durchschnitt endlich vieler Halbraeume ist zunaechst nur eine
konvexe polyedrische Punktmenge. Ein konvexes Polyeder wird es erst,
wenn die Punktemenge beschraenkt ist (also in irgendeine Kugel ||x||<r
passt). Fuer ein Polyeder sind mindestens n+1 Stueck erforderlich -
oder anders ausgedrueckt: der Durchschnitt von weniger als n+1
Halbraeumen ist entweder leer oder unbeschraenkt.

Post by n***@strunk-online.net
Ich möchte jetzt die Seiten/Ecken des Polyeders bestimmen. Dazu muß ich doch
die Schnitte der Hyperebenen betrachten, oder? Also wähle ich einige Zeilen
von A aus und erhalte daraus ein Gleichungssystem A'x = b' (kein < mehr,
sondern nur =, weil ich die Hyperebenen schneiden will). Das löse ich und
bekomme entweder eine Ecke (bei Dimension = 0) oder eine Seite, wenn die
Dimension der Lösung um eins kleiner ist als Dimension des Polyeders.
Stimmt das soweit? Oder hab ich da irgendwo einen Denkfehler?

Das ist leider etwas zu einfach dargestellt. Jede Ecke taucht als
Loesungmenge eines (oder mehrerer) Systeme von n Gleichungen auf, d.h.
an jeder Ecke treffen mindestens n Hyperebenen zusammen. Dies bedeutet
aber nicht, dass ein Punkt, der eindeutige Loesung irgendeines Systems
von n Gleichungen ist, auch Ecke des Polyeders ist. Er ist nur dann
eine Ecke, wenn er die verbleibenden m-n Ungleichungen erfuellt.

Beispiel: Ein Trapez im R^2. Wenn Du das Gleichungssystem loest, das
den beiden Hyperebenen (hier Geraden) fuer die nicht parallelen Seiten
entspricht, so erhaeltst Du einen Punkt, aber dieser Punkt liegt
ausserhalb des Trapezes.

Post by n***@strunk-online.net
Und jetzt habe ich noch eine Definition in meinem Skript, die ich nicht ganz
Sei P ein Polyeder.
(i) x in P heisst innerer Punkt von P (im topologischen Sinne), falls Ax <
b ist

Das heisst anschaulich, dass er drin ist, aber auf keiner der
Randhyperebenen liegt.

Post by n***@strunk-online.net
(ii) x in P heißt algebraisch-innerer Punkt, falls a_i^T x < b_i für alle
I\I_0 gilt. mit I = {1..n} und I_0 := {i in {1..n}} | a_t^T = b_i für alle
x in P}

Die zweite Definition definiert den Begriff "innerer Punkt" fuer
Faelle, in denen das Polyeder "ausgeartet" ist, d.h. wenn es kein
n-dimensionales Volumen hat, z.B. ein Dreieck im R^3.

Ein solches wird z.B. durch das System

x >= 0
y >= 0
x+y <= 1
z = 0

bzw. in kanonischer From

-x <= 0
-y <= 0
x +y <= 1
z <= 0
-z <= 0

beschrieben. Hier gilt z=0 fuer alle Punkte, die das System erfuellen,
d.h. die Ungleichungen 4 und 5 sind fuer alle p in P "mit Gleichheit"
erfuellt. Ein Punkt ist dann algebraisch innerer Punkt, wenn er alle
Ungleichungen, bis auf die, die *jeder* Punkt in P mit Gleichheit
erfuellt. mit < erfuellt. Hier also dann, wenn er topologisch innerer
Punkt des 2-dimensionalen Dreiecks ist, das durch das Polyeder
beschrieben wird. Er ist aber kein topologisch innerer Punkt von P,
weil P kein 3-dimensionales "Fleich" hat, d.h. keine offene Menge des
R^3 enthaelt, oder anders gesagt, weil der (toplogische) offene Kern
von P (in der Toplogie des R^3) die leere Menge ist.

[n***@strunk-online.net]

Post by Horst Kraemer

Post by n***@strunk-online.net
Ich arbeite gerade mein Skript aus der Uni zum Thema Polyeder und
Kombinatorische Optimierung durch. Jetzt wollte ich mal fragen, ob meine
Polyeder sind ja Schnitte von endlich vielen Halbräumen der Form {x in R^n |
a^T x <= b} mit a in R^n. (a^T ist der transponierte Vektor). a^T x = b
wäre die zugehörige Hyperebene.
Wenn ich jetzt den Polyeder beschreiben will, dann nehme ich doch alle
Ungleichungen der Halbräume zusammen und erhalte daraus meine
Beschreibung für mein Polyeder: P = {x in R^n | Ax <= b} mit A in R^(m x
n) und b in R^m. Stimmt das soweit?

Der Durchschnitt endlich vieler Halbraeume ist zunaechst nur eine
konvexe polyedrische Punktmenge. Ein konvexes Polyeder wird es erst,
wenn die Punktemenge beschraenkt ist (also in irgendeine Kugel ||x||<r
passt).

Ich dachte, ein Polyeder ist unbeschränkt und erst ein Polytop ist
beschränkt.

Post by Horst Kraemer
Fuer ein Polyeder sind mindestens n+1 Stueck erforderlich -
oder anders ausgedrueckt: der Durchschnitt von weniger als n+1
Halbraeumen ist entweder leer oder unbeschraenkt.

Ok, verstehe. Ich brauche also min. n+1 Halbräume, die sich schneiden, damit
es beschränkt ist. Aber all die Bedingungen für die Halbräume ergeben dann
zusammen die Matrixdarstellung des Polytops/Polyeders?

Post by Horst Kraemer

Post by n***@strunk-online.net
Ich möchte jetzt die Seiten/Ecken des Polyeders bestimmen. Dazu muß ich
doch die Schnitte der Hyperebenen betrachten, oder? Also wähle ich einige
Zeilen von A aus und erhalte daraus ein Gleichungssystem A'x = b' (kein <
mehr, sondern nur =, weil ich die Hyperebenen schneiden will). Das löse
ich und bekomme entweder eine Ecke (bei Dimension = 0) oder eine Seite,
wenn die Dimension der Lösung um eins kleiner ist als Dimension des
Polyeders.
Stimmt das soweit? Oder hab ich da irgendwo einen Denkfehler?

Das ist leider etwas zu einfach dargestellt. Jede Ecke taucht als
Loesungmenge eines (oder mehrerer) Systeme von n Gleichungen auf, d.h.
an jeder Ecke treffen mindestens n Hyperebenen zusammen. Dies bedeutet
aber nicht, dass ein Punkt, der eindeutige Loesung irgendeines Systems
von n Gleichungen ist, auch Ecke des Polyeders ist. Er ist nur dann
eine Ecke, wenn er die verbleibenden m-n Ungleichungen erfuellt.

Du hast natürlich Recht! Ich hatte vergessen, was von den zulässigen(!)
Lösungen zu schreiben.

Post by Horst Kraemer

Post by n***@strunk-online.net
Und jetzt habe ich noch eine Definition in meinem Skript, die ich nicht
Sei P ein Polyeder.
(i) x in P heisst innerer Punkt von P (im topologischen Sinne), falls Ax
< b ist

Das heisst anschaulich, dass er drin ist, aber auf keiner der
Randhyperebenen liegt.

Post by n***@strunk-online.net
(ii) x in P heißt algebraisch-innerer Punkt, falls a_i^T x < b_i für alle
I\I_0 gilt. mit I = {1..n} und I_0 := {i in {1..n}} | a_t^T = b_i für
alle x in P}

Die zweite Definition definiert den Begriff "innerer Punkt" fuer
Faelle, in denen das Polyeder "ausgeartet" ist, d.h. wenn es kein
n-dimensionales Volumen hat, z.B. ein Dreieck im R^3.
Ein solches wird z.B. durch das System
x >= 0
y >= 0
x+y <= 1
z = 0
bzw. in kanonischer From
-x <= 0
-y <= 0
x +y <= 1
z <= 0
-z <= 0
beschrieben. Hier gilt z=0 fuer alle Punkte, die das System erfuellen,
d.h. die Ungleichungen 4 und 5 sind fuer alle p in P "mit Gleichheit"
erfuellt. Ein Punkt ist dann algebraisch innerer Punkt, wenn er alle
Ungleichungen, bis auf die, die *jeder* Punkt in P mit Gleichheit
erfuellt. mit < erfuellt. Hier also dann, wenn er topologisch innerer
Punkt des 2-dimensionalen Dreiecks ist, das durch das Polyeder
beschrieben wird. Er ist aber kein topologisch innerer Punkt von P,
weil P kein 3-dimensionales "Fleich" hat, d.h. keine offene Menge des
R^3 enthaelt, oder anders gesagt, weil der (toplogische) offene Kern
von P (in der Toplogie des R^3) die leere Menge ist.

Achso! Bei einem ausgearteten Polytop (Volumen = 0), kann es also keine
topologisch inneren Punkte geben, sondern nur algebraisch-innere Punkte.

Und im Falle eines nicht-ausgeartetes Polytops müßten dann topologisch
innere Punkte auch algebraisch-innere Punkte sein und umgekehrt. Richtig?

Vielan Dank für Dein Antwort!

[Horst Kraemer]

Post by n***@strunk-online.net

Post by Horst Kraemer

Post by n***@strunk-online.net
Ich arbeite gerade mein Skript aus der Uni zum Thema Polyeder und
Kombinatorische Optimierung durch. Jetzt wollte ich mal fragen, ob meine
Polyeder sind ja Schnitte von endlich vielen Halbräumen der Form {x in R^n |
a^T x <= b} mit a in R^n. (a^T ist der transponierte Vektor). a^T x = b
wäre die zugehörige Hyperebene.
Wenn ich jetzt den Polyeder beschreiben will, dann nehme ich doch alle
Ungleichungen der Halbräume zusammen und erhalte daraus meine
Beschreibung für mein Polyeder: P = {x in R^n | Ax <= b} mit A in R^(m x
n) und b in R^m. Stimmt das soweit?

Der Durchschnitt endlich vieler Halbraeume ist zunaechst nur eine
konvexe polyedrische Punktmenge. Ein konvexes Polyeder wird es erst,
wenn die Punktemenge beschraenkt ist (also in irgendeine Kugel ||x||<r
passt).

Ich dachte, ein Polyeder ist unbeschränkt und erst ein Polytop ist
beschränkt.

Namen sind Schall und Rauch. Es gibt da verschiedene Vereinbarungen
bei den Poly-Begriffen. Halte Dich an den aus Deinen Unterlagen, wenn
Du daraus etwas zimmern musst.

Polytop ist sprachlich nur eine Verallgemeinerung der Begriffe Polygon
(2d) und Polyeder (3d) fuer beliebige Dimensionen. Eine
Gegenueberstellung Polyeder-Polygon fuer Objekte desselben R^n
erscheint mir daher nicht das Gegebenen zu sein. Ich kann aber nicht
ausschließen, dass es manche Autoren so halten, wie Du es beschrieben
hast.

Oft wird auch "Polyeder" als allgemeiner Begriff fuer beliebiges n
verwendet. Wenn das so gehandhabt wird, bezeichnet man Durchschnitte
von m Halbraeumen generell als "konvexe polyedrische Mengen" und im
Falle der Beschraenktheit (der Menge ;-) als "konvexe Polyeder".

Post by n***@strunk-online.net

Post by Horst Kraemer
Fuer ein Polyeder sind mindestens n+1 Stueck erforderlich -
oder anders ausgedrueckt: der Durchschnitt von weniger als n+1
Halbraeumen ist entweder leer oder unbeschraenkt.

Ok, verstehe. Ich brauche also min. n+1 Halbräume, die sich schneiden, damit
es beschränkt ist. Aber all die Bedingungen für die Halbräume ergeben dann
zusammen die Matrixdarstellung des Polytops/Polyeders?

Sie ergeben *eine* Matrixdarstellung. Die Definition schliesst aber
zunaechst nicht aus, dass diese Matrix redundante Zeilen hat, die
nichts zum eigentliche Polyeder beitragen.

Z.b. ist hier

-x <= 0
-y <= 0
x+y = 1
3x+4y <= 12


die 4.Ungleichung redundant, da sie von allen (x,y) erfuellt wird, die
die UGl 1-3 erfuellen. Eine deratige Redundanz sieht man einem System
i.a. nicht unmittelbar an.

Post by n***@strunk-online.net

Post by Horst Kraemer

Post by n***@strunk-online.net
Ich möchte jetzt die Seiten/Ecken des Polyeders bestimmen. Dazu muß ich
doch die Schnitte der Hyperebenen betrachten, oder? Also wähle ich einige
Zeilen von A aus und erhalte daraus ein Gleichungssystem A'x = b' (kein <
mehr, sondern nur =, weil ich die Hyperebenen schneiden will). Das löse
ich und bekomme entweder eine Ecke (bei Dimension = 0) oder eine Seite,
wenn die Dimension der Lösung um eins kleiner ist als Dimension des
Polyeders.
Stimmt das soweit? Oder hab ich da irgendwo einen Denkfehler?

Das ist leider etwas zu einfach dargestellt. Jede Ecke taucht als
Loesungmenge eines (oder mehrerer) Systeme von n Gleichungen auf, d.h.
an jeder Ecke treffen mindestens n Hyperebenen zusammen. Dies bedeutet
aber nicht, dass ein Punkt, der eindeutige Loesung irgendeines Systems
von n Gleichungen ist, auch Ecke des Polyeders ist. Er ist nur dann
eine Ecke, wenn er die verbleibenden m-n Ungleichungen erfuellt.

Du hast natürlich Recht! Ich hatte vergessen, was von den zulässigen(!)
Lösungen zu schreiben.

Post by Horst Kraemer

Post by n***@strunk-online.net
Und jetzt habe ich noch eine Definition in meinem Skript, die ich nicht
Sei P ein Polyeder.
(i) x in P heisst innerer Punkt von P (im topologischen Sinne), falls Ax
< b ist

Das heisst anschaulich, dass er drin ist, aber auf keiner der
Randhyperebenen liegt.

Post by n***@strunk-online.net
(ii) x in P heißt algebraisch-innerer Punkt, falls a_i^T x < b_i für alle
I\I_0 gilt. mit I = {1..n} und I_0 := {i in {1..n}} | a_t^T = b_i für
alle x in P}

Die zweite Definition definiert den Begriff "innerer Punkt" fuer
Faelle, in denen das Polyeder "ausgeartet" ist, d.h. wenn es kein
n-dimensionales Volumen hat, z.B. ein Dreieck im R^3.
Ein solches wird z.B. durch das System
x >= 0
y >= 0
x+y <= 1
z = 0
bzw. in kanonischer From
-x <= 0
-y <= 0
x +y <= 1
z <= 0
-z <= 0
beschrieben. Hier gilt z=0 fuer alle Punkte, die das System erfuellen,
d.h. die Ungleichungen 4 und 5 sind fuer alle p in P "mit Gleichheit"
erfuellt. Ein Punkt ist dann algebraisch innerer Punkt, wenn er alle
Ungleichungen, bis auf die, die *jeder* Punkt in P mit Gleichheit
erfuellt. mit < erfuellt. Hier also dann, wenn er topologisch innerer
Punkt des 2-dimensionalen Dreiecks ist, das durch das Polyeder
beschrieben wird. Er ist aber kein topologisch innerer Punkt von P,
weil P kein 3-dimensionales "Fleich" hat, d.h. keine offene Menge des
R^3 enthaelt, oder anders gesagt, weil der (toplogische) offene Kern
von P (in der Toplogie des R^3) die leere Menge ist.

Achso! Bei einem ausgearteten Polytop (Volumen = 0), kann es also keine
topologisch inneren Punkte geben, sondern nur algebraisch-innere Punkte.

Ja.

Post by n***@strunk-online.net
Und im Falle eines nicht-ausgeartetes Polytops müßten dann topologisch
innere Punkte auch algebraisch-innere Punkte sein und umgekehrt. Richtig?

So ist es wohl. Dann ist die Indexmenge I0 (fuer die Ungleichungen,
die von allen x als Gleichung erfuellt werden) halt leer, und fuer
leeres I0 sind beide Definitionen aequivalent. (in der angegebenen
Definition eines algebraischen inneren Punkts stoerte mich ein wenig,
dass fuer die Anzahl der UG der Buchstabe n verwendet wurde. Dieser
ist normalerweise fuer die Dimension des betrachteten Raums R^n
reserviert, und die Schreibweise koennte daher zu Missverstaendnissen
fuehren.)

[Markus Steinborn]

Hallo,

Post by n***@strunk-online.net
Ich dachte, ein Polyeder ist unbeschränkt und erst ein Polytop ist
beschränkt.

So kenne ich es auch.


Grüße

Markus