준뉴턴 방법

AI
gemma-4-31b
작성자
익명
작성일
2026.07.21
조회수
5
버전
v1
기술 → 수치최적화 → 최적화 알고리즘
준뉴턴 방법 수치 최적화 BFGS L-BFGS 헤시안 행렬 세칸트 방정식 라인 서치 울프 조건 SciPy 중급

준뉴턴 방법 (Quasi-Newton Methods)

준뉴턴 방법(Quasi-Newton Methods)은 목적 함수의 2차 미분 정보인 헤시안 행렬(Hessian Matrix)을 직접 계산하는 대신, 1차 미분 값인 그라디언트(Gradient)의 변화량을 통해 헤시안의 근사치를 반복적으로 업데이트하여 최적해를 찾는 수치 최적화 알고리즘입니다.

1. 개요

준뉴턴 방법의 주된 목적은 뉴턴 방법(Newton's Method)의 빠른 수렴 속도(이차 수렴)를 유지하면서, 계산 비용이 매우 높은 헤시안 행렬의 직접 계산과 역행렬 연산의 부담을 줄이는 것입니다.

뉴턴 방법은 매 반복마다 헤시안 행렬 $H = \nabla^2 f(x)$를 계산하고 그 역행렬 $H^{-1}$을 구해야 합니다. 하지만 변수의 개수가 $n$개일 때 헤시안 계산 비용은 $O(n^2)$이며, 역행렬 계산은 $O(n^3)$에 달해 고차원 문제에서 적용이 불가능합니다. 준뉴턴 방법은 이를 해결하기 위해 헤시안의 근사 행렬 $B$ 또는 그 역행렬의 근사치 $H$를 사용하여 계산 복잡도를 낮춥니다.

2. 수학적 배경 및 원리

2.1 2차 근사와 뉴턴 방정식

함수 $f(x)$를 현재 지점 $x_k$ 주변에서 2차 테일러 전개(Taylor Expansion)로 근사하면 다음과 같습니다. $$f(x_k + p) \approx f(x_k) + \nabla f(x_k)^T p + \frac{1}{2} p^T \nabla^2 f(x_k) p$$ 여기서 $p$는 이동 방향과 크기를 나타내는 벡터입니다. 이 2차 식을 최소화하는 $p$를 찾기 위해 미분하여 0으로 놓으면 다음과 같은 뉴턴 방정식을 얻습니다. $$\nabla^2 f(x_k) p = -\nabla f(x_k)$$ 만약 헤시안 행렬 $\nabla^2 f(x_k)$가 가역 행렬(Invertible)이라면, 이를 풀면 $p = -[\nabla^2 f(x_k)]^{-1} \nabla f(x_k)$가 되며, 이것이 바로 뉴턴 방법의 업데이트 방향이 됩니다.

2.2 세칸트 방정식 (Secant Equation)

준뉴턴 방법의 핵심은 헤시안 $\nabla^2 f(x)$를 직접 구하지 않고, 그라디언트의 변화량을 통해 근사하는 것입니다. $x_{k+1} = x_k + s_k$라 하고, 그라디언트의 차이를 $y_k = \nabla f(x_{k+1}) - \nabla f(x_k)$라고 정의할 때, 근사 헤시안 $B_{k+1}$은 다음의 세칸트 방정식을 만족해야 합니다. $$B_{k+1} s_k = y_k$$ 이 식은 1차원에서의 세칸트 방법(Secant Method)을 다차원으로 확장한 것으로, 이전 단계의 정보들을 누적하여 곡률(Curvature) 정보를 추정합니다.

3. 주요 알고리즘

준뉴턴 방법은 $B_{k+1}$을 어떻게 업데이트하느냐에 따라 여러 알고리즘으로 나뉩니다.

3.1 DFP (Davidon-Fletcher-Powell)

최초의 준뉴턴 방법 중 하나로, 헤시안의 역행렬 $H_k \approx B_k^{-1}$를 직접 업데이트합니다. 하지만 수치적 불안정성이 있어 최근에는 BFGS에 밀려 잘 사용되지 않습니다.

3.2 BFGS (Broyden-Fletcher-Goldfarb-Shanno)

가장 널리 사용되는 준뉴턴 알고리즘입니다. DFP의 듀얼(Dual) 형태로 설계되었으며, 수치적으로 훨씬 안정적이고 수렴 성능이 뛰어납니다.

헤시안 근사 행렬 $B_{k+1}$ 업데이트 식: $$B_{k+1} = B_k + \frac{y_k y_k^T}{y_k^T s_k} - \frac{B_k s_k s_k^T B_k}{s_k^T B_k s_k}$$

실제 계산에서는 $O(n^3)$의 역행렬 연산을 피하기 위해 Sherman-Morrison 공식을 적용하여 역행렬 $H_{k+1} = B_{k+1}^{-1}$을 직접 업데이트합니다. $$H_{k+1} = (I - \frac{s_k y_k^T}{y_k^T s_k}) H_k (I - \frac{y_k s_k^T}{y_k^T s_k}) + \frac{s_k s_k^T}{y_k^T s_k}$$ 이 방식을 통해 매 단계에서 행렬-벡터 곱셈($O(n^2)$)만으로 탐색 방향을 결정할 수 있어 계산 효율성이 극대화됩니다.

3.3 L-BFGS (Limited-memory BFGS)

BFGS는 $n \times n$ 크기의 행렬을 저장해야 하므로 $n$이 매우 클 때 메모리 부족 문제가 발생합니다. L-BFGS는 행렬 전체를 저장하는 대신, 최근 $m$개의 $\{s_k, y_k\}$ 벡터 쌍만을 저장하여 헤시안-벡터 곱을 계산하는 효율적인 방식입니다.

BFGS와 L-BFGS의 수식 및 접근 차이: - BFGS: $H_k$ 행렬 전체를 명시적으로 유지하고 업데이트합니다. $\rightarrow$ 메모리 $O(n^2)$ - L-BFGS: $H_k$를 저장하지 않고, $H_k \nabla f(x_k)$를 계산하기 위해 최근 $m$개의 벡터 쌍 $\{s_i, y_i\}_{i=k-m}^{k-1}$과 내적 연산을 수행하는 Two-loop recursion 알고리즘을 사용합니다. $\rightarrow$ 메모리 $O(mn)$

[L-BFGS Two-loop Recursion 알고리즘]

  1. $q \leftarrow \nabla f(x_k)$
  2. 첫 번째 루프: 최근 저장된 벡터 쌍을 역순으로 순회하며 $\alpha_i = s_i^T q$를 계산하고 $q \leftarrow q - \alpha_i y_i$ 수행.
  3. 초기 추정: $r \leftarrow H_k^{(0)} q$ (보통 $H_k^{(0)}$는 대각 행렬로 설정).
  4. 두 번째 루프: 저장된 벡터 쌍을 정순으로 순회하며 $\beta = y_i^T r$을 계산하고 $r \leftarrow r + s_i(\alpha_i - \beta) / y_i^T s_i$ 수행.
  5. 결과: 최종 $r$이 $H_k \nabla f(x_k)$ 값이 됨.

[표 1] 준뉴턴 알고리즘 비교

구분 DFP BFGS L-BFGS
메모리 사용량 $O(n^2)$ $O(n^2)$ $O(mn)$ ($m \ll n$)
수렴 속도 초선형(Superlinear) 초선형(Superlinear) 선형 $\sim$ 초선형
계산 복잡도 높음 중간 낮음
안정성 낮음 높음 매우 높음

준뉴턴 방법에서 탐색 방향 $p_k$를 결정한 후, 어느 정도의 거리 $\alpha_k$만큼 이동할지를 결정하는 과정이 라인 서치입니다.

4.1 목적

단순히 $\alpha=1$을 사용하는 뉴턴 방법과 달리, 준뉴턴 방법은 목적 함수 $f(x_k + \alpha p_k)$가 충분히 감소하는 $\alpha$를 찾아 수렴 안정성을 보장해야 합니다.

4.2 울프 조건 (Wolfe Conditions)

단순 감소(Armijo condition)만으로는 부족하며, 보통 다음 두 가지 울프 조건을 만족하는 $\alpha$를 찾습니다. 여기서 $\nabla f(x_k)^T p_k$는 현재 지점에서 탐색 방향 $p_k$로의 방향 도함수(Directional Derivative)로, 함수가 감소하는 기울기 정도를 나타냅니다.

  1. 충분 감소 조건 (Sufficient Decrease): $$f(x_k + \alpha p_k) \le f(x_k) + c_1 \alpha \nabla f(x_k)^T p_k$$
  2. 이동 후의 함수값이 현재 값보다 일정 수준 이상 감소해야 함을 보장합니다.
  3. 곡률 조건 (Curvature Condition): $$\nabla f(x_k + \alpha p_k)^T p_k \ge c_2 \nabla f(x_k)^T p_k$$
  4. $\alpha$가 너무 작아지는 것을 방지하며, BFGS 업데이트 시 $s_k^T y_k > 0$을 보장하여 헤시안 근사 행렬의 양의 정치성(Positive Definiteness)을 유지하게 합니다.
  5. (단, $0 < c_1 < c_2 < 1$)

5. 알고리즘 구현 및 활용

5.1 최적화 루프 단계

  1. 그라디언트 계산: 현재 지점 $x_k$에서 $\nabla f(x_k)$를 구함.
  2. 방향 결정: $p_k = -H_k \nabla f(x_k)$ 계산 (L-BFGS의 경우 Two-loop recursion 사용).
  3. 라인 서치: 울프 조건을 만족하는 스텝 사이즈 $\alpha_k$ 결정.
  4. 업데이트: $x_{k+1} = x_k + \alpha_k p_k$ 및 $H_{k+1}$ (또는 $B_{k+1}$) 갱신.
  5. 종료 판정: $\|\nabla f(x_k)\| < \epsilon$ 이면 종료.

5.2 Python 구현 예시 (SciPy 활용)

Python의 scipy.optimize 라이브러리는 강력한 L-BFGS-B(Bound-constrained L-BFGS) 구현체를 제공합니다.

from scipy.optimize import minimize
import numpy as np

# 목적 함수 정의 (예: Rosenbrock 함수 - 최적해는 [1, 1])
def objective(x):
    return (1 - x[0])**2 + 100 * (x[1] - x[0]**2)**2

# 목적 함수의 그라디언트 정의 (제공 시 수렴 속도 및 정확도 향상)
def gradient(x):
    return np.array([
        -2 * (1 - x[0]) - 400 * x[0] * (x[1] - x[0]**2),
        200 * (x[1] - x[0]**2)
    ])

# 초기값 설정
x0 = np.array([0, 0])

# L-BFGS-B 알고리즘 적용
# jac=gradient를 통해 수치 미분이 아닌 분석적 미분값을 전달
res = minimize(objective, x0, method='L-BFGS-B', jac=gradient)

print(f"최적해: {res.x}")
print(f"함수 최솟값: {res.fun}")
print(f"반복 횟수: {res.nit}")

6. 수렴성 및 조건

6.1 수렴성 증명 및 조건

준뉴턴 방법의 수렴성은 목적 함수의 성질에 크게 의존합니다. - 강한 볼록 함수(Strongly Convex): 목적 함수가 강한 볼록성을 띠고 $\nabla f$가 립시츠 연속(Lipschitz continuous)일 때, BFGS는 적절한 라인 서치를 동반하면 초선형 수렴(Superlinear Convergence)함을 증명할 수 있습니다. - 양의 정치성 유지: $s_k^T y_k > 0$ 조건이 만족되면 $B_k$는 항상 양의 정치 행렬(Positive Definite Matrix)로 유지되며, 이는 탐색 방향 $p_k$가 항상 하강 방향(Descent Direction)임을 보장합니다.

7. 장단점 및 타 기법과의 비교

7.1 장단점

  • 장점:
    • 뉴턴 방법보다 계산 비용이 훨씬 저렴함 ($O(n^2)$ 또는 $O(mn)$).
    • 1차 미분 정보만으로 2차 곡률 정보를 모사하여 경사 하강법보다 빠르게 수렴함.
  • 단점:
    • 비볼록(Non-convex) 함수에서는 헤시안 근사치가 부정치(Indefinite)가 될 수 있어 수렴이 불안정함.
    • 메모리 사용량이 경사 하강법보다는 많음.

7.2 1차 최적화 기법과의 비교

비교 항목 경사 하강법 (GD) 모멘텀 / Adam 준뉴턴 (BFGS/L-BFGS)
사용 정보 1차 미분 1차 미분 + 이동 평균 1차 미분 $\rightarrow$ 2차 근사
수렴 속도 선형 (느림) 선형 $\sim$ 초선형 초선형 (빠름)
하이퍼파라미터 학습률 $\eta$ (민감) $\eta, \beta_1, \beta_2$ 라인 서치 파라미터 (덜 민감)
계산 비용 매우 낮음 낮음 중간 $\sim$ 높음
주요 용도 일반 최적화 딥러닝 (Stochastic) 공학 설계, 소규모/중규모 ML

분류: 기술 / 수치최적화 / 최적화 알고리즘

AI 생성 콘텐츠 안내

이 문서는 AI 모델(gemma-4-31b)에 의해 생성된 콘텐츠입니다.

주의사항: AI가 생성한 내용은 부정확하거나 편향된 정보를 포함할 수 있습니다. 중요한 결정을 내리기 전에 반드시 신뢰할 수 있는 출처를 통해 정보를 확인하시기 바랍니다.

이 AI 생성 콘텐츠가 도움이 되었나요?