Ganzzahlige Optimierung oder so ^^
-
Hallo ich habe eine Funktion
f(a,b) gegeben.Nun brauche ich 2 ganzzahlige Parameter a und b so dass
f(a,b) - K = min
gilt.
Also wenn ich a und b einsetze kommt f(a,b) so nahe es für ganzzahlige Werte geht an K heran.Gibt es da ein Standardvorgehen, das unabhängig von f ist?
-
Also wenns vollkommen unabhängig von f (also f nicht stetig, differenzierbar, etc.) dann fallen mir nur Methoden aus der KI wie Hill-Climbing, evolutionäre Algorithmen etc. ein.
-
Hast du nicht wenigstens ein bißchen mehr struktur? Gefühlt lässt sich so ziemlich jedes kombinatorische Optimierungsproblem auf diese Form bringen...
-
Also die Funktion ist recht einfach und ich kann sie auf IR auch exakt lösen.
Ist etwa die Form:
f(a,b)= k * Q(a) * Q(b)
wobei Q quadratische Terme sind.
-
1.) Es gibt nur problembezogene Optimierungsstrategien
2.) Wo ist das Problem bei den quadratischen Termen?
-
Sorry Knivil, deinen Beitrag verstehe ich nicht.
Ums mal so einfach wie möglichzu machen:
a^2 + b^2 +a = 2400
Diese Gleichung würde ich gerne lösen. Ich hoffe mal dass es keine ganzzahlige Lösung so geht. Also suche ich möglichst gute Näherungen.
Sopontan fällt mir dazu aber nichts ein.
-
Das hört sich nach einer "Integer Programming" Problemstellung an.
...um mal das Stichwort zu sagen. Lass Dich mal nicht von dem kurzen Wikipedia Artikel abschrecken und vor allem nicht von der Erwähnung von "NP hart". Diese Klassifizierung betrifft natürlich erstmal nur die allgemeinste Definition des Integer Programming Problems. Ich glaube, für viele Arten von Integer Programming Problemen gibt es effizientere Herangehensweisen. Außerdem bist Du wahrscheinlich eh nur an kleinen Problemgrößen interessiert.
EDIT: Der deutsche Wikipedia-Artikel ist etwas ausführlicher: http://de.wikipedia.org/wiki/Ganzzahlige_lineare_Optimierung
-
Gregor schrieb:
"NP hart".
NP-schwer, es heißt NP-schwer. "hart" ist einfach nur eine schlechte Übersetzung von "hard".
@Topic:
Dummerweise ist sein Problem auch nicht linear.
Andererseits hat er keine Nebenbedingungen. Sofern die Funktion konvex ist, sollte sich da doch auch eine gute Lösung in der Nähe der reellen Lösung finden...
-
Jester schrieb:
Gregor schrieb:
"NP hart".
NP-schwer, es heißt NP-schwer. "hart" ist einfach nur eine schlechte Übersetzung von "hard".
Hmmm... da habe ich mich wohl der Fehlübersetzung schuldig gemacht. Wird nicht wieder vorkommen.
Jester schrieb:
@Topic:
Dummerweise ist sein Problem auch nicht linear.
Andererseits hat er keine Nebenbedingungen. Sofern die Funktion konvex ist, sollte sich da doch auch eine gute Lösung in der Nähe der reellen Lösung finden...Ja, habe ich im Nachhinein auch realisiert. Das macht das ganze natürlich wesentlich problematischer.
-
a^2 + b^2 +a = 2400
Das Problem sieht so freundlich (bzw. konvex) aus, dass du einfach die reelle Lösung hernehmen kannst und viermal alle möglichen Rundungen ausprobierst, um zum Minimum zu kommen.
f(a,b)= k * Q(a) * Q(b)
Das sieht aber anders aus als dein zweites Problem - hier werden die quadratischen Terme multipliziert, nicht addiert.
Prüfe doch mal, ob deine Zielfuktion immer konvex ist!
-
was ist denn die reelle Lösung? die Lösungsmenge ist eine Kurve im R^2 ...
wenndu die 2400 gegen eine 2401 tauschst, finde ich zwei ganzzahlige Lösungen im Kopf:
a=0, b=49
a=-1, b=49
-
Sorry, habe im Beispiel addiert statt zu multiplizieren.
Eine geeignete Aufgabe wäre :
a^2 * b^2 * a = 2400
Ich schau mir das mit dem "konvex-Sein" nochmal genauer an.
Danke soweit
-
buchstaben schrieb:
was ist denn die reelle Lösung? die Lösungsmenge ist eine Kurve im R^2 ...
Ache auf mein Haupt - du hast natürlich recht
-
shisha schrieb:
a^2 * b^2 * a = 2400
Das ist aber nicht mehr so recht quadratisch
a^2 * b^2 * a = a^3 * b^2
-
Die erste Problemstellung lautete ja "f(a,b)-K = min". Wenn das konvex ist, dann ist das ne relativ kleine Kurve.
@OP: wenn da ein Problem zugrunde liegt, das Du glaubst auf diese Weise gut formalisiert zu haben, wäre jetzt der richtige Zeitpunkt mit der echten Problemstellung rauszurücken. -- In der Allgemeinheits wirds ansonsten schwierig.
-
shisha schrieb:
Diese Gleichung würde ich gerne lösen.
Loesen oder ueber a,b minimieren? Fuers Minimieren sollte nur nach a bzw. b abzuleiten sein. Da keine Nebenbedingungen erfuellt warden muessen, ist das Problem trivial. Dann suchst du einfach im Bereich der ganzen Zahlen um der reellen Loesung herum, nach dem optimalen Wert.
-
a^3 * b^2 = 2400 hat keine ganzzahlige Lösung, weil der Primfaktor 3 in der 2400 nur 1-fach vorkommt.
-
buchstaben schrieb:
a^3 * b^2 = 2400 hat keine ganzzahlige Lösung, weil der Primfaktor 3 in der 2400 nur 1-fach vorkommt.
Interessanter Ansatz. Kann man die Problemstellung so formulieren, dass man eine moeglichst kleine Zahl groesser gleich 2400 sucht, deren Primfaktorzerlegung bestimmte Eigenschaften hat, was die Anzahl identischer Primfakoren betrifft?
-
Das Thema ist "ganzzahlige Optimierung" und im Anfangsposting steht "f(a,b) - K = min". Das lässt nur den Schluss zu, dass es um ein Minimierungsproblem geht, nicht um Gleichunglösen.
-
| a^3 * b^2 - 2400 | = min löse ich auch noch im Kopf:
b = 49 ergibt a^3 - 2400/2401 = min
also a = 1, b = +/- 49, und | a^3 * b^2 - 2400 | = 2401 - 2400 = 1
besser als mit einer Abweichung von 1 kann man's ganzzahlig nicht hinbekommen, da Abweichung 0 wegfällt, weil es als Gleichung nicht ganzzahlig lösbar ist (wegen Primfaktor 3 in 2400) also gelöst.
nächstes Problem ?