Перегляд вихідного коду сторінки Алгоритм Франк — Вульфа

'''Алгори́тм Франк-Ву́льфа'''<ref>Алгоритм розробили Маргарита Франк і Філіп Вульф, тому поширена в літературі назва ''Алгоритм '''Франка'''&nbsp;— Вульфа'' є помилковою.</ref>&nbsp;— це [[Метод ітерації|ітеративний]] [[алгоритм]] [[Оптимізація (математика)|оптимізації]] {{Не перекладено|Наближення першого порядку|першого порядку|en|First-order approximation}} для [[Опукла оптимізація|опуклої оптимізації]] [[Умовний екстремум|з обмеженнями]]. Алгоритм відомий також як '''ме́тод умо́вного градіє́нта'''{{Sfn|Левитин, Поляк|1966|с=787-823}}, '''ме́тод зве́деного градіє́нта''' і '''алгори́тм опу́клих комбіна́цій'''. Метод першими запропонували 1956 року {{Не перекладено|Маргарита Франк||en|Marguerite Frank}} і {{Не перекладено|Філіп Вульф||en|Philip Wolfe (mathematician)}}{{Sfn|Frank, Wolfe|1956|с=95–110}}. На кожній ітерації алгоритм Франк&nbsp;— Вульфа розглядає [[лінійне наближення]] цільової функції і рухається в напрямку мінімізації цієї лінійної функції (на тій самій множині допустимих розв'язків).

== Формулювання задачі ==
Припустимо, що <math>\mathcal{D}</math>&nbsp;— [[Компактний простір|компактна]] [[опукла множина]] у [[Векторний простір|векторному просторі]], а <math>f \colon \mathcal{D} \to \mathbb{R}</math>&nbsp;— [[Опукла функція|опукла]], [[Диференційовна функція|диференційовна]] [[дійснозначна функція]]. Алгоритм Франк&nbsp;— Вульфа розв'язує [[Оптимізація (математика)|задачу оптимізації]]: Мінімізувавши <math> f(\mathbf{x})</math>
: за умови <math> \mathbf{x} \in \mathcal{D}</math>.

== Алгоритм ==
[[Файл:Frank-Wolfe_Algorithm.png|праворуч|міні|Крок алгоритму Франк&nbsp;— Вульфа]]

: ''Ініціалізація:'' Нехай <math>k \leftarrow 0</math> і нехай <math>\mathbf{x}_0 \!</math> буде точкою в <math>\mathcal{D}</math>.

: '''Крок 1.''' ''Підзадача пошуку напрямку:'' Знаходимо <math>\mathbf{s}_k</math>, яке розв'язує задачу
:: Мінімізувати <math> \mathbf{s}^T \nabla f(\mathbf{x}_k)</math>
:: за умов <math>\mathbf{s} \in \mathcal{D}</math>
: ''(Інтерпретація: мінімізуємо лінійне наближення задачі, отримане [[Ряд Тейлора|апроксимацією Тейлора]] першого порядку функції <math>f</math> поблизу <math>\mathbf{x}_k \!</math>.)''

: '''Крок 2.''' ''Визначення розміру кроку:'' Нехай <math>\gamma \leftarrow \frac{2}{k+2}</math>, або, альтернативно, знаходимо <math>\gamma</math>, яке мінімізує <math> f(\mathbf{x}_k+\gamma(\mathbf{s}_k -\mathbf{x}_k))</math> за умови <math>0 \leqslant \gamma \leqslant 1</math> .

: '''Крок 3.''' ''Перерахунок:'' Нехай <math>\mathbf{x}_{k+1}\leftarrow \mathbf{x}_k+\gamma(\mathbf{s}_k-\mathbf{x}_k)</math>, <math>k \leftarrow k+1</math> і переходимо до кроку 1.

== Властивості ==
Тоді як конкурентні методи, такі як [[градієнтний спуск]] для оптимізації з обмеженнями, вимагають на кожній ітерації [[Проєкція (математика)|кроку проєктування]] у множину допустимих значень, для алгоритму Франк&nbsp;— Вульфа потрібно на кожній ітерації лише розв'язати задачу лінійного програмування на тій самій самій множині, так що розв'язок завжди залишається належним множині допустимих розв'язків.

Збіжність алгоритму Франк&nbsp;— Вульфа в загальному випадку сублінійна&nbsp;— помилка цільової функції відносно оптимального значення після ''k'' ітерацій дорівнює <math>O(1/k)</math> за умови, що градієнт [[Ліпшицеве відображення|неперервний за Ліпшицом]] за деякою нормою. Таку ж збіжність можна показати, якщо підзадачі розв'язуються лише наближено{{Sfn|Dunn, Harshbarger|1978|с=432}}.

Ітерації алгоритму можна завжди подати як нещільну опуклу комбінацію екстремальних точок множини допустимих розв'язків, що допомогло популярності алгоритму для задач розрідженої жадібної оптимізації в [[Машинне навчання|машинному навчанні]] і [[Обробка сигналів|обробці сигналів]]{{Sfn|Clarkson|2010|с=1–30}}, а також для знаходження [[Потокова мережа|потоків мінімальної вартості]] в транспортних мережах{{Sfn|Fukushima|1984|с=169–177}}.

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

Хоча швидкість збіжності в гіршому випадку <math>O(1/k)</math> для загального випадку не можна покращити, вищу швидкість збіжності можна отримати для спеціальних задач, таких як строго опуклі задачі{{Sfn|Bertsekas|1999|с=215}}.

== Нижні межі на значення розв'язку і прямо-двоїстий аналіз ==
Оскільки функція <math>f</math> [[Опукла функція|опукла]], для будь-яких двох точок <math>\mathbf{x}, \mathbf{y} \in \mathcal{D}</math> маємо:

: <math>
 f(\mathbf{y}) \geqslant f(\mathbf{x}) + (\mathbf{y} - \mathbf{x})^T \nabla f(\mathbf{x})
</math>

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

: <math>
 \begin{align}
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{align}
</math>

Ця остання задача розв'язується на кожній ітерації алгоритму Франк&nbsp;— Вульфа, тому розв'язок <math>\mathbf{s}_k</math> підзадачі знаходження напрямку на <math>k</math>-й ітерації можна використати для визначення зростаючих нижніх меж <math>l_k</math> на кожній ітерації присвоєнням <math>l_0 = - \infty</math> і

: <math>
 l_k := \max (l_{k - 1}, f(\mathbf{x}_k) + (\mathbf{s}_k - \mathbf{x}_k)^T \nabla f(\mathbf{x}_k))
</math>

Такі нижні межі на невідоме оптимальне значення на практиці дуже важливі, оскільки їх можна використати як критерій зупинки алгоритму і вони на кожній ітерації дають ефективний показник якості наближення, оскільки завжди <math>l_k \leqslant f(\mathbf{x}^*) \leqslant f(\mathbf{x}_k)</math>.

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

== Примітки ==
{{Reflist|2}}

== Література ==
{{Refbegin|colwidth=30em}}
* {{Стаття|author=Левитин Е.С., Поляк Б.Т.|ref=Левитин, Поляк|doi=10.1016/0041-5553(66)90114-5|title=Методы минимизации при наличии ограничений|видання=Ж. вычисл. матем. и матем. физ.|том=6|issue=5|рік=1966}}
* {{Стаття|author=Frank M., Wolfe P.|ref=Frank, Wolfe|doi=10.1002/nav.3800030109|title=An algorithm for quadratic programming|видання=Naval Research Logistics Quarterly|том=3|issue=1–2|pages=95–110|рік=1956}}
* {{Стаття|author=Dunn J. C., Harshbarger S.|ref=Dunn, Harshbarger|doi=10.1016/0022-247X(78)90137-3|title=Conditional gradient algorithms with open loop step size rules|видання=Journal of Mathematical Analysis and Applications|том=62|issue=2|pages=432|рік=1978}}
* {{Стаття|author=Clarkson K. L.|ref=Clarkson|title=Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm|doi=10.1145/1824777.1824783|видання=ACM Transactions on Algorithms|том=6|issue=4|pages=1–30|рік=2010}}
* {{Стаття|Fukushima M.|title=A modified Frank-Wolfe algorithm for solving the traffic assignment problem|doi=10.1016/0191-2615(84)90029-8|видання=Transportation Research Part B: Methodological|том=18|issue=2|рік=1984}}
* {{Книга
|заголовок = Nonlinear Programming
|автор = Dimitri Bertsekas
|ref = Bertsekas
|рік = 1999
|сторінки = 215
|видавництво = Athena Scientific
|ISBN = 978-1-886529-00-7
}}
* {{Стаття|author=Martin Jaggi|ref=Jaggi|title=Revisiting Frank–Wolfe: Projection-Free Sparse Convex Optimization|видання=Journal of Machine Learning Research: Workshop and Conference Proceedings|том=28|issue=1|pages=427–435|рік=2013|url=http://jmlr.csail.mit.edu/proceedings/papers/v28/jaggi13.html|accessdate=8 травня 2022|archivedate=17 листопада 2016|archiveurl=https://web.archive.org/web/20161117205744/http://jmlr.csail.mit.edu/proceedings/papers/v28/jaggi13.html}} (Оглядова стаття) 
* [http://www.math.chalmers.se/Math/Grundutb/CTH/tma946/0203/fw_eng.pdf Опис алгоритму Франк&nbsp;— Вульфа] {{Webarchive|url=https://web.archive.org/web/20210507004343/http://www.math.chalmers.se/Math/Grundutb/CTH/tma946/0203/fw_eng.pdf |date=7 травня 2021 }} {{ref-en}}
* {{Книга
|автор = Jorge Nocedal, Stephen J. Wright
|заголовок = Numerical Optimization
|видавництво = [[Springer Science+Business Media|Springer-Verlag]]
|місце = Berlin, New York
|видання = 2nd
|ISBN = 978-0-387-30303-1
|рік = 2006
}}
* {{Cite journal|last=Fukushima|first=M.|year=1984|title=A modified Frank-Wolfe algorithm for solving the traffic assignment problem|journal=Transportation Research Part B: Methodological|volume=18|issue=2|pages=169–177|doi=10.1016/0191-2615(84)90029-8|ref=Fukushima}}
{{Refend}}

== Посилання ==
* {{YouTube|24e08AX9Eww|Маргарита Франк розповідає про історію алгоритму}}

== Див. також ==
* [[Метод проксимального градієнта]]

{{Бібліоінформація}}
{{Алгоритми оптимізації}}

[[Категорія:Градієнтні методи]]
[[Категорія:Алгоритми оптимізації]]
[[Категорія:1956 у науці]]
[[Категорія:Методи першого порядку]]