globale Optimierung einer min-Funktion

03.07.2013, 16:23	marocaine	Auf diesen Beitrag antworten »
globale Optimierung einer min-Funktion Hallo Matheboard-Gemeinde, welcher globale und gradienten-basierte Optimierungsalgorithmus ist für folgendes Problem angemessen: $\begin{eqnarray} \min\limits_{x \in \Re^n} -min[a_i \; ln(\frac{x_i}{w_i})] \end{eqnarray}$ s.t. $\begin{eqnarray} \sum_{i=1}^n x_i \leq K \end{eqnarray}$ $\begin{eqnarray} -x_i \leq 0 \end{eqnarray}$ mit $\begin{eqnarray} w_i, K \in \Re_{++} \end{eqnarray}$ In einer Einführung zum Optimierungspaket nloptr für die Software R (Link) bin ich schließlich auf den Tip gestoßen, das Ganze wie folgt umzuschreiben: $\begin{eqnarray} \min\limits_{x \in \Re^n, t \in \Re} -t \end{eqnarray}$ s.t. $\begin{eqnarray} t - a_i \; ln(\frac{x_i}{w_i}) \leq 0 \end{eqnarray}$ $\begin{eqnarray} \sum_{i=1}^n x_i \leq K \end{eqnarray}$ $\begin{eqnarray} -x_i \leq 0 \end{eqnarray}$ Nun ist die (triviale) Zielfunktion stetig differenzierbar und ich kann für sie einen Gradienten angeben. Ebenso kann ich für die Nebenbedingungen eine exakte Jakobi-Matrix angeben, und wäre somit theoretisch in der Lage, einen gradienten-basierten globalen Optimierungsalgorithmus zu verwenden. Gradienten-basiert ist wichtig, weil ich über tausende von $\begin{eqnarray} x_i \end{eqnarray}$ optimiere. Hat mir jemand Algorithmen-Namen, optimalerweise mit Implementierung in R? Danke und beste Grüße, maro
05.08.2013, 02:55	Frehmen	Auf diesen Beitrag antworten »
hallo marocaine, du kannst dir überlegen, dass für das Optimum die n+1 Gleichungen $\begin{eqnarray} $t=a_i\ln(x_i/w_i)\ \forall i$ \end{eqnarray}$ und $\begin{eqnarray} $\sum x_i=K$ \end{eqnarray}$ gelten. Das Gleichungssystem lässt sich mit dem eindimensionalen Newtonverfahren lösen, da du $\begin{eqnarray} $x_2,...,x_n$ \end{eqnarray}$ aus $\begin{eqnarray} $x_1$ \end{eqnarray}$ berechnen kannst, somit erhältst du die Problemstellung $\begin{eqnarray} $f(x_1):=x_1+x_2(x_1)+...+x_n(x_1)-K=0$ \end{eqnarray}$ . Da die Nullstelle einfach ist, konvergiet das Verfahren quadratisch.
28.08.2013, 20:46	marocaine	Auf diesen Beitrag antworten »
Hi Frehmen, danke für deine Antwort! Ich habe das ganze bei mir auf der Software R umgesetzt und in ein paar Sekunden eine Antwort erhalten. Allerdings macht sie grafisch betrachtet nicht viel Sinn, weshalb ich mal meine konkrete Ausführung darlege: Durch die Bedingung $\begin{eqnarray} a_i ln(\frac{x_i}{w_i}) = t \end{eqnarray}$ erhalte ich $\begin{eqnarray} a_i ln(\frac{x_i}{w_i}) = a_1 ln(\frac{x_1}{w_1}) \end{eqnarray}$ . Ich löse nach $\begin{eqnarray} x_i \end{eqnarray}$ auf und erhalte $\begin{eqnarray} x_i = e^{\frac{a_1}{a_i}ln(\frac{x_1}{w_1})+ln(w_i)}. \end{eqnarray}$ . Daraus folgt dann $\begin{eqnarray} f(x_1) = x_1 + \sum \nolimits_{i=2}^n e^{\frac{a_1}{a_i}ln(\frac{x_1}{w_1})+ln(w_i)} = 0 . \end{eqnarray}$ Ich habe das nun mit folgenden Werten für $\begin{eqnarray} a_i \end{eqnarray}$ bzw. $\begin{eqnarray} w_i \end{eqnarray}$ per Newton-Verfahren gelöst: $\begin{eqnarray} a_i \end{eqnarray}$ : 0.003847201 0.005128778 0.005964946 0.006183100 0.006773856 0.007548244 0.008244311 0.008709588 0.008903145 0.009909643 0.010064489 $\begin{eqnarray} w_i \end{eqnarray}$ : 2.5 2.0 2.0 2.0 2.0 2.5 2.8 2.3 2.0 2.0 2.0 2.8 2.5 5.3 2.8 3.0 2.0 3.3 2.8 Für $\begin{eqnarray} K= 100000 \end{eqnarray}$ erhalte ich die Lösungen 945695.9400 30553.4197 7916.6536 5910.3454 2944.0093 1741.1965 1122.1198 669.2062 514.3960 292.7472 271.1292 353.0151 308.9265 570.0618 293.3868 235.6960 153.4734 249.8520 204.4255. Wie man sieht, ist $\begin{eqnarray} x_1 \end{eqnarray}$ relativ zu den anderen Variablen enorm groß. Mir scheint das zu groß zu sein, weshalb ich einen Fehler meinerseits vermute. Habe ich im Post irgendwo einen Denkfehler gemacht? Falls nicht: Hat jemand die Möglichkeit, das Optimierungsproblem auf seinem Computer zu lösen und seine Ergebnisse zu posten? Dann kann ich sehen, ob der Fehler vielleicht in meinem R-Code liegt. Danke und beste Grüße, maro
29.08.2013, 03:29	marocaine	Auf diesen Beitrag antworten »
Korrektur (K vergessen): $\begin{eqnarray} f(x_1) = x_1 + \sum \nolimits_{i=2}^n e^{\frac{a_1}{a_i}ln(\frac{x_1}{w_1})+ln(w_i)} - K = 0 . \end{eqnarray}$

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »