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

ітеративний алгоритм для опуклої оптимізації першого порядку з обмеженнями

Алгори́тм Франк-Ву́льфа[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.

ЛітератураРедагувати

ПосиланняРедагувати

Див. такожРедагувати