본문으로 바로가기



Optimization with R - 3. 2차 근사로서의 뉴턴 방법에 대하여(테일러 정리의 활용)

category Statistics/Optimization 2017.07.15 00:21
Optimization with R - 3. 2차 근사로서의 뉴턴 방법에 대하여

1차 근사를 이용한 뉴턴 방법의 해찾기

지난 포스팅에서 우리는 newton method를 이용한 최소값을 만드는 \(x\)값을 찾는 방법에 대하여 알아보았다. 이 방법의 핵심은 해를 찾는 방법이었던 뉴턴 방법을 최소값을 찾고 싶은 함수의 1차 도함수에 적용하는 것이라고 할 수 있다.

필자가 첫번째 포스팅에서 링크했던 아래의 그림은 해를 찾는 방법에 있어서 Newton’s method가 어떻게 동작하는지를 잘 보여준다.

위의 그림에서 기울기를 나타내는 선인 빨간색 선을 주목해 보자. 뉴턴 방법은 현재 위치(\(x_n\))에서 해를 찾고자하는 함수를 1차 근사(빨간색 직선)를 시킨다. 즉, 빨간색 선과 비슷하다고 생각하는 것이다. 그리고 그렇게 근사된 함수(빨간색 선)의 해를 찾는 것(\(x_{n+1}\))을 반복하는 것이라 생각할 수 있다.

2차 근사로서의 Newton’s method

이것과 유사하게 최적화 문제에서의 뉴턴 방법은 함수를 2차 근사 시키는 방법이라 생각할 수 있다. 다음과 같은 함수를 생각해보자.

\[ f\left(x\right)=-2sin\left(x\right)+\frac{x^{3}}{10} \]

우리의 목표는 0보다 큰 범위의 \(x\)값들 중에 위의 함수값을 가장 작게 만드는 \(x\)값을 찾는 것이라 가정하자. 위의 함수를 그래프로 나타내면 다음과 같다. 그래프의 결과를 살펴보면 1과 2사이에 우리가 찾는 값이 있다는 것을 알 수 있다.

첫번째 시작점을 \(x=3\)이라고 가정할 때, 뉴턴 방법은 주어진 파란색 함수를 \(x=3\)에서의 정보들을 이용하여 2차 근사를 시킨다고 생각할 수 있다. 이 때 2차 근사 곡선을 찾는 방법은 우리가 미적시간에 배원던 테일러의 2차 근사를 이용한다.

\[ f(x)\approx f(a)+f'(a)(x-a)+\frac{f''(a)}{2!}(x-a)^{2} \]

실제 값을 구하기 위하여 주어진 함수의 1차와 2차 도함수를 구하면 다음과 같다.

\[ \begin{align*} f'\left(x\right) & =-2cos\left(x\right)+\frac{3}{10}x^{2}\\ f''\left(x\right) & =2sin\left(x\right)+\frac{6}{10}x \end{align*} \]

따라서, 주어진 함수 \(f\)\(x=3\)의 위치에서 2차 근사를 해보면 다음과 같은 함수가 된다.

\[ f(x)\approx f(3)+f'(3)(x-3)+\frac{f''(3)}{2!}(x-3)^{2} \]

library(ggplot2)

# define derivatives
f   <- function(x){ - 2*sin(x) +   x^3 / 10 }
df  <- function(x){ - 2*cos(x) + 3*x^2 / 10 }
d2f <- function(x){   2*sin(x) + 6*x   / 10 }

# define approx. function of f at x = 3
appf <- function(x){ f(3) + df(3)*(x-3) + 0.5 * d2f(3)*(x-3)^2 }

# prepare plot
p <- ggplot(data = data.frame(x = 0)) +
      geom_hline(yintercept=0) + geom_vline(xintercept=0) + xlim(0, 5)

# draw f and appf
p <- p + stat_function(fun = f, color = "blue") +
          stat_function(fun = appf, color = "red")

# labelling
p + labs(title = expression(paste(f(x), " and its ", 2^nd, " order approx.")),
         x = "x", y = "",
         caption = "The red line is the 2nd order approximation of the blue line at 3.")

위에서 볼 수 있는 것처럼 빨간선은 우리가 시작 위치인 3에서 주어진 함수 \(f\)(파란선)를 2차 근사한 것이다. 근사가 꽤 잘 되었음을 알 수 있다. 이 사실을 바탕으로 우리는 최소화하고 싶은 함수가 2차 곡선과 비슷한 모양일 수록 뉴턴 방법의 수렴이 빨라질 것이라는 것을 추론해볼 수 있다. 자, 이제 근사시킨 빨간 함수를 최소로 만드는 \(x\)값은 무엇일까? 바로 근사시킨 2차 함수를 한번 미분 한 도함수를 0으로 만드는 값이다. 따라서 이 값을 찾으면 다음과 같다.

\[ \begin{align*} appf(x) & =f(3)+f'(3)(x-3)+\frac{f''(3)}{2!}(x-3)^{2}\\ appf'(x) & =f'\left(3\right)+f''\left(3\right)\left(x-3\right)\overset{set}{=}0\\ \Rightarrow & x=3-\frac{f'\left(3\right)}{f''\left(3\right)} \end{align*} \]

이미 눈치챈 독자들도 있겠지만, 결국 이 방법은 최적화 문제에서의 뉴턴 방법의 핵심 스텝과 동일하다.이러한 과정을 R의 그래프를 이용하여 나타내어보면 다음과 같다.

x_positions <- c(3, 3 - df(3)/d2f(3))
my_points <- data.frame(x_pos = x_positions,
                        y_pos = 0)
p <- p + geom_point(data = my_points,
                    mapping = aes(x = x_pos, y = y_pos),
                    color = "green")

p <- p + labs(title = "Newton's method in Optimization",
              x = "x", y = "",
              caption = "Newton's second step, x1, is the optimal 
                         point of the 2nd order approx. function") +
         annotate("text",
                  x = x_positions,
                  y = 0.7,
                  label = c("x[0]", "x[1]"), parse = TRUE)
p

위의 그래프에서 볼 수 있듯 최적화 문제에서의 뉴턴 방법은 주어진 함수를 2차 근사시키는 방법를 이용하여 최소값을 만드는 \(x\)값을 찾아나간다. 우리가 이전에 정의했던 newton_method를 통하여 이러한 방법이 잘 작동하는지 확인해보도록 하자.

# package installation
# devtools::install_github("issactoast/r4issactoast")
library(r4issactoast)
newton_method(df, d2f, 3)
## Final value of function: -2.220446e-16
## [1] 1.31032
optimal_p <- newton_method(df, d2f, 3)
## Final value of function: -2.220446e-16
p + geom_vline(xintercept = optimal_p,
               linetype = 2) +
    geom_point(x = optimal_p, y = 0,
               color = "black")


Reference

[1] Wikipedia Newton’s method page: https://en.wikipedia.org/wiki/Newton%27s_method

[2] Wikipedia Newton’s method in optimization page: https://en.wikipedia.org/wiki/Newton%27s_method_in_optimization


SHARE TO



티스토리 툴바