метод Брегмана

Метод Брегмана — это итерационный алгоритм для решения некоторых выпуклой оптимизации, задач включающих регуляризацию . Оригинальная версия принадлежит Льву М. Брегману , опубликовавшему ее в 1967 году.

Алгоритм представляет собой метод действия по строкам, осуществляющий доступ к функциям ограничений одну за другой, и этот метод особенно подходит для больших задач оптимизации, где ограничения могут быть эффективно пронумерованы. . Алгоритм особенно хорошо работает для регуляризаторов, таких как $\ell _{1}$ норма, где она сходится очень быстро из-за эффекта компенсации ошибок.

Алгоритм

Чтобы иметь возможность использовать метод Брегмана, необходимо сформулировать интересующую проблему как поиск $\min _{u}J(u)+f(u)$, где $J$ является регуляризирующей функцией, такой как $\ell _{1}$.

Расстояние Брегмана определяется как $D^{p}(u,v):=J(u)-(J(v)+\langle p,u-v\rangle )$ где $p$ принадлежит субдифференциалу ​ $J$ в $u$ (который мы обозначили $\partial J(u)$). Выполняется итерация $u_{k+1}:=\min _{u}(\alpha D(u,u_{k})+f(u))$, с $\alpha$ константа, выбираемая пользователем (и минимизация, выполняемая обычным алгоритмом выпуклой оптимизации), или $u_{k+1}:=\min _{u}(D^{p_{k}}(u,u_{k})+f(u))$, с $p_{k}$ каждый раз выбирался в качестве члена $\partial J(u_{k})$.

Алгоритм начинается с пары простых и двойственных переменных. Затем для каждого ограничения выполняется обобщенная проекция на его допустимый набор, обновляя как двойственную переменную ограничения, так и все основные переменные, для которых есть ненулевые коэффициенты в градиенте функций ограничений. В случае, если цель строго выпукла и все функции ограничений выпуклы, предел этой итеративной проекции сходится к оптимальной прямой дуальной паре.

В случае преследования базиса задачи типа $\min _{x:Ax=b}(|x|_{1}+{\frac {1}{2\alpha }}|x|_{2}^{2})$, метод Брегмана эквивалентен обычному градиентному спуску в двойственной задаче $\min _{y}(-b^{t}y+{\frac {\alpha }{2}}|A^{t}y-{\text{Proj}}_{[-1,1]^{n}}(A^{t}y)|^{2})$. В этом случае также имеет место точный эффект типа регуляризации; если $\alpha$ превышает определенный порог, оптимальное значение $x$ это именно оптимальное решение $\min _{x:Ax=b}|x|_{1}$.

Приложения

Метод Брегмана или его обобщения можно применять для:

• Удаление размытия изображения или шумоподавление (включая общее шумоподавление )
• МРТ-изображение реконструкция
• Магнитно-резонансная томография
• Радар
• Гиперспектральная визуализация
• Сжатое зондирование
• Наименьшие абсолютные отклонения или $\ell _{1}$-регуляризованная линейная регрессия
• Ковариационный выбор (обучение разреженной ковариационной матрицы)
• Завершение матрицы
• Структурная минимизация рисков

Обобщения и недостатки

Метод имеет связи с методом множителей и методом двойного восхождения (посредством так называемого метода чередующихся направлений множителей Брегмана) . обобщая метод чередующихся множителей ) и существует множество обобщений.

Одним из недостатков метода является то, что он доказуемо сходится только в том случае, если целевая функция строго выпукла. В случае, если это невозможно обеспечить, как для линейных программ или нестрого выпуклых квадратичных программ, дополнительные методы, такие как методы проксимального градиента . разработаны В случае Рудина-Ошера-Фатеми модели шумоподавления изображения , метод Брегмана доказуемо сходится.

Некоторые обобщения метода Брегмана включают:

• Метод обратного масштаба пространства
• Линеаризованный Брегман
• Логистический Брегман
• Сплит Брегман

Линеаризованный Брегман

В линеаризованном методе Брегмана линеаризуются промежуточные целевые функции. $D^{p}(u,u_{k})+f(u)$ заменив второе слагаемое на $f(u_{k})+\langle f'(u_{k}),u-u_{k}\rangle$ (что приближает второй член вблизи $u_{k}$) и добавление срока наказания ${\frac {1}{2\delta }}|u-u_{k}|_{2}^{2}$ для постоянного $\delta$. Результат становится гораздо более доступным в вычислительном отношении, особенно в поиска базиса . задачах типа В случае общей задачи преследования базиса $\min \mu |u|_{1}+{\frac {1}{2}}|Au-f|_{2}^{2}$, можно выразить итерацию как $v_{k+1}:=v_{k}+A^{t}(f-Au_{k}),u_{k+1,i}:=\delta ~{\text{shrink}}(v_{k,i},\mu )$ для каждого компонента $i$, где мы определяем ${\text{shrink}}(y,a):={\begin{cases}y-a,&y\in (a,\infty )\\0,&y\in [-a,a]\\y+a,&y\in (-\infty ,-a)\end{cases}}$.

Иногда при использовании линеаризованного метода Брегмана бывают периоды «застоя», когда остаток практически постоянен. Чтобы облегчить эту проблему, можно использовать линеаризованный метод Брегмана с пинком , где по существу обнаруживается начало периода застоя, затем прогнозируется и переходит к его концу.

Поскольку линеаризованный метод Брегмана математически эквивалентен градиентному спуску, его можно ускорить с помощью методов ускорения градиентного спуска, таких как поиск линии, L-BGFS , шаги Барзилай-Борвейна или метод Нестерова ; последний был предложен как ускоренный линеаризованный метод Брегмана .

Сплит Брегман

Метод Сплит-Брегмана решает задачи вида $\min _{u}|\Phi (u)|_{1}+H(u)$, где $\Phi$ и $H$ оба выпуклые, особенно проблемы формы $\min _{u}|\Phi u|_{1}+|Ku-f|^{2}$. Начнем с того, что перепишем ее как задачу ограниченной оптимизации. $\min _{u:d=\Phi (u)}|d|_{1}+H(u)$, затем расслабьте его в $\min _{u,d}|d|_{1}+H(u)+{\frac {\lambda }{2}}|d-\Phi (u)|_{2}^{2}$ где $\lambda$ является константой. Определив $J(u,d):=|d|+H(u)$, можно свести задачу к задаче, которую можно решить с помощью обычного алгоритма Брегмана.

Метод Сплит-Брегмана был обобщен для оптимизации комплексных чисел с использованием производных Виртингера .