준-뉴턴법

수치해석 최적설계 마지막 수정: 2026-07-13 04:27:33

1. 개요[편집]

준-뉴턴법(Quasi-Newton method)은 비선형 방정식의 해나 함수의 극값을 찾을 때, 매 반복마다 정확한 자코비안 행렬(또는 헤시안 행렬)을 다시 계산하는 대신 이전 정보로 근사행렬을 저렴하게 갱신하며 전진하는 반복법 계열이다. 뉴턴-랩슨법의 빠른 수렴을 최대한 흉내 내되, 그 최대 약점인 “매 스텝 야코비안/헤시안 계산과 역행렬 비용”을 회피하는 것이 목표다.

한 줄 요약: “뉴턴은 정확하지만 비싸고, 최급강하법은 싸지만 느리다. 그 사이 어딘가에서 타협 본 게 준-뉴턴이다.” 대규모 최적화와 비선형 구조해석에서 사실상 표준 도구가 되었다.

2. 뉴턴법의 비용 문제[편집]

$n$ 개의 미지수를 갖는 비선형 방정식 $\mathbf{F}(\mathbf{x}) = \mathbf{0}$ 에 대해 뉴턴-랩슨법은 다음을 반복한다.

\mathbf{x}_{k+1} = \mathbf{x}_k - \mathbf{J}(\mathbf{x}_k)^{-1}\mathbf{F}(\mathbf{x}_k)

이 방법은 이차 수렴(quadratic convergence)이라는 강력한 무기를 가졌지만, 대가가 만만치 않다.

$n \times n$ 자코비안 행렬 $\mathbf{J}$ 의 모든 성분을 매 스텝 계산해야 한다. 해석적 미분이 없으면 수치미분으로 $O(n^2)$ 번 함수 평가.
매 스텝 $\mathbf{J}$ 의 역(또는 선형계 풀이)에 $O(n^3)$ 연산.

$n$ 이 수천~수백만인 최적설계나 대규모 시스템에서는 이 비용이 감당이 안 된다. 준-뉴턴법은 “야코비안을 매번 새로 만들지 말고, 이번 스텝에서 관측한 변화량으로 살짝 고쳐 쓰자”는 발상으로 이 벽을 넘는다.

3. 시컨트 조건과 갱신 공식[편집]

준-뉴턴의 심장은 **시컨트 조건(secant condition)**이다. 근사행렬 $\mathbf{B}_{k+1}$ 이 최근의 스텝 변화 $\mathbf{s}_k = \mathbf{x}_{k+1}-\mathbf{x}_k$ 와 그래디언트(또는 잔차) 변화 $\mathbf{y}_k$ 를 다음처럼 만족해야 한다.

\mathbf{B}_{k+1}\,\mathbf{s}_k = \mathbf{y}_k

이는 1차원 시컨트법(할선법)을 다차원으로 일반화한 것이다. 하지만 이 조건 하나로는 $\mathbf{B}_{k+1}$ 이 유일하게 결정되지 않으므로( $n>1$ ), “이전 행렬 $\mathbf{B}_k$ 에서 최소한으로만 바꾼다”는 최소 변화 원리를 추가해 갱신 공식을 유도한다. 대표적인 것들은 다음과 같다.

Broyden 법 — 비선형 방정식 풀이용. $\mathbf{B}$ 를 랭크-1(rank-one)로 갱신. 대칭성이 필요 없는 일반 문제에 쓴다.
DFP 법(Davidon-Fletcher-Powell) — 최적화용. 헤시안의 역을 랭크-2로 갱신하는 최초의 실용적 준-뉴턴법.
BFGS 법(Broyden-Fletcher-Goldfarb-Shanno) — 최적화의 사실상 왕. 랭크-2 갱신에 대칭·양정치성을 보존해 수치적으로 튼튼하다.¹ 헤시안의 역을 직접 갱신해 매 스텝 역행렬 계산 자체가 없다.

메모리가 부족한 초대규모 문제에서는 전체 행렬을 저장하지 않고 최근 몇 개의 $(\mathbf{s}_k, \mathbf{y}_k)$ 쌍만으로 행렬-벡터 곱을 재구성하는 L-BFGS(제한 메모리 BFGS)를 쓴다. 딥러닝 이전 시대 대규모 최적화의 주력이었고, 지금도 로그-우도 최적화 등에서 현역이다.

4. 수렴 속도와 비용 트레이드오프[편집]

준-뉴턴법의 수렴 차수는 **초선형(superlinear)**이다. 뉴턴법의 이차 수렴보다는 느리지만 최급강하법 같은 선형 수렴보다는 확실히 빠르다. 스텝 수는 뉴턴보다 조금 더 들 수 있어도, 스텝당 비용이 $O(n^3) \to O(n^2)$ (또는 L-BFGS는 $O(n)$ )로 확 줄어드니 총 비용에서 압도적으로 유리한 경우가 많다.

정리하면 이런 그림이다.

함수/그래디언트 평가가 아주 비싸고 미분 정보가 없다 → 준-뉴턴(야코비안 안 만들어도 됨).
조건수가 나쁘거나 시작점이 해에서 멀다 → 라인 서치·신뢰 영역(trust region)과 결합해 전역 수렴성 보강. BFGS의 양정치성 보존이 여기서 빛을 발한다.
정확한 야코비안이 싸게 얻어지고 $n$ 이 작다 → 그냥 뉴턴-랩슨법이 낫다.

5. 시뮬레이션에서의 활용[편집]

준-뉴턴법은 시뮬레이션 곳곳에 숨어 있다.

비선형 구조해석 — 재료·기하 비선형, 접촉 해석 문제에서 매 하중 증분마다 강성행렬(≈ 접선 강성)을 다시 조립·분해하는 비용이 어마어마하다. 그래서 상용 코드(Abaqus 등)는 강성행렬을 몇 스텝 동안 재사용하는 수정 뉴턴(modified Newton)이나 BFGS 옵션을 제공한다. 뉴마크법 시간 적분 내부 반복에도 들어간다.
최적설계 — 목적함수 최소화 루프에서 헤시안을 직접 계산하기 어려울 때 BFGS/L-BFGS가 기본 선택.
역문제와 파라미터 추정 — 측정값에 모델을 맞추는 최소자승법 비선형 버전에서 자주 등장한다.

물론 만능은 아니다. 근사가 틀어지면 수렴이 정체될 수 있고, 강한 비선형에서는 오히려 정직한 뉴턴이 안전하다. 수렴은 신에게 맡기되, 준비는 준-뉴턴으로 하는 것이 현업의 현실이다.

6. 관련 문서[편집]

BFGS는 네 사람(Broyden·Fletcher·Goldfarb·Shanno)이 1970년 거의 동시에 독립적으로 같은 공식을 발표해서 이름이 넷 다 붙었다. 수치해석 역사상 가장 유명한 “동시 발견”이자, 알파벳 순서로 이름을 나열해 지분 다툼을 피한 우아한 사례다. ↩