Lagrange und Bedingungen 2. Ordnung

16/09/2010 - 17:50 von Christoph Braun | Report spam
Hallo!

Ich habe ein nichtlineares Optimierungsproblem, das ich mittels des
Lagrange-Ansatzes lösen möchte. Konkret habe ich eine Zielfunktion f(x),
wobei x ein Vektor von fünf Elementen ist. Weiter habe ich eine
Nebenbedingung g, die ebenfalls nur von x abhàngt.

Wie überprüfe ich nun, ob ich eine innere Lösung habe?

Zum einen sollte ich für ein Maximierungsproblem eine konkave
Lagrange-Funktion haben.

Reicht es dann aus, sich die dazugehörige Hesse-Matrix anzuschauen und
zu überprüfen, ob sie negativ-definit ist? In meinem Fall wàre dies eine
5x5-Matrix.

Zu beachten ist für die Nebenbedingung g, dass dg = g'dx=0 ist. Diese
Gleichung ist doch erfüllt, wenn es eine Lösung für das System der
Bedingungen erster Ordnung gibt. Die Existenz würde ich doch zunàchst
unterstellen.

Wie verhàlt es sich mit der erweiterten Hessematrix (in meinem Fall
6x6), die auch noch die ersten Ableitungen der Nebenbedingungen enthàlt?
Ist dies einfach eine àquivalente Bedingung für den ersten Test, wo ich
nur die einfache Hesse-Matrix betrachte? Warum wird gesagt, dass man
damit nur ein lokales Optimum sicherstellt?

Für den zweiten Test muss man sich ja ohnehin die einfache Hesse-Matrix
anschauen. Erst die weiteren Hauptminoren haben überhaupt Eintràge, die
sich auf die Nebenbedingungen beziehen.

In diesem Zusammenhang habe ich eine letzte Frage zur Darstellung der
erweiterten Hesse-Matrix:
In manchen Darstellungen steh die Null oben links. Aber man kann sie
doch auch nach unten rechts schreiben. Dies würde ich mittels
Vertauschungen von Zeilen und Spalten erreichen, was in meinem Fall 5+5
Vertauschen sind. Also sollte sich das Vorzeichen der Determinante doch
nicht àndern.

Irgendwie habe ich wohl zu lange auf den ökonomischen Gehalt der
Gleichungen geachtet, ohne auf die Mathematik dahinter zu achten. Nun
muss es eben sein. Hoffentlich kann mir hier einer kurz einen Denkanstoß
geben.

Grüße,
Christoph
 

Lesen sie die antworten

#1 Alois Steindl
16/09/2010 - 18:32 | Warnen spam
Hallo,
recht viele Fragen auf einmal!

Christoph Braun writes:

Hallo!

Ich habe ein nichtlineares Optimierungsproblem, das ich mittels des
Lagrange-Ansatzes lösen möchte. Konkret habe ich eine Zielfunktion
f(x), wobei x ein Vektor von fünf Elementen ist. Weiter habe ich eine
Nebenbedingung g, die ebenfalls nur von x abhàngt.

Wie überprüfe ich nun, ob ich eine innere Lösung habe?



Ist Deine NB eine Ungleichheitsnebenbedingung der Form g(x)>=0? Dann mußt
Du einfach nur
die Lösung einsetzen und schauen, ob g(x) = 0 oder g(x) > 0.
(Eventuell verstehe ich die Frage aber auch ganz falsch.)

Zum einen sollte ich für ein Maximierungsproblem eine konkave
Lagrange-Funktion haben.

Reicht es dann aus, sich die dazugehörige Hesse-Matrix anzuschauen und
zu überprüfen, ob sie negativ-definit ist? In meinem Fall wàre dies
eine 5x5-Matrix.



Das spielts sicher nicht. Schau dir mal in 2 Dimensionen das Beispiel
f = -(x^2 + y^2), g = (x^2 + 4 y^2 - 4) = 0
an: Obwohl f an allen Extrempunkten negativ definit ist, gibt es lokale
Maxima und Minima.

Zu beachten ist für die Nebenbedingung g, dass dg = g'dx=0 ist. Diese
Gleichung ist doch erfüllt, wenn es eine Lösung für das System der
Bedingungen erster Ordnung gibt. Die Existenz würde ich doch zunàchst
unterstellen.



Eine Lösung eines nichtlinearen Gleichungssystems muss natürlich nicht
in jedem Fall existieren; aber wenn sie nicht existiert, hast Du auch
andere Probleme zu lösen.

Wie verhàlt es sich mit der erweiterten Hessematrix (in meinem Fall
6x6), die auch noch die ersten Ableitungen der Nebenbedingungen
enthàlt? Ist dies einfach eine àquivalente Bedingung für den ersten
Test, wo ich nur die einfache Hesse-Matrix betrachte? Warum wird
gesagt, dass man damit nur ein lokales Optimum sicherstellt?



Ich glaube, um diese Fragen zu beantworten, wirst Du um die Lektüre
einschlàgiger Arbeiten wohl nicht herumkommen.

Wenn H die Hessematrix von f und b der Gradient von g an der Lösung ist,
lautet die erweiterte Matrix
H b'
A =
b 0
Sie führt auf das verallgemeinerte Eigenwertproblem

(A - S lambda) v = 0
mit S = diag(1, 1, 1, 1, 0)

Da S singulàr ist, liefern Eigenwertlöser gern einen unendlichen
Eigenwert zurück, den man aber vergessen kann. Alle anderen Eigenwerte
müssen negativ sein.
Du kannst natürlich auch das entsprechende charakteristische Polynom
4. Grades mit dem Routh-Hurwitz-Kriterium untersuchen.

Für den zweiten Test muss man sich ja ohnehin die einfache
Hesse-Matrix anschauen. Erst die weiteren Hauptminoren haben überhaupt
Eintràge, die sich auf die Nebenbedingungen beziehen.

In diesem Zusammenhang habe ich eine letzte Frage zur Darstellung der
erweiterten Hesse-Matrix:
In manchen Darstellungen steh die Null oben links. Aber man kann sie
doch auch nach unten rechts schreiben. Dies würde ich mittels
Vertauschungen von Zeilen und Spalten erreichen, was in meinem Fall
5+5 Vertauschen sind. Also sollte sich das Vorzeichen der Determinante
doch nicht àndern.



Sollte kein Problem sein.
Irgendwie habe ich wohl zu lange auf den ökonomischen Gehalt der
Gleichungen geachtet, ohne auf die Mathematik dahinter zu achten. Nun
muss es eben sein. Hoffentlich kann mir hier einer kurz einen
Denkanstoß geben.

Grüße,
Christoph



Beste Grüße und viel Erfolg!
Alois


Alois Steindl, Tel.: +43 (1) 58801 / 32558
Inst. for Mechanics and Mechatronics Fax.: +43 (1) 58801 / 32598
Vienna University of Technology, A-1040 Wiedner Hauptstr. 8-10

Ähnliche fragen