Ganzzahlige Optimierung mit quadratischen Randbedingungen

Neue Frage »

Jone Auf diesen Beitrag antworten »
Ganzzahlige Optimierung mit quadratischen Randbedingungen
Meine Frage:
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.
RavenOnJ Auf diesen Beitrag antworten »
RE: Ganzzahlige Optimierung mit quadratischen Randbedingungen
Zitat:
Original von Jone

Sehr geehrtes Forum,


überheb dich nicht. Man duzt sich hier.

Zitat:

Minimiere die Funktion
, sodass reelle Zahlen sind und zu gegebenen Randbedingungen: (exemplarisch)






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
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von Jone
Weiß irgendjemand wie man so etwas angeht?

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. Augenzwinkern

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.
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.
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!
Neue Frage »
Antworten »



Verwandte Themen

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