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

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

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

[ред. | ред. код]

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

за умови .

Алгоритм

[ред. | ред. код]
Крок алгоритму Франк — Вульфа
Ініціалізація: Нехай і нехай буде точкою в .
Крок 1. Підзадача пошуку напрямку: Знаходимо , яке розв'язує задачу
Мінімізувати
за умов
(Інтерпретація: мінімізуємо лінійне наближення задачі, отримане апроксимацією Тейлора першого порядку функції поблизу .)
Крок 2. Визначення розміру кроку: Нехай , або, альтернативно, знаходимо , яке мінімізує за умови .
Крок 3. Перерахунок: Нехай , і переходимо до кроку 1.

Властивості

[ред. | ред. код]

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

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

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

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

Хоча швидкість збіжності в гіршому випадку для загального випадку не можна покращити, вищу швидкість збіжності можна отримати для спеціальних задач, таких як строго опуклі задачі[7].

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

[ред. | ред. код]

Оскільки функція опукла, для будь-яких двох точок маємо:

Це виконується також для (невідомого) оптимального розв'язку . Тобто . Краща нижня межа з урахуванням точки задається формулою

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

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

Показано, що розрив двоїстості, що є різницею між і нижньою межею , зменшується з тією ж швидкістю, тобто

Примітки

[ред. | ред. код]
  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.

Посилання

[ред. | ред. код]

Див. також

[ред. | ред. код]