프랭크-울프 알고리즘

1. 개요[편집]

프랭크-울프 알고리즘 Frank–Wolfe algorithm
다른 이름	조건부 경사법 (conditional gradient method)
제안	Marguerite Frank & Philip Wolfe (1956), 원래는 이차계획법용
대상	컴팩트 볼록집합 위의 미분가능 볼록함수 최소화
핵심 부품	선형 최소화 오라클 $s_k=\arg\min_{s\in\mathcal D}\langle\nabla f(x_k),s\rangle$
스텝	$\gamma_k=2/(k+2)$ 또는 선탐색
최대 장점	투영이 없다 · 반복해가 항상 실행가능 · 해가 희소
수렴	$f(x_k)-f^\star \le 2C_f/(k+2)$ — 일반적으로 개선 불가
정지조건	쌍대갭 $g_k=\langle\nabla f(x_k),x_k-s_k\rangle$ (공짜)

프랭크-울프 알고리즘(Frank–Wolfe algorithm)은 컴팩트 볼록집합 위에서 미분가능 볼록함수를 최소화할 때, 매 반복마다 목적함수를 현재 점에서 선형화하고 그 선형함수를 제약집합 위에서 최소화해 얻은 극점 쪽으로 조금만 이동하는 1차 최적화 알고리즘이다. 조건부 경사법(conditional gradient method)이라는 이름으로도 똑같이 통용된다. 마거리트 프랭크와 필립 울프가 1956년에 이차계획법을 풀려고 만들었는데¹, 정작 이차계획법에서는 더 좋은 방법에 밀려나고 전혀 다른 두 동네에서 두 번 부활했다 — 1970년대의 교통 통행배정과 2010년대의 대규모 기계학습이다.

부활의 이유는 매번 같다. 투영을 안 한다. 경사하강법 계열을 제약집합 위에서 돌리려면 매 스텝 결과를 집합 안으로 되돌리는 투영 연산이 필요한데, 이게 원래 문제만큼 어려운 경우가 흔하다. 프랭크-울프는 투영 대신 선형 최소화만 쓴다. 선형함수를 볼록집합 위에서 최소화하는 문제는 답이 항상 꼭짓점(극점)에 있어서, 집합의 구조를 알면 대개 어이없이 싸게 풀린다. 도로망이면 최단경로, ℓ1 공에서는 최대 성분 하나 고르기, 핵노름 공에서는 최대 특이벡터 한 쌍이다.

2. 알고리즘[편집]

문제는 이렇게 둔다. $\mathcal D \subset \mathbb R^n$ 은 컴팩트 볼록집합, $f$ 는 $\mathcal D$ 위에서 미분가능한 볼록함수.

$$\min_{x \in \mathcal D} \ f(x)$$

$x_k$ 에서 $f$ 를 1차 테일러 전개하면 $f(s) \approx f(x_k) + \langle \nabla f(x_k),\, s - x_k\rangle$ 인데, 상수항을 버리면 남는 건 선형함수뿐이다. 이걸 그대로 최소화하는 것이 선형 최소화 오라클(Linear Minimization Oracle, LMO)이다.

$$s_k \;=\; \arg\min_{s \in \mathcal D} \ \langle \nabla f(x_k),\, s \rangle$$

그리고 그 방향으로 볼록 결합만큼만 간다.

$$x_{k+1} \;=\; (1-\gamma_k)\, x_k + \gamma_k\, s_k, \qquad \gamma_k \in [0,1]$$

여기가 이 알고리즘의 전부이자 요령의 전부다. $x_k \in \mathcal D$ 이고 $s_k \in \mathcal D$ 이므로 둘의 볼록 결합인 $x_{k+1}$ 도 자동으로 $\mathcal D$ 안에 있다. 실행가능성이 공짜로 유지되고, 그래서 투영이 필요 없다. 초기점만 $\mathcal D$ 의 아무 꼭짓점으로 잡아 주면 그 뒤로는 집합 밖으로 나갈 방법이 아예 없다.

스텝은 두 갈래로 정한다.

• 개루프(open-loop): $\gamma_k = 2/(k+2)$. 함수값을 한 번도 평가하지 않는다. 아래의 수렴 보장이 그대로 붙는 표준값이다.
• 선탐색: $\gamma_k = \arg\min_{\gamma\in[0,1]} f\bigl(x_k + \gamma(s_k - x_k)\bigr)$. 1차원 볼록 문제이므로 도함수의 근만 찾으면 되고, 라인서치의 교과서적 사용례다. 실전 성능은 보통 이쪽이 낫다.

투영 기반 방법과의 대비는 이렇다.

항목	경사투영법	프랭크-울프
집합을 다루는 도구	투영 연산	선형 최소화 오라클
반복당 비용	투영이 병목	LMO가 병목(보통 훨씬 싸다)
반복해의 성격	집합 내부 어디든	꼭짓점 $k{+}1$ 개의 볼록 결합
매끄러운 볼록 문제 수렴	$O(1/k)$, 가속 시 $O(1/k^2)$	$O(1/k)$, 일반적으로 가속 불가
비평활 목적함수	근접 연산자로 대응	그대로는 안 됨

즉 한 스텝을 싸게 만드는 대신 스텝 수를 많이 쓰는 거래다. 투영이 비싸거나 아예 불가능한 문제에서만 이 거래가 이득이다.

3. 쌍대갭 — 공짜 정지조건[편집]

프랭크-울프의 진짜 매력은 부분문제를 푸는 김에 최적성 간극의 상한이 덤으로 나온다는 점이다. 정의는 이렇다.

$$g_k \;=\; \langle \nabla f(x_k),\, x_k - s_k \rangle \;=\; \max_{s \in \mathcal D}\ \langle \nabla f(x_k),\, x_k - s \rangle \;\ge\; 0$$

$f$ 의 볼록성에서 임의의 $x^\star$ 에 대해 $f(x^\star) \ge f(x_k) + \langle \nabla f(x_k), x^\star - x_k\rangle \ge f(x_k) - g_k$ 이므로

$$f(x_k) - f^\star \;\le\; g_k$$

가 항상 성립한다. $s_k$ 를 계산했으면 $g_k$ 는 내적 한 번이다. 다른 알고리즘에서 최적성 간극을 알려면 쌍대문제를 따로 세워 풀어야 하는 걸 생각하면 이건 거의 반칙이다. 그래서 프랭크-울프의 정지조건은 “잔차가 안 줄어든다” 같은 감각적 기준이 아니라 증명 가능한 상한이다.

수렴률은 곡률 상수 $C_f$ 로 표현한다.

$$C_f \;=\; \sup_{\substack{x,s \in \mathcal D,\ \gamma \in (0,1] \\ y = x + \gamma(s-x)}} \frac{2}{\gamma^2}\Bigl[f(y) - f(x) - \langle y - x,\, \nabla f(x)\rangle\Bigr]$$

$\nabla f$ 가 $L$-립시츠면 $C_f \le L\,\mathrm{diam}(\mathcal D)^2$ 로 눌린다. 이 상수로 $\gamma_k = 2/(k+2)$ 스텝에서

$$f(x_k) - f^\star \;\le\; \frac{2C_f}{k+2}$$

가 나오고, 같은 논증으로 $k$ 회 안에 $g_j \le O(C_f/k)$ 인 반복이 반드시 존재한다는 것도 보인다.² 즉 $\varepsilon$-정확도에 $O(1/\varepsilon)$ 반복. 화려하지 않다. 하지만 이 $O(1/k)$ 는 LMO만 쓰는 방법 부류에서는 일반적으로 개선할 수 없다 — 최적해가 집합의 꼭짓점이 아니라 면 안쪽에 있으면 꼭짓점들의 볼록 결합으로 그걸 표현하는 데 원자가 계속 필요하기 때문이다. 네스테로프 가속 같은 트릭이 여기서는 통하지 않는다.

4. 교통 통행배정 — 60년 현역[편집]

이 알고리즘이 죽지 않은 첫 번째 이유는 도로망이다. 베크만 변환은 워드롭 균형을 볼록계획으로 바꿔 놓는다.

$$\min_{x \in \Omega} \ z(x) = \sum_a \int_0^{x_a} t_a(w)\,dw$$

$\Omega$ 는 OD 수요를 만족하는 링크 유량 다면체, $t_a$ 는 BPR 같은 순증가 링크 성능함수다. 그래디언트가 $\nabla z = (t_a(x_a))$ 이므로 부분문제는

$$\min_{y \in \Omega}\ \sum_a t_a(x_a^k)\, y_a$$

인데, 이건 현재 통행시간으로 최단경로를 찾아 수요를 통째로 얹는 전량배정(all-or-nothing)과 정확히 같다. 유량 보존 다면체 위의 선형계획이 OD별 최단경로 문제로 분해되기 때문이다. LP 솔버 대신 다익스트라 알고리즘만 있으면 되고, 상태로 들고 있는 것이 링크 유량뿐이라 메모리가 링크 수에 비례한다. 1970년대 계산기로 대도시 네트워크를 돌릴 수 있었던 이유이자, 이 조합이 지금도 교통 배정의 기본형인 이유다.

여기서 실무 지표로 쓰는 상대격차(relative gap)의 정체도 드러난다. 총 통행시간 $\mathrm{TSTT}=\sum_a x_a t_a(x_a)$ 와 최단경로 통행시간 합 $\mathrm{SPTT}=\sum_a y_a t_a(x_a)$ 의 차이는

$$\mathrm{TSTT} - \mathrm{SPTT} \;=\; \sum_a t_a(x_a)\,(x_a - y_a) \;=\; g_k$$

즉 프랭크-울프의 쌍대갭 바로 그것이다. 상대격차는 그걸 TSTT로 정규화해 단위를 없앤 값이다. 교통계획 보고서에 적히는 “상대격차 $10^{-4}$ 달성”이라는 문장은, 번역하면 “베크만 목적함수의 최적성 간극이 총 통행시간의 0.01 % 이하임을 증명했다”는 뜻이다. 배정 절차의 나머지 디테일 — MSA, 경로기반·기점기반 알고리즘, 동적 배정 — 은 교통 배정 문서가 다룬다.

5. 지그재그와 개선판[편집]

$O(1/k)$ 는 평균적인 이야기이고, 실제로 사람들을 괴롭히는 건 꼬리 수렴이다. 최적해가 다면체의 어떤 면 위에 있으면, 방향 $s_k - x_k$ 가 그 면과 거의 수직이 되어 이동해도 목적함수가 거의 안 준다. 반복마다 꼭짓점을 좌우로 번갈아 찍으며 답 주위를 지그재그로 맴돈다. 교통 배정에서 상대격차 $10^{-2}$ 까지는 수십 번이면 가는데 $10^{-4}$ 에 수천 번이 드는 것이 정확히 이 현상이다.

처방은 이미 쓴 원자를 되돌릴 길을 열어 주는 것이다.

• 이탈 스텝(away-step) FW. 현재 해를 구성하는 활성 원자 집합에서 그래디언트가 가장 나쁜 원자 $v_k$ 를 골라 그 쪽에서 질량을 빼는 방향 $x_k - v_k$ 도 후보에 넣고, 두 방향 중 감소가 큰 쪽을 택한다. 다면체 위 강볼록 문제에서 선형 수렴이 증명된다.³
• 쌍방향(pairwise) FW. 한 스텝에서 $v_k$ 의 질량을 $s_k$ 로 통째로 옮긴다. 활성 원자 수가 늘지 않아 희소성 유지에 유리하다.
• 켤레 FW / 이중켤레 FW(CFW·BFW). 새 방향을 이전 방향들과 켤레가 되게 섞는다. 교통 배정 쪽에서 표준으로 자리 잡았고, 같은 반복 수로 격차를 한두 자릿수 더 번다.

공통점은 활성 집합을 관리한다는 것이고, 대가는 그 집합을 저장해야 한다는 것이다. 원본 프랭크-울프의 “상태가 $x_k$ 하나뿐”이라는 미덕을 일부 반납하는 거래다.

6. 희소 원자 표현과 기계학습[편집]

두 번째 부활은 2010년대다. 관찰의 핵심은 이렇다. $x_0$ 를 꼭짓점 하나로 잡으면 $x_k$ 는 많아야 $k+1$ 개 극점의 볼록 결합이다. 즉 반복 수가 곧 해의 복잡도 예산이고, 일찍 멈추면 자동으로 희소한 해가 나온다. 정규화를 따로 걸 필요 없이 알고리즘 자체가 희소성을 만든다.

이 성질은 제약집합이 원자 노름 공일 때 특히 빛난다.

• ℓ1 공. 극점이 $\pm e_i$ 이므로 LMO는 그래디언트의 절댓값 최대 성분을 찾는 것. 한 스텝이 좌표 하나를 건드리며, 라쏘의 제약형과 궁합이 좋다.
• 핵노름 공. 극점이 랭크 1 행렬 $uv^{\mathsf T}$ 이고, LMO는 $-\nabla f$ 의 최대 특이벡터 한 쌍이다. 거듭제곱법이나 란초스로 뽑으면 되므로 특이값 분해를 전부 계산할 필요가 없다. 반복마다 랭크가 1씩만 오르니 $k$ 번 돌면 랭크 $k$ 해다. 행렬 완성이나 저랭크 반정부호계획에서 이 성질이 결정적이다.⁴
• 일반 원자 노름. 원자 집합을 정하면 LMO는 “그래디언트와 가장 잘 정렬된 원자 하나 고르기”가 된다. 이 관점이 다양한 구조적 희소성 문제를 한 틀에 묶는다.

여기에 투영이 비싼 대신 LMO는 싸다는 조건이 겹치면 프랭크-울프가 유일한 현실적 선택이 되는 경우가 많다. 핵노름 공으로의 투영은 전체 SVD가 필요하지만 LMO는 최대 특이벡터 하나면 된다 — $n\times n$ 행렬에서 $O(n^3)$ 대 $O(n^2)$ 의 차이다. 대규모 문제에서는 그냥 다른 종목이 된다. 확률적 그래디언트를 쓰는 변형, 블록 좌표 변형(구조적 서포트 벡터 머신의 쌍대문제가 대표적), 분산 구현 등이 이 위에 얹혀 있다.

7. 실무 감각[편집]

• 투영이 싸면 쓰지 마라. 단순 상자 제약이나 단체(simplex)처럼 투영이 $O(n \log n)$ 이면 근접 경사법이나 가속법이 거의 항상 이긴다. 프랭크-울프의 존재 이유는 “투영이 비싸다”는 조건 하나다.
• 비평활 목적함수에는 그대로 못 쓴다. 수렴 보장이 $C_f$ 유한, 즉 그래디언트 립시츠 연속을 요구한다. 비평활이면 평활화하거나 다른 계열로 가야 한다(비평활 최적화).
• 쌍대갭을 반드시 로그로 남겨라. 공짜로 나오는 상한을 안 찍는 건 낭비다. 반복 수만 적힌 보고서는 재현이 안 된다.
• 꼬리가 안 죽으면 지그재그를 의심하라. 반복 수를 늘리는 것보다 이탈 스텝이나 켤레 변형으로 바꾸는 쪽이 거의 항상 빠르다.
• 의외의 사촌들. D-최적 설계의 고전적 순차 알고리즘, 부스팅류의 탐욕적 기저 추가, 배낭 완화 기반 조합 문제의 라그랑주 완화 반복 — 전부 프랭크-울프로 읽힌다. “선형화하고, 극점 하나 고르고, 조금 섞는다”는 골격이 그만큼 넓다.⁵

8. 관련 문서[편집]

• 볼록 최적화 · 경사하강법 · 근접 경사법 · 미러 하강
• 라인서치 · 선형계획법 · 카루시-쿤-터커 조건 · 쌍대성
• 교통 배정 · 워드롭 균형 · 브라에스 역설 · 다익스트라 알고리즘
• 이산 선택 모형 · 중력 모형
• 라쏘 · 저랭크 근사 · 특이값 분해 · D-최적 설계
• 비평활 최적화 · 온라인 볼록 최적화 · 조합 최적화

9. Footnotes[편집]

1. Frank, M. & Wolfe, P. (1956). “An algorithm for quadratic programming”. Naval Research Logistics Quarterly 3(1–2), 95–110. 제목에 이차계획법이 박혀 있는데 정작 이차계획법에서는 능동집합법·내점법에 밀려 거의 안 쓰인다. 논문 제목이 그 알고리즘의 미래를 가장 못 맞힌 사례 중 하나. ↩

2. 증명의 골격은 세 줄이다. 곡률 상수의 정의로 $f(x_{k+1}) \le f(x_k) - \gamma_k g_k + \tfrac{\gamma_k^2}{2}C_f$ 를 얻고, $g_k \ge f(x_k)-f^\star$ 를 대입해 오차 $h_k = f(x_k)-f^\star$ 의 재귀식 $h_{k+1} \le (1-\gamma_k)h_k + \tfrac{\gamma_k^2}{2}C_f$ 를 만든 뒤, $\gamma_k = 2/(k+2)$ 로 귀납하면 끝. 스텝을 선탐색으로 잡아도 개루프 스텝보다 나쁠 수 없으므로 같은 상한이 그대로 성립한다. ↩

3. 이탈 스텝 아이디어 자체는 울프 본인이 1970년경에 이미 제시했고, 다면체 위 강볼록 문제에서의 선형 수렴은 Guélat & Marcotte (1986)가 정리했다. 다만 그 수렴률의 상수에 “최적해가 면의 경계에서 얼마나 떨어져 있는가”가 들어가 있어서, 해가 면 경계에 딱 붙어 있으면 상수가 폭발한다. 2015년에 이 조건을 다면체의 기하로 깔끔하게 다시 쓴 결과들이 나오면서 계열 전체가 재조명됐다. ↩

4. 랭크가 반복마다 1씩 오른다는 건 축복이자 저주다. 랭크 50짜리 해가 필요하면 최소 50번은 돌려야 하고, 그 50번이 $O(1/k)$ 수렴의 50번이라 정확도는 형편없다. 그래서 실무에서는 주기적으로 활성 원자 위에서 목적함수를 다시 최적화하는 “완전 보정(fully corrective)” 변형을 섞는다. 결국 공짜는 없다. ↩

5. 그래서 최적화 수업에서 프랭크-울프를 배우고 나면 갑자기 여기저기서 프랭크-울프가 보이기 시작한다. “이거 그냥 선형화하고 극점 하나 찍는 거 아닌가?” 싶으면 대개 맞다. 물론 그렇게 말했다가 저자 앞에서 논문의 기여를 부정하는 사람이 되는 수가 있으니 발표장에서는 자제하자. ↩