1계 도함수법은 그래디언트를 이용해 목적함수의 1차 근사를 하는 최적화 방법이다. 이에 비해 2계 도함수법은 헤시안 등을 사용해 2차 근사를 이용한다. 1계 도함수법에 비해 많은 정보를 활용하기 때문에, 더욱 정확한 근사를 기대할 수 있을 것이다.

1. 뉴턴법

그래디언트는 최적해로 향하는 방향은 알려주지만, 그 스텝의 크기는 알려주지 못한다. 그래서 1계 도함수법에서 다양한 방법을 통해 적절한 스텝의 크기를 조절하려고 했다. 이에 비해 2계 정보는 목적함수의 2차 근사를 가능하게 하고, 최적해 혹은 local minima에 도달할 수 있는 스텝의 크기 역시 근사할 수 있다. 아래 그림을 보도록 하자.

왼쪽은 목적함수를 1차 근사할 경우를, 오른쪽은 목적함수를 2차 근사할 경우를 나타낸다. 오른쪽 그림을 살펴보면 1차 근사로는 얼마나 이동해야하는지 알 수 없지만, 왼쪽 그림을 살펴보면 2차 근사에서 구할 수 있는 최소값이 최적해 근처에 위치할 것을 알 수 있다.

목적함수 $f(x)$에 대해 테일러 전개를 이용하면 2차 근사식 $q(x)$는 다음과 같이 구해질 것이다.

이때 2차 함수의 최소값을 구하기 위해 미분을 이용하면 다음과 같다.

즉, 1계 도함수법과 달리 뉴턴법은 2차 근사한 식의 최소점으로 이동함으로써 가중치들을 업데이트하게 된다. 이는 방향과 스텝의 크기가 분리되지 않고, 함께 계산되는 모습을 보여준다.

결국 뉴턴법의 업데이트 방식은 아래 식으로 정리할 수 있다.

그 결과는 위의 그림과 같으며, 이를 1차 미분한 함수로 생각해보자면, 우리는 1차 미분한 함수에서 실제 함수의 값이 0이 되는 지점을 찾기 위해, 근사한 함수의 값이 0이 되는 지점으로 반복해서 이동하는 것이라 볼 수 있을 것이다.

하지만 뉴턴법은 2차 도함수를 분모로 가지고 있기 때문에, 2차 미분이 0이 되면 업데이트를 할 수 없다. 이는 국소적으로 수평선인 경우에 발생하게 되는데, 2차 미분이 0에 가깝더라도 문제가 발생한다. 2차 미분의 값이 매우 작기 때문에 업데이트가 멀리 일어나게 되고, overshoot이 발생할 수 있다. 이는 아래 그림과 같이 근사식의 최소값이 최적해로부터 멀리 떨어져 있을 경우에 발생하게 된다.

2-1. 뉴턴법의 오차

뉴턴법의 오차는 1차 근사를 이용할 경우 다음과 같이 구할 수 있다.

증명
함수 $f(x)$의 해를 $x=a$라고 하자.

즉, 뉴턴법의 오차는 시행을 거듭할 수록 제곱꼴로 줄어드는 것을 알 수 있다. 하지만 반대로 시작점을 잘못잡는다면 제곱꼴로 증가하게 될 것이다. 이로 인해 뉴턴법의 수렴조건은 최적해 $x^*$의 $\delta$ 거리 내에 있는 시작점 $x_0$에 대해 다음과 같다.

1. $[x^* - \delta, x^* + \delta]$내의 모든 점에 대해 $f''(x) \neq 0$
2. $[x^* - \delta, x^* + \delta]$에서 $f'''(x)$가 연속
3. 어던 $c < \infin$에 대해 ${1 \over 2} |{f'''(x_0)\over f''(x_0)}| < c |{f'''(x^*) \over f''(x^*)}|$

마지막 조건은 overshoot을 방지하는 조건이 된다.

1-2. 다변수 함수에서의 뉴턴법

지금까지 일변수 함수에서의 뉴턴법을 살펴보았는데, 이를 다변수 함수로 확장하면 다음과 같다.
$\textbf{x}_k$에서 다변수 2차 테일러 전개는 다음과 같다. 이때 $g_k$는 그래디언트를, $H_k$는 헤시안 행렬을 의미한다.

위의 식에 대해 동일하게 그래디언트를 0으로 설정하면 다음과 같은 업데이트 식을 얻게 된다.

여기서 이전에 다룬 것처럼 만약 $\textbf{H}$가 positive definite하다면 당연하게도 한번에 최적해로 수렴하게 된다. 하지만 매 반복마다 헤시안 행렬을 계산하고, 그 역행렬을 계산하는 것은 정말 계산량이 많기 때문에 쉬운 일은 아니라고 한다.

2. Secant Method

일변수 함수에서 뉴턴법은 1차 2차 미분 함수를 이용하면 되기 때문에 얼핏 간단해 보일 수 있다. 하지만, 실제로는 1차 미분 함수는 존재하지만 2차 미분 함수는 구하기 어려운 함수들이 많다. 이때 1차 미분함수는 사용하되, 2차 미분함수는 근사값을 사용하는 것이 시컨트법이다. 시컨트법에서 2차 미분함수를 근사하는 법은 다음과 같이 수치해석을 이용한다.

$x_k$와 $x_{k-1}$이 충분히 가깝지 않다면 오차가 크지 않을까 걱정되지만 편리하기 때문에 실제로는 많이 사용된다고 한다.

업데이트 식은 이제 다음과 같이 바뀐다.

시컨트법 역시 뉴턴법과 동일하게 구성되어 있기 때문에, 기울기가 0과 가까운 지점에서 수렴이 힘들어지는 등의 동일한 문제를 겪는다고 한다.

3. quasi-Newton Method

시컨트법이 일변수 함수에 대해 2차 미분 함수를 근사하듯이 준뉴턴법은 다변수 함수에 대해 헤시안 역행렬을 근사한다. 이때의 식은 다음과 같다.

이때 $\alpha$는 스칼라인 스텝 크기이고, $\textbf{Q}_k$는 $\textbf{x}_k$에서 헤시안 역행렬을 근사한 항이다. 준뉴턴법은 다양한 방법으로 근사하는데 일반적으로는 초기 행렬 $\textbf{Q}_0$를 단위행렬로 설정한 후 반복 시행하면서 정보를 업데이트한다.

앞으로 소개할 방법들에서 동일하게 사용되는 노테이션은 다음과 같다.

3-1. DFP

DFP는 다음 수식을 통해 $\textbf{Q}$를 업데이트 한다.

여기서 $Q$는 다음과 같은 특징을 가져야 한다.

1. $Q$는 대칭 행렬이어야 한다. : 헤시안 행렬에 대한 추정치로 $Q$를 사용하기 때문에, 당연히 헤시안 행렬과 같이, 대칭행렬이어야 한다.
2. $Q$는 possitive definite해야 한다. : 최적해를 보장하기 위해서는 헤시안 행렬이 possitive definite해야 한다.
3. 만약 $f(x) = {1 \over 2}\textbf{x}^T A \textbf{x} + \textbf{b}^T\textbf{x} + c$라면, 자연스럽게 $Q = A^{-1}$이다.