Субградиентный метод
Субградиентные методы — это методы выпуклой оптимизации , в которых используются субпроизводные . Первоначально разработанные Наумом З. Шором и другими в 1960-х и 1970-х годах, субградиентные методы сходятся, когда применяются даже к недифференцируемой целевой функции. Когда целевая функция дифференцируема, субградиентные методы для задач без ограничений используют то же направление поиска, что и метод наискорейшего спуска .
Субградиентные методы работают медленнее, чем метод Ньютона, когда они применяются для минимизации дважды непрерывно дифференцируемых выпуклых функций. Однако метод Ньютона не может сходиться в задачах, имеющих недифференцируемые изломы.
В последние годы некоторые методы внутренней точки для решения задач выпуклой минимизации были предложены , но методы проекции субградиента и связанные с ними пучковые методы спуска остаются конкурентоспособными. Для задач выпуклой минимизации с очень большим количеством измерений подходят методы субградиентной проекции, поскольку они требуют небольшого объема памяти.
Методы субградиентного проецирования часто применяются для решения крупномасштабных задач с помощью методов декомпозиции. Такие методы декомпозиции часто позволяют использовать простой распределенный метод решения проблемы.
Классические правила субградиента
[ редактировать ]Позволять быть выпуклой функцией с областью определения Классический субградиентный метод повторяет где обозначает любой субградиент в и это итерация Если дифференцируема, то ее единственным субградиентом является вектор градиента сам.Может случиться так, что не является направлением спуска для в Поэтому мы ведем список который отслеживает наименьшее найденное на данный момент значение целевой функции, т.е.
Правила размера шага
[ редактировать ]В субградиентных методах используется множество различных типов правил размера шага. В этой статье отмечаются пять классических правил размера шага, для которых доказательства известны сходимости:
- Постоянный размер шага,
- Постоянная длина шага, что дает
- Квадратно суммируемый, но не суммируемый размер шага, т.е. любой размер шага, удовлетворяющий
- Несуммируемое убывающее, т.е. любой размер шага, удовлетворяющий
- Несуммируемые убывающие длины шагов, т.е. где
Для всех пяти правил размеры шагов определяются «автономно», до итерации метода; размеры шагов не зависят от предыдущих итераций. Это «автономное» свойство субградиентных методов отличается от «онлайновых» правил размера шага, используемых для методов спуска для дифференцируемых функций: многие методы минимизации дифференцируемых функций удовлетворяют достаточным условиям сходимости Вульфа, где размеры шагов обычно зависят от текущая точка и текущее направление поиска. Подробное обсуждение правил размера шага для субградиентных методов, включая инкрементальные версии, дано в книгах Берцекаса. [1] и Берцекас, Недич и Оздаглар. [2]
Результаты конвергенции
[ редактировать ]Для постоянной длины шага и масштабированных субградиентов, имеющих евклидову норму , равную единице, метод субградиентов сходится к сколь угодно близкому приближению к минимальному значению, т.е.
Эти классические субградиентные методы имеют низкую производительность и больше не рекомендуются для общего использования. [4] [5] Однако они по-прежнему широко используются в специализированных приложениях, поскольку они просты и их можно легко адаптировать с учетом особой структуры рассматриваемой задачи.
Методы субградиентной проекции и расслоения
[ редактировать ]В 1970-е годы Клод Лемарешаль и Фил Вулф предложили «групповые методы» спуска для решения задач выпуклой минимизации. [6] С тех пор значение термина «пакетные методы» существенно изменилось. Современные версии и полный анализ конвергенции были предоставлены Kiwiel. [7] Современные пакетные методы часто используют правила « контроля уровня » для выбора размеров шага, развивая методы на основе метода «субградиентной проекции» Бориса Т. Поляка (1969). Однако существуют проблемы, в которых методы пакетирования дают мало преимуществ перед методами проекции субградиента. [4] [5]
Ограниченная оптимизация
[ редактировать ]Прогнозируемый субградиент
[ редактировать ]Одним из расширений метода субградиента является метод проецируемого субградиента , который решает оптимизации задачу с ограничениями.
- минимизировать при условии
где представляет собой выпуклое множество . Метод проецируемого субградиента использует итерацию где это проекция на и любой субградиент в
Общие ограничения
[ редактировать ]Метод субградиента можно расширить для решения проблемы с ограничениями в виде неравенства.
- минимизировать при условии
где являются выпуклыми. Алгоритм принимает ту же форму, что и случай без ограничений. где - это размер шага, и является субградиентом цели или одной из функций ограничений в точке Брать где обозначает субдифференциал Если текущая точка осуществима, алгоритм использует целевой субградиент; если текущая точка невозможна, алгоритм выбирает субградиент любого нарушенного ограничения.
См. также
[ редактировать ]- Стохастический градиентный спуск – алгоритм оптимизации
Ссылки
[ редактировать ]- ^ Берцекас, Дмитрий П. (2015). Алгоритмы выпуклой оптимизации (второе изд.). Бельмонт, Массачусетс: Athena Scientific. ISBN 978-1-886529-28-1 .
- ^ Берцекас, Дмитрий П.; Недич, Ангелия; Оздаглар, Асуман (2003). Выпуклый анализ и оптимизация (второе изд.). Бельмонт, Массачусетс: Athena Scientific. ISBN 1-886529-45-0 .
- ^ Приблизительная сходимость субградиентного метода с постоянным размером шага (масштабированного) изложена в упражнении 6.3.14(a) в Берцекасе (стр. 636): Берцекас, Дмитрий П. (1999). Нелинейное программирование (Второе изд.). Кембридж, Массачусетс: Athena Scientific. ISBN 1-886529-00-0 . На странице 636 Берцекас приписывает этот результат Шору: Шор, Наум З. (1985). Методы минимизации недифференцируемых функций . Спрингер-Верлаг . ISBN 0-387-12763-1 .
- ^ Jump up to: а б Лемарешаль, Клод (2001). «Лагранжева релаксация». В Михаэле Юнгере и Денисе Наддефе (ред.). Вычислительная комбинаторная оптимизация: доклады весенней школы, проходившей в замке Дагштуль, 15–19 мая 2000 г. Конспекты лекций по информатике. Том. 2241. Берлин: Springer-Verlag. стр. 112–156. дои : 10.1007/3-540-45586-8_4 . ISBN 3-540-42877-1 . МР 1900016 . S2CID 9048698 .
- ^ Jump up to: а б Кивиэль, Кшиштоф К.; Ларссон, Торбьёрн; Линдберг, ПО (август 2007 г.). «Лагранжева релаксация с помощью методов шарикового субградиента» . Математика исследования операций . 32 (3): 669–686. дои : 10.1287/moor.1070.0261 . МР 2348241 .
- ^ Берцекас, Дмитрий П. (1999). Нелинейное программирование (Второе изд.). Кембридж, Массачусетс: Athena Scientific. ISBN 1-886529-00-0 .
- ^ Кивил, Кшиштоф (1985). Методы спуска для недифференцируемой оптимизации . Берлин: Springer Verlag . п. 362. ИСБН 978-3540156420 . МР 0797754 .
Дальнейшее чтение
[ редактировать ]- Берцекас, Дмитрий П. (1999). Нелинейное программирование . Бельмонт, Массачусетс: Athena Scientific. ISBN 1-886529-00-0 .
- Берцекас, Дмитрий П.; Недич, Ангелия; Оздаглар, Асуман (2003). Выпуклый анализ и оптимизация (второе изд.). Бельмонт, Массачусетс: Athena Scientific. ISBN 1-886529-45-0 .
- Берцекас, Дмитрий П. (2015). Алгоритмы выпуклой оптимизации . Бельмонт, Массачусетс: Athena Scientific. ISBN 978-1-886529-28-1 .
- Шор, Наум З. (1985). Методы минимизации недифференцируемых функций . Спрингер-Верлаг . ISBN 0-387-12763-1 .
- Рущинский, Анджей (2006). Нелинейная оптимизация . Принстон, Нью-Джерси: Издательство Принстонского университета . стр. xii+454. ISBN 978-0691119151 . МР 2199043 .