Beschränktheit von H-Polytopen

Neue Frage »

[email protected] Auf diesen Beitrag antworten »
Beschränktheit von H-Polytopen
Hallo Leute,

kennt einer ein Kriterium, mit dem man nachweisen kann, dass die Menge

(mit vorgegebenen konstanten Vektoren . Somit ist die obige Menge ein Schnitt von Halbräumen oder auch ein Polyeder.)

beschränkt ist?

Eine weitere Frage wäre, wie man die Beschränktheit von



nachweisen kann (hier hat man im schnitt also immer paare von halbräumen mit paralleler grenzfläche).

Im letzteren Problemfall drängt sich mir dir Vermutung auf, dass die Menge genau dann beschränkt ist, wenn die Normalenvektoren den ganzen aufspannen. Jedenfalls ist das im 2-dim und 3-dimensionalen intuitiv nachvollziehbar. Aber ein Beweis ist mir hier nicht gelungen.

Jemand eine Idee???
Abakus Auf diesen Beitrag antworten »
RE: Beschränktheit von H-Polytopen
Hallo,

zB im 2-dimensionalen Raum:



und



Wird das beschränkt?

Abakus smile
smalls Auf diesen Beitrag antworten »
RE: Beschränktheit von H-Polytopen
Nein, das ist natürlich nicht beschränkt. Aber was willst du mir damit sagen?

(Falls damit meine Vermutung für den zweiten Fall widerlegt werden soll, dann muss ich sagen, dass die unteren Schranken fehlen.)
René Gruber Auf diesen Beitrag antworten »

Eine Möglichkeit scheint mir zu sein, das ganze als zulässiges Gebiet eines Linearen Optimierungsproblems zu formulieren und dann mit den dort üblichen Methoden zu entscheiden, ob dieses Gebiet leer ist oder nicht.
keinthema Auf diesen Beitrag antworten »

Man sollte für die erste Menge eine Fallunterscheidung machen.
Sind die v linear unabhängig so ist die Menge nie leer und man sieht die Unbeschränktheit schnell ein.
Allgemein würde ich das Lemma von Farkas empfehlen um auszuschließen, dass die Menge leer ist. (Hierzu die transponierten v als Zeilen einer Matrix A schreiben.)
So viel für den Moment...
Abakus Auf diesen Beitrag antworten »
RE: Beschränktheit von H-Polytopen
Zitat:
Original von smalls
(Falls damit meine Vermutung für den zweiten Fall widerlegt werden soll, dann muss ich sagen, dass die unteren Schranken fehlen.)


Es ist ja selbst mit unteren Schranken immer noch unbeschränkt. Demnach geht es so nicht?

Abakus smile
 
 
smalls Auf diesen Beitrag antworten »

Zitat:
Original von René Gruber
Eine Möglichkeit scheint mir zu sein, das ganze als zulässiges Gebiet eines Linearen Optimierungsproblems zu formulieren und dann mit den dort üblichen Methoden zu entscheiden, ob dieses Gebiet leer ist oder nicht.


Hi, danke für den Vorschlag. Aber welche Optimierungsrichtung soll man da angeben? Selbst wenn es unbeschränkt ist, wird es Richtungen geben in denen es beschränkt ist und dann bekomme ich ein Optimum und weiß dass es in der gegebenen Richtung beschränkt ist. Ich muss dann schon das Glück haben, eine Richtung zu haben, in der es unbeschränkt sein muss und kann das dann mit einem Linearen Programm testen. Siehst du das anders?
smalls Auf diesen Beitrag antworten »
RE: Beschränktheit von H-Polytopen
Zitat:
Original von Abakus
[quote]Original von smalls

Es ist ja selbst mit unteren Schranken immer noch unbeschränkt. Demnach geht es so nicht?

Abakus smile


Ist es das? Zeig mir ein Beispiel wo das so ist, und ich falle vor dir auf die Knie! verwirrt
smalls Auf diesen Beitrag antworten »

Zitat:
Original von keinthema
Allgemein würde ich das Lemma von Farkas empfehlen um auszuschließen, dass die Menge leer ist. (Hierzu die transponierten v als Zeilen einer Matrix A schreiben.)
So viel für den Moment...



Hi, wie ich das genau anwenden soll ist mir jetzt auch nicht klar und ein prinzipielles Problem scheint mir zu sein, dass Farkas Lemma nur betrachtet. Solche Einschränkungen sind im hier betrachteten Problem kontraproduktiv, denke ich..
smalls Auf diesen Beitrag antworten »

Hi Leute,
für das zweite Problem habe ich nun eine Lösung gefunden. Es ist tatsächlich so, dass

beschränkt ist genau dann wenn die den gesamen aufspannen.

Grundlegend ist es davon auszugehen, dass die Unbeschränktheit des Polyeders, ich nenne ihn mal P, die Existenz eines Strahls mit sich bringt, der vollständig im Polyeder P liegt. Dann sieht man schnell, dass für alle Normalenvektoren n_i gelten muss: vn_i=0. Denn sonst, also falls vn_i<0 für ein n_i gilt, komme ich auf dem Strahl unter die untere Schranke A_i. Und wenn vn_i>0, dann komme ich auf dem Strahl über die obere Schranke B_i. Damit liegen sie aber alle in einer Ebene und spannen eben nicht mehr den ganzen R^n auf...
Dieser Fall ist also ganz einfach (es sei denn man versucht zu zeigen, dass die Norm aller Elemente in P beschränkt ist, so habe ich angefangen, und es ging einfach nicht auf...)

Und jetzt wird mir vielleicht auch klar wie das im ersten Problemfall mit Farkas Lemma funktionieren könnte...
Abakus Auf diesen Beitrag antworten »
RE: Beschränktheit von H-Polytopen
Zitat:
Original von Abakus
zB im 2-dimensionalen Raum:



und



Wird das beschränkt?


Ist das kein Beispiel? Du kannst noch hinzufügen und hast untere Grenzen. Dennoch lässt sich das x beliebig groß wählen.

Oder hab ich da was völlig missverstanden?

Und nein, für ein Anbetungsobjekt baue ich selbst zu viel Mist Augenzwinkern , zuviel der Ehre.

Abakus smile
smalls Auf diesen Beitrag antworten »
RE: Beschränktheit von H-Polytopen
Hi Abakus,

es muss schon eine linearform sein, die nach unten und oben beschränkt ist. also -x+y müsste nach oben und unten beschränkt sein, oder aber y nach oben und unten. dann wäre es eine instanz des zweiten problems.
Abakus Auf diesen Beitrag antworten »
RE: Beschränktheit von H-Polytopen
Zitat:
Original von smalls
es muss schon eine linearform sein, die nach unten und oben beschränkt ist. also -x+y müsste nach oben und unten beschränkt sein, oder aber y nach oben und unten. dann wäre es eine instanz des zweiten problems.


Ich bezog mich erstmal auf die erste Frage nur. Da haben wir uns missverstanden.

Abakus smile
gonnabphd Auf diesen Beitrag antworten »

Hi,

Man könnte sich mal die Matrix anschauen für das erste Problem (insbesondere sollte man die Linearität des Problems ausnutzen). Beachte insbesondere, dass mit stets folgt und der Kern ein Unterraum von ist.


Beispielhaft mal, was du eh schon bewiesen hast wie ich oben lese:
Für die zweite Frage ergibt sich z.B. damit sofort: Wenn die Vektoren v_i linear unabhängig sind, dann ist A ein Homöomorphismus (da Vektorraumisomorphismus).

Edit: (weiss nicht, was ich gestern genau gedacht habe)

Die Menge ist genau die Menge



Da stetig ist, folgt aus der Kompaktheit von auch diejenige von .

Insbesondere ist letztere Menge beschränkt.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »