Метод проксимального градиента: различия между версиями
[отпатрулированная версия] | [отпатрулированная версия] |
Содержимое удалено Содержимое добавлено
м Удаление шаблонов: {{нп5}}×2 |
Liasmi (обсуждение | вклад) м оформление, проверка орф., пункт. |
||
Строка 1:
'''Метод проксимального градиента'''<ref>{{lang-en|Proximal}} = ближайший</ref>
Много интересных задач можно сформулировать как задачи выпуклого программирования вида
Строка 7:
</math>
где <math>f_i,\ i = 1, \dots, n</math>
Они называются проксимальными ({{lang-en|proximal}}, ближайший), поскольку каждая не[[гладкая функция]] среди <math>f_1, . . . , f_n</math> вовлекается в процесс через оператор близости. Итерационный алгоритм мягкой пороговой фильтрации{{sfn|Daubechies, Defrise, De Mol|2004|с=1413–1457}}, [[Итерация Ландвебера|проекция Ландвебера]], проекция градиента, {{не переведено 5|Проекция в выпуклое множество|попеременные проекции||alternating projection}}, {{не переведено 5|Метод обобщённого лагранжиана|метод чередующихся направлений мультипликаторов||Alternating direction method of multipliers}}, метод чередующихся расщеплений [[Метод Брэгмана|Брэгмана]] являются частными случаями проксимальных алгоритмов{{r|CP09}}. Для рассмотрения проксимальных градиентных методов со стороны [[Статистическая теория обучения|статистической теории обучения]] и приложений к этой теории
== Обозначения и терминология ==
Пусть <math>\mathbb{R}^N</math>, <math>N</math>-мерное [[
<math> f: \mathbb{R}^N \rightarrow (-\infty,+\infty]</math>. Предположим, что <math>C</math> является непустым выпуклым подмножеством множества <math>\mathbb{R}^N</math>. Тогда индикаторная функция множества <math>C</math> определяется как
: <math> \iota_C : x \mapsto
Строка 36:
== Проецирование в выпуклые множества ==
Одним из широко используемых выпуклых алгоритмов оптимизации является [[проецирование в выпуклые множества]]. Этот алгоритм используется для обнаружения/синтезирования сигнала, удовлетворяющего одновременно нескольким выпуклым ограничениям. Пусть <math>f_i</math> будет индикаторной функцией на непустом замкнутом выпуклом множестве <math>C_i</math>, моделирующей ограничение. Это сводит задачу к задаче выпуклой осуществимости (достижимости), в которой нужно найти решение, содержащееся в пересечении всех выпуклых множеств <math>C_i</math>. В методe проецирования в выпуклые множества каждое множество <math>C_i</math> ассоциируется с его
▲Одним из широко используемых выпуклых алгоритмов оптимизации является [[проецирование в выпуклые множества]]. Этот алгоритм используется для обнаружения/синтезирования сигнала, удовлетворяющего одновременно нескольким выпуклым ограничениям. Пусть <math>f_i</math> будет индикаторной функцией на непустом замкнутом выпуклом множестве <math>C_i</math>, моделирующей ограничение. Это сводит задачу к задаче выпуклой осуществимости (достижимости), в которой нужно найти решение, содержащееся в пересечении всех выпуклых множеств <math>C_i</math>. В методe проецирования в выпуклые множества каждое множество <math>C_i</math> ассоциируется с его [[Проектор (математика)|проектором]] <math>P_{C_i}</math>. Таким образом, на каждой [[Итерация (математика)|итерации]] <math>x</math> пересчитывается по формуле
: <math>x_{k+1} = P_{C_1} P_{C_2} \cdots P_{C_n} x_k</math>
Однако за пределами таких задач [[Проектор (математика)|проекторы]] не подходят и требуются операторы более общего вида. Среди различных существующих обобщений понятия выпуклого проектора
== Определение ==
{{не переведено 5|Проксимальный оператор|Оператор близости||proximal operator}} выпуклой функции <math>f</math> в точке <math>x</math> определяется как единственное решение
: <math>
\operatorname{argmin}\limits_y \bigg( f(y) + \frac{1}{2} \left\| x-y \right\|_2^2 \bigg)
</math>
Строка 52 ⟶ 51 :
</math>
Заметим, что в случае, когда <math>f</math> является индикаторной функцией <math>\iota_C</math> некоторого выпуклого множества <math>C</math>
: <math>
Строка 75 ⟶ 74 :
</math>
Если <math>f</math> дифференцируема, то уравнение выше сводится к
: <math>
Строка 82 ⟶ 81 :
== Примеры ==
Частными случаями проксимальных градиентных методов
* [[Итерация Ландвебера|проекция Ландвебера]]
* {{не переведено 5|Попеременное проецирование|||Alternating projection}}
* {{не переведено 5|Метод обобщённого лагранжиана|метод чередующихся направлений мультипликаторов||Alternating direction method of multipliers}}
== См. также ==
Строка 92 ⟶ 91 :
* {{не переведено 5|Проксимальный оператор|||Proximal operator}}
== Примечания ==
{{примечания
<ref name=CP09>{{cite arXiv
|author=Patrick L. Combettes, Jean-Christophe Pesquet
Строка 101 ⟶ 100 :
}} Обсуждаются проксимальные методы в деталях</ref>
}}
== Литература ==
* {{статья
|автор=Daubechies I., Defrise M., De Mol C.
|ref= Daubechies, Defrise, De Mol
Строка 115 ⟶ 114 :
|doi=10.1002/cpa.20042
}}
* {{книга
|автор=Rockafellar R. T.
|ref=Rockafellar
Строка 131 ⟶ 130 :
|страницы=185–212
}}
== Ссылки ==
Строка 143 ⟶ 141 :
[[Категория:Градиентные методы]]
{{rq|checktranslate|style
|