1950년대 중반, Argonne 국립 연구소에서 근무 중이었던 물리학자 W.C. Davidon은 coordinate descent method를 이용하여 계산량이 큰 최적화 문제를 풀고 있었다. 불행하게도 당시의 컴퓨터가 불안정했던 탓에 계산이 끝나기도 전에 시스템의 충돌이 빈번히 일어났고, 이에 좌절한 Davidon은 계산속도를 좀 더 향상시킬 수 있는 방법을 찾기로 결심하게 된다. 그렇게 탄생하게 된 것이 바로 최초의 Quasi-Newton 알고리즘이다. 이는 nonlinear optimization을 극적으로 진보시키는 계기가 되었으며, 뒤이어 20여 년 동안 이 방법에 대한 다양한 후속연구들이 등장하였다.
아이러니하게도 Davidon의 연구는 당시 출판되지 못하고 30년 이상을 technical report로 남아있었다. 그리고 마침내 1991년이 되어서야 SIAM Journal on Optimization의 첫 번째 판에 실리게 되었다.
Quasi-Newton methods는 각 반복(iteration)에서 objective function에 대한 gradient만을 필요로 한다. 이는 이차 미분을 필요로하는 newton methods보다 계산적인 부담이 훨씬 적으며 더불어 superlinear convergence를 보인다는 점에서 충분히 매력적인 방법이라고 볼 수 있다 [14].
다음과 같은 unconstrained, smooth optimization problem이 있다고 해보자.
\[\min_x \: f(x), \\\\ \text{where } f \text{ is twice differentiable, and } dom \; f = \mathbb{R}^n.\]
위 문제에 대한 Gradient descent method와 Newton’s method에서의 x에 대한 업데이트 방법은 각각 아래와 같다.
Gradient descent method: \(x^+ = x - t \nabla f(x)\)
Newton’s method: \(x^+ = x - t \nabla^2 f(x)^{-1} \nabla f(x)\)
Newton’s method는 quadratic convergence rate (\(O(\log \log 1/ \epsilon)\))의 수렴속도를 보이는 장점이 있는 반면에 아래 두 과정에 의해 상당히 큰 계산비용이 발생하는 문제가 있다.
Quasi-Newton method에서는 대신 \(\nabla^2 f(x)\)를 근사(approximation)한 \(B\)를 이용한다.
Quasi-Newton method: \(x^+ = x + tp \\\\ \text{where } Bp = -\nabla f(x).\)
이때 B는 계산하기 쉬워야 하며, 또한 방정식 \(Bp = g\)를 풀기에도 용이해야 한다.
Quasi-Newton algorithm은 다음과 같다.
Optimal point에 점진적으로 다가갈 수 있도록 \(B\)를 업데이트 해가는 것이 이 방법의 큰 특징이다. 즉, \(B\)를 통해 next step인 \(B^+\)를 구하는 방법에 대해 이번 장에서 주로 논의하게 될 것이다. (Note: 편의상 \(B^{k+1}, B^k\)와 \(B^+, B\) 두 가지 표기를 혼용하여 사용하겠다.)