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

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

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

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

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

Алгоритм

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

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

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

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

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

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

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

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

Властивості

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

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

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

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

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

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

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

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

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

${\displaystyle {\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}}}$

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

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

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

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

Примітки

1. Алгоритм розробили Маргарита Франк і Філіп Вульф, тому поширена в літературі назва Алгоритм Франка — Вульфа є помилковою.
2. Левитин, Поляк, 1966, с. 787-823.
3. Frank, Wolfe, 1956, с. 95–110.
4. Dunn, Harshbarger, 1978, с. 432.
5. Clarkson, 2010, с. 1–30.
6. Fukushima, 1984, с. 169–177.
7. Bertsekas, 1999, с. 215.

Література

• Левитин Е.С., Поляк Б.Т. Методы минимизации при наличии ограничений // Ж. вычисл. матем. и матем. физ.. — 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

Див. також

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