프랭크-울프 알고리즘

프랭크-울프 알고리즘은 제한된 볼록 최적화를 위한 반복적 1차 최적화 알고리즘이다.조건부 그라데이션 방법,^[1] 감소된 그라데이션 알고리즘, 볼록 결합 알고리즘으로도 알려져 있는 이 방법은 원래 1956년 마르그리트 프랑크와 필립 울프가 제안하였다.^[2]각 반복에서, 프랭크-울프 알고리즘은 목표 함수의 선형 근사치를 고려하며, 이 선형 함수의 최소제 쪽으로 이동한다(동일한 영역에 걸쳐 있음).

문제명세서

$D{\displaystyle \mathcal{}}$ ${\$이(가) 벡터 공간에 설정된 콤팩트 볼록이고 $f{\displaystyle }$: ${\displaystyle D\mathbb{}}$→ R ${\$이$($가) 볼록하고 서로 다른 실제 값 함수라고 가정해 보십시오.Frank-Wolfe 알고리즘을 통해 최적화 문제 해결

$f{\displaystyle }$( ${\displaystyle x\mathbf{}}$) ${\displaystyle f(\mathbf {x})$ 최소화

$x{\displaystyle \mathbf{}}$ ${\displaystyle \in }$ ${\displaystyle D\mathcal{}}$ ${\$의 적용을 받는다$.$

알고리즘.

초기화:$k{\displaystyle }$ ${\displaystyle \leftarrow }$ ${\displaystyle 0}$ ${\displaystyle k\leftarrow 0}$을$($를) 설정하고 x $0{\displaystyle {\mathbf{}}_{}}$ $displaystyle \mathbf {$x$} _{0}\!}$을(를) $D{\displaystyle \mathcal{}}$ ${\$의 어느 점으로$$ 두십시오$.$

단계 1.방향 찾기 하위 문제:${\displaystyle {}_{}}$ ${\$ 해결 방법$$ 찾기

$S{\displaystyle {\mathbf{}}^{}}$ ${\displaystyle {}^{}}$ ${\displaystyle {}^{}\mathrm{}}$ ${\displaystyle f}$( ${\displaystyle {}_{}}$ k${\displaystyle {}_{}}$) ${\displaystyle \mathbf {s} ^{T}\nabla f(\mathbf {x} _{k})$ 최소화

$s{\displaystyle \mathbf{}}$ ${\displaystyle \in }$ ${\displaystyle D\mathcal{}}$ ${\$의 적용을 받는다.

(해석:$1차{\displaystyle {\mathbf{}}_{}}$ Taylor의 x ${\displaystyle {}_{}}$ $displaystyle \mathbf {x} _{k}\}$ 주위에$$ $f{\displaystyle }$ ${\displaystyle f}$ 근사치가 제공하는 문제의 선형 근사치를 최소화하십시오.$$

2단계. 단계 크기 결정:Set ${\displaystyle \alpha \leftarrow {\frac {2}{k+2}}}$, or alternatively find ${\displaystyle \alpha }$ that minimizes ${\displaystyle f(\mathbf {x} _{k}+\alpha (\mathbf {s} _{k}-\mathbf {x} _{k}))}$ subject to ${\displaystyle 0\leq \alpha \leq 1}$$$ .

3단계. 업데이트:Let ${\displaystyle \mathbf {x} _{k+1}\leftarrow \mathbf {x} _{k}+\alpha (\mathbf {s} _{k}-\mathbf {x} _{k})}$, let ${\displaystyle k\leftarrow k+1}$ and go to Step 1.

특성.

제약적 최적화에 대한 구배 강하와 같은 경쟁적 방법에는 각 반복에서 실현 가능한 집합으로 회귀하는 투영이 필요한 반면, Frank-Woolfe 알고리즘은 각 반복에서 동일한 집합에 걸쳐 선형 문제의 해결책만 필요로 하며, 자동으로 실현 가능한 집합에 머무른다.

프랭크-울프 알고리즘의 수렴은 일반적으로 하위 선형이므로, 최적치에 대한 객관적 함수의 오차는 K 반복 후${\displaystyle }O{\displaystyle }$ (${\displaystyle 1}$ / k$){\displaystyle O$ ($1/k)$이며, 따라서 경사가 어떤 표준에 관해서 립스키츠가 연속적이다.하위 문제가 근사적으로만 해결되는 경우에도 동일한 수렴 비율을 나타낼 수 있다.^[3]

이 알고리즘의 예제가 항상 알고리즘의 인기에 기계 학습에서 sparse 탐욕스러운 최적화 및 신호 처리 problems,[4]뿐만 아니라 예를 들어 minimum–cost 흐름의 교통 완벽의 최적화를 위하는 것을 도왔다 실현 가능한 세트가 극단적인 포인트의 희박한 볼록 조합으로 표시할 수 있다.2rks^[5]

만약 실현 가능한 집합이 일련의 선형 제약조건에 의해 주어진다면, 각 반복에서 해결해야 할 하위 문제는 선형 프로그램이 된다.

$일반적$으로 O${\displaystyle (1}$/ ${\displaystyle k}$ )${\디스플레이$ 스타일 O$(1/k$)}이$($가) 있는 최악의 경우 수렴률을 개선할 수 없지만$$, 일부 강한 볼록형 문제와 같은 특수 문제 등급의 경우 보다 빠른 수렴 속도를 얻을 수 있다.^[6]

솔루션 값 하한 및 원시 이중 분석

$f{\displaystyle }$ ${\displaystyle f}$은(는) 볼록하므로, 임의의 두 $지점{\displaystyle \mathbf{}x\mathcal{}}$, ${$ D {\$displaystyle \mathbf${x$},\mathbf$ {$y} \mathbf {d}$에 대해 다음$$ 사항을 확인하십시오.

${\displaystyle f(\mathbf {y} )\geq f(\mathbf {x})+(\mathbf {y} -\mathbf {x})^{T}\nabla f(\mathbf {x} )}$

This also holds for the (unknown) optimal solution ${\displaystyle \mathbf {x} ^{*}}$. That is, ${\displaystyle f(\mathbf {x} ^{*})\geq f(\mathbf {x} )+(\mathbf {x} ^{*}-\mathbf {x} )^{$$T}\nabla$ f$(\mathbf {x}$ $)\}.$주어진 점 $x{\displaystyle \mathbf{}}$ ${\$에 대한 최상의 하한은 다음과$$ 같다$.$

${\displaystyle {\mathbf {x}f(\mathbf {x} ^*})f(\mathbf {x})+(\mathbf {x} ^*}-\mathbf {x}^{}}^{}-\mathbf {x}}}^{{{}}}}}}}}}}}^{{{}}}}}}}T}\\nabla f(\mathbf {x} )\\&\geq \min _{\mathbf {y}\in D}\f(\mathbf {x})++(\mathbf {y} -\mathbf {x} )^{{{}T}\nabla f(\mathbf {x} )\right\}\\&=f(\mathbf {x} )-\mathbf {x} ^{T}\nabla f(\mathbf {x} )+\min _{\mathbf {y} \in D}\mathbf {y} ^{T}\nabla f(\mathbf {x} )\end{aligned}}}$

후자의 최적화 문제는 Frank-Wolfe 알고리즘의 모든 반복에서 해결되므로 $k{\displaystyle }$ ${\displaystyle k}$ -th$$ 반복의 방향 탐색$$ 하위 ${\displaystyle {}_{}}$의 솔루션 k ${\$ {s}$_{k}$을 사용하여 각 반복 중 증가하는$$ 하한 ${\displaystyle l_{}}$ ${\$을 결정할 수 있다.$l{\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$= -${\displaystyle \mathrm{\infty }}$ ${\displaystyle l_{0}=-\inflt }$을(를) 설정하여 지우기$$

${\displaystyle l_{k}=\max(l_{k-1},f(\mathbf {x} _{k})+(\mathbf {s}) _{k}-\mathbf {x}^{k}^{k}{k}}}^{{}}}}{}}}}}}}}}}}T}\nabla f(\mathbf {x} _{k})}$

알 수 없는 최적 값에 대한 이러한 하한은 항상 $l{\displaystyle {}_{}}$ ${\displaystyle k_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle f}$( ${\displaystyle {\mathbf{}}^{}}$ ${\displaystyle {}^{}}$) ${\displaystyle \le }$ ${\displaystyle f}$ ( ${\displaystyle {\mathbf{}}_{}}$ k ) ≤ f${\displaystyle }$( x ${\displaystyle {}_{}}$) ${\displaystyle l_{k}\leq f(\mathbf {x} ^*}}\mathb$ f (\$mathb {x} _}$ _$\{$$k})$ }}}}}}}}}}}}을(으)로 사용할 수 있기 때문에 모든 반복에서 근사치의 효율적인 품질의 인증서를 제공할 수 있기 때문에 실제로 중요하다.

It has been shown that this corresponding duality gap, that is the difference between ${\displaystyle f(\mathbf {x} _{k})}$ and the lower bound ${\displaystyle l_{k}}$, decreases with the same convergence rate, i.e. ${\displaystyle f(\mathbf {x} _{k})-l_{k}=O(1/k).$$}$

메모들

참고 문헌 목록

• Jaggi, Martin (2013). "Revisiting Frank–Wolfe: Projection-Free Sparse Convex Optimization". Journal of Machine Learning Research: Workshop and Conference Proceedings. 28 (1): 427–435. (개요지)
• 프랭크-울프 알고리즘 설명
• Nocedal, Jorge; Wright, Stephen J. (2006). Numerical Optimization (2nd ed.). Berlin, New York: Springer-Verlag. ISBN 978-0-387-30303-1..

외부 링크

• 마거릿 프랭크가 알고리즘의 역사에 대해 개인적인 설명을 했다.

참고 항목

• 근위부 그라데이션 방법