Субградиентный метод - Subgradient method - Wikipedia

Субградиентные методы находятся итерационные методы для решения выпуклая минимизация проблемы. Первоначально разработан Наум З. Шор и другие в 1960-х и 1970-х годах, субградиентные методы сходятся при применении даже к недифференцируемой целевой функции. Когда целевая функция является дифференцируемой, методы субградиента для неограниченных задач используют то же направление поиска, что и метод крутой спуск.

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

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

Методы субградиентной проекции часто применяются к крупномасштабным задачам с методами декомпозиции. Такие методы декомпозиции часто позволяют использовать простой распределенный метод для задачи.

Классические правила субградиента

Позволять быть выпуклая функция с доменом . Классический субградиентный метод повторяет

куда обозначает любой субградиент из в , и это повторение . Если дифференцируема, то ее единственный субградиент - вектор градиента может случиться так, что это не направление спуска для в . Поэтому мы ведем список который отслеживает наименьшее найденное значение целевой функции, т. е.

Правила размера шага

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

  • Постоянный размер шага,
  • Постоянная длина шага, , который дает
  • Суммируемый квадрат, но не суммируемый размер шага, т.е. любые размеры шага, удовлетворяющие
  • Несчетное уменьшение, т.е. любые размеры шага, удовлетворяющие
  • Невозможное уменьшение длины шага, т.е. , куда

Для всех пяти правил размеры шага определяются "в автономном режиме" перед повторением метода; размеры шага не зависят от предыдущих итераций. Это «автономное» свойство субградиентных методов отличается от «интерактивных» правил размера шага, используемых для методов спуска для дифференцируемых функций: многие методы минимизации дифференцируемых функций удовлетворяют достаточным условиям Вульфа для сходимости, где размеры шага обычно зависят от текущая точка и текущее направление поиска. Подробное обсуждение правил размера шага для субградиентных методов, включая инкрементные версии, дано в книгах Бертсекаса.[1]и Бертсекасом, Недичем и Оздагларом. [2]

Результаты сходимости

Для постоянной длины шага и масштабированных субградиентов, имеющих Евклидова норма равным единице, метод субградиента сходится к сколь угодно близкому приближению к минимальному значению, то есть

в результате Шор.[3]

Эти классические субградиентные методы имеют низкую производительность и больше не рекомендуются для общего использования.[4][5] Тем не менее, они по-прежнему широко используются в специализированных приложениях, поскольку они просты и могут быть легко адаптированы для использования преимуществ специальной структуры решаемой проблемы.

Методы субградиентной проекции и связки

В 1970-е годы Клод Лемарешаль и Фил Вулф предложили «связочные методы» спуска для задач выпуклой минимизации.[6] С тех пор значение термина «пакетные методы» значительно изменилось. Современные версии и полный анализ сходимости предоставлены Kiwiel.[7] Современные бандл-методы часто используют "уровень control "правила выбора размеров шага, разработка методов на основе метода" субградиентной проекции "Бориса Т. Поляка (1969). Однако существуют проблемы, в которых методы связки не имеют большого преимущества перед методами субградиентной проекции.[4][5]

Ограниченная оптимизация

Прогнозируемый субградиент

Одним из расширений метода субградиентов является прогнозируемый субградиентный метод, который решает задачу ограниченной оптимизации

свести к минимуму при условии

куда это выпуклый набор. Прогнозируемый метод субградиента использует итерацию

куда проекция на и любой субградиент в

Общие ограничения

Метод субградиента может быть расширен для решения задачи с ограничениями по неравенству

свести к минимуму при условии

куда выпуклые. Алгоритм имеет ту же форму, что и безусловный случай

куда размер шага, а является субградиентом цели или одной из функций ограничения при Брать

куда обозначает субдифференциальный из . Если текущая точка возможна, алгоритм использует целевой субградиент; если текущая точка неосуществима, алгоритм выбирает субградиент любого нарушенного ограничения.

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

  1. ^ Бертсекас, Дмитрий П. (2015). Алгоритмы выпуклой оптимизации (Второе изд.). Бельмонт, Массачусетс: Athena Scientific. ISBN  978-1-886529-28-1.
  2. ^ Bertsekas, Dimitri P .; Недич, Анжелиа; Оздаглар, Асуман (2003). Выпуклый анализ и оптимизация (Второе изд.). Бельмонт, Массачусетс: Athena Scientific. ISBN  1-886529-45-0.
  3. ^ Приблизительная сходимость метода субградиента с постоянным размером шага (масштабированного) изложена в упражнении 6.3.14 (a) в Бертсекас (стр. 636): Бертсекас, Дмитрий П. (1999). Нелинейное программирование (Второе изд.). Кембридж, Массачусетс: Athena Scientific. ISBN  1-886529-00-0. На странице 636 Бертсекас приписывает этот результат Шору: Шор, Наум З. (1985). Методы минимизации недифференцируемых функций. Springer-Verlag. ISBN  0-387-12763-1.
  4. ^ а б Лемарешаль, Клод (2001). «Лагранжева релаксация». В Михаэле Юнгере и Денисе Наддефе (ред.). Вычислительная комбинаторная оптимизация: доклады весенней школы, прошедшей в Шлос-Дагштуле, 15–19 мая 2000 г.. Конспект лекций по информатике. 2241. Берлин: Springer-Verlag. С. 112–156. Дои:10.1007/3-540-45586-8_4. ISBN  3-540-42877-1. МИСТЕР  1900016.CS1 maint: ref = harv (связь)
  5. ^ а б Kiwiel, Krzysztof C .; Ларссон, Торбьорн; Линдберг, П. О. (август 2007 г.). «Лагранжева релаксация с помощью методов шарикового субградиента». Математика исследования операций. 32 (3): 669–686. Дои:10.1287 / moor.1070.0261. МИСТЕР  2348241.CS1 maint: ref = harv (связь)
  6. ^ Бертсекас, Дмитрий П. (1999). Нелинейное программирование (Второе изд.). Кембридж, Массачусетс: Athena Scientific. ISBN  1-886529-00-0.
  7. ^ Кивель, Кшиштоф (1985). Методы спуска для недифференцируемой оптимизации. Берлин: Springer Verlag. п. 362. ISBN  978-3540156420. МИСТЕР  0797754.

дальнейшее чтение

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

  • EE364A и EE364B, Последовательность курсов выпуклой оптимизации Стэнфорда.