Алгори́тм Франк-Ву́льфаАлгоритм розробили Маргарита Франк і Філіп Вульф, тому поширена в літературі назва Алгоритм Франка — Вульфа є помилковою. — це ітеративний алгоритм оптимізації для опуклої оптимізації з обмеженнями. Алгоритм відомий також як ме́тод умо́вного градіє́нта, ме́тод зве́деного градіє́нта і алгори́тм опу́клих комбіна́цій. Метод першими запропонували 1956 року і . На кожній ітерації алгоритм Франк — Вульфа розглядає лінійне наближення цільової функції і рухається в напрямку мінімізації цієї лінійної функції (на тій самій множині допустимих розв'язків).
Формулювання задачі Припустимо, що — компактна опукла множина у векторному просторі, а — опукла, диференційовна дійснозначна функція. Алгоритм Франк — Вульфа розв'язує задачу оптимізації: Мінімізувавши за умови .
Алгоритм
Ініціалізація: Нехай і нехай буде точкою в .
Крок 1. Підзадача пошуку напрямку: Знаходимо , яке розв'язує задачу Мінімізувати за умов (Інтерпретація: мінімізуємо лінійне наближення задачі, отримане апроксимацією Тейлора першого порядку функції поблизу .)
Крок 2. Визначення розміру кроку: Нехай , або, альтернативно, знаходимо , яке мінімізує за умови .
Крок 3. Перерахунок: Нехай , і переходимо до кроку 1.
Властивості Тоді як конкурентні методи, такі як градієнтний спуск для оптимізації з обмеженнями, вимагають на кожній ітерації кроку проєктування у множину допустимих значень, для алгоритму Франк — Вульфа потрібно на кожній ітерації лише розв'язати задачу лінійного програмування на тій самій самій множині, так що розв'язок завжди залишається належним множині допустимих розв'язків.
Збіжність алгоритму Франк — Вульфа в загальному випадку сублінійна — помилка цільової функції відносно оптимального значення після k ітерацій дорівнює за умови, що градієнт неперервний за Ліпшицом за деякою нормою. Таку ж збіжність можна показати, якщо підзадачі розв'язуються лише наближено.
Ітерації алгоритму можна завжди подати як нещільну опуклу комбінацію екстремальних точок множини допустимих розв'язків, що допомогло популярності алгоритму для задач розрідженої жадібної оптимізації в машинному навчанні і обробці сигналів, а також для знаходження потоків мінімальної вартості в транспортних мережах.
Якщо множину допустимих розв'язків задано набором лінійних нерівностей, то підзадача, розв'язувана на кожній ітерації, стає задачею лінійного програмування.
Хоча швидкість збіжності в гіршому випадку для загального випадку не можна покращити, вищу швидкість збіжності можна отримати для спеціальних задач, таких як строго опуклі задачі.
Нижні межі на значення розв'язку і прямо-двоїстий аналіз Оскільки функція опукла, для будь-яких двох точок маємо:
Це виконується також для (невідомого) оптимального розв'язку . Тобто . Краща нижня межа з урахуванням точки задається формулою
Ця остання задача розв'язується на кожній ітерації алгоритму Франк — Вульфа, тому розв'язок підзадачі знаходження напрямку на -й ітерації можна використати для визначення зростаючих нижніх меж на кожній ітерації присвоєнням і
Такі нижні межі на невідоме оптимальне значення на практиці дуже важливі, оскільки їх можна використати як критерій зупинки алгоритму і вони на кожній ітерації дають ефективний показник якості наближення, оскільки завжди .
Показано, що розрив двоїстості, що є різницею між і нижньою межею , зменшується з тією ж швидкістю, тобто
Примітки
Література
(Оглядова стаття) Опис алгоритму Франк — Вульфа
Посилання
Див. також Метод проксимального градієнта