Метод проксимального градиента: различия между версиями

[отпатрулированная версия][отпатрулированная версия]
Содержимое удалено Содержимое добавлено
м Удаление шаблонов: {{нп5}}×2
м оформление, проверка орф., пункт.
Строка 1:
'''Метод проксимального градиента'''<ref>{{lang-en|Proximal}} = ближайший</ref>  — это обобщение проецирования, используемое для решения недифференцируемых задач [[Выпуклое программирование|выпуклого программирования]].
 
Много интересных задач можно сформулировать как задачи выпуклого программирования вида
Строка 7:
</math>
 
где <math>f_i,\ i = 1, \dots, n</math>  — [[Выпуклая функция|выпуклые функции]], определённые как отображения <math>f: \mathbb{R}^N \rightarrow \mathbb{R}</math>, где некоторые из функций недифференцируемы, что исключает обычные техники гладкой оптимизации, такие как [[Градиентный спуск|метод наискорейшего спуска]] или [[Метод сопряжённых градиентов (для решения СЛАУ)|метод сопряжённых градиентов]] и др., вместо них могут быть использованы проксимальные градиентные методы. Эти методы работают путём расщепления, так что функции <math>f_1, . . . , f_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}}. Для рассмотрения проксимальных градиентных методов со стороны [[Статистическая теория обучения|статистической теории обучения]] и приложений к этой теории, см. статью {{не переведено 5|Методы проксимального градиента для обучения машин|||proximal gradient methods for learning}}.
 
== Обозначения и терминология ==
Пусть <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>P_{C_i}</math>. Таким образом, на каждой [[Итерация (математика)|итерации]] <math>x</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}}
 
== Примечания ==
{{примечания|2|refs=
<ref name=CP09>{{cite arXiv
|author=Patrick L. Combettes, Jean-Christophe Pesquet
Строка 101 ⟶ 100 :
}} Обсуждаются проксимальные методы в деталях</ref>
}}
 
== Литература ==
{{refbegin|colwidth=30em}}
* {{статья
|автор=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
}}
{{refend}}
 
== Ссылки ==
Строка 143 ⟶ 141 :
[[Категория:Градиентные методы]]
 
{{rq|checktranslate|style|grammar}}