Halbraum Schnitte und Normalengleichungen

Neue Frage »

LtJax Auf diesen Beitrag antworten »
Halbraum Schnitte und Normalengleichungen
Ich weiss nicht so recht wie ich das ganze beschreiben soll, deshalb schiess ich einfach mal nach besten Gewissen los und wenn ich etwas unklar bin lässt sich das später ja bestimmt noch verbessern.
Also, ich habe einen nichtleeren Schnitt von m Halbräumen im Q^n gegeben, also ein Gleichungssystem der Form Ax<=b, wobei A Element von Q^(m x n) ist, x aus Q^n und b aus Q^m.
Ich brauche jetzt nur eine (nicht weiter spezielle) Lösung von diesem Gleichungssystem.
Meine Frage ist nun: passt die Lösung der zugehörigen Normalengleichung, die ja min{|Ax-b|} löst immer da rein? das wäre nämlich sehr praktisch...
AD Auf diesen Beitrag antworten »

I.a. leider nicht: Ändere z.B. mal bei nur einer Halbraumungleichung das Relationszeichen (d.h. betrachte gerade den anderen Halbraum), dann ändert sich die Lösung von min( |Ax-b|) nicht, wohl aber das Gebiet, welches zu dem ursprünglichen Gebiet sogar disjunkt ist!
LtJax Auf diesen Beitrag antworten »

klar, allein aus den Eigenschaften der beiden Gleichungen sehe ich das auch ein. Aber ich dachte halt dass das vielleich durch zusätzliche Eigenschaften der Normalgleichung hinkommen könnte. So rein anschaulich würd ich nämlich Erwarten dass die Lösung der Normalgleichung innerhalb des durch die Hyperebenen eingegrenzten Raums liegt (und auch so ne art Mittelpunkt is) da wenn man was von dem Mittelpunkt entfernt, der Abstand zu mind einer der Ebenen quadratisch wächst, während zu den (mehr oder weniger) gegenüberliegenden Ebenen der Abstand in viel geringerem Maße schwindet (weils ja quadratisch is). Ich würds ja gerne Beweisen (oder zur Not auch widerlegen), aber bis jetzt is mir fehlt mir für beides ein Ansatz.
Also hilfe bezüglich des Beweises oder Widerspruchs wäre sehr hilfreich...

Edit: Meine These ist also: Sei y so dass |Ay-b| minimal ist und Ax<=b lösbar für x => x=y ist Lösung von Ax<=b
(Dein Beispiel widerspricht dem ja nicht)
AD Auf diesen Beitrag antworten »

Ein Beispiel: Ich betrachte das Dreieck



und lege jetzt noch die Gerade rein, die zusammen mit den obigen Bedingungen über



ein Gebiet (ein Trapez) definiert, oder über das Gegenteil



ein anderes, von dem ersten disjunktes Gebiet (Dreieck), d.h., zumindest das Innere beider Gebiete ist disjunkt Trotzdem ist



in deinem min(|Ax-b|) ein und dasselbe.


LtJax Auf diesen Beitrag antworten »

joa okay, das ist wohl richtig, auch wenns schade ist.
Was wäre denn der direkte Weg einen Punkt innerhalb eines gegebenen Konvexen Raumes zu finden?
Ben Sisko Auf diesen Beitrag antworten »

Zitat:
Original von LtJax
joa okay, das ist wohl richtig, auch wenns schade ist.
Big Laugh

Willst du einen beliebigen Punkt in dem konvexen Raum, den du durch gegeben hast?
Wäre es praktikabel das zugehörige Gleichungssystem zu lösen?

Gruß vom Ben
 
 
LtJax Auf diesen Beitrag antworten »

jop, ein beliebiger Punkt tut's. Das zugehörige LGS kann man ja in der Regel nicht lösen, das es meistens überbesetzt ist.
Und wie man das gegebene Ungleichungsystem löst weiss ich nicht. (Obwohl ich mal gehört hab dass man sowas mit dem Simplex Algorithmus lösen kann)

mfg, ltj
Ben Sisko Auf diesen Beitrag antworten »

Ja, hier könnte dir der Simplex-Algorithmus (Phase I) helfen, der eine zulässige Lösung bestimmt, unabhängig von der Zielfunktion, also einfach einen Punkt in deinem Polyeder.
Die Phase I wird vermutlich nicht ganz so einfach zu finden sein wie der Simplex-Algo generell, da in nicht-mathematischen Beispielen häufig davon ausgegangen wird, dass man einen zulässigen Punkt sofort hinschreiben kann (häufig der Nullpunkt).

Gruß vom Ben
AD Auf diesen Beitrag antworten »

Hmmm, lange nicht gemacht, aber es dürfte ungefähr so gehen:

Du startest im Nullpunkt und schaust dir an:

a) Sind alle Komponenten nichtnegativ, dann kannst du den Nullpunkt als Startpunkt nehmen. Andernfalls

b) In alle Zeilen mit negativen Werten führst du eine zusätzliche Schlupfvariable ein. Dadurch gelangst du zu einem zulässigen Anfangstableau des Simplexalgorithmus. Als Zielfunktion nimmst du nun die Summe der zusätzlichen Schlupfvariablen und minimierst diese durch den Simplexalgorithmus. Ist das Minimum Null, dann bist du mit den Endtableau in deinem gewünschten Gebiet "drin" (genauer gesagt: auf dem Rand); ist das Minimum dagegen größer als Null, dann ist dein Gebiet leer.
Neue Frage »
Antworten »



Verwandte Themen

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