Algorithmus zur mehrdimensionalen Optimierung / root-finding / something

Question

Ich habe fünf Werte, A, B, C, D und E.

die Einschränkung A Gegeben + B + C + D + E = 1 und fünf Funktionen F (A), F (B), F (C), F (D), F (E), ich brauche zu lösen für A bis E, so dass F (A) = F (B) = F (C) = F (D) = F (E).

Was ist der beste Algorithmus / Ansatz für diesen Einsatz? Ist mir egal, wenn ich es selbst schreiben, ich möchte nur wissen, wo sie suchen müssen.

EDIT: Dies sind nichtlineare Funktionen. Darüber hinaus können sie nicht charakterisiert werden. Einige von ihnen schließlich aus einer Tabelle von Daten interpoliert werden können.

Answer 1

Es gibt keine allgemeingültige Antwort auf diese Frage. Ein Solver, die Lösung zu finden, zu jeder Gleichung existiert nicht. Wie Lance Roberts schon sagt, müssen Sie mehr über die Funktionen kennen. Nur ein paar Beispiele

• Wenn die Funktionen zweimal differenzierbar sind, und Sie können die erste Ableitung berechnen, könnte man eine Variante versuchen Lagrange Multiplier Methode für die Einschränkung zu implementieren.
• Ist die Funktion F stetig ist (was es wahrscheinlich ist, wenn es sich um eine Interpolant ist), können Sie auch die Bisektionsmethode versuchen könnte, die viel wie binäre Suche ist.

Bevor Sie das Problem lösen können, müssen Sie wirklich mehr über die Funktion wissen Sie studieren.

Answer 2

Wie andere haben bereits gebucht, haben wir einige weitere Informationen zu den Funktionen benötigen. Angesichts der Tatsache, dass, können wir immer noch versuchen, die folgende Entspannung mit einer Standard-nicht-linearen Programmierung Toolbox zu lösen.

min k
st.
A + B + C + D + E = 1 | F1 (A) - k = 0
F2 (B) - k = 0
F3 (C) -k = 0
F4 (D) - k = 0
F5 (E) k = 0

Jetzt können wir dieses Problem lösen in irgendeiner Art und Weise wir, wie Strafmethode wünschen

min k + mu * Summe (Fi (x_i) - k) ^ 2 st
A + B + C + D + E = 1

oder eine einfache SQP oder Innen-Punkt-Methode.

Mehr Details und ich kann auf eine gute Methode helfen, beraten.

m

Answer 3

Die Funktionen sind alle monoton steigend mit ihrem Argument. Darüber hinaus können sie nicht charakterisiert werden. Der Ansatz, der arbeitete erwies sich als:

Starten

1) mit A = B = C = D = E = 1/5
2) Berechne F1 (A) bis F5 (E), und neu berechnen A bis E, so dass jede Funktion entspricht diese Summe dividiert durch 5 (im Mittel).
3) die neuen Rescale A bis E so, dass sie alle Summe 1 ist, und neu berechnen F1 bis F5.
Wiederholen Sie die 4), bis zufrieden.

Es konvergiert überraschend schnell - nur ein paar Wiederholungen. Natürlich jede Iteration erfordert 5 Wurzel 2 für Schritt findet.

Answer 4

Eine Lösung der Gleichungen

A + B + C + D + E = 1
F(A) = F(B) = F(C) = F(D) = F(E)

ist, A, B, C, D und E alle gleich 1/5 zu nehmen. Nicht sicher, obwohl, ob das ist, was Sie wollen ...

hinzugefügt nach Johns Kommentar (danke!)

die zweite Gleichung Unter der Annahme, sollte F1 (A) = F2 (B) = F3 (C) = F4 (D) = F5 (E) lesen, würde ich die Newton-Raphson-Methode (Martijn Antwort sehen). A - - B - C - D. Bei jedem Schritt der Iteration Sie ein 4x4-System zu lösen, müssen Sie die Einstellung E = 1 eine Variable eliminieren. Das größte Problem ist wahrscheinlich, wo die Iteration zu starten. Eine Möglichkeit ist, an einer beliebigen Stelle zu beginnen, einige Iterationen, und wenn Sie nicht überall bekommen, wählen Sie einen anderen beliebigen Punkt und starten Sie es erneut.

Beachten Sie, dass, wenn Sie wirklich wissen nichts über die Funktion dann bedarf es nicht eine Lösung zu sein.

Answer 5

ALGENCAN (Teil von TANGO) ist wirklich schön. Es gibt Python-Bindungen, auch.

http://www.ime.usp.br/~egbirgin /tango/codes.php -. "allgemeine nicht-lineare Programmierung, die Matrix Manipulationen gar nicht nutzen und so, in der Lage ist, extrem große Probleme mit mäßiger Rechenzeit lösen der allgemeine Algorithmus ist von Augmented Lagrangian Typ ... „

http://pypi.python.org/pypi/ TANGO% 20Project% 20-% 20ALGENCAN / 1.0

Answer 6

Google OPTIF9 oder ALLUNC. Wir verwenden diese für die allgemeine Optimierung.

Answer 7

Sie könnten Standard-Suchtechnik verwenden, wie die anderen erwähnt. Es gibt ein paar Optimierung Sie davon Gebrauch machen könnten, während die Suche zu tun.

Zunächst einmal müssen Sie nur A lösen, B, C, D, weil 1-E = A + B + C + D.

Zweitens haben Sie F (A) = F (B) = F (C) = F (D), dann können Sie für A. suchen Sobald Sie F (A) zu erhalten, Sie B lösen könnte, C, D wenn das möglich ist. Wenn es nicht möglich ist, die Funktionen zu lösen, müssen Sie jede Variable sucht weiter, aber jetzt haben Sie einen begrenzten Bereich zu suchen, weil A + B + C + D <= 1.

Wenn Sie Ihre Suche diskret und endlich ist, sollten die oben genannten Optimierungen auch vernünftig arbeiten.

Answer 8

Ich würde versuchen, erste Particle Swarm Optimization. Es ist sehr einfach zu implementieren und zu optimieren. Sehen Sie sich die Wiki-Seite für sie.