길리랩blog

BFGS와 비선형 공액기울기: 대규모 미분 가능 최적화 선택법

BFGS와 비선형 공액기울기의 방향 계산, 선형탐색, 안정화 전략을 바탕으로 대규모 미분 가능 최적화 문제의 선택 기준을 정리한다.

2026-08-14 · 최초 발행 2024-04-29

Hessian을 직접 다루지 않는 경로

대규모 연속 최적화에서는 Hessian을 직접 계산하는 비용이 빠르게 부담이 된다. BFGS와 Conjugate Gradient(CG)는 선형탐색을 통해 스텝 크기를 정하면서, 경사 정보로 다음 탐색 방향을 구성한다.

BFGS는 목적함수 (f(x))의 곡률을 Hessian 근사로 대신한다. 역헤시안 근사 (H_k)를 반복마다 갱신하고, 이를 사용해 뉴턴 방향에 가까운 탐색 방향을 얻는다.

(s_k = x_{k+1} - x_k), (y_k = g_{k+1} - g_k), (\rho_k = 1/(y^T s))로 두면 업데이트는 다음과 같다.

[ H_{k+1} = (I - \rho_k s y^T) H_k (I - \rho_k y s^T) + \rho_k s s^T ]

이 갱신에는 (s^T y > 0)이라는 곡률 조건이 필요하다.

CG는 공액 방향을 이용한다. 선형 CG는 대칭 양정치(SPD) 선형계 (Ax=b)를 이상적 조건에서 (n)번 이내에 푼다. 일반 비선형 함수에 적용하는 NCG는 (p_0=-g_0)에서 출발하며, 이후 다음 방향을 계산한다.

[ p_{k+1} = -g_{k+1} + \beta_k p_k ]

(\beta_k)에는 FR, PR+, HS 등의 변형을 쓸 수 있다. 강한 Wolfe 조건을 만족하는 선형탐색은 이 과정의 수렴 안정성을 뒷받침한다.

탐색 방향과 스텝이 만나는 지점

BFGS의 방향은 (p_k=-H_k g_k)로 계산된다. 곡률이 강한 문제에서도 뉴턴 방향을 근사하므로 초선형(superlinear) 수렴 경향을 보인다.

NCG는 이전 방향에 담긴 정보를 공액성으로 이어 간다. 메모리 사용량이 O(n)이어서 변수 수가 매우 큰 문제에 적합하다.

두 방법 모두 방향만으로는 충분하지 않다. 선형탐색은 방향 위에서 스텝 크기 (\alpha)를 정하며, Armijo의 충분 감소 조건과 곡률 조건을 조합한 Wolfe 또는 Strong-Wolfe 조건을 사용한다. Strong Wolfe 조건은 다음과 같다.

[ |g(x_k + \alpha p_k)^T p_k| \le c_2 |g_k^T p_k| ]

이 조건은 과도한 스텝을 막고 공액성 유지에도 도움을 준다. 조건을 만족하지 못하면 백트래킹, 구간 축소, 보간을 적용한다. 초기 (\alpha_0)는 Barzilai–Borwein 추정으로 잡거나 1.0으로 고정한 뒤 백트래킹할 수 있으며, 선형탐색을 비활성화하지 않는다.

스케일이 맞지 않거나 반복이 흔들릴 때

BFGS는 초기 (H_0)의 스케일이 맞지 않으면 수렴이 지연될 수 있다. 이때 (\gamma I) 형태로 초기화하고, (\gamma=(s^T y)/(y^T y))를 사용할 수 있다.

CG에서는 사전조건화가 중요한 선택지가 된다. (M \approx A^{-1})를 적용하는 PCG는 조건수를 개선한다. 비선형 문제에서 이 접근이 맞지 않으면 L-BFGS로 전환하는 방법도 있다.

곡률 조건이 깨지는 BFGS 반복에서는 (s^T y \le 0)을 감지해야 한다. Powell-damped BFGS를 적용하거나 (H_k)를 (I) 스케일로 리셋한다.

NCG는 (\beta_k < 0), (k \bmod n = 0), 또는 (g_{k+1}^T g_k \approx 0)일 때 (p_k=-g_{k+1})로 재시작할 수 있다. 이는 수렴성과 견고성을 높이기 위한 장치다.

문제 성격에 따른 적용 범위

대규모 로지스틱 회귀나 선형모형 학습에서는 정규화를 포함한 목적함수가 매끄러울 때 BFGS/L-BFGS가 빠르게 수렴한다. 피처 수가 (10^5) 이상이면 L-BFGS를 권장한다. 메모리 제약이 있는 환경에서는 NCG가 유용하지만, 배치와 미니배치를 섞으면 그라디언트 잡음을 완화해야 한다.

공학·과학 계산에서는 선형 CG가 유한요소법(FEM)의 SPD 선형계를 푸는 데 쓰인다. 불완전 Cholesky 또는 Multigrid 사전조건화를 함께 적용할 수 있다. 비선형 역문제에서는 NCG로 초기 근사를 찾고 BFGS로 정밀 수렴을 이어 가는 하이브리드 전략도 가능하다.

임베디드와 고성능 컴퓨팅(HPC)에서는 메모리 예산이 제한될 때 NCG를 우선 고려한다. 분산 환경에서는 L-BFGS가 통신 비용을 최소화하는 장점이 있다.

계산 비용과 수렴 특성 비교

항목 BFGS Nonlinear CG
시간복잡도(스텝당) O(n^2) O(n)
메모리 사용 O(n^2), L-BFGS는 O(nm) O(n)
수렴률 초선형(일반적) 선형(일반적)
확장성(n > 1e5) L-BFGS 권장 적합
잡음 민감도 낮음(평활화 효과) 높음(재시작 필요)
튜닝 난이도 낮음~중간 중간(β, 재시작, line search)

BFGS는 스텝당 O(n^2) 메모리와 O(n^2) 연산을 사용하지만 Hessian 계산 비용을 없앤다. NCG는 O(n) 메모리와 O(n)~O(n + cost_grad) 연산/스텝으로 초대규모 문제에 맞는다.

표준 가정 아래 BFGS는 초선형 수렴하며, 실무에서는 뉴턴-선형해결과 비교해 경쟁력을 확보한다. NCG는 적절한 (\beta)와 강한 Wolfe 조건에서 견고한 선형 수렴을 보이고, 사전조건화를 적용하면 반복 수를 크게 줄일 수 있다. 선형탐색과 재시작 또는 댐핑을 갖추면 실패율을 낮추고, 튜닝 변수 수도 제한할 수 있다.

반복 상태를 점검하는 흐름

⤢✕예아니오BFGSNCGBFGS: sTy ≤ 0NCG: βk < 0 또는 주기실패/미충족입력: f(x), ∇f(x), x0, tol,maxiter, method ∈ {BFGS,NCG}수렴 검사: ||∇f(xk)|| ≤ tol출력: x*, f(x*), 상태코드탐색 방향 계산pk = -Hk gkβk 계산(PR+/FR/HS), pk =-gk + βk pk-1선형탐색: Strong Wolfe 만족αk 탐색xk+1 = xk + αk pk그라디언트 갱신: gk+1안정화댐핑/리셋 Hk재시작 pk = -gk+1상태 업데이트(Hk+1)백트래킹/보간, 허용 반복 초과시 종료 코드

운영 설정에서 확인할 항목

피처 스케일은 표준화나 최대-최소 정규화로 맞춘다. 이는 BFGS의 초기 (H_0) 스케일을 안정화하는 데도 연결된다.

선형탐색은 Strong Wolfe((c_1\approx1e-4), (c_2\approx0.9))를 사용한다. 탐색이 실패하면 (\alpha \leftarrow \alpha\cdot\tau), (\tau\in(0,1)) 방식으로 백트래킹한다.

BFGS에서는 Powell-damped BFGS로 (s^T y>0)을 보장하고, NaN 또는 Inf가 발생하면 (H_k)를 리셋한다. NCG에서는 PR+를 사용해 (\beta=\max(0,\beta_{PR}))로 두고, (k \bmod n=0)에서 재시작한다.

종료 여부는 (||g_k||\infty \le gtol), 상대 함수 감소 (|f{k+1}-f_k|/\max(1,|f_k|)\le ftol), 반복 상한을 함께 본다.

SciPy에서 BFGS와 NCG 실행하기

전제조건: Python 3.10+, numpy, scipy>=1.10 설치

# python -m pip install numpy scipy
import numpy as np
from scipy.optimize import minimize

def rosenbrock(x):
    # f(x, y) = 100(y - x^2)^2 + (1 - x)^2
    return 100.0*(x[1] - x[0]**2)**2 + (1.0 - x[0])**2

def rosenbrock_grad(x):
    df_dx = -400*x[0]*(x[1] - x[0]**2) - 2*(1 - x[0])
    df_dy = 200*(x[1] - x[0]**2)
    return np.array([df_dx, df_dy])

x0 = np.array([-1.2, 1.0])

# BFGS
res_bfgs = minimize(
    rosenbrock, x0, method='BFGS', jac=rosenbrock_grad,
    options=dict(gtol=1e-8, maxiter=1000, disp=False)
)
print("BFGS:", res_bfgs.nit, "iters,", "f*=", res_bfgs.fun, ", x*=", res_bfgs.x)

# Nonlinear Conjugate Gradient (FR by default in SciPy)
res_cg = minimize(
    rosenbrock, x0, method='CG', jac=rosenbrock_grad,
    options=dict(gtol=1e-8, maxiter=5000, disp=False)
)
print("CG:", res_cg.nit, "iters,", "f*=", res_cg.fun, ", x*=", res_cg.x)

gtol은 그라디언트 정지 기준으로 1e-6~1e-8을 권장한다. maxiter는 BFGS 10^3, CG 10^4 수준에서 시작한다. SciPy는 강한 Wolfe 기반의 내부 선형탐색을 사용하며, 실패 시 경고를 처리하고 초기값을 조정한다.

각 방법의 반복 구성

BFGS는 다음 순서로 진행한다.

  1. (g_k)를 계산하고 수렴을 검사한다.
  2. (p_k=-H_k g_k)를 구한 뒤 Strong Wolfe 선형탐색으로 (\alpha_k)를 찾는다.
  3. (x_{k+1}=x_k+\alpha_k p_k)를 계산하고 (s_k)와 (y_k)를 검증한다.
  4. 댐핑 또는 리셋 뒤 (H_{k+1})를 갱신하고 반복한다.

Nonlinear CG는 (p_0=-g_0)에서 시작한다. 선형탐색으로 업데이트한 뒤 (\beta_k=\max(0,\beta_{PR})) 또는 (\beta_{FR})을 선택한다. 이어서 (p_{k+1}=-g_{k+1}+\beta_k p_k)를 계산하고 주기적으로 재시작한다.

선택은 메모리와 잡음 특성에서 갈린다

BFGS는 견고한 수렴, 잡음 내성, 비교적 쉬운 튜닝이 장점이다. 반면 O(n^2) 메모리와 시간이 필요하므로 초대규모 문제에는 맞지 않으며, L-BFGS로 보완한다.

NCG는 O(n) 메모리로 대규모 문제를 다룰 수 있고 Hessian 근사가 필요 없다. 대신 선형탐색과 (\beta) 선택에 민감하며 잡음에 약하다. 재시작과 사전조건화가 그 약점을 보완한다.

매끄러운 중규모 문제에서는 BFGS/L-BFGS가 빠른 수렴을 제공한다. 초대규모 문제나 메모리 제약 환경에서는 NCG가 실용적인 해법이 된다. 어느 쪽이든 선형탐색, 댐핑 또는 재시작, 종료 기준을 함께 운영해야 한다.

BFGS공액기울기최적화선형탐색사전조건화수치해석