Метод Ньютона для оптимизации в Python

Метод Ньютона для оптимизации в Python

Самое короткое и понятное объяснение с нуля построчно

Метод Ньютона для оптимизации является частным случаем метода спуска.

Где "f''(xk​)" является производной от производной "f " оценивается на итерации "k".

Рассмотрим функцию:

Давайте построим это:

import matplotlib.pyplot as plt
import numpy as np
from numpy import log

x = np.linspace(0, 1.2, 100)
y = 2*x - log(x)

plt.plot(x, y, '-r', label='y = 2*x - log(x)')

plt.title('Graph of y = 2*x - log(x)')
plt.xlabel('x', color='#1C2833')
plt.ylabel('y', color='#1C2833')
plt.legend(loc='upper left')
plt.grid()

plt.show()

Первая и вторая производные:

from sympy import diff, ln
from sympy.abc import x

f = 2*x - ln(x)
df = diff(f)
ddf = diff(df)
print(df)
print(ddf)

# 2 - 1/x
# x**(-2)

Показать в обычном режиме:

Начнем итерацию с x0 ​= 0,1:

x0 = 0.1
fx0 = 2*x0 - ln(x0)
print(fx0)
# 2.50258509299405

Чтобы найти x1, воспользуемся формулой сверху:

x1 = x0 - (2 - 1/x0) / x0**(-2)
print(x1)
# 0.18000000000000002

fx1 = 2*x1 - ln(x1)
print(fx1)
# 2.07479842809193

Чтобы найти x2, мы должныповторить это:

x2 = x1 - (2 - 1/x1) / x1**(-2)
print(x2)
# 0.2952

fx2 = 2*x2 - ln(x2)
print(fx2)
# 1.81050218625582

Выглядит скучно. Давайте создадим цикл и выведем результат:

Давайте проверим минимум реальной функции:

from sympy.calculus.util import Interval, minimum
from sympy.abc import x
from sympy import ln

print(minimum(2*x - ln(x), x, Interval(0, 1)))

# log(2) + 1

log(2) + 1 = 1,6931471805599454, поэтому точность на пятой итерации составляет около 0,0000003.

Давайте построим, как это выглядит:

for x, fx in zip(x_list, fx_list):
    plt.plot(x, fx, marker="o", markersize=10, markeredgecolor="red", markerfacecolor="green")
plt.show()

Полный код здесь:

Если вам нужны некоторые вещи для оптимизации 3D, попробуйте посмотреть: