Über ein nichtlineares Optimierungsproblem

09.02.2019, 20:49	Zeno-2	Auf diesen Beitrag antworten »
Über ein nichtlineares Optimierungsproblem Liebe Leute, bereits seit einer ganzen Weile denke ich über ein interessantes Problem aus der nichtlinearen Optimierung nach. Ich habe leider keine formale Ausbildung in (nichtlinearer) Optimierung. Ich nutze daher dieses besondere Problem auch, um auf diesem Gebiet Kenntnisse zu sammeln und grundsätzlich, um mathematisch etwas "auf Trab" zu bleiben. Die Fragestellung entstammt, in speziellerer Form, einer realen Anwendung. Wenn meine Gedankengänge einigermaßen richtig sind, dann würde ich es gerne auch praktisch anwenden. Ich möchte zunächst, so weit es geht, analytische (Näherungs-)Lösungen erhalten. Soweit zu den ganzen "Nebenbedingungen", jetzt zum Problem: Ich habe eine Anzahl von konstanten $\begin{eqnarray} E_i \end{eqnarray}$ die ich jeweils um Variablen $\begin{eqnarray} q_i \end{eqnarray}$ erhöhen/erniedrigen kann: $\begin{eqnarray} E_i + q_i \end{eqnarray}$ mit $\begin{eqnarray} i=1,...,N \end{eqnarray}$ . Ich möchte die $\begin{eqnarray} E_i + q_i \end{eqnarray}$ maximieren. In meinem Fall kann ich dies so zusammenfassen: $\begin{eqnarray} \text{maximiere } f(q) = \sum\limits_{i=1}^{N} (E_i + q_i) \end{eqnarray}$ Das dazugehörige Minimierungsproblem lautet bekanntlich: $\begin{eqnarray} \text{minimiere } f(q) = -\left( \sum\limits_{i=1}^{N} \left(E_i + q_i \right) \right) \end{eqnarray}$ Mit den $\begin{eqnarray} E_i \end{eqnarray}$ über einen funktionalen Zusammenhang assoziiert sind Zahlenwerte $\begin{eqnarray} T_{i,j} \end{eqnarray}$ . Der genau Zusammenhang ist hier nicht wichtig. Es gelten jedoch folgende $\begin{eqnarray} j = 1,...,M \end{eqnarray}$ Nebenbedingungen für das Optimierungsproblem: $\begin{eqnarray} g_j(q) = \left(\sum\limits_{i=1}^{N} e^{\left(T_{i,j} + b\, q_{i}\right)} \right) - I_j \leq 0 \end{eqnarray}$ Bis auf die $\begin{eqnarray} q_i \end{eqnarray}$ sind nur reele und bekannte Konstanten verarbeitet und $\begin{eqnarray} b > 0 \end{eqnarray}$ . Die gesamte Aufgabenstellung lautet also: $\begin{eqnarray} (1) \qquad \text{min} \qquad f(q) = -\left( \sum\limits_{i=1}^{N} \left(E_i + q_i \right) \right) \qquad \text{s. t.} \qquad g_j(q) = \left(\sum\limits_{i=1}^{N} e^{\left(T_{i,j} + b\, q_{i}\right)} \right) - I_j \leq 0 \qquad \text{mit} \qquad j=1,...,M \end{eqnarray}$ Man kann nun zunächst festhalten: $\begin{eqnarray} f(q) \end{eqnarray}$ ist konvex, denn lineare Funktionen sind immer konvex (und konkav, jedoch nicht strikt konvex/konkav). Die e-Funktion ist konvex und die Summe konvexer Funktionen ist ebenfalls konvex. Somit ist das Optimierungsproblem konvex. Ein lokales Minimum bei $\begin{eqnarray} q^{} \end{eqnarray}$ ist somit auch globales Minumum. Allerdings haben wir hier Ungleichungsnebenbedingungen. Wenn es nur eine Nebenbedingung (d. h. $\begin{eqnarray} j=M=1 \end{eqnarray}$ ) gibt, ist das Problem via Lagrange-Multiplikator analytisch lösbar: $\begin{eqnarray} L(q,\lambda)= -\left( \sum\limits_{i=1}^{N} (E_i + q_i ) \right) + \lambda \, \left[\left(\sum\limits_{i=1}^{N} e^{(T_{i,1} + b\, q_{i})}\right) - I_1 \right] \end{eqnarray}$ Die Lagrange-Gleichungen lauten dann: $\begin{eqnarray} \frac{\partial L}{\partial q_{1}} &= -1 + \lambda \left( b\, e^{(T_{1,1} + b\, q_{1}) } \right) &&= 0 \\ &\vdots \\ \frac{\partial L}{\partial q_{N}} &= -1 + \lambda \left( b\, e^{(T_{N,1} + b\, q_{N}) } \right) &&= 0.\\ \end{eqnarray}$ und $\begin{eqnarray} \frac{\partial L}{\partial \lambda} &= \left(\sum\limits_{i=1}^{N} e^{\left(T_{i,j} + b\, q_{i}\right)} \right) - I_j &&= 0. \qquad \text{(Gleichung N+1)} \end{eqnarray}$ Diese Gleichungen sind lösbar, indem man die ersten $\begin{eqnarray} N \end{eqnarray}$ Gleichungen nach $\begin{eqnarray} e^{(T_{i,1} + b\, q_{i})} \end{eqnarray}$ umstellt: $\begin{eqnarray} e^{(T_{i,1} + b\, q_{1}) } &&= \frac{1}{\lambda\, b} \qquad (i=1,...,N) \end{eqnarray}$ und in die $\begin{eqnarray} N+1 \end{eqnarray}$ -ste Gleichung einsetzt: $\begin{eqnarray} \left[\left(\sum\limits_{i=1}^{N} \frac{1}{\lambda\, b}\right) - I_1 = \frac{N}{\lambda\, b} - I_1 = 0 \right] \end{eqnarray}$ Also ist $\begin{eqnarray} \lambda = \frac{N}{I_1\, b} \end{eqnarray}$ . Dies kann man wieder in die obigen Lagrange-Gleichungen 1 bis N einsetzen um die $\begin{eqnarray} q_i \end{eqnarray}$ zu bestimmen: $\begin{eqnarray} \frac{\partial L}{\partial q_{1}} &= -1 + \frac{N}{I_1\, b} \left( b\, e^{(T_{i,1} + b\, q_{i}) } \right) &&= 0 \qquad (i=1,...,N) \end{eqnarray}$ $\begin{eqnarray} \Rightarrow \end{eqnarray}$ $\begin{eqnarray} q_{i} = \frac{1}{b} \, \left[ -T_{i,1} + ln(I_1) - ln(N) \right] \end{eqnarray}$ . Damit ist das Optimierungsproblem für eine Nebenbedingung (d. h. $\begin{eqnarray} j=M=1 \end{eqnarray}$ ) gelöst. Leider kann man, soweit ich sehen kann, das allgemeine Problem analytisch nicht lösen. Ich würde gerne in einem 2. Teil, wenn ich dazu komme, ein paar weitere Überlegungen darlegen. Ein Frage habe ich aber: Verstehe ich es richtig, dass die Methode der Lagrangen Multiplikatoren nur für Nebenbedingungen mit Gleichungen* funktioniert? Also, wenn Ungleichungen als Nebenbedingungen vorkommen, dann funktioniert die analytische Lösung allgemein nicht? Ich finde das immer schwer zu verstehen, da relativ schnell Karush-Kuhn-Tucker-Bedingungen die Rede ist, und ich da noch nicht wirklich den Sinn drin sehe. Ansonsten vielen Dank erstmal fürs Zuhören. Wenn hier jemand tolle Tipps oder mir sagt, alles trivial und mit links lösbar und seit 100 Jahren bekannt... immer her damit.
10.02.2019, 20:15	Zeno-2	Auf diesen Beitrag antworten »
Ok, hier ein zweiter Teil, mit ein paar Überlegungen und Fragen. Oben wurde gesagt, dass für den Fall mit einer Ungleichungsnebenbedingung $\begin{eqnarray} j=M=1 \end{eqnarray}$ das Optimierungsproblem min $\begin{eqnarray} \text{min}\quad f(q) \end{eqnarray}$ analytisch gelöst werden kann. Dier Lösungsvekor $\begin{eqnarray} q^{} \end{eqnarray}$ für $\begin{eqnarray} \text{min} \qquad f(q) = -\left( \sum\limits_{i=1}^{N} \left(E_i + q_i \right) \right) \qquad \text{s. t.} \qquad g_1(q) = \left(\sum\limits_{i=1}^{N} e^{\left(T_{i,1} + b\, q_{i}\right)} \right) - I_1 \leq 0 \ \end{eqnarray}$ lautet $\begin{eqnarray} q^{} = \left[ -T_{i,1} + ln(I_1) - ln(N) \right] \end{eqnarray}$ . Wenn eine weitere Ungleichungsrestriktion hinzugenommen wird: $\begin{eqnarray} g_2(q) = \left(\sum\limits_{i=1}^{N} e^{\left(T_{i,2} + b\, q_{i}\right)} \right) - I_2 \leq 0 \ \end{eqnarray}$ gibt es 2 Möglichkeiten: Für die bisherige Lösung $\begin{eqnarray} q^{} \end{eqnarray}$ kann diese inaktiv* sein, d. h. $\begin{eqnarray} \text{(I)} \qquad g_2(q^{}) = \left(\sum\limits_{i=1}^{N} e^{\left(T_{i,2} + b\, q^{}_{i}\right)} \right) - I_2 \leq 0 \ \end{eqnarray}$ Dann passiert nichts und $\begin{eqnarray} q^{} \end{eqnarray}$ ist immer noch die gesuchte Lösung. Oder die zusätzliche Ungleichungsrestriktion wird mit der Lösung $\begin{eqnarray} q^{} \end{eqnarray}$ nicht eingehalten: $\begin{eqnarray} \text{(II)} \qquad g_2(q^{}) = \left(\sum\limits_{i=1}^{N} e^{\left(T_{i,2} + b\, q^{}_{i}\right)} \right) - I_2 > 0 \ \end{eqnarray}$ In diesem Fall kann man "die Seite wechseln" und prüfen, ob, wenn man zuerst die Minimierungsaufgabe mit der (einzelnen) Nebenbedingung $\begin{eqnarray} g_2 \end{eqnarray}$ löst, und dann die Lösung $\begin{eqnarray} q^{} \end{eqnarray}$ erhält, die erste Ungleichung $\begin{eqnarray} \left[ g_1(q^{}) \leq I_1 \right] \end{eqnarray}$ inaktiv ist. Dann ist $\begin{eqnarray} q^{} \end{eqnarray}$ die neue Lösung. Der worst-case ist, dass die Lösung $\begin{eqnarray} q^{} \end{eqnarray}$ für das Optimierungsproblem mit einer Ungleichungsrestriktion $\begin{eqnarray} g_1 \end{eqnarray}$ zu $\begin{eqnarray} \left[ g_2(q^{}) - I_2 > 0 \right] \end{eqnarray}$ führt und die Lösung $\begin{eqnarray} q^{} \end{eqnarray}$ für das Optimierungsproblem mit einer Ungleichungsrestriktion $\begin{eqnarray} g_2 \end{eqnarray}$ zu $\begin{eqnarray} \left[ g_1(q^{}) - I_1 > 0 \right] \end{eqnarray}$ führt. Man kann dann folgende Heuristik anwenden: Wenn $\begin{eqnarray} \left[ g_1(q^{}) - I_1 = 0 \right] \end{eqnarray}$ aber $\begin{eqnarray} \left[ g_2(q^{}) - I_2 > 0 \right] \end{eqnarray}$ ist, dann werden "händisch" so lange die Werte für $\begin{eqnarray} (q^{}_i \end{eqnarray}$ reduziert, bis irgendwann $\begin{eqnarray} \left[ g_2(q^{red}) - I_2 = 0 \right] \end{eqnarray}$ ist (und zwangsläufig $\begin{eqnarray} \left[ g_1(q^{red}) - I_1 < 0 \right] \end{eqnarray}$ ). Die Werte $\begin{eqnarray} q_i^{red} = q_i^{} - \Delta q_i \end{eqnarray}$ lösen zwar das Optimierungsproblem im allgemeinen nicht optimal. Aber was besseres fällt mir nicht ein. In Teil 3 geht es um die "optimale" Bestimmung der Werte $\begin{eqnarray} \Delta q_i \end{eqnarray}$ . Vielen Dank wieder für's Zuhören. Möglicherweise ist das alles ein bisschen Quatsch, jedoch, mir hilft es meine Gedanken zu sortieren.
10.02.2019, 20:47	hgseib	Auf diesen Beitrag antworten »
hallo nur eine idee, falls programmieren für dich auch ein gangbarer weg wäre: dann such mal im internet nach: Dr.-Ing. Jürgen Adamy Fuzzy-Logik, Neuronale Netze und Evolutionäre Algorithmen ich habe da ein buch von dem über: steuerungs- und regelungstechnik. das ist sehr verständlich geschrieben und auf jeden fall interessant, auch wenn du nicht programmieren willst/ kannst. mfg.
10.02.2019, 21:44	Zeno-2	Auf diesen Beitrag antworten »
Ok, Fortsetzung. Man hat das o.g. Optimierungsproblem mit einer Ungleichungsrestriktion $\begin{eqnarray} g_1 \end{eqnarray}$ gelöst und die optimalen Werte $\begin{eqnarray} q^{} \end{eqnarray}$ ermittelt. Allerdings gibt es jetzt folgendes Problem: $\begin{eqnarray} g_1(q^{}) - I_1 = 0 \qquad \text{ok!} \end{eqnarray}$ aber $\begin{eqnarray} g_2(q^{}) - I_2 > 0 \end{eqnarray}$ Es sollen jetzt folgende Werte gefunden werden: $\begin{eqnarray} g_2(q^{red}) - I_2 = 0 \qquad \text{mit} \qquad q^{red} = q^{} - \Delta q \end{eqnarray}$ Mein Gedanke dabei ist jetzt wie folgt: Es gilt: $\begin{eqnarray} g_2(q^{}) = \left(\sum\limits_{i=1}^{N} e^{\left(T_{i,2} + b\, q^{}_{i}\right)} \right) = I^{} > I_2 \end{eqnarray}$ Ich will mich nun bei meiner Funktion $\begin{eqnarray} g_2 \end{eqnarray}$ auf "auf dem schnellsten" Weg, oder besser, auf dem "steilsten Weg" bergab zum Wert $\begin{eqnarray} g_2(q^{}-\Delta q) = I_2 \end{eqnarray}$ . Der steilste Weg wird durch den Gradienten der skalaren Funktion $\begin{eqnarray} g_2(q) \end{eqnarray}$ vorgegeben: $\begin{eqnarray} \nabla \, g_2(q) =\begin{pmatrix}\frac{\partial g_2}{\partial q_{1}}\\ \vdots\\ \frac{\partial g_2}{\partial q_{N}} \end{pmatrix} (q) =\begin{pmatrix} b\, e^{(T_{i,2} + b \, q_{1})} \\ \vdots\\ b \, e^{(T_{i,2} + b\, q_{N})} \end{pmatrix} \end{eqnarray}$ Ich benötige jetzt den "steilsten" Pfad vom Punkt $\begin{eqnarray} \left(q^{}, g_2(q^{}) = I^{} \right) \end{eqnarray}$ zum Punkt $\begin{eqnarray} \left( q^{}-\Delta q, g_2(q^{}-\Delta q) = I_2 \right) \end{eqnarray}$ . Dazu muss ich die Integralkurve bestimmen, also: $\begin{eqnarray} \frac{d\hat{q}_1}{dt} &= \frac{\partial g_2(\hat{q}_1)}{\partial q_{1}} = b\, e^{(T_{i,2} + b \, \hat{q}_{1})} \\ &\vdots \\\frac{d\hat{q}_N}{dt} &= \frac{\partial g_2(\hat{q}_N)}{\partial q_{N}} = b \, e^{(T_{i,2} + b\, \hat{q}_{N})}. \end{eqnarray}$ Dieses Differentialgleichungssystem ist lösbar. Mit der Symbolic Math Toolbox von Matlab konnte ich folgende Lösung generieren: $\begin{eqnarray} \hat{q}_i(t) = - \frac{1}{b} \left( T_{i,2} + ln \left( e^{(-T_{i,2} -b\, q^{}_i)}-b^{2}\,t \right) \right) \end{eqnarray}$ Was bedeutet das nun? Für $\begin{eqnarray} t=0 \end{eqnarray}$ ergibt sich $\begin{eqnarray} \hat{q}_i(0) = q_i^{} \end{eqnarray}$ . Das soll so sein. Wenn ich den Parameter $\begin{eqnarray} t>0 \end{eqnarray}$ werden lasse, steigt man auf dem steilsten Weg bergab. Irgendwann hat man man für ein $\begin{eqnarray} t_1 > 0 \end{eqnarray}$ den Wert $\begin{eqnarray} \hat{q}(t_1) < q^{} \end{eqnarray}$ und $\begin{eqnarray} g_2(\hat{q}(t_1)) = I_2 \end{eqnarray}$ erreicht. Ich brauche aber eigentlich nicht $\begin{eqnarray} \hat{q} \end{eqnarray}$ von $\begin{eqnarray} t_1 \end{eqnarray}$ sondern $\begin{eqnarray} \hat{q}(I_2)) \end{eqnarray}$ . Leider kann ich aus $\begin{eqnarray} g_2(\hat{q}(t_1)) = I_2 \end{eqnarray}$ die Funktion nicht als $\begin{eqnarray} t_1(I_2) \end{eqnarray}$ ableiten. Ich bekomme die analytisch offenbar nicht auflösbare Gleichung: $\begin{eqnarray} \sum\limits_{i=1}^{N} \frac{1}{e^{(T_{i,2} - b\, q_{i})} - b^{2}\, t_1 } = I_2 \end{eqnarray}$ Und hier endet die Reise zunächst. Vielen Dank erstmal für's zuhören.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »