Forum:  Numerik & Optimierung
Thema: Nichttriviale Seitenflächen von "reduzierten" Polyedern
Themen-Übersicht
Pathygoras
Junior
Dabei seit: 03.11.2019
Mitteilungen: 5
Aus:
Themenstart: 2019-11-19 16:22

Hallo zusammen,

ich möchte/soll folgendes beweisen:

Sei \(P(A, b)\) ein volldimensionales Polyeder mit der Indexmenge \(M=\{1,...,m\}\), \(A\in R^{mxn}\), \(b\in R^m\) und sei \( \tilde{P}=P(A_{M \setminus \{i\}}, b_{M \setminus\{i\}}) \)

Z.z: \(P \neq \tilde{P} \Leftrightarrow \) \(\exists\) eine nichttriviale Seitenfläche \(F \subseteq P\) mit EqualitySet(\(F\))=\(\{i\}\)

Leider komme ich weder für die eine, noch für die andere Richtung auf einen Ansatz.
Vielleicht kann mir jemand einen Tipp geben :)
Danke schon mal

Pathygoras


ochen
Senior
Dabei seit: 09.03.2015
Mitteilungen: 2877
Aus: der Nähe von Schwerin
Beitrag No.1, eingetragen 2019-11-20 11:46

Hallo,

ich verstehe die rechte Seite von dem Äquvalenzpfeil nicht. Bei $\tilde{P}$ ist einfach nur die $i$-te Ungleichungsrestriktion weggestrichen. Falls die beiden Polytope immernoch die gleichen sind (also $P=\tilde{P}$ gilt), so ist diese Ungleichungsrestriktion bedeutungslos. Das heißt also, dass das gesamte Polytop in dem Halbraum $\{x\mid \langle a_i,x\rangle \leq b_i\}$ liegt.


Pathygoras
Junior
Dabei seit: 03.11.2019
Mitteilungen: 5
Aus:
Beitrag No.2, vom Themenstarter, eingetragen 2019-11-20 13:31

2019-11-20 11:46 - ochen in Beitrag No. 1 schreibt:
Hallo,

ich verstehe die rechte Seite von dem Äquvalenzpfeil nicht. Bei $\tilde{P}$ ist einfach nur die $i$-te Ungleichungsrestriktion weggestrichen. Falls die beiden Polytope immernoch die gleichen sind (also $P=\tilde{P}$ gilt), so ist diese Ungleichungsrestriktion bedeutungslos. Das heißt also, dass das gesamte Polytop in dem Halbraum $\{x\mid \langle a_i,x\rangle \leq b_i\}$ liegt.

Hi,

in der Äquivalenz hatte sich ein Fehler eingeschlichen, ich habe diesen behoben.

Leider verstehe ich noch nicht, inwiefern eine redundante i-te Ungleichung die Existenz einer Seitenfläche mit \(eq(F)=\{i\}\) induziert und andersrum.

Wir haben noch einen Tipp bekommen, über die Existenz eines relativ inneren Punktes der Seitenfläche \(fa(i\) zu gehen.
VG


ochen
Senior
Dabei seit: 09.03.2015
Mitteilungen: 2877
Aus: der Nähe von Schwerin
Beitrag No.3, eingetragen 2019-11-20 14:10

Ist dir $P\subseteq \tilde{P}\cap \{x\mid \langle a_i,x\rangle \leq b_i\}$ klar? Gilt auch die umgekehrte Inklusion?


Pathygoras
Junior
Dabei seit: 03.11.2019
Mitteilungen: 5
Aus:
Beitrag No.4, vom Themenstarter, eingetragen 2019-11-20 20:10

2019-11-20 14:10 - ochen in Beitrag No. 3 schreibt:
Ist dir $P\subseteq \tilde{P}\cap \{x\mid \langle a_i,x\rangle \leq b_i\}$ klar?
Ja das verstehe ich. Wenn wir \(\tilde{P}\) mit der i-ten Ungleichung weiter restringieren, landen wir bei \(P\)

Gilt auch die umgekehrte Inklusion?
Ich würde sagen nein, bzw nur, wenn die i-te Ungleichung redundant ist


ochen
Senior
Dabei seit: 09.03.2015
Mitteilungen: 2877
Aus: der Nähe von Schwerin
Beitrag No.5, eingetragen 2019-11-21 15:11

2019-11-20 20:10 - Pathygoras in Beitrag No. 4 schreibt:
2019-11-20 14:10 - ochen in Beitrag No. 3 schreibt:
Ist dir $P\subseteq \tilde{P}\cap \{x\mid \langle a_i,x\rangle \leq b_i\}$ klar?
Ja das verstehe ich. Wenn wir \(\tilde{P}\) mit der i-ten Ungleichung weiter restringieren, landen wir bei \(P\)

Gilt auch die umgekehrte Inklusion?
Ich würde sagen nein, bzw nur, wenn die i-te Ungleichung redundant ist

Warum sollte $P\supseteq \tilde{P}\cap \{x\mid \langle a_i,x\rangle \leq b_i\}$ nicht gelten? Kannst du ein Gegenbeispiel angeben?




Dieses Forumbeitrag kommt von Matroids Matheplanet
https://https://matheplanet.de

Die URL für dieses Forum-Thema ist:
https://https://matheplanet.de/default3.html?topic=244456=110
Druckdatum: 2020-08-14 02:47