1. Zusammenfassung

Dieses Mal fasste ich den Überblick über die Newton-Methode zusammen, die bekannteste und am häufigsten verwendete nichtlineare Optimierungsmethode, und lieferte ein Beispiel für die Implementierung in R und Python. Ich habe es (geplant) für die Parameterschätzung einer Analysemethode mit multivariater Analyse verwendet, also habe ich es auch für das Studium implementiert.

2. Nichtlineare Optimierung

2.1 Was ist das?

So wie es ist, ist es die Optimierung (= Minimierung / Maximierung) nichtlinearer Funktionen. Beispiele für nichtlineare Funktionen sind $ y = x ^ 2 $ und $ y = x \ log_e x $. Nehmen Sie zum Beispiel $ y = x \ log_e x $ als Beispiel, wenn Sie einen Punkt erhalten möchten, der den Mindestwert dieser Funktion angibt (vorausgesetzt, Sie wissen, dass $ 0 <x $ nach unten konvex ist). ) Unterscheide in Bezug auf $ x $ $\frac{d}{dx}y = \log_e x + 1$ Sie müssen lediglich den Wert der Funktion an dem Punkt berechnen, an dem dieser Gradient $ 0 $ beträgt. Mit anderen Worten $\log x_e + 1 = 0$ Alles was Sie tun müssen, ist die Wurzel von zu finden. Übrigens ist $ \ hat {x} = 1 / e $. Auf diese Weise ist es in Ordnung, wenn die Gleichung einfach als Spanne gelöst werden kann (wenn sie analytisch gelöst werden kann), aber in vielen Fällen kann die Lösung nicht explizit ausgedrückt werden. In solchen Fällen sind nichtlineare Optimierungsmethoden nützlich.

2.2 Newton-Raphson-Methode

Unter den nichtlinearen Optimierungen ist die Newton-Methode (Newton-Raphson-Methode, wiki die bekannteste, einfachste und am weitesten verbreitete Methode. Es gibt Newton% 27s_method)). Für mathematische Details siehe Hier (Was ist die Newton-Methode? Ungefähre Lösung der durch die Newton-Methode gelösten Gleichung). Wenn Sie höflich illustriert sind und die Mathematik der High School leise verstehen, können Sie sich eine allgemeine Vorstellung machen. Um dies umzusetzen

Numerische Differenzierung zur Berechnung des Gradienten
Iteration der Aktualisierungsformel der Newton-Methode

Zwei sind erforderlich. In Bezug auf die erste vorerst

\frac{d}{dx}f(x) = \underset{h\rightarrow 0}\lim \frac{f(x + h) - f(x)}{h}

Lassen Sie uns implementieren. In R,

numerical.differentiate = function(f.name, x, h = 1e-6){
  return((f.name(x+h) - f.name(x))/h)
}

Also, in Python,

def numerical_diff(func, x, h = 1e-6):
    return (func(x + h)-func(x))/h

Ist es so Unter Verwendung dieser und der sequentiellen Berechnung nach der Newton-Methode

\log_e x + 1 = 0

Lass uns lösen. Ein Beispiel für die Ausführung in R ist

newton.raphson(f.5, 100, alpha = 1e-3) # 0.3678798

Ein Beispiel für die Ausführung in Python ist

newton_m(f_1, 100, alpha = 1e-3) # 0.36787980890600075

Sie können sehen, dass beide nahe an der Lösung der obigen Gleichung $ 1 / e \ fallenddotseq1 / 2.718 = 0.3679176 $ liegen.

3. Beispielcode

Es ist ein verschiedener Code ...

`{r, newton_raphson.R}`


numerical.differentiate = function(f.name, x, h = 1e-6){
  return((f.name(x+h) - f.name(x))/h)
}

newton.raphson = function(equa, ini.val, alpha = 1, tol = 1e-6){
  x = ini.val
  while(abs(equa(x)) > tol){
    #print(x)
    grad = numerical.differentiate(equa, x)
    x = x - alpha * equa(x)/grad
  }
  return(x)
}

f.5 = function(x)return(log(x) + 1)
newton.raphson(f.5, 100, alpha = 1e-3)

`{python, newton_raphson.py}`


import math
def numerical_diff(func, x, h = 1e-6):
    return (func(x + h)-func(x))/h

def newton_m(func, ini, alpha = 1, tol = 1e-6):
    x = ini
    while abs(func(x)) > tol:
        grad = numerical_diff(func, x)
        x = x - alpha * func(x)/grad
    return x

def f_1(x):
    return math.log(x) + 1

print(newton_m(f_1, 100, alpha = 1e-3))

Damit die Newton-Methode zu einer globalen optimalen Lösung konvergieren kann, muss die zu optimierende Funktion im Optimierungsintervall $ [a, b] $ eine globale optimale Lösung haben und in diesem Intervall konvex sein. Lass uns aufpassen. Das Programm, das ich geschrieben habe, war nicht leicht zu verstehen, da es sich um mehrere Variablen handelte, aber es ist einfach und leicht zu verstehen, wenn es sich um eine Variable handelt. Die Genauigkeit der Berechnung hängt vom tol-Parameter und dem h-Parameter ab.

[PYTHON] Einführung in die nichtlineare Optimierung (I)