Метод Брегмана - Bregman method

Метод Брегмана является итерационный алгоритм решить определенные выпуклая оптимизация проблемы. Алгоритм представляет собой строковый метод доступ функции ограничения один за другим, и этот метод особенно подходит для больших задач оптимизации, где ограничения могут быть эффективно перечислены. Исходная версия связана с Лев М. Брегман.^[1]

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

У метода есть ссылки на метод множителей и метод двойного восхождения и существует множество обобщений.

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

внешняя ссылка

• Итерационная процедура Брегмана в Райсе

Рекомендации

1. Брегман Л. "Релаксационный метод поиска точки пересечения выпуклых множеств и его приложение к задачам оптимизации". Докл. Акад. Наук СССР, т. 171, № 5, 1966 г., п.п. 1019-1022. (Английский перевод: Советская математика. Докл., Т. 7, 1966, л. С. 1578-1581)