Ganzzahlige Optimierung mit quadratischen Randbedingungen |
06.03.2013, 12:57 | Jone | Auf diesen Beitrag antworten » | ||||
Ganzzahlige Optimierung mit quadratischen Randbedingungen Sehr geehrtes Forum, habe folgende Optimierungsaufgabe: Minimiere die Funktion , sodass reelle Zahlen sind und zu gegebenen Randbedingungen: (exemplarisch) Weiß irgendjemand wie man so etwas angeht? Oder umformuliert? Oder hat einer Links zu diesem Thema? Meine Ideen: Mir ist auf jeden Fall bewusst, dass das Problem NP-schwer ist, aber ich hoffe dennoch, dass man irgendwie diese nicht-Linearität aus den Randbedingungen kriegen könnte, um damit dann einen LP-Solver zu füttern. Mein eigentliches Problem ist dann bspw. gegeben mit 100 Variablen und vielen gleichartigen Bedingungen wie letztere. |
||||||
06.03.2013, 14:54 | RavenOnJ | Auf diesen Beitrag antworten » | ||||
RE: Ganzzahlige Optimierung mit quadratischen Randbedingungen
überheb dich nicht. Man duzt sich hier.
Müsste sowas nicht mit Lagrange lösbar sein? Also: Lagrange-Funktion aufstellen, nach den Variablen ableiten und die Ableitungen =0 setzen. Dann erhält man ein inhomogenes lineares Gleichungssystem, solange die Produkte in den Randbedingungen in höchstens 2. Potenz auftreten. Edit: So geht's wohl nicht, wegen der Bedingung |
||||||
06.03.2013, 17:40 | HAL 9000 | Auf diesen Beitrag antworten » | ||||
Das hängt wohl auch entscheidend davon ab, wie groß ist. Mit Computerunterstützung würde ich bis ca. schlicht sagen: Brute force! Also alle Kombinationen ausrechnen. U.U. könnte man auch einige der NB analysieren und somit von vornherein die Menge der zu untersuchenden Tupel aus drastisch einschränken: So heißt z.B. dass genau eine der vier Variablen gleich 1 ist und die anderen drei 0. Das sind dann statt nur noch Varianten bzg. dieser vier Komponenten zu untersuchen. |
||||||
06.03.2013, 17:59 | RavenOnJ | Auf diesen Beitrag antworten » | ||||
Das kann man auf alle Fälle reduzieren für die , die in keiner Nebenbedingung auftauchen. Für die kann man den Wert wählen, der minimiert. |
||||||
14.03.2013, 12:45 | CPBach | Auf diesen Beitrag antworten » | ||||
Umformulierung des Problems Habe das Problem mal als Graphenproblem formuliert. Das könnte dann bspw. so aussehen (siehe Anhang). Dazu nehmen wir an, dass die Kantenlängen hier die Gewichte sind und die Bedingungen sagen hier, dass wir aus jedem Kasten GENAU einen Punkt wählen müssen. Als Randbedingung könnte man annehmen, dass der Weg genau k Kanten enthalten muss und die Einschränkungen der Kantenverbindungen durch eine Bedingungen der Form gegeben sind. Wie man das jetzt allerdings löst, weiß ich auch nicht so recht. Vielleicht haben die anderen ja eine Idee. Schönen Tag noch! |
|