Метод Брэгмана
Метод Брэгмана — это итеративный алгоритм решения некоторых задач выпуклого программирования. Алгоритм поочерёдно просматривает функции ограничения[англ.] одну за другой и метод особенно подходит для задач оптимизации большого размера, в которых можно эффективно перенумеровать ограничения. Исходная версия алгоритма принадлежит Льву Мееровичу Брэгману[1].
Алгоритм начинает с пары наборов переменных прямой и двойственной задач. Затем для каждого ограничения находится обобщённая проекция[англ.] в множество допустимых решений, обновляя двойственные переменные ограничений и все переменные прямой задачи, для которых есть ненулевые коэффициенты в градиенте функций ограничений. В случае, когда целевая функция строго выпукла и все функции ограничений выпуклы, итеративные проекции сходятся к оптимальной паре переменных прямой и двойственной задач.
Метод имеет связь с методом множителей Лагранжа и двойственным методом наискорейшего подъёма (англ. dual ascent). Существует множество обобщений метода.
Одним из недостатков метода является то, что метод доказуемо сходится только если целевая функция строго выпукла. Если это нельзя гарантировать, как в случае задач линейного программирования или для нестрого выпуклых задач квадратичного программирования, нужно разрабатывать дополнительные методы, такие как метод проксимального градиента.
Ссылки[править | править код]
Примечания[править | править код]
- ↑ Брэгман, 1967, с. 620—631.
Литература[править | править код]
- Брэгман Л. М. Релаксационный метод нахождения общей точки выпуклых множеств и его применение для решения задач выпуклого программирования // Ж. вычисл. матем.и матем. физ.. — 1967. — Т. 7, № 3.