Метод Брегмана - это итерационный алгоритм для решения некоторых задач выпуклой оптимизации, включающих регуляризацию . [1] Оригинальная версия принадлежит Льву М. Брегману , который опубликовал ее в 1967 году. [2]
Алгоритм представляет собой метод строкового действия, обращающийся к функциям ограничений одну за другой, и этот метод особенно подходит для больших задач оптимизации, где ограничения могут быть эффективно перечислены [ необходима цитата ] . Алгоритм особенно хорошо работает для регуляризаторов, таких какnorm, где он сходится очень быстро из-за эффекта отмены ошибок. [3]
Алгоритм
Чтобы иметь возможность использовать метод Брегмана, нужно сформулировать интересующую задачу как нахождение , где является регуляризующей функцией, такой как . [3]
Расстояние Брегмана определяется как где принадлежит субдифференциалу из в (который мы обозначили ). [3] [4] Выполняется итерация., с участием константа, выбираемая пользователем (и минимизация, выполняемая обычным алгоритмом выпуклой оптимизации), [3] или, с участием выбирается каждый раз, чтобы быть членом . [4]
Алгоритм начинается с пары первичных и двойственных переменных. Затем для каждого ограничения выполняется обобщенная проекция на его допустимый набор, обновляя как двойственную переменную ограничения, так и все основные переменные, для которых есть ненулевые коэффициенты в градиенте функций ограничения. В случае, если цель строго выпуклая и все функции ограничений выпуклые, предел этой итерационной проекции сходится к оптимальной прямой двойственной паре. [ необходима цитата ]
В случае задачи типа преследования за базис, метод Брегмана эквивалентен обычному градиентному спуску на двойственной задаче. [5] В этом случае также возникает точный эффект типа регуляризации; если превышает определенный порог, оптимальное значение это как раз оптимальное решение . [3] [5]
Приложения
Метод Брегмана или его обобщения можно применять к:
- Удаление размытости изображения или шумоподавление [3] (включая полное изменение шумоподавления [4] )
- МР-изображение [ требуется уточнение ] реконструкция [3]
- Магнитно-резонансная томография [1] [6]
- Радар [1]
- Гиперспектральная визуализация [7]
- Сжатое зондирование [5]
- Наименьшие абсолютные отклонения или-регуляризованная линейная регрессия [8]
- Выбор ковариации (изучение разреженной матрицы ковариаций) [8]
- Завершение матрицы [9]
- Минимизация структурных рисков [8]
Обобщения и недостатки
Метод имеет ссылки на метод множителей и методу двойного подъема (через так называемый Брегман метод переменных направлений множителей , [10] [7] , обобщающих метод переменного направления множителей [8] ) и многочисленные обобщения существуют.
Одним из недостатков метода является то, что он доказуемо сходится только в том случае, если целевая функция строго выпуклая. В случае, если это не может быть обеспечено, как для линейных программ или нестрого выпуклых квадратичных программ, были разработаны дополнительные методы, такие как методы проксимального градиента . [ необходима цитата ] В случае модели шумоподавления изображения Рудина-Ошера-Фатеми [ требуется пояснение ] , метод Брегмана доказуемо сходится. [11]
Некоторые обобщения метода Брегмана включают:
- Метод обратного масштабного пространства [ требуется пояснение ] [3]
- Линеаризованный Брегман [3]
- Логистик Брегман [3]
- Сплит Брегман [3]
Линеаризованный Брегман
В линеаризованном методе Брегмана линеаризуются промежуточные целевые функции заменив второй член на (что приближает второй член около ) и прибавив срок штрафа для постоянного . Результат гораздо более податлив с вычислительной точки зрения, особенно в задачах базисного типа. [4] [5] В случае общей задачи поиска базиса, можно выразить итерацию как для каждого компонента , где мы определяем . [4]
Иногда при использовании линеаризованного метода Брегмана бывают периоды «застоя», когда остаток [ требуется уточнение ] почти постоянный. Чтобы решить эту проблему, можно использовать линеаризованный метод Брегмана с ударом ногой , при котором по существу определяют начало периода застоя, затем прогнозируют его и пропускают до его конца. [4] [5]
Поскольку линеаризованный спуск Брегмана математически эквивалентен градиентному спуску, его можно ускорить с помощью методов ускорения градиентного спуска, таких как линейный поиск, L-BGFS , шаги Барзилаи -Борвейна или метод Нестерова ; последний был предложен как ускоренный линеаризованный метод Брегмана . [5] [9]
Сплит Брегман
Метод Split Bregman решает задачи вида , где а также обе выпуклые, [4] в частности задачи вида. [6] Начнем с того, что переписываем ее как задачу оптимизации с ограничениями., затем расслабьте его в где является константой. Определив, проблема сводится к той, которую можно решить с помощью обычного алгоритма Брегмана. [4] [6]
Метод Сплит Брегмана был обобщен на оптимизацию комплексных чисел с использованием производных Виртингера . [1]
Рекомендации
- ^ а б в г Сюн, Кай; Чжао, Гуанхуй; Ши, Гуанмин; Ван, Инбинь (2019-09-12). "Выпуклый алгоритм оптимизации для сжатого зондирования в сложной области: комплекснозначный метод расщепления Брегмана" . Сенсоры (Базель) (опубликовано 18 октября 2019 г.). 19 (20): 4540. Bibcode : 2019Senso..19.4540X . DOI : 10.3390 / s19204540 . PMC 6832202 . PMID 31635423 .
- ^ Брегман Л. "Релаксационный метод поиска точки пересечения выпуклых множеств и его применение к задачам оптимизации". Докл. Акад. Наук СССР, т. 171, № 5, 1966, с. 1019-1022. (Английский перевод: Советская математика. Докл., Т. 7, 1966, стр. 1578-1581)
- ^ Б с д е е г ч я J K Инь, Wotao (8 декабря 2009 г.). «Методы Брегмана: обзор и новые результаты» (PDF) . Получено 16 апр 2021 .
- ^ Б с д е е г ч Буш, Жаклин (10 июня 2011 г.). "Калифорнийский университет, Санта-Барбара Старшая диссертация: алгоритмы Брегмана" (PDF) . Калифорнийский университет Санта-Барбары . Получено 16 апр 2021 .
- ^ а б в г д е Инь, Wotao (28 мая 2009 г.). "Анализ и обобщения линеаризованного метода Брегмана" (PDF) . SIAM Journal on Imaging Sciences . 3 (4): 856–877. DOI : 10.1137 / 090760350 . Получено 16 апр 2021 .
- ^ а б в Гольдштейн, Том; Ошер, Стэнли (2 июня 2008 г.). "Сплит-метод Брегмана для L1-регуляризованных задач" . SIAM J. Imaging Sci . 2 (2): 323–343. DOI : 10.1137 / 080725891 . Проверено 22 апр 2021 .
- ^ а б Цзян, Чунжи (май 2015 г.). «Сравнение ADMM с переменным штрафом и сплит-методом Брегмана для задач гиперспектральной визуализации» . Проверено 20 апр 2021 .
- ^ а б в г Бойд, Стивен; Парих, Нил; Чу, Эрик; Пелеато, Борха; Экштейн, Джонатан (19 ноября 2010 г.). «Распределенная оптимизация и статистическое обучение с помощью метода переменных направлений множителей» . Основы и тенденции в машинном обучении . 3 : 1–122. CiteSeerX 10.1.1.722.981 . DOI : 10.1561 / 2200000016 . Проверено 20 апр 2021 .
- ^ а б Хуанг, Бо; Ма, Шицянь; Гольдфарб, Дональд (27 июня 2011 г.). «Ускоренный линеаризованный метод Брегмана» (PDF) . Журнал научных вычислений . Plenum Press (опубликовано 1 февраля 2013 г.). 54 (2–3): 428–453. arXiv : 1106.5413 . DOI : 10.1007 / s10915-012-9592-9 . ISSN 0885-7474 . Проверено 22 апр 2021 .
- ^ Ван, Хуахуа; Банерджи, Ариндам (13 июня 2013 г.). «Метод переменного направления множителей Брегмана» . НИПС'14: Материалы 27-й Международной конференции по системам обработки нейронной информации . 2 : 2816–2824. arXiv : 1306,3203 . Проверено 20 апр 2021 .
- ^ Цзя, Жун-Цин (3 октября 2008 г.). «Анализ сходимости метода Брегмана для вариационной модели шумоподавления изображения» (PDF) . Прикладной и вычислительный гармонический анализ (опубликовано в ноябре 2009 г.). 27 (3): 367–379. DOI : 10.1016 / j.acha.2009.05.002 . Проверено 22 апр 2021 .