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

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

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

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

за умови $𝐱\in 𝒟$.

Алгоритм

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

Ініціалізація: Нехай $k\leftarrow 0$ і нехай ${𝐱}_0$ буде точкою в $𝒟$.

Крок 1. Підзадача пошуку напрямку: Знаходимо ${𝐬}_k$, яке розв'язує задачу

Мінімізувати ${𝐬}^T\mathrm{\nabla }f({𝐱}_k)$

за умов $𝐬\in 𝒟$

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

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

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

Властивості

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

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

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

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

Хоча швидкість збіжності в гіршому випадку $O(1/k)$ для загального випадку не можна покращити, вищу швидкість збіжності можна отримати для спеціальних задач, таких як строго опуклі задачіШаблон:Sfn.

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

Оскільки функція $f$ опукла, для будь-яких двох точок $𝐱,𝐲\in 𝒟$ маємо:

$f(𝐲)⩾f(𝐱)+(𝐲-𝐱{)}^T\mathrm{\nabla }f(𝐱)$

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

$\begin{array}{cc}f({𝐱}^{*})& ⩾f(𝐱)+({𝐱}^{*}-𝐱{)}^T\mathrm{\nabla }f(𝐱)\\ & ⩾\underset{𝐲\in D}{\min }\{f(𝐱)+(𝐲-𝐱{)}^T\mathrm{\nabla }f(𝐱)\}\\ & =f(𝐱)-{𝐱}^T\mathrm{\nabla }f(𝐱)+\underset{𝐲\in D}{\min }{𝐲}^T\mathrm{\nabla }f(𝐱)\end{array}$

Ця остання задача розв'язується на кожній ітерації алгоритму Франк — Вульфа, тому розв'язок ${𝐬}_k$ підзадачі знаходження напрямку на $k$-й ітерації можна використати для визначення зростаючих нижніх меж $l_k$ на кожній ітерації присвоєнням $l_0=-\mathrm{\infty }$ і

$l_k:=\max (l_{k-1},f({𝐱}_k)+({𝐬}_k-{𝐱}_k{)}^T\mathrm{\nabla }f({𝐱}_k))$

Такі нижні межі на невідоме оптимальне значення на практиці дуже важливі, оскільки їх можна використати як критерій зупинки алгоритму і вони на кожній ітерації дають ефективний показник якості наближення, оскільки завжди $l_k⩽f({𝐱}^{*})⩽f({𝐱}_k)$.

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

Література

• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Книга
• Шаблон:Стаття (Оглядова стаття)
• Опис алгоритму Франк — Вульфа Шаблон:Webarchive Шаблон:Ref-en
• Шаблон:Книга
• Шаблон:Cite journal

Посилання

• Шаблон:YouTube

Див. також

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