본문으로 건너뛰기

11. Newton과 quasi-Newton — 곡률을 쓰되 비용을 통제하기

// CORE 5/7 — Newton, quasi-Newton, DFP, BFGS

Gradient descent는 1차 정보만 봅니다. Newton 계열은 2차 곡률을 사용해 더 똑똑한 step을 만들지만, Hessian 계산과 선형 시스템 풀이 비용이 문제입니다.

Newton​

Newton method는 2차 Taylor model을 최소화합니다.

mk(p)=f(xk)+∇f(xk)⊤p+12p⊤∇2f(xk)p.m_k(p)=f(x_k)+\nabla f(x_k)^\top p+\frac{1}{2}p^\top \nabla^2 f(x_k)p.

이 quadratic model을 pp에 대해 최소화하면 Newton equation이 나옵니다.

∇2f(xk)pk=−∇f(xk).\nabla^2 f(x_k)p_k=-\nabla f(x_k).

업데이트는 다음과 같습니다.

xk+1=xk+pk.x_{k+1}=x_k+p_k.

좋은 조건에서는 매우 빠르게 수렴하지만, Hessian이 positive definite가 아니면 descent direction이 아닐 수 있습니다.

Damped Newton​

실무에서는 보통 line search를 붙입니다.

xk+1=xk+αkpk.x_{k+1}=x_k+\alpha_k p_k.

이렇게 하면 Newton direction의 빠른 국소 수렴성과 line search의 안정성을 함께 얻습니다.

Quasi-Newton​

quasi-Newton은 Hessian 또는 inverse Hessian을 직접 계산하지 않고 반복 중에 근사합니다.

gradient 변화량을 정의합니다.

sk=xk+1−xk,s_k=x_{k+1}-x_k, yk=∇f(xk+1)−∇f(xk).y_k=\nabla f(x_{k+1})-\nabla f(x_k).

좋은 Hessian 근사는 secant equation을 만족해야 합니다.

Bk+1sk=yk.B_{k+1}s_k=y_k.

DFP​

DFP는 inverse Hessian 근사 Hk≈(∇2f(xk))−1H_k\approx (\nabla^2 f(x_k))^{-1}를 업데이트하는 고전적 quasi-Newton 방법입니다. 방향은 다음처럼 구합니다.

pk=−Hk∇f(xk).p_k=-H_k\nabla f(x_k).

DFP는 역사적으로 중요하지만, 실무에서는 보통 BFGS가 더 안정적이라 많이 쓰입니다.

BFGS​

BFGS는 positive definiteness를 잘 보존하는 quasi-Newton 업데이트입니다. sk⊤yk>0s_k^\top y_k>0이면 BkB_k가 positive definite일 때 Bk+1B_{k+1}도 positive definite로 유지됩니다.

이 성질 때문에 BFGS direction은 descent direction이 되기 쉽고, Wolfe line search와 잘 맞습니다.

대규모 문제에서는 전체 행렬을 저장하지 않는 L-BFGS가 자주 쓰입니다.

비교​

방법정보장점비용
Gradient descentgradient싸고 단순반복 많음
Newtongradient + Hessian국소적으로 매우 빠름Hessian/linear solve 비쌈
DFPgradient historyinverse Hessian 근사행렬 저장 필요
BFGSgradient history안정적, 실무 강함행렬 저장 필요
L-BFGS최근 history대규모 가능근사 품질은 history에 의존

다음: Coordinate descent와 conjugate gradient