konvexes OP mit linearen Nb < Operations Research < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 17:40 Fr 08.05.2009 | | Autor: | mathema |
| Aufgabe | Seien [mm]\ S= conv({{P1,P2,P3,P4}}) \subset \IR^2 ~mit ~P1=[-2,0],P2=[-2,6], P3=[4,3],P4=[\bruch{1}{2},\bruch{3}{2}] ~und~ P=[\bruch{1}{2},0] ~gegeben.~ Gesucht ~ist~ ein~ P^\*\inS ~mit~ minimalem~ (euklidischen)~ Abstand ~zu~ P. [/mm]
(a) Formulieren Sie das Problem als konvexes Optimierungsproblem mit linearen Nebenbedingungen.
(b) Stellen Sie das zugehörige KKT-System auf.
(c) Finden Sie eine Lösung für das System aus (b) |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Hallo zusammen.
Ich bin mir unsicher mit der Aufgabe und hoffe auf Hilfestellung. Habe bisher noch wenig Erfahrung mit Optimierungsproblemen.
zu (a): Ein konvexes Optimierungsproblem mit linearen Nebenbedingungen ist von der folgenden Form:
min f(x) s.d [mm]\ Ax \le b [/mm] . Gesucht ist meines Erachtens der minimale Abstand von P zu [mm]\ P^\* [/mm] unter der Nebenbedingung, dass [mm]\ P^\* [/mm] in S liegt.
Als Zielfunktion habe ich mir folgendes überlegt:
[mm]\ min(f(x)) ~=~min \parallel P-P^\*\parallel ~= ~min\wurzel{(\bruch{1}{2}~-~X^\*)^2~+~(0-Y^\*)^2} [/mm]
Zu den Nebenbedingungen.
Ich habe mir die konvexe Hülle einmal aufgemalt und habe festgestellt, dass der Punkt P unterhalb der Menge S liegt. Daraus lässt sich folgern, dass der gesuchte Punkt [mm]\ P^\* [/mm] auf der Verbindungsstrecke von P1 und P4 liegen muss. Also auf der Geraden g(x)=1/2x +1 Meine Nebenbedingung habe ich dann formuliert als
1/2x + 1= y
Dies kann nicht stimmen. Allein schon weil ich zwei Gleichungen benötige (da ich zwei Unbekannte habe). Ein anderer Gedanke, den ich dann hatte ist der folgende: Ich habe die Gleichung der Gerade bestimmt die durch den Punkt P geht und senkrecht zu der Gerade g(x) verläuft.
also die Gleichung h(x)= -2x+1 .
Der gesuchte Punkt muss ja auf dem Schnitt der beiden Geraden liegen.
Die Nebenbedingung wäre dann.
-2x +1 =y
1/2x +1 =y
Der Nachteil hierbei: Ich benötige garnicht mehr meine Zielfunktion f(x), da ich den Punkt allein mit den Nebenbedingungen ermitteln kann.
Ich komme hier irgendwie nicht weiter. Sind meine Überlegungen überhaupt richtig? Wäre über einen Denkanstoß sehr dankbar.
Leider kann ich ja ohne den (a)-Teil die anderen Aufgabenteile nicht lösen.
Dankeschön
Mathema
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:20 Mo 11.05.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
