CG·BFGS·Differential Evolution 최적화 알고리즘 선택과 운영
Conjugate Gradient, BFGS, Differential Evolution의 조건·비용·병렬성 차이와 최적화 운영 기준을 정리한다.
2026-08-14 · 최초 발행 2024-04-29
선택 기준은 목적함수의 성질과 평가 환경이다
수치 최적화는 모델 학습, 파라미터 추정, 설계 최적화처럼 데이터와 엔지니어링 전반에서 반복적으로 등장한다. CG, BFGS, DE는 같은 최적화 문제를 푸는 도구처럼 보이지만, 미분 가능성, 차원 수, 노이즈, 제약 조건, 병렬 자원에 따라 적합한 선택이 달라진다.
CG는 대규모 대칭 양의 정부호(SPD) 선형계와 여기서 유도되는 이차 목적함수 최소화에 적합하다. 기울기와 선형 결합해 헤시안 공액인 탐색 방향을 만들며, 선형 CG에는 유한 단계 수렴 이론이 있다. 비선형 CG는 선탐색(line search)과 결합해 일반 목적함수에도 적용할 수 있다.
BFGS는 준-뉴턴(quasi-Newton) 계열이다. 기울기 차이로 헤시안 역행렬을 점진적으로 근사하므로, 곡률 정보를 모두 보관하지 않고도 뉴턴급 수렴을 실용적으로 추구한다. 대용량 문제에서는 O(n) 메모리로 확장 가능한 제한 메모리 버전인 L-BFGS를 사용한다.
DE는 연속 공간을 대상으로 하는 전역 최적화용 진화 알고리즘이다. 해 집단에서 차분 기반 돌연변이, 교차, 선택을 반복한다. 미분이 어렵거나 잡음과 다봉성이 있는 문제에서 강건하게 해를 탐색할 수 있고, 개체 평가를 병렬화하기도 쉽다.
탐색 방향·곡률·집단을 다루는 방식
CG에서는 Fletcher–Reeves, Polak–Ribiere 등의 β 갱신식으로 공액 방향을 만든다. 방향 갱신 과정에서 수치 불안정이 누적되면 주기적인 리스타트를 고려한다. 단계 크기는 Wolfe/Strong Wolfe 조건을 만족하도록 선탐색으로 정한다. 지나치게 정확한 선탐색은 비용을 키우고, 너무 관대한 설정은 수렴을 늦출 수 있다. 대각·ILU 같은 전처리(preconditioning)는 조건수를 개선해 수렴을 가속하지만, 전처리 품질과 구축 비용 사이에는 트레이드오프가 있다.
BFGS에서는 sᵀy>0이라는 곡률 조건이 안정적인 업데이트의 기준이다. 조건이 깨지면 BFGS damping을 적용하거나 근사를 재설정한다. Wolfe 조건과 초기 헤시안 스케일링은 수렴 속도에 영향을 준다. 실무에서는 L-BFGS와 Strong Wolfe를 함께 사용하는 조합이 보편적이다. 일반 BFGS의 메모리·시간 복잡도는 O(n²)이고, L-BFGS는 m개 이력을 사용해 O(nm)으로 낮춘다.
DE는 DE/rand/1/bin, DE/best/1/bin, DE/current-to-best/1 등의 돌연변이 전략을 선택할 수 있다. F∈[0.4,0.9]는 다양성과 수렴성 사이의 균형을 조정하는 범위다. CR∈[0.5,0.9] 역시 탐색과 착취의 균형에 관여한다. 반사, 재표본, 클리핑 중 어떤 경계 처리 정책을 택하든 일관되게 적용해야 한다. 개선이 정체되면 adaptive F, CR이나 리셋 전략을 적용할 수 있다.
| 알고리즘 | 반복당 비용(계산/평가) | 메모리 | 수렴 특성 | 필요 조건 | 병렬성 | 노이즈 민감도 | 주 사용처 |
|---|---|---|---|---|---|---|---|
| CG | 1회 기울기 + 벡터 연산 | O(n) | 이차/볼록에 빠름, 비선형은 중간 | 미분 가능, 종종 SPD 근사 | 낮음 | 중간 | 대규모 이차/근사 볼록, 선형계 |
| BFGS | 1회 기울기 + 행렬-벡터 업데이트 | O(n²) (L-BFGS: O(nm)) | 준-뉴턴, 국소 수렴 빠름 | 미분 가능(연속), 곡률 양호 | 낮음 | 중간 | 매끄러운 비선형 최적화 |
| DE | 다수 함수 평가(집단 크기×전략) | O(pop×n) | 전역 탐색, 다봉에 강건 | 미분 불필요, 경계 필수 | 높음 | 낮음~중간 | 블랙박스/잡음/비미분 문제 |
문제 조건에서 알고리즘까지 이어지는 흐름
입력으로는 목적함수 f(x), 선택적인 ∇f(x), 경계·제약, 초기점 또는 초기 집단, 종료 기준(예: ||∇f||<ε, 예산 E< E_max)이 필요하다.
CG와 BFGS는 탐색 방향 dk를 만든 뒤 선탐색으로 α_k를 얻고, x{k+1}=x_k+α_k d_k로 갱신한다. 이후 수렴 여부와 곡률, 재시작 같은 안정성 조건을 검사한다. DE는 돌연변이 v_i와 교차 결과 u_i를 만들고, 선택을 통해 다음 세대 집단을 구성한다. 이때 수렴과 다양성도 함께 확인한다.
출력에는 최적 추정치 x*, 목적값, 반복 수, 평가 횟수와 함께 조건수, 곡률 위반, 정체 구간 같은 진단 정보를 남긴다.
문제 유형별 적용 방식
정규화된 최소제곱이나 PDE 역문제의 선형화 스텝처럼 대규모 선형·이차 구조가 강한 문제에는 전처리 CG를 적용할 수 있다. 금융 파라미터 추정, 로보틱스 보정, 로지스틱 회귀 대규모 학습처럼 매끄러운 비선형 캘리브레이션에는 L-BFGS와 Strong Wolfe 조합이 맞는다.
시뮬레이션 기반 설계(컴퓨테이셔널 플루이드, RF 튜닝), 하이퍼파라미터 튜닝, 재료 탐색처럼 블랙박스이거나 잡음이 있는 환경은 DE 병렬화의 대상이다. 전역 탐색은 DE로 수행하고, 이후 L-BFGS로 국소 정밀화를 진행하는 혼성 최적화 파이프라인도 사용할 수 있다.
L-BFGS와 CG는 O(n) 메모리를 달성해 수백만 차원에서도 실용적으로 운영할 수 있다. BFGS는 준-뉴턴 특성으로 기울기 하강 대비 수렴 반복 수가 3~10배 감소할 수 있으며, 이는 문제에 의존한다. DE는 비미분·노이즈 문제에서 지역해 탈출 확률을 높이고 병렬 자원을 사용할 때 시간 단축이 비례한다. DE의 F, CR, popsize처럼 파라미터 수가 적어 튜닝 공간을 제한할 수 있으며, 자동 선탐색은 실무 안정성을 높인다.
실행 가능한 Python 예제
전제조건: Python 3.10+, numpy, scipy>=1.11
# pip install numpy scipy
import numpy as np
from scipy.optimize import minimize, differential_evolution
# Rosenbrock 함수(매끄러운 비선형)
def rosen(x):
x = np.asarray(x)
return np.sum(100.0*(x[1:]-x[:-1]**2.0)**2.0 + (1-x[:-1])**2.0)
def rosen_grad(x):
x = np.asarray(x)
grad = np.zeros_like(x)
grad[0:-1] = -400*x[0:-1]*(x[1:]-x[0:-1]**2) - 2*(1-x[0:-1])
grad[1:] += 200*(x[1:]-x[0:-1]**2)
return grad
x0 = np.array([-1.2, 1.0, 0.5, -0.5])
# 1) L-BFGS-B (박스 제약 가능)
res_bfgs = minimize(rosen, x0, jac=rosen_grad, method="L-BFGS-B",
options=dict(gtol=1e-6, maxiter=500))
print("L-BFGS-B:", res_bfgs.nit, res_bfgs.fun)
# 2) 비선형 CG + Strong Wolfe
res_cg = minimize(rosen, x0, jac=rosen_grad, method="CG",
options=dict(gtol=1e-6, maxiter=2000))
print("CG:", res_cg.nit, res_cg.fun)
# 3) Differential Evolution (경계 필수)
bounds = [(-2, 2)] * 4
res_de = differential_evolution(rosen, bounds, maxiter=2000, popsize=20,
mutation=(0.5, 0.9), recombination=0.7,
tol=1e-7, workers=-1) # 병렬
print("DE:", res_de.nit, res_de.fun)BFGS/L-BFGS에서는 Strong Wolfe 선탐색이 기본 옵션으로 내장되어 있다. gtol을 지나치게 작게 잡으면 선탐색 반복이 늘어 속도가 떨어질 수 있다. DE는 popsize≈10~20×차원을 권장하며, 평가 비용이 높을수록 workers 병렬 사용이 적합하다. 경계는 박스로 지정해야 한다.
실패 징후를 로그에서 다루기
선탐색이 최대 반복 횟수를 넘겨 실패하면 보수적인 스텝을 재시도하거나 탐색 방향을 다시 계산한다. BFGS에서 sᵀy≤0으로 곡률 조건이 위반되면 댐핑을 적용하고, 헤시안 근사를 I 스케일링으로 재설정하거나 더 강한 선탐색을 사용한다.
DE가 정체되면 jDE, SaDE 같은 적응형 파라미터, 전략 혼합, 집단 리샘플링 또는 노이즈 주입을 검토한다. 경계는 반사 또는 재표본을 일관되게 처리한다. 클리핑만 사용하면 경계 부근 바이어스를 주의해야 한다.
CG에서는 대각·ILU 전처리로 반복 수를 절반 이하로 낮출 수 있지만, 전처리 구축 비용과 반복 절감 이득을 비교해야 한다. 리스타트 주기는 n 또는 50 같은 기준으로 설정한다. L-BFGS는 m=10~20 이력으로 대규모 문제를 처리할 수 있으며, m을 늘리면 수렴은 빨라질 수 있지만 메모리와 연산도 증가한다. DE/rand/1/bin은 강건하고 DE/best/1/bin은 빠르게 수렴할 수 있으나 조기 수렴 위험이 있다. F↑, CR↓는 탐색을 넓히는 대신 속도를 낮추고, F↓, CR↑는 수렴을 가속하는 대신 지역해 위험을 높인다.
기울기를 쓸 수 있는 고차원 문제라면 L-BFGS를 먼저 검토하고, 이차 구조가 강하면 전처리 CG를 병용한다. 기울기를 사용할 수 없고 잡음이나 비미분성이 있으면 DE를 우선 적용한 뒤 L-BFGS로 국소 정밀화를 수행한다. 공통적으로는 동등한 평가 예산에서 알고리즘을 여러 번 실행하고 로그를 비교해 재현성과 강건성을 확인하며, 랜덤 시드를 관리한다.