C/C++ Forum :: Suche: einfaches numerisches Verfahren f. nichtlineares Optimierungsproblem

Unregistrierter

Hallo, gegeben ist ein Polynom

f: IR^2 -> IR,

bspw. f(x) = x^3 - y^2 + 3

Ich suche ein möglichst einfaches, numerisches Verfahren, welches mir lokale Extrema bei einer solchen Funktion findet - dieses würde ich gerne in C oder C++ implementieren.

Das ist keine Hausaufgabe, mich interessiert nur, ob man solche nichtlinearen Optimierungsprobleme mit moderatem Aufwand programmatisch lösen kann.

danke

Unregistrierter

Ich meine natürlich bei dem Beispiel f(x,y) = ..., also y ist keine Konstante.

Unregistrierter

Hmm, ich würde mir einen Punkt heraussuchen und dann drumherum die Funktionswerte auslesen. Dann vergleichen und in Richtung abnehmender bzw. zunehmender Werte weiter wandern.

knivil Mitglied 10:05:02 17.01.2012 Titel:

Lokale Extrema zu finden ist meist nie das Problem. Einfach entlang des Gradienten wandern. Lohnt sich aber nicht fuer solch simple Beispiele.

zeusosc Mitglied 10:08:34 17.01.2012 Titel:

Hi,

Was definierst du als lokal?

Ansonsten die partiellen Ableitungen bilden und checken ob die null werden,..

§\partial_x f=3x^2 , \partial_y f=2y§

Unregistrierter

Wie man damit in der Analysis umgeht, ist mir klar. Aber mal schnell Ableitungen bilden und nach 0-Stellen in dieser suchen, ist ja programmatisch so eine Sache. Genau darum geht es mir ja.

Wie ein lokales Extremum definiert ist, sollte klar sein. Jedes Extremum ist lokal, ich wollte nur betonen, dass es mir nicht auf das globale Extremum ankommt, welches, soweit ich weiß, auch nicht effizient gefunden werden kann in der nichtlinearen Optimierung.

ProgChild Autor 10:35:39 17.01.2012 Titel:

Falls du nichts über die Funktion weist, könntest du den Nelder-Mead Algorithmus verwenden. Ansonsten ein Gradientenverfahren (wie schon erwähnt), Verfahren des steilsten Abstiegs (Steepest Decent), wobei du halt das Vorzeichen der Funktion umdrehen musst, wenn du ein Maximum suchst.

Ein Gradientenverfahren sucht nicht nach der Nullstelle der 1. Ableitung. Und kannst die Ableitung auch numerisch berechnen/approximieren.

zeusosc Mitglied 10:51:25 17.01.2012 Titel:

Numerisch bilde ich auch nur die richtungsableitungen,..

Im mehrdimensionalen hab ich das noch nicht gemacht, aber
diese sind doch im prinzip :

Interpolierter Wert:
§f(x_1,\frac{y_1-y_2}{2}+y_1)=f(x_1,y_1)+\frac{f(x_1,y_1)-f(x_1,y_2)}{2}§

Die Steigung der Tangente an der Interpolierten Stelle (quasi Partielle Ableitung):
§m=\frac{f(x_1,y_1+h)-f(x_1,y_1)}{h}=\frac{2(f(x_1,y_1+\frac{y_1-y2}{2})-f(x_1,y_2))}{y_1-y_2}§

--Stimmt, das newton Verfahren ist ganz gut (Gradientenverfahren),..

Bashar Mitglied 11:20:06 17.01.2012 Titel:

Die meisten Verfahren der nichtlinearen Optimierung sind darauf ausgelegt, von einem gegebenen Startpunkt aus EINE Nullstelle möglichst schnell und genau zu finden. Die genannten Verfahren, Gradientenverfahren und Newtonverfahren sind sowas. Nelder-Mead kenn ich leider nicht, aber laut Wikipedia funktioniert es auch nur für unimodale Funktionen (also welche mit nur einem Extremalpunkt).
Ich muss also hier erstmal fragen: Geht es darum, ALLE Nullstellen zu finden oder genügt obiges? Falls letzteres, ist das Gradientenverfahren sicher das einfachste, das kann aber auch bei manchen Funktionen richtig langsam sein, wenn es sich in winzigen Zickzackschritten an den Optimalpunkt herantastet. Eventuell ist also ein globalisiertes Newton-Verfahren angeraten, bei solchen einfachen Funktionen ist das in jedem Fall drin.
(Falls ersteres: Keine Ahnung.)

Unregistrierter

Bashar schrieb:

Ich muss also hier erstmal fragen: Geht es darum, ALLE Nullstellen zu finden oder genügt obiges?
(Falls ersteres: Keine Ahnung.)

"falls ersteres:" alle Nullstellen eines Systems F zu finden, ist schon ein ziemlich nichttriviales problem, egal ob numerisch oder exakt, schon im relativ einfachen Fall von Polynomen - von komplizierteren Funktionen ganz zu schweigen.

Eine allgemeine methode ist, erstmal ein System G aufzustellen, dessen Nullstellen man sehr leicht berecchnen kann (sagen wir: x(x-1)(x-2)(x-3)), und dann mit einer Homotopie

Hom(t) = t*F+(1-t)*G

das Startsystem G nach und nach in F zu verwandeln, während man mit Newton die Lösungspfade trackt.
Und hofft, daß man nicht auf eine "Mine latscht", etwa eine Singularität auf einem der Lösungspfade, oder auf einen Lösungspfad, der nach einigen Pirouetten zum Anfangspunkt zurückkehrt.

Braucht man sämtliche Lösungen, und zwar alle exakt, dann: Gröbnerbasen

Unregistrierter

Vielen Dank für eure Beiträge. Da die Sache doch ziemlich kompliziert zu sein scheint, gebe ich mich erstmal mit irgendeinem lokalen Extremum zufrieden und verwende ein Gradientenverfahren