14-01 Newton's method
제약조건이 없고(unconstrained), 두 번 미분 가능하고 convex이며, dom(\(f\)) = \(\mathbb{R}^{n}\)인 함수 \(f\)에 대한 최적화 문제를 살펴보자.
\[\begin{align} \min_{x} f(x) \end{align}\]
Gradient descent에서는 이 함수 \(f\)에 대해 아래와 같은 과정을 수행하였다.
- 2차 테일러 근사를 수행
- 2차 미분 항에 해당하는 Hessian matrix를 \(I/t\), 즉 정방행렬에 t(step size)를 나눈 값으로 가정
- Quadratic approximation을 수행하여 update step를 진행
자세한 과정은 다음 페이지의 gradient descent update step에서 설명한다. 이 때의 매 update step 식은 다음과 같다.
\[\begin{align} &\text{choose initial } x^{(0)} \in \mathbb{R}^{n},\\\\ &x^{(k)} = x^{(k-1)} - t_{k} \cdot \nabla f(x^{(k-1)}), \qquad k = 1,2,3,... \end{align}\]
Newton’s method(pure Newton’s method)는 기존 gradient descent에서 \(\frac{1}{t}I\)로 가정했던 2차 미분항을 실제로 계산하여 quadratic approximation을 수행하고, update step 를 진행한다. 이 과정 또한 다음 페이지의 Newton’s method update step에서 설명한다. 이 때의 매 update step 식은 다음과 같다.
\[\begin{align} &\text{choose initial } x^{(0)} \in \mathbb{R}^{n},\\\\ &x^{(k)} = x^{(k-1)} - \Big(\nabla^{2}f(x^{(k-1)})\Big)^{-1} \nabla f(x^{(k-1)}), \qquad k = 1,2,3,... \end{align}\]
