번들법

1. 개요[편집]

번들법 Bundle Method
대상	비평활 볼록 최소화 — 함수값 + 부기울기 하나만 주는 오라클
모형	과거 절단평면들의 max (= 번들)
안정화	근접항 (μ/2)‖x − x̂‖²
부문제	번들 크기만 한 단체 제약 QP (쌍대에서 푼다)
판정	serious step / null step
주 무대	라그랑주 완화, 확률계획법의 쌍대
강점	비평활에서 구현 가능한 정지 판정을 준다

번들법은 비평활 볼록함수를 최소화할 때, 지금까지 모은 부기울기들로 만든 절단평면 모형에 근접항을 붙여 안정화한 알고리즘 계열이다. 이름의 “번들”은 과거 시행점에서 얻은 $(y_j,\ f(y_j),\ g_j\in\partial f(y_j))$ 삼중항들의 묶음을 가리킨다.

전제하는 상황이 뚜렷하다. 목적함수 $f$ 는 볼록이지만 각져 있고, 우리가 가진 것은 점 하나를 넣으면 함수값과 부기울기 하나를 돌려주는 오라클뿐이다. 이런 문제는 만들어서 푸는 게 아니라 저절로 생긴다 — 정수계획의 라그랑주 쌍대, 확률계획법의 기대 보정비용, 최대-마진 손실, 최소-최대 문제의 내부 최댓값. 전부 “최솟값 또는 최댓값을 취한 결과”라 매끄러울 이유가 없다.

핵심 주장은 하나다. 경사하강법의 비평활 버전(부경사법)은 언제 멈춰야 할지 알 수 없고, 절단평면법은 반복점이 미쳐 날뛴다. 번들법은 근접항 하나로 후자를 잡고, 그 부산물로 전자까지 해결한다.¹

2. 부경사법이 부족한 이유[편집]

비평활 볼록 최소화의 교과서적 첫 알고리즘은 부경사법이다.

$$x_{k+1} = x_k - t_k\, g_k,\qquad g_k \in \partial f(x_k)$$

문제가 셋 있고, 셋째가 치명적이다.

• 하강 방향이 아니다. 매끄러운 경우와 달리 $-g_k$ 는 감소 방향이라는 보장이 없다. 그래서 $f(x_k)$ 가 단조감소하지 않고, 최선값을 따로 기록해 둬야 한다. 라인서치도 못 쓴다.
• 스텝을 미리 정해야 한다. $t_k = c/\sqrt{k}$ 같은 사전 스케줄에 의존하며, 상수를 잘못 잡으면 그냥 느리다.
• 정지 판정이 없다. 이게 핵심이다. 매끄러운 문제에서는 $\|\nabla f(x)\|$ 가 작으면 최적에 가깝다. 그러나 비평활에서 $\partial f(x)$ 는 집합이고, 최적점 근처의 꺾인 점에서 오라클이 골라 주는 부기울기 하나는 노름이 여전히 클 수 있다. $f(x)=|x|$ 의 최적점은 $x=0$ 이지만 $x=10^{-9}$ 에서 오라클은 $g=1$ 을 돌려준다. ”$\|g_k\|$ 가 작아질 때까지 돌린다”는 기준 자체가 성립하지 않는다.

수렴 속도는 $O(1/\sqrt{k})$, 즉 $\varepsilon$-해까지 $O(1/\varepsilon^2)$ 회다. 이건 부경사법이 못나서가 아니라 비평활 볼록 문제의 블랙박스 1차 방법이 넘을 수 없는 하한(네미롭스키-유딘)이라, 번들법도 최악의 경우 이 벽 아래로는 못 간다. 번들법이 사는 이유는 점근 속도가 아니라 실전 성능과 정지 판정이다.

3. 절단평면 모형과 켈리법의 불안정[편집]

볼록성 덕에 각 부기울기는 전역 하한을 준다. $f(x) \ge f(y_j) + \langle g_j, x-y_j\rangle$ 이므로, 모아 놓은 절단평면들의 최댓값

$$\check{f}_k(x) \;=\; \max_{j \in J_k}\ \bigl\{\, f(y_j) + \langle g_j,\ x - y_j\rangle \,\bigr\}$$

는 항상 $\check{f}_k \le f$ 인 조각별 아핀 하한 모형이다. 켈리(1960)의 절단평면법은 이 모형을 그냥 최소화하고, 그 최소점에서 오라클을 불러 새 절단을 하나 더 얹는 것을 반복한다.

문제는 모형의 최소점이 항상 절단평면이 아직 하나도 없는 미개척지에 찍힌다는 것이다. 그래야 하한이 낮으니까. 그 결과 반복점이 매번 정의역의 반대편 끝으로 순간이동하고, 좋은 점을 찾아 놓고도 그 근처를 다시 안 본다. 게다가 정의역이 유계가 아니면 모형이 아래로 무한대라 첫 반복부터 정의가 안 된다. 최악의 경우 반복 수가 차원에 지수적이라는 예도 알려져 있다.

4. 근접 번들법 — 근접항 하나[편집]

처방은 놀랄 만큼 단순하다. **“어제 있던 곳에서 너무 멀리 가지 마라”**는 벌점을 붙인다. 현재의 안정화 중심 $\hat{x}_k$ 에 대해

$$y_{k+1} \;=\; \arg\min_{x}\ \left\{\, \check{f}_k(x) \;+\; \frac{\mu_k}{2}\,\|x - \hat{x}_k\|^2 \,\right\}$$

을 푼다. 이것이 근접 번들법(르마레샬 1975, 울프 1975, 이후 키비엘·미플린이 정리)이다. 구조를 보면 모형 $\check{f}_k$ 에 대한 근접점 알고리즘 한 스텝 — $\hat{x}_k$ 에서 $\check{f}_k$ 의 근접 연산자를 한 번 평가하는 것이고, 부문제의 최적값이 곧 $\check{f}_k$ 의 모로 포락이다. 근접항이 하는 일도 정확히 그것 — 모형을 강볼록으로 만들어 최소점을 유일하고 유계로 만들고, 반복점이 중심 주위에 머물게 한다. $\mu_k$ 는 신뢰반경의 역수 노릇을 한다.

편의를 위해 절단평면을 중심 기준으로 다시 쓰자. 선형화 오차

$$e_j \;=\; f(\hat{x}_k) - f(y_j) - \langle g_j,\ \hat{x}_k - y_j\rangle \;\ge\; 0$$

를 두면(볼록성에서 비음성) 모형이 $\check{f}_k(x) = f(\hat{x}_k) + \max_j\{\langle g_j, x-\hat{x}_k\rangle - e_j\}$ 로 정리된다. $e_j$ 는 “이 절단이 현재 중심에서 얼마나 뒤떨어진 정보인가”를 재는 값이고, 중심이 바뀌면 전부 갱신된다.

5. QP 부문제와 그 쌍대[편집]

위 부문제는 보조변수 $r$ 을 도입하면 이차계획법 문제다.

$$\min_{x,\,r}\ \ r + \frac{\mu_k}{2}\|x-\hat{x}_k\|^2 \quad \text{s.t.}\quad r \ge f(y_j) + \langle g_j, x-y_j\rangle,\ \ j\in J_k$$

변수가 $n+1$ 개, 제약이 번들 크기 $|J_k|$ 개다. 그런데 실제로 푸는 것은 이것의 쌍대다.

$$\min_{\lambda \in \Delta}\ \ \frac{1}{2\mu_k}\Bigl\| \sum_{j\in J_k} \lambda_j g_j \Bigr\|^2 \;+\; \sum_{j\in J_k}\lambda_j e_j, \qquad \Delta = \Bigl\{\lambda\ge0:\ \sum_j \lambda_j = 1\Bigr\}$$

단체 위의 작은 QP이고 변수 개수가 번들 크기(보통 10~100)라 문제 차원 $n$ 과 무관하다. $n$ 이 수십만이어도 부문제는 손바닥만 하다는 뜻이며, 이것이 번들법이 대규모 쌍대 문제에서 살아남은 실무적 이유다. 최적 $\lambda^\star$ 로부터

$$\hat{g}_k = \sum_j \lambda^\star_j g_j, \qquad \hat{e}_k = \sum_j \lambda^\star_j e_j, \qquad y_{k+1} = \hat{x}_k - \frac{1}{\mu_k}\hat{g}_k$$

를 얻는다. $\hat{g}_k$ 를 집약 부기울기(aggregate subgradient), $\hat{e}_k$ 를 집약 오차라 한다. 즉 다음 시행점은 집약 부기울기 방향으로 $1/\mu_k$ 만큼 간 곳이며, 형태만 보면 경사하강법과 똑같다. 다른 점은 방향을 오라클이 준 부기울기 하나에서 고르는 게 아니라 번들 전체의 볼록결합에서 골라낸다는 것이고, 그 결합계수를 QP가 정해 준다.

6. serious step과 null step[편집]

부문제가 예측한 감소량은

$$\delta_k \;=\; f(\hat{x}_k) - \check{f}_k(y_{k+1}) \;=\; \frac{\|\hat{g}_k\|^2}{\mu_k} + \hat{e}_k \;\ge\; 0$$

이다. 이제 오라클을 $y_{k+1}$ 에서 부르고, 예측한 만큼의 일정 비율이 실제로 실현됐는지 본다. $m \in (0,1)$ (보통 0.1)에 대해

$$f(y_{k+1}) \;\le\; f(\hat{x}_k) - m\,\delta_k$$

• 성립하면 serious step(하강 스텝). 중심을 옮긴다: $\hat{x}_{k+1} = y_{k+1}$. 모든 선형화 오차 $e_j$ 를 새 중심 기준으로 다시 계산한다.
• 성립하지 않으면 null step. 중심은 그대로 두고($\hat{x}_{k+1}=\hat{x}_k$) $y_{k+1}$ 에서 얻은 새 절단만 번들에 추가한다. 헛걸음처럼 보이지만 아니다 — 모형이 지나치게 낙관적이었던 바로 그 지점에 절단이 하나 꽂히므로, 다음 부문제의 모형은 그 방향에서 반드시 나아진다. 연속된 null step은 결국 serious step을 끌어내거나, 무한히 이어지는 경우 $\delta_k \to 0$ 이 되어 현재 중심이 이미 최적임을 확정한다 — 이 이분법이 수렴 증명의 뼈대다.

이 구조가 신뢰 영역 방법의 “예측 감소 대 실제 감소 비율” 판정과 사실상 같은 논리라는 점을 알아 두면 좋다. 다만 신뢰영역은 반경을 조이는 것으로 반응하고, 번들법은 모형에 절단을 추가하는 것으로 반응한다는 차이가 있다. 실무 구현은 둘 다 한다 — null step이 연달아 나오면 $\mu_k$ 를 키운다.

7. 정지 판정 — 번들법의 진짜 상품[편집]

$\delta_k$ 는 단순한 진행 지표가 아니라 최적성 증명서다. 최적성 조건을 정리하면

$$\hat{g}_k \in \partial_{\hat{e}_k} f(\hat{x}_k) \qquad\text{즉}\qquad f(x) \ \ge\ f(\hat{x}_k) + \langle \hat{g}_k,\ x-\hat{x}_k\rangle - \hat{e}_k \quad \forall x$$

가 성립한다. 여기에 $x = x^\star$ 를 넣으면

$$f(\hat{x}_k) - f^\star \;\le\; \hat{e}_k + \|\hat{g}_k\|\cdot\|x^\star - \hat{x}_k\|$$

즉 $\|\hat g_k\|$ 와 $\hat e_k$ 가 둘 다 작으면 현재 중심이 최적에 가깝다는 것이 보장된다. 그리고 그 둘의 조합이 바로 $\delta_k$ 다. $\delta_k \le \texttt{tol}$ 로 멈추는 것이 근거 있는 정지 판정이고, 부경사법이 끝내 주지 못한 것이 이것이다. 앞서 $f(x)=|x|$ 의 예에서, 번들에 $g=+1$ 과 $g=-1$ 이 둘 다 들어오는 순간 $\lambda=(\frac12,\frac12)$ 이 $\hat g = 0$ 을 만들어 즉시 최적성을 확정한다. 하나짜리 부기울기로는 절대 볼 수 없던 정보를 묶음이 보게 해 주는 것, 이 문서를 한 문장으로 줄이면 그렇다.

8. 번들 압축[편집]

번들이 무한정 커지면 QP가 무거워지므로 잘라내야 한다. 여기서 집약 부기울기가 두 번째 역할을 한다 — $(\hat{g}_k, \hat{e}_k)$ 자체를 하나의 절단으로 번들에 남기면, 버려진 절단들이 담고 있던 정보의 필요한 부분이 보존된다. 이론적으로는 번들에 (가) 집약 절단과 (나) 방금 얻은 새 절단, 딱 둘만 남겨도 수렴이 유지된다. 실무에서는 $\lambda_j^\star > 0$ 인 활성 절단들을 우선 남기고 전체 크기를 상한(예: 50~100)으로 관리한다.

메모리와 속도만의 문제가 아니다. 오래된 절단은 $e_j$ 가 크고, 큰 $e_j$ 는 QP에서 자동으로 낮은 가중치를 받는다. 번들법은 낡은 정보를 스스로 할인한다.

9. 왜 라그랑주 완화의 표준 도구가 됐나[편집]

번들법이 태어난 무대는 정수계획의 쌍대다. $\min\{c^\top x:\ Ax\le b,\ x\in X\}$ 에서 다루기 어려운 제약 $Ax\le b$ 만 목적함수로 올리면

$$\theta(u) \;=\; \min_{x \in X}\ \bigl\{\, c^\top x + u^\top (Ax - b) \,\bigr\},\qquad u \ge 0$$

이 라그랑주 완화의 쌍대함수다. $X$ 가 유한집합(정수해 집합)이면 $\theta$ 는 유한 개 아핀함수의 최솟값, 즉 조각별 아핀 오목함수다. 이 문제가 번들법과 궁합이 완벽한 이유는 셋이다.

• 오라클이 정확히 우리가 원하는 것을 준다. $\theta(u)$ 를 계산하려면 어차피 최소화기 $x(u)$ 를 구해야 하고, 그러면 $Ax(u)-b$ 가 부기울기로 공짜로 나온다. 값과 부기울기를 한 번에 주는 오라클이 저절로 존재한다.
• 비평활성이 본질적이다. 최소화기가 여럿인 $u$ 에서 $\theta$ 는 반드시 각져 있고, 최적 쌍대해는 거의 항상 그런 점에 있다. 평활화로 도망갈 수 없다.
• 하한을 언제 그만 끌어올릴지 알 수 있다. 약쌍대성에 의해 $\theta(u)$ 는 어느 $u$ 에서든 그대로 분지한정법 트리에 쓸 수 있는 하한이다. 문제는 “더 돌리면 하한이 얼마나 더 올라가나”인데, $\delta_k$ 가 바로 그 남은 여지를 정량화한다. 무한정 돌릴 이유도, 너무 일찍 끊을 이유도 없어진다.

같은 구조가 확률계획법에도 있다. 2단계 문제의 보정비용 함수(recourse function) $Q(x)=\mathbb{E}_\xi[Q(x,\xi)]$ 는 조각별 아핀 볼록이고, 시나리오별 LP를 풀면 값과 부기울기가 나온다. 벤더스 분해·L-shaped 방법이 이 위의 절단평면법이며, 그 안정화 버전이 곧 번들법이다.² 발전기 기동정지 계획, 승무원 스케줄링, 네트워크 설계처럼 “라그랑주 쌍대를 풀어 하한을 얻고 휴리스틱으로 상한을 맞추는” 산업 문제에서 번들법은 여전히 현역이다.

10. 수렴률과 변형들[편집]

• 일반 비평활 볼록의 벽. 앞서 말한 $O(1/\varepsilon^2)$ 하한은 어떤 알고리즘도 못 넘는다. 고전적인 근접 번들 분석은 오랫동안 점근 수렴만 보였고 명시적 복잡도는 $O(1/\varepsilon^3)$ 수준에 머물렀는데, 근래(2020년대) 분석이 적절한 $\mu$ 관리 아래 최적 차수 $O(1/\varepsilon^2)$ 를 회복할 수 있음을 보였다. 실전 성능이 이론보다 한참 좋았던 오랜 간극이 이제야 좁혀지는 중이다.
• 레벨 번들법(르마레샬-네미롭스키-네스테로프 1995). 근접항 대신 레벨 집합 제약 $\check{f}_k(x) \le \ell_k$ 를 걸고 그 안에서 현재 점에 가장 가까운 점으로 사영한다. $\ell_k$ 는 지금까지의 상한과 모형 하한 사이를 비례로 잡는다. 매개변수 튜닝이 $\mu$ 보다 덜 예민하고 명시적 복잡도 보증이 깔끔하다는 것이 장점.
• 신뢰영역 번들법(슈람-초베). 근접항 대신 $\|x-\hat x_k\|\le\Delta_k$ 를 제약으로 걸고 반경을 신뢰영역식으로 조정한다. 근접형과 수학적으로 밀접하지만($\mu$ 와 $\Delta$ 가 서로의 쌍대 역할) 구현 감각이 다르다.
• 비볼록 번들법. $e_j$ 가 음수가 될 수 있으므로 $|e_j|$ 나 $e_j + \gamma\|\hat x_k - y_j\|^2$ 로 바꿔 하한 성질을 인위적으로 회복시킨다. 약볼록 함수 정도의 구조가 있으면 이론이 붙지만, 일반 비볼록에서는 임계점 수렴 이상을 기대하기 어렵다.
• 비정확 오라클. 실무의 오라클(내부 LP를 근사로 푼 것)은 부정확하다. 오차가 유계면 번들법은 그 오차 크기만큼의 근사 최적해로 수렴한다는 결과가 있고, 이 견고성이 대규모 분해 알고리즘에서 특히 고맙다.³

11. 관련 문서[편집]

• 절단평면법 · 지지함수 · 하한 합성곱 · 모로 포락
• 근접점 알고리즘 · 근접 경사법 · 단조 작용소
• 볼록 최적화 · 이차계획법 · 쌍대성 · 쌍대 상승법
• 정수계획법 · 선형계획법 · 분지한정법 · 조합 최적화
• 신뢰 영역 방법 · 경사하강법 · 미러 하강 · 라인서치
• 르장드르-펜셸 변환 · 약볼록 함수 · 벌점법

12. Footnotes[편집]

1. 번역어가 안 잡혀서 “묶음법”, “다발법”, 그냥 “번들법”이 다 돌아다닌다. 그리고 subgradient도 부기울기·부경사·열등기울기·하위기울기가 섞여 쓰인다. 이 문서는 심위키의 다른 문서들에 맞춰 부기울기/부미분으로 통일했지만, 논문을 찾아볼 때는 원어를 같이 검색하는 편이 빠르다. ↩

2. 그래서 “번들법 = 안정화된 절단평면법”이라는 요약은 게으른 게 아니라 정확하다. 실제로 $\mu_k \to 0$ 이면 켈리법으로 돌아가고, $\mu_k \to \infty$ 면 제자리걸음이 된다. 알고리즘 하나가 매개변수 하나로 두 극단을 잇는 구조라, $\mu$ 관리 휴리스틱이 논문 절반을 차지하는 것도 이해할 만하다. ↩

3. 대규모 라그랑주 완화에서 부문제를 최적으로 푸는 것은 사치인 경우가 많다. 배낭 부문제 수천 개를 매 반복 정확히 푸느니 근사로 빨리 푸는 편이 이득인데, 그러면 부기울기가 틀린 방향을 가리킬 위험이 생긴다. “오라클이 좀 틀려도 알고리즘이 안 무너진다”는 보증이 있느냐 없느냐가 이때 논문과 현장을 가른다. ↩