Calculon - Fr 16.05.08 16:42
Titel: Optimierungskriterium mit quadratischer Zielfunktion

---

Hallo zusammen,

ich versuche gerade ein lineares Gleichungssystem mit 2 Unbekannten und einer Gleichung zu optimieren. Für eine lineare Zielfunktion gibt's ja den Simplexalgorithmus, den ich hier [http://pagesperso-orange.fr/jean-pierre.moreau/p_linear.html] gefunden und implementiert habe. Für meinen einfachen Fall reicht eine geometrische Lösung zwar aus, jedoch bei mehr als 2 Unbekannten wird es wiederum schwieriger.

Mein Gleichungssystem lautet:
0.808x_1 + 1x_2 = 0.167

Lineare Zielfunktion:
Summe aller x soll minimiert werden: Z = x_1 + x_2

Dafür liefert mir die graphische Lösung sowie der Simplexalgorithmus:
x_1 = 0
x_2 = 0.167

Quadratische Zielfunktion:
Summe aller x-Quadrate soll minimiert werden: Z = x_1^2 + x_2^2

Dafür liefert mir die graphische Lösung:
x_1 = 0.08
x_2 = 0.1

Der Simplexalgorithmus kann nur für lineare Zielfunktionen benutzt werden. Welchen Algorithmus benutz' ich denn für quadratische Zielfunktionen?

Gruß

Calculon
--

Tilo - Fr 16.05.08 18:28

---

Wenn es nur Potenzen sind(keine Winkel oder Logarhythmen) könnte partielles Differenzieren helfen.
Schrittweise nach jeder Variablen 1 mal differenzieren. Dort nach Nullstellen suchen -> Extremalpunkte.
Die Werte dieser Extremalpunkte vergleichen -> niedriegsten merken.
Nun noch von den Randlösungen die Werte berechen. Sind alle Randwerte größer so hast Du mit den niedrigtes Extremalpunkt das Minimum.


//Lese gerade genauer.
Da es sich um die Quadrate handelt ist das Differenzial linear. Vielleicht hilft hier Simplex.

Delete - Fr 16.05.08 20:02

---

z. b. http://de.wikipedia.org/wiki/Dynamische_Programmierung auf dynamische programmierung. kommt aber sehr auf deinen fall an.

hast recht, die lineare optimierung ist hierfür nicht mehr brauchbar...

BenBE - Fr 16.05.08 23:38

---

hmmm, ich würde's rein klassisch versuchen:

ax+by=c

x=(by-c)/a
y=(ax-c)/b

entweder x oder y im folgenden Schritt nehmen:

Z=x^2+y^2

Für x oder y jetzt die umgestellte Gleichung einsetzen:

Z=x^2+((ax-c)/b)^2
Z=((by-c)/b)^2+y^2

Z nun einmal ableiten (überlass ich dem Threadstarter) und Nullstellen suchen (Hab ich jetzt auch grad keine Lust zu rechnen).

Danach zweite Ableitung von Z bilden und auf Minimum\Maximum prüfen.

Wenn ich mich nicht vertan hab, sollte man damit recht einfach vorwärts kommen. Wenn man nun für x oder y nen Wert hat, zurück substituieren und in die Original-Gleichung einsetzen und ausrechnen.

HTH.

Calculon - Fr 16.05.08 23:54

---

BenBE hat folgendes geschrieben:

hmmm, ich würde's rein klassisch versuchen: ax+by=c x=(by-c)/a y=(ax-c)/b entweder x oder y im folgenden Schritt nehmen: Z=x^2+y^2 Für x oder y jetzt die umgestellte Gleichung einsetzen: Z=x^2+((ax-c)/b)^2 Z=((by-c)/b)^2+y^2 Z nun einmal ableiten (überlass ich dem Threadstarter) und Nullstellen suchen (Hab ich jetzt auch grad keine Lust zu rechnen). Danach zweite Ableitung von Z bilden und auf Minimum\Maximum prüfen. Wenn ich mich nicht vertan hab, sollte man damit recht einfach vorwärts kommen. Wenn man nun für x oder y nen Wert hat, zurück substituieren und in die Original-Gleichung einsetzen und ausrechnen. HTH.

Okay, das ist jetzt'n analytischer Weg die Sache zu handlen. Aber da später etwa bis zu 200 Unbekannte auftreten können würde ich das Ganze gerne numerisch handlen. Ich weiß' nur nicht nach welchen Verfahren/Methoden/Algorithmen ich suchen soll...

BTW.: Wusstet ihr, dass in kommerzieller Software [http://www.anybodytech.com/] so unsere Muskelkräfte bei gewissen Beanspruchungen berechnet werden? Die Muskelaktivitäten müssen wegen der redundanten Anzahl von Muskeln irgendwie verteilt werden. Da benutzt man die Zielfunktion: Summe aller Muskelkräfte^2 soll minimal sein...

Gruß

Calculon
--

Delete - Sa 17.05.08 09:23

---

falls es sich rein und ausschliesslich um quadradische gleichungen handelt, kannst du ein modifiziertes symplex verwenden. sieh hierzu: QUADRATIC PROGRAMMING das sollte dir weiterhelfen.

ansonsten ist hierfür i.a.R. als gernallösung die DYNAMIC PROGRAMMING anzusehen.

<HTH> GG

Calculon - Sa 17.05.08 19:49

---

Grenzgaenger hat folgendes geschrieben:

falls es sich rein und ausschliesslich um quadradische gleichungen handelt, kannst du ein modifiziertes symplex verwenden. sieh hierzu: QUADRATIC PROGRAMMING das sollte dir weiterhelfen. [..]

Danke, werd' ich mir mal ankucken!

Gruß

Calculon
--