수치 최적화

1차원 최소화: 황금 분할 탐색과 포물선 보간

근은 부호가 바뀌는 두 점이면 가둬지지만, 최솟값은 세 점이 필요합니다. $a \lt c \lt b$이고 $f(c) \lt f(a)$, $f(c) \lt f(b)$이면 연속함수의 최솟값은 $(a, b)$ 안에 있습니다. 가운데가 양 끝보다 낮은 "골짜기 모양"이기 때문입니다.

두 내부 점을 비교할 때마다 구간의 일부를 버립니다. 남는 점 하나는 다음 단계에서 다시 쓰고 싶습니다. 그러면 단계마다 $f$를 한 번만 새로 계산하면 됩니다. 구간 길이를 1로 두고 내부 점을 $c = 1 - \tau$, $d = \tau$에 놓았다고 합시다. $[0, \tau]$가 남으면 옛 $c = 1 - \tau$가 새 구간의 $d$ 자리 $\tau\cdot\tau$에 와야 하므로 $1 - \tau = \tau^2$, 곧

function golden(f, a, b, tol)
  t = (sqrt(5) - 1) / 2                // 0.618...
  c = b - t*(b - a);  fc = f(c)
  d = a + t*(b - a);  fd = f(d)
  while b - a > tol
    if fc < fd then                   // 최소는 [a, d]
      b = d;  d = c;  fd = fc
      c = b - t*(b - a);  fc = f(c)
    else                               // 최소는 [c, b]
      a = c;  c = d;  fc = fd
      d = a + t*(b - a);  fd = f(d)
  return (a + b) / 2

황금 분할은 안전하지만 1차 수렴이라 느립니다. 함수가 매끄러우면 더 좋은 길이 있습니다. 세 점 $(x_0, f_0)$, $(x_1, f_1)$, $(x_2, f_2)$를 지나는 포물선을 그리고 그 꼭짓점으로 건너뛰는 포물선 보간(successive parabolic interpolation)입니다.

예제 15.1의 함수에 $x = 0, 1, 2$에서 출발해 적용하면 오차가 $9.8\times10^{-2}$, $3.7\times10^{-2}$, $1.2\times10^{-2}$, $4.8\times10^{-4}$, $7.6\times10^{-5}$, $1.1\times10^{-6}$, $5.9\times10^{-9}$, $1.3\times10^{-10}$으로 줄어듭니다. 여덟 번에 황금 분할의 서른 번 이상보다 정확합니다. 수렴 차수는 $p^3 = p + 1$의 실근 $p \approx 1.3247$로 알려진 초선형입니다. 그 대신 포물선이 위로 볼록하거나 세 점이 거의 일직선이면 엉뚱한 곳으로 뛰거나 분모가 0이 됩니다. 그래서 실무의 브렌트 방법(Brent's method)은 최소 가둠 구간을 늘 유지하면서, 포물선 걸음이 구간 안에 떨어지고 충분히 줄어들 때만 받아들이고 그렇지 않으면 황금 분할 걸음을 씁니다. 3장의 브렌트 근 찾기와 같은 "빠른 방법 + 안전망" 설계입니다. SciPy의 minimize_scalar와 MATLAB의 fminbnd가 이 방식입니다.

경사 하강과 직선 탐색: 아르미호 조건

일반적인 반복은 $\mathbf x_{k+1} = \mathbf x_k + \alpha_k\mathbf p_k$입니다. $\mathbf p_k$는 방향, $\alpha_k > 0$은 걸음 크기입니다. $\nabla f_k^{\mathsf T}\mathbf p_k \lt 0$이면 $\mathbf p_k$를 하강 방향(descent direction)이라 합니다. 테일러 전개 $f(\mathbf x_k + \alpha\mathbf p_k) = f(\mathbf x_k) + \alpha\nabla f_k^{\mathsf T}\mathbf p_k + O(\alpha^2)$에서 충분히 작은 $\alpha$는 반드시 $f$를 줄입니다. 경사 하강(gradient descent)은 $\mathbf p_k = -\nabla f_k$를 씁니다.

걸음 크기는 1변수 함수 $\varphi(\alpha) = f(\mathbf x_k + \alpha\mathbf p_k)$를 줄이는 1차원 문제, 곧 직선 탐색(line search)입니다. 앞 절의 방법으로 $\varphi$를 정확히 최소화할 수도 있지만 그것은 낭비입니다. 우리가 원하는 것은 충분히 줄이는 것뿐입니다.

function backtrack(f, x, p, g, c = 1e-4, rho = 0.5)
  alpha = 1;  fx = f(x);  slope = dot(g, p)   // slope < 0 이어야 한다
  while f(x + alpha*p) > fx + c*alpha*slope
    alpha = rho * alpha
  return alpha

function gradient_descent(f, grad, x, tol)
  while norm(grad(x)) > tol
    g = grad(x);  p = -g
    x = x + backtrack(f, x, p, g) * p
  return x

아르미호 조건은 "너무 긴 걸음"만 막습니다. "너무 짧은 걸음"은 되돌아가기가 $\alpha = 1$에서 출발해 필요한 만큼만 줄이는 것으로 막습니다. 준뉴턴 방법처럼 $\alpha = 1$이 자연스러운 방법에는 기울기 조건 $\nabla f(\mathbf x_k + \alpha\mathbf p_k)^{\mathsf T}\mathbf p_k \ge c_2\nabla f_k^{\mathsf T}\mathbf p_k$($c \lt c_2 \lt 1$)를 더한 울프 조건(Wolfe conditions)을 씁니다. 이 두 조건만으로 다음이 보장됩니다.

정리는 정류점($\nabla f = \mathbf 0$)으로 간다는 것만 말합니다. 그것이 최솟값인지, 얼마나 빨리 가는지는 말하지 않습니다. 속도는 함수의 모양, 정확히는 헤세 행렬의 조건수가 정합니다.

조건수와 지그재그, 그리고 모멘텀

최솟값 근처의 매끄러운 함수는 이차 함수 $f(\mathbf x) = \frac12\mathbf x^{\mathsf T}A\mathbf x$($A$는 대칭 양정치)처럼 보입니다. 고유값을 $0 \lt \mu = \lambda_{\min} \le \dots \le \lambda_{\max} = L$이라 하고 조건수 $\kappa = L/\mu$를 둡니다(12장의 행렬 조건수와 같은 양). 등고선은 축 길이 비가 $\sqrt\kappa$인 타원입니다.

$\kappa = 100$이면 수렴률은 $99/101 = 0.980$이고, 오차를 $10^{-6}$배로 줄이려면 $\ln 10^{-6}/\ln 0.980 = 691$걸음이 필요합니다. $\kappa$에 비례하는 걸음 수입니다. 정확한 직선 탐색도 소용없습니다. 걸음마다 그 방향으로는 최소가 되므로 다음 기울기는 지금 방향에 수직이고, 경로는 직각으로 꺾이는 지그재그가 됩니다.

지그재그를 줄이는 오래된 처방은 관성입니다. 언덕을 구르는 무거운 공은 가파른 벽 사이를 오가는 성분은 서로 상쇄하고, 골짜기를 따라 일정하게 미는 성분은 쌓아 갑니다.

네스테로프(Yurii Nesterov)의 가속 경사법은 기울기를 "모멘텀으로 미리 가 본 점"에서 재는 변형으로, 이차 함수가 아닌 볼록 함수에서도 비슷한 가속을 보장합니다. 딥러닝 옵티마이저의 momentum=0.9가 이 $\beta$입니다. 다만 $\beta$를 너무 크게 두면 공이 골짜기 바닥을 지나쳐 오래 출렁입니다.

뉴턴 방법과 헤세 행렬

$\mathbf x_k$ 근처의 2차 테일러 근사 $m(\mathbf p) = f_k + \nabla f_k^{\mathsf T}\mathbf p + \frac12\mathbf p^{\mathsf T}\nabla^2 f_k\,\mathbf p$를 최소화하면 $\nabla^2 f_k\,\mathbf p = -\nabla f_k$입니다. $\nabla^2 f$는 2계 편도함수의 행렬, 곧 헤세 행렬(Hessian)입니다(CalculusBook 15장: 임계점 판정).

대가는 둘입니다. 첫째, 헤세 행렬을 계산하고 $n\times n$ 연립방정식을 풀어야 하므로 한 걸음에 약 $n^3/3$번(촐레스키, 12장)의 연산이 듭니다. 둘째, 헤세 행렬이 양정치가 아니면 이차 근사에 최솟값이 없고, $\mathbf p_k$가 오르막이나 안장점 쪽을 가리킬 수 있습니다. 그래서 실무의 뉴턴 방법은 직선 탐색을 붙이고, $\nabla^2 f_k$가 양정치가 아니면 $\nabla^2 f_k + \tau I$처럼 대각을 키워 양정치로 만듭니다(수정 뉴턴). 큰 $\tau$에서는 걸음이 $-\nabla f/\tau$, 곧 짧은 경사 하강이 됩니다.

준뉴턴 방법: BFGS

1차원에서 $f''(x_{k+1}) \approx (f'_{k+1} - f'_k)/(x_{k+1} - x_k)$, 곧 할선 기울기입니다(3장의 할선법). 다변수에서 $\mathbf s_k = \mathbf x_{k+1} - \mathbf x_k$, $\mathbf y_k = \nabla f_{k+1} - \nabla f_k$라 하면 헤세 행렬의 근삿값 $B_{k+1}$에 대해 할선 조건 $B_{k+1}\mathbf s_k = \mathbf y_k$를 요구합니다. 방정식은 $n$개인데 미지수는 $n(n+1)/2$개이므로, 지금의 $B_k$에서 가장 조금 바꾸는 것을 고릅니다. 4장의 브로이든 방법도 같은 생각이었습니다. 최적화에서 가장 성공한 공식은 1970년에 브로이든, 플레처, 골드파브, 샤노(Broyden, Fletcher, Goldfarb, Shanno)가 각각 발표한 BFGS 갱신입니다.

function bfgs(f, grad, x, tol)
  H = I;  g = grad(x)
  while norm(g) > tol
    p = -H * g
    alpha = line_search(f, x, p, g)      // 울프 조건, 처음 시도는 alpha = 1
    s = alpha * p;  x = x + s
    g_new = grad(x);  y = g_new - g;  g = g_new
    if dot(y, s) > 0 then                // 곡률 조건이 깨지면 갱신을 건너뛴다
      r = 1 / dot(y, s)
      H = (I - r*s*y') * H * (I - r*y*s') + r*s*s'
  return x

변수가 수만 개 이상이면 $n\times n$ 행렬 $H$를 저장하는 것조차 부담입니다. L-BFGS(limited-memory BFGS)는 최근 $m$개(흔히 5~20)의 $(\mathbf s, \mathbf y)$ 쌍만 저장하고 $H\nabla f$를 두 번의 루프로 직접 계산합니다. 메모리와 연산이 $O(mn)$이라, 기상 자료 동화나 큰 회귀 모델처럼 변수가 수백만 개인 문제의 표준입니다.

표는 이 장의 스크립트로 직접 센 값입니다. BFGS는 헤세 행렬 없이 뉴턴의 두 배 안쪽 걸음으로 끝납니다. 처음 몇 걸음은 $H_0 = I$라 경사 하강처럼 걷다가, 곡률을 배워 가며 걸음이 길어지고 끝에서는 뉴턴처럼 빠르게 수렴합니다. 아래 시뮬레이터에서 출발점을 끌어 세 방법의 경로를 비교하세요.

도함수 없는 방법: 넬더–미드 심플렉스

1965년 넬더와 미드(John Nelder, Roger Mead)가 발표한 방법은 $n$차원에서 꼭짓점 $n + 1$개의 심플렉스(2차원에서는 삼각형)를 굴립니다. 가장 나쁜 꼭짓점을 나머지의 무게중심 반대편으로 뒤집고, 그쪽이 좋으면 더 늘리고, 나쁘면 줄입니다. 삼각형이 골짜기를 따라 아메바처럼 기어가다 바닥에서 오그라듭니다.

넬더–미드는 단순하고 잡음에 강해서 지금도 MATLAB의 fminsearch와 SciPy의 method="Nelder-Mead"로 널리 쓰입니다. 그러나 이론적 보장이 약합니다. 맥키넌(K. McKinnon)은 1998년에 2변수의 매끄러운 볼록 함수에서도 심플렉스가 최소점이 아닌 점으로 오그라드는 예를 보였습니다. 차원이 커지면($n \gtrsim 10$) 매우 느려지기도 합니다. 그래서 도함수 없는 최적화의 현대적 방법(패턴 탐색, 대리 모델 기반 방법)은 수렴이 증명된 규칙을 쓰고, 넬더–미드는 "변수 몇 개, 기울기 없음, 빨리 대충"에 쓰는 도구로 남았습니다. 실패하면 다시 시작(재시작)하는 것이 흔한 처방입니다.

비선형 최소제곱: 가우스–뉴턴과 레벤버그–마쿼트

잔차 벡터 $\mathbf r(\boldsymbol\beta)$, $r_i = m(t_i; \boldsymbol\beta) - y_i$와 그 야코비안 $J_{ij} = \partial r_i/\partial\beta_j$를 두면 $S = \|\mathbf r\|^2$의 기울기는 $2J^{\mathsf T}\mathbf r$, 헤세 행렬은 $2J^{\mathsf T}J + 2\sum_i r_i\nabla^2 r_i$입니다. 맞춤이 좋으면 잔차 $r_i$가 작으므로 둘째 항을 버릴 수 있습니다. 2계 도함수 없이 뉴턴 방법을 흉내 내는 셈입니다.

$\lambda \to 0$이면 가우스–뉴턴(빠르지만 무모함), $\lambda$가 크면 $\boldsymbol\delta \approx -J^{\mathsf T}\mathbf r/\lambda$(조심스러운 짧은 경사 하강)입니다. 레벤버그(Kenneth Levenberg, 1944)는 $\lambda I$를, 마쿼트(Donald Marquardt, 1963)는 변수의 단위에 맞춰 대각 성분을 늘리는 $\lambda\operatorname{diag}$를 제안했습니다. 이것은 "이차 근사를 믿을 수 있는 반경 안에서만 걷는다"는 신뢰 영역(trust region) 방법의 원조이기도 합니다. $\lambda$는 그 반경의 역수 구실을 합니다.

제약 최적화: 벌칙법, 라그랑주 승수, KKT 조건

문제를 $\min f(\mathbf x)$, 등식 제약 $h_j(\mathbf x) = 0$, 부등식 제약 $g_i(\mathbf x) \le 0$으로 씁니다. 가장 단순한 길은 벌칙법(penalty method)입니다.

최적점에서는 $f$의 등고선이 제약 곡면에 접합니다. 그렇지 않다면 제약면을 따라 조금 움직여 $f$를 더 줄일 수 있기 때문입니다. 접한다는 것은 두 기울기가 평행하다는 뜻, 곧 라그랑주 승수(Lagrange multiplier) 조건 $\nabla f + \lambda\nabla h = \mathbf 0$입니다(CalculusBook 15장: 라그랑주 승수). 부등식이 섞이면 이것이 다음과 같이 확장됩니다.

이 병을 고친 것이 증강 라그랑주 방법(augmented Lagrangian)입니다. $Q$에 승수 항 $\lambda h$를 더해 두고, 매 단계 $\lambda \leftarrow \lambda + \mu h(\mathbf x)$로 승수를 고치면 $\mu$를 무한히 키우지 않아도 정확한 답에 갑니다. 반대 방향의 장벽법(내점법)은 $-\mu\sum\log(-g_i)$를 더해 안쪽에서 벽에 다가가며, 선형·이차 계획법의 대규모 해법이 이 계열입니다. 부등식 예: $\min(x - 2)^2 + (y - 1)^2$, $g = x + y - 1 \le 0$의 답은 $(2, 1)$을 직선에 수직으로 내린 $(1, 0)$이고 $\nabla f = (-2, -2)$이므로 $\nabla f + \mu\nabla g = \mathbf 0$에서 $\mu = 2 \ge 0$. 제약이 걸려 있고 승수가 양수, KKT를 만족합니다.

확률적 경사 하강: 데이터가 너무 많을 때

$\mathbf g_k$는 참 기울기의 불편 추정량입니다: $\mathbb E[\mathbf g_k] = \nabla F(\mathbf w_k)$. 그 분산은 데이터별 기울기의 분산 $\sigma^2$에 대해 약 $\sigma^2/B$입니다(복원 추출). 그래서 배치를 4배로 늘리면 잡음의 표준편차가 절반이 되지만 비용은 4배입니다. 잡음 때문에 SGD는 고정 걸음으로는 최소점에 멈추지 못하고, 걸음 크기에 비례하는 반경 안에서 계속 흔들립니다. 정확히 수렴시키려면 걸음을 줄여야 하고, 로빈스–먼로(Robbins–Monro) 조건 $\sum\alpha_k = \infty$, $\sum\alpha_k^2 \lt \infty$(예: $\alpha_k \propto 1/k$)가 표준적인 충분조건입니다. 첫 조건은 어디든 갈 수 있을 만큼 걷는다는 것, 둘째는 잡음의 누적이 유한하다는 것입니다.

실무에서 SGD가 이기는 이유는 비용 계산에 있습니다. 데이터에 중복이 많으면(비슷한 사진이 많으면) 작은 배치의 기울기도 이미 좋은 방향이고, 같은 계산량으로 훨씬 많은 걸음을 걷습니다. 딥러닝에서는 모멘텀과 좌표별 걸음 크기 조절을 합친 Adam 같은 변형이 표준이며, 걸음 크기 일정(learning rate schedule)을 조절하는 것이 학습의 중요한 기술입니다.

국소 최솟값과 전역 최적화: 담금질 기법

볼록 함수에서는 모든 국소 최솟값이 전역 최솟값이라 이 걱정이 없습니다(선형·이차 계획법, 최소제곱이 여기에 속합니다). 볼록이 아니면 전역 최솟값을 보장하는 일반적인 효율적 방법은 없다고 보는 것이 안전합니다. 실무의 처방은 여러 출발점(다중 시작)에서 국소 방법을 돌려 가장 좋은 것을 고르거나, 무작위성을 일부러 넣는 것입니다. 후자의 대표가 금속을 천천히 식혀 결정 결함을 없애는 열처리에서 이름을 딴 담금질 기법(simulated annealing)입니다. 1983년 커크패트릭, 겔라트, 베키(Kirkpatrick, Gelatt, Vecchi)가 최적화에 쓰면서 널리 알려졌습니다.

뜨거울 때($T$가 클 때)는 거의 모든 오르막을 받아들여 넓게 돌아다니고, 식으면 내리막만 받는 국소 탐색이 됩니다. 높이 1의 언덕을 넘을 확률은 $T = 1$에서 $e^{-1} = 0.368$, $T = 0.1$에서 $e^{-10} = 4.5\times10^{-5}$입니다. 그래서 얕은 골짜기에서는 일찍 빠져나오고, 깊은 골짜기에 머무는 시간이 상대적으로 길어집니다. 이론적으로는 $T_k \propto 1/\log k$처럼 아주 느리게 식히면 전역 최솟값에 확률 1로 간다는 결과가 있지만, 그 속도는 실용적이지 않습니다. 실무에서는 등비 냉각과 재가열을 섞어 쓰고, 결과를 "보장된 최적"이 아니라 "좋은 해"로 받아들입니다. 유전 알고리즘, 입자 군집 최적화, 베이즈 최적화도 같은 문제를 다른 방식으로 다룹니다.

이 도구가 쓰이는 곳

어떤 최적화 방법을 고를지는 문제의 네 가지 성질, 곧 도함수가 있는가, 변수가 몇 개인가, 제약이 있는가, 볼록인가로 대부분 정해집니다.