O
Hey Leute,
ich muss in letzter Zeit öfter mal Newton-Verfahren auf konvexen, nicht quadratischen Funktionen durchführen.
D.h. ich berechne
xn+1=x_n−f′(x_n)f′′(xn)x_{n+1} = x\_n - \frac {f'(x\_n)}{f''(x_n)}
xn+1=x_n−f′′(xn)f′(x_n)
Das Problem bei nichtkonvexen funktionen ist ja, dass
f(xn+1)<f(xn)f(x_{n+1})<f(x_n)
f(xn+1)<f(xn)
nicht mehr unbedingt gilt, weswegen in vielen Papern eine rückwärtsgerichtete Liniensuche durchgeführt wird:
xn+1=x_n−βkf′(x_n)f′′(xn),β∈(0,1)x_{n+1} = x\_n - \beta^k \frac {f'(x\_n)}{f''(x_n)}, \quad\beta \in (0,1)
xn+1=x_n−βkf′′(xn)f′(x_n),β∈(0,1)
Dabei wird das kleinste k=0,1,2... gesucht, für das die Bedingung gilt. Allerdings wird als Abbruchbedingung häufig sowas verwendet:
f(xn+1)<f(x_n)+αβkf′(x_n),α∈(0,0.5)f(x_{n+1})<f(x\_n)+\alpha \beta^k f'(x\_n), \quad \alpha \in (0,0.5)
f(xn+1)<f(x_n)+αβkf′(x_n),α∈(0,0.5)
Wenn ich das richtig verstehe, ist das ein viel härteres Kriterium, da der linke Term kleiner als der Startpunkt ist. Gibt es da eine Theorie zu, wieso man das macht? In der Praxis funktionieren bei mir beide Abbruchkriterien schlecht (und ich hab das Gefühl, dass bei dem härteren Abbruchkriterium die numerischen Fehler schlimmer sind...).
