Алгоритм Франк — Вульфа

Алгори́тм Франк-Ву́льфа — це ітеративний алгоритм оптимізації першого порядку для опуклої оптимізації з обмеженнями. Алгоритм відомий також як ме́тод умо́вного градіє́нта, ме́тод зве́деного градіє́нта і алгори́тм опу́клих комбіна́цій. Метод першими запропонували 1956 року Маргарита Франк і Філіп Вульф. На кожній ітерації алгоритм Франк — Вульфа розглядає лінійне наближення цільової функції і рухається в напрямку мінімізації цієї лінійної функції (на тій самій множині допустимих розв'язків).

Формулювання задачі

Припустимо, що ${\mathcal {D}}$ — компактна опукла множина у векторному просторі, а $f\colon {\mathcal {D}}\to \mathbb {R}$ — опукла, диференційовна дійснозначна функція. Алгоритм Франк — Вульфа розв'язує задачу оптимізації: Мінімізувавши $f(\mathbf {x} )$

за умови $\mathbf {x} \in {\mathcal {D}}$.

Алгоритм

Крок алгоритму Франк — Вульфа

Ініціалізація: Нехай $k\leftarrow 0$ і нехай $\mathbf {x} _{0}\!$ буде точкою в ${\mathcal {D}}$.

Крок 1. Підзадача пошуку напрямку: Знаходимо $\mathbf {s} _{k}$, яке розв'язує задачу

Мінімізувати $\mathbf {s} ^{T}\nabla f(\mathbf {x} _{k})$

за умов $\mathbf {s} \in {\mathcal {D}}$

(Інтерпретація: мінімізуємо лінійне наближення задачі, отримане апроксимацією Тейлора першого порядку функції $f$ поблизу $\mathbf {x} _{k}\!$.)

Крок 2. Визначення розміру кроку: Нехай $\gamma \leftarrow {\frac {2}{k+2}}$, або, альтернативно, знаходимо $\gamma$, яке мінімізує $f(\mathbf {x} _{k}+\gamma (\mathbf {s} _{k}-\mathbf {x} _{k}))$ за умови $0\leqslant \gamma \leqslant 1$ .

Крок 3. Перерахунок: Нехай $\mathbf {x} _{k+1}\leftarrow \mathbf {x} _{k}+\gamma (\mathbf {s} _{k}-\mathbf {x} _{k})$, $k\leftarrow k+1$ і переходимо до кроку 1.

Властивості

Тоді як конкурентні методи, такі як градієнтний спуск для оптимізації з обмеженнями, вимагають на кожній ітерації кроку проєктування у множину допустимих значень, для алгоритму Франк — Вульфа потрібно на кожній ітерації лише розв'язати задачу лінійного програмування на тій самій самій множині, так що розв'язок завжди залишається належним множині допустимих розв'язків.

Збіжність алгоритму Франк — Вульфа в загальному випадку сублінійна — помилка цільової функції відносно оптимального значення після k ітерацій дорівнює $O(1/k)$ за умови, що градієнт неперервний за Ліпшицом за деякою нормою. Таку ж збіжність можна показати, якщо підзадачі розв'язуються лише наближено.

Ітерації алгоритму можна завжди подати як нещільну опуклу комбінацію екстремальних точок множини допустимих розв'язків, що допомогло популярності алгоритму для задач розрідженої жадібної оптимізації в машинному навчанні і обробці сигналів, а також для знаходження потоків мінімальної вартості в транспортних мережах.

Якщо множину допустимих розв'язків задано набором лінійних нерівностей, то підзадача, розв'язувана на кожній ітерації, стає задачею лінійного програмування.

Хоча швидкість збіжності в гіршому випадку $O(1/k)$ для загального випадку не можна покращити, вищу швидкість збіжності можна отримати для спеціальних задач, таких як строго опуклі задачі.

Нижні межі на значення розв'язку і прямо-двоїстий аналіз

Оскільки функція $f$ опукла, для будь-яких двох точок $\mathbf {x} ,\mathbf {y} \in {\mathcal {D}}$ маємо:

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

Це виконується також для (невідомого) оптимального розв'язку $\mathbf {x} ^{*}$. Тобто $f(\mathbf {x} ^{*})\geqslant f(\mathbf {x} )+(\mathbf {x} ^{*}-\mathbf {x} )^{T}\nabla f(\mathbf {x} )$. Краща нижня межа з урахуванням точки $\mathbf {x}$ задається формулою

${\begin{aligned}f(\mathbf {x} ^{*})&\geqslant f(\mathbf {x} )+(\mathbf {x} ^{*}-\mathbf {x} )^{T}\nabla f(\mathbf {x} )\\&\geqslant \min _{\mathbf {y} \in D}\left\{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}}$

Ця остання задача розв'язується на кожній ітерації алгоритму Франк — Вульфа, тому розв'язок $\mathbf {s} _{k}$ підзадачі знаходження напрямку на $k$-й ітерації можна використати для визначення зростаючих нижніх меж $l_{k}$ на кожній ітерації присвоєнням $l_{0}=-\infty$ і

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

Такі нижні межі на невідоме оптимальне значення на практиці дуже важливі, оскільки їх можна використати як критерій зупинки алгоритму і вони на кожній ітерації дають ефективний показник якості наближення, оскільки завжди $l_{k}\leqslant f(\mathbf {x} ^{*})\leqslant f(\mathbf {x} _{k})$.

Показано, що розрив двоїстості, що є різницею між $f(\mathbf {x} _{k})$ і нижньою межею $l_{k}$, зменшується з тією ж швидкістю, тобто $f(\mathbf {x} _{k})-l_{k}=O(1/k).$

Література

• Левитин Е.С., Поляк Б.Т. Методы минимизации при наличии ограничений // Ж. вычисл. матем. и матем. физ.. — 1966. — Т. 6, вип. 5. — DOI:10.1016/0041-5553(66)90114-5.
• Frank M., Wolfe P. An algorithm for quadratic programming // Naval Research Logistics Quarterly. — 1956. — Т. 3, вип. 1–2. — С. 95–110. — DOI:10.1002/nav.3800030109.
• Dunn J. C., Harshbarger S. Conditional gradient algorithms with open loop step size rules // Journal of Mathematical Analysis and Applications. — 1978. — Т. 62, вип. 2. — С. 432. — DOI:10.1016/0022-247X(78)90137-3.
• Clarkson K. L. Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm // ACM Transactions on Algorithms. — 2010. — Т. 6, вип. 4. — С. 1–30. — DOI:10.1145/1824777.1824783.
• A modified Frank-Wolfe algorithm for solving the traffic assignment problem // Transportation Research Part B: Methodological. — 1984. — Т. 18, вип. 2. — DOI:10.1016/0191-2615(84)90029-8.
• Dimitri Bertsekas. Nonlinear Programming. — Athena Scientific, 1999. — С. 215. — ISBN 978-1-886529-00-7.
• Martin Jaggi. Revisiting Frank–Wolfe: Projection-Free Sparse Convex Optimization // Journal of Machine Learning Research: Workshop and Conference Proceedings. — 2013. — Т. 28, вип. 1. — С. 427–435. Архівовано з джерела 17 листопада 2016. Процитовано 8 травня 2022. (Оглядова стаття)
• Опис алгоритму Франк — Вульфа [Архівовано 7 травня 2021 у Wayback Machine.] (англ.)
• Jorge Nocedal, Stephen J. Wright. Numerical Optimization. — 2nd. — Berlin, New York : Springer-Verlag, 2006. — ISBN 978-0-387-30303-1.
• 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.

Посилання

• Маргарита Франк розповідає про історію алгоритму на YouTube

Див. також

• Метод проксимального градієнта