본문으로 바로가기



Optimization with R - 2. Newton’s method를 통한 최대값 찾기

category Statistics/Optimization 2017.07.14 15:02
Optimization with R - 2. Newton’s method를 통한 최대값 찾기

\(f(x)\)의 최대값를 찾아라.

오랜만에 다시 opimization 연재를 시작한다. 지난 포스팅에서 우리는 newton method를 이용한 해을 찾는 방법(root finding)에 대하여 알아보았다. 어쩌면 독자 중에는 이전 포스팅의 제목인 ’Optimization with R - 1. Newton’s method를 통한 해찾기’를 읽으면서 고개를 갸웃거린 독자가 있을 것이라 생각한다. 왜냐하면 옵티마이제이션이라 함은 어떤 함수의 최대값이나 최소값을 찾는 방법에 대한 내용이지 어떤 방정식의 해를 찾는 내용은 아니기 때문이다. 하지만 optimization 시리즈의 첫번째를 Newton’s method를 다룬 이유가 있는데, 바로 이 알고리즘을 최대, 혹은 최소값을 구하는데에도 적용할 수 있기 때문이다.

최소값 문제와 해 찾기의 관계

제일 간단한 예를 들어서 생각해보도록 하자. 만약 우리가 아래의 함수를 최소로 만드는 \(x\)의 값을 찾고 싶다고 가정하자.

\[ f\left(x\right)=(x-1)^{4}+8(x-1)^{2}+1 \]

먼저 위의 함수를 한번 그려보면 다음과 같다.

우리의 목표는 \(f(x)\)의 값을 최소로 만드는 값, 즉 \(x = 1\)을 찾는 것이다. Newton's method을 이용해서 0값을 어떻게 찾을 수 있을까? 우리가 알고 있는 것은 뉴턴의 방법을 이용하면 적어도 어떤 함수를 0으로 만드는 x값, 즉 해를 찾을 수 있다는 사실이다.

주어진 함수에 대하여 생각해보자. \(f\)\(x\)에 대한 연속함수로써 아주 예쁜 함수이다. 또한 \(x = 1\)일 때, 함수는 최소값을 가지면서, 동시에 미분계수(즉, 기울기)가 0이 된다. 따라서, 우리가 찾고싶은 최소값을 만드는 x값을 찾기위하여 뉴턴의 방법을 이용하기 위해서는 \(f\)을 이용하는 대신에 \(f\)의 도함수를 사용하면 된다. 왜냐하면 \(f(x)\)를 최소 혹은 최대값을 만드는 \(x\)이 되려면, 적어도 그 자리에서의 미분계수가 0이라는 조건을 만족시켜야 하기 때문이다. 즉, 아래의 방정식을 만족하는 해를 찾으면 된다.

\[ f'\left(x\right)=4\left(x-1\right)^{3}+16\left(x-1\right)=0 \]

결국, 이 문제에서는 함수 \(f\)의 최소값을 만드는 \(x\)를 구하는 것과 도함수 \(f'(x)\)를 0으로 만드는 해를 찾는 문제가 같다 것을 의미한다.

\[ \begin{array}{ccc} \underset{x}{argmin}\,f\left(x\right) & \Longleftrightarrow & f'\left(x\right)=0\end{array} \]


뉴턴 방법을 ’도함수’에 적용하기

지난 시간에 배운 뉴턴 방법을 이용한 해찾기를 어떤 함수(예를 들어 \(g\)라고 하자.)에 적용하기 위해서는 다음의 두 가지의 조건을 만족해야 한다고 배웠다.

  1. 함수 \(g\)는 결과값이 1차원인 real-value function이어야 한다.
  2. \(g\)는 미분가능한 함수, 즉 \(g'(x)\)를 구할 수 있는 함수이어야 한다.

우리가 풀려고 하는 문제에서 함수 \(g\)\(f\)의 도함수인 \(f'(x)\)가 된다. 따라서, 1번의 조건은 쉽게 만족함을 알 수 있고, 2번 역시 주어진 \(f'(x)\)를 한번 더 미분한 2차 도함수를 구할 수 있으므로, 두 가지 조건을 모두 만족한다.

\[ f''\left(x\right)=12\left(x-1\right)^{2}+16 \]

이 조건으로 미루어보아, 최적화 기법에 뉴턴 방법을 적용하기 위해서는 위의 조건은 다음과 같다는 것을 알 수 있다.

  1. 적용하려는 함수는 결과값이 1차원인 real-value function이어야 한다.
  2. 적용하려는 함수는 적어도 2차 도함수가 존재하여야 한다.

뉴턴 방법을 R로 적용하기

지난 포스팅에서 해를 찾기 위한 뉴턴 알고리즘의 핵심 단계는 다음의 iteration이었다.

\[ x_{n+1}:=x_{n}-\frac{f\left(x_{n}\right)}{f'\left(x_{n}\right)} \]

따라서 이번 문제를 풀기위한 뉴턴 알고리즘은 다음의 업데이트를 행하게된다.

\[ x_{n+1}:=x_{n}-\frac{f'\left(x_{n}\right)}{f''\left(x_{n}\right)} \]

앞에서 구한 1차와 2차 도함수를 R에 정의한 후, 지난 포스팅에서 정의했던 newton_method를 이용하여 구해보자.

# package installation
# devtools::install_github("issactoast/r4issactoast")
library(r4issactoast)
df <- function(x){ 4 * (x-1)^3 + 16 * (x-1) }
d2f <- function(x){ 12 * (x-1)^2 + 16 }
newton_method(df, d2f, 10)
## Final value of function: 0
## [1] 1

예상대로 잘 구해지는 것을 알 수 있다. 다음 시간에는 좀 더 복잡한 예제(입력값이 2개인 함수)를 가지고 좀 더 뉴턴 방법에 대해 심도있게 이해해보도록 하자.

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



티스토리 툴바