フランク・ウルフのアルゴリズム
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/11/26 02:14 UTC 版)
フランク・ウルフのアルゴリズム (英: Frank–Wolfe algorithm) とは、条件付き凸最適化問題を反復的一次最適化により解くアルゴリズム である。条件付き勾配法 (conditional gradient method)、[1] 簡約勾配法 (reduced gradient algorithm)、 凸結合法 (convex combination algorithm) とも呼ばれ、1956年にマルグリート・フランクおよびフィリップ・ウルフにより提案された[2]。このアルゴリズムでは、各反復毎に目的関数の線形近似を行い、この(定義域を同じくする)線形関数を最適化する方向へと移動する。
- ^ Levitin, E. S.; Polyak, B. T. (1966). “Constrained minimization methods”. USSR Computational Mathematics and Mathematical Physics 6 (5): 1. doi:10.1016/0041-5553(66)90114-5.
- ^ Frank, M.; Wolfe, P. (1956). “An algorithm for quadratic programming”. Naval Research Logistics Quarterly 3: 95. doi:10.1002/nav.3800030109.
- ^ Dunn, J. C.; Harshbarger, S. (1978). “Conditional gradient algorithms with open loop step size rules”. Journal of Mathematical Analysis and Applications 62 (2): 432. doi:10.1016/0022-247X(78)90137-3.
- ^ Clarkson, K. L. (2010). “Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm”. ACM Transactions on Algorithms 6 (4): 1. doi:10.1145/1824777.1824783.
- ^ Fukushima, M. (1984). “A modified Frank-Wolfe algorithm for solving the traffic assignment problem”. Transportation Research Part B: Methodological 18 (2): 169–177. doi:10.1016/0191-2615(84)90029-8.
- ^ Bertsekas, Dimitri (1999). Nonlinear Programming. Athena Scientific. p. 215. ISBN 1-886529-00-0
- 1 フランク・ウルフのアルゴリズムとは
- 2 フランク・ウルフのアルゴリズムの概要
- 3 解の値の下限と主双対解析
- 4 参考文献
- フランク・ウルフのアルゴリズムのページへのリンク