Метод Брэгмана — это итеративный алгоритм решения некоторых задач выпуклого программирования. Алгоритм поочерёдно просматривает одну за другой и метод особенно подходит для задач оптимизации большого размера, в которых можно эффективно перенумеровать ограничения. Исходная версия алгоритма принадлежит Льву Мееровичу Брэгману.
Алгоритм начинает с пары наборов переменных прямой и двойственной задач. Затем для каждого ограничения находится в множество допустимых решений, обновляя двойственные переменные ограничений и все переменные прямой задачи, для которых есть ненулевые коэффициенты в градиенте функций ограничений. В случае, когда целевая функция строго выпукла и все функции ограничений выпуклы, итеративные проекции сходятся к оптимальной паре переменных прямой и двойственной задач.
Метод имеет связь с методом множителей Лагранжа и двойственным методом наискорейшего подъёма (). Существует множество обобщений метода.
Одним из недостатков метода является то, что метод доказуемо сходится только если целевая функция строго выпукла. Если это нельзя гарантировать, как в случае задач линейного программирования или для нестрого выпуклых задач квадратичного программирования, нужно разрабатывать дополнительные методы, такие как метод проксимального градиента.
Ссылки The Bregman Iterative Procedure at Rice
Примечания
Литература
Категория:Алгоритмы и методы оптимизации Категория:Выпуклая оптимизация