상승 사다리법이 뭐예요?

매끄러운 곡선 $y=f(x)$의 극값을 구하는 방법입니다.
1단계.사용자는 초기 값, 곡선을 제공합니다
두 번째 단계.초기 값의 점에 대해 곡선의 경사율을 계산하고 초기 값이 곡선이 상승하는 방향(x축 방향)으로 이동하는 처리를 합니다.
세 번째 단계.단계 2에서 초기값이 이동하는 점에 대해 다음 단계 4를 평가하고 단계 2를 다시 진행합니다.
4단계.이동 거리가 충분하면 처리를 끝내세요.

극치 부근에서 곡선의 경사율은 매우 작다.2단계에서 이동하는 점의 거리가 매우 작아지고 처리가 끝납니다.
2단계는 다음과 같은 처리입니다.
$x_0$을(를) 초기값으로 합니다. $x_1달러는 다음과 같이 정의됩니다.
$x_1 = x_0 +\theta\cdot f'(x_0)$
여기 $\theta$는 작은 양입니다.
지금, $x_1달러는 곡선이 상승하는 x축 방향으로 이동한다.
일반적인 정의는 다음과 같다.
$x_{i + 1} = x_i +\theta\cdot f'(x_i)\\(i = 0, 1,\cdots)$

예제 코드

epsilon는 4단계에서 이동하는 거리가 충분한 미소량인지 판정하는 것이다.step_size는 단계 2에서 초기 값을 커브가 상승하는 방향으로 이동하는 데 사용되는 작은 양입니다.

from sympy import *
import numpy as np
import matplotlib.pyplot as plt

def gradient(initial_value, f):
    # 変数を指定
    x = Symbol('x')
    # fを微分する
    f1 = diff(f, x)
    # 微小な量を定義する
    epsilon = 1e-6
    step_size = 1e-2
    x_old = initial_value
    x_new = x_old + step_size * f1.subs(x, x_old)
    cnt = 0
    # 変化を追うための各点を格納する配列
    x_array = np.empty(0)
    y_array = np.empty(0)
    # ステップ2とステップ4の処理
    while abs(x_old - x_new) > epsilon:
        x_array = np.append(x_array, x_old)
        y_array = np.append(y_array, f.subs(x, x_old))
        x_old = x_new
        x_new = x_old + step_size * f1.subs(x, x_old)
    # プロットする区間を定義する
    x_interval = np.linspace(-2, 2, 100)
    y_images = np.empty(0)
    # プロットする区間の各点xに対応するf(x)を計算する
    for x_val in x_interval:
        y_images = np.append(y_images, f.subs(x, x_val))
    # (x, f(x))をプロット
    plt.plot(x_interval, y_images, label='curve')
    # 上昇勾配法による変化をプロット
    plt.scatter(x_array, y_array, marker='o', s=50, color='lime')
    # 初期位置をプロット
    plt.scatter(
        [initial_value], [f.subs(x, initial_value)],
        label='initial position', marker='o', s=200, color='blue'
    )
    # 停止位置をプロット
    plt.scatter(
        [x_new], [f.subs(x, x_new)],
        label='stop position', marker='o', s=200, color='red'
    )
    print('勾配法で求めた極大値\nx = {} のとき極大値 {}\n'.format(
        x_new, f.subs(x, x_new)
    ))


def cal_extremes(curve, length):
    """
    微分を使って極値を計算するメソッド
    """
    x = Symbol('x')
    epsilon = 1e-10
    critical_points = solve(diff(curve, x))
    critical_points = [re(point) for point in critical_points
                       if abs(im(point)) < epsilon]
    for critical_point in critical_points:
        if im(critical_point) != 0\
           or length < critical_point or critical_point < -length:
            continue
        extreme_value = curve.subs(x, critical_point)
        diff1 = diff(curve, x)
        diff2 = diff(diff1, x)
        if diff2.subs(x, critical_point) < 0:
            print('微分で求めた極大値\nx = {} のとき極大値 {}\n'.format(
                critical_point.evalf(), extreme_value.evalf()
            ))


plt.figure(figsize=(14.0, 12.0))
initial_value = 0
x = Symbol('x')
f = x ** 3 - 2 * x
gradient(initial_value, f)
cal_extremes(f, 5)
plt.tick_params(labelsize=20)
plt.rc('legend', fontsize=15)
plt.legend()
plt.show()

실행 결과

勾配法で求めた極大値
x = -0.816477683180498 のとき極大値 1.08866210702887

微分で求めた極大値
x = -0.816496580927726 のとき極大値 1.08866210790363

하강 사다리법이 뭐예요?

상승 사다리법과 반대로 초기값이 곡선이 내려가는 방향으로 이동하는 것은 하락 사다리법이다.2단계는 다음과 같습니다.
$x_{i + 1} = x_i -\theta\cdot f'(x_i)\\(i = 0, 1,\cdots)$
아래처럼 기호를 줄이면 됩니다.

x_new = x_old - step_size * f1.subs(x, x_old)

실패 예

단계 2에서 이동 거리가 크면 사다리꼴이 실패합니다.이동 거리가 커서 목표 극치의 x 좌표를 초과합니다.다음은 실패할 때의 도표입니다.

해결책은
$x_{i + 1} = x_i +\theta\cdot f'(x_i)\\(i = 0, 1,\cdots)$
의 $\theta$가 작아집니다.

실패 시

step_size = 1e-2

이것을 더욱 작게 하다.

step_size = 1e-4

참고 문헌

Amit Saha 저흑천 이명역 2016년 05월 Python 수학 입문