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

Алгори́тм Франк-Ву́льфа^[1] — це ітеративний алгоритм оптимізації першого порядку для опуклої оптимізації з обмеженнями. Алгоритм відомий також як ме́тод умо́вного градіє́нта^[2], ме́тод зве́деного градіє́нта і алгори́тм опу́клих комбіна́цій. Метод першими запропонували 1956 року Маргарита Франк і Філіп Вульф^[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).}$

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

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