Jump to content

Субградиентный метод

(Перенаправлено из методов субградиента )

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

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

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

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

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

[ редактировать ]

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

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

[ редактировать ]

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

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

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

Результаты конвергенции

[ редактировать ]

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

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

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

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

[ редактировать ]

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

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

[ редактировать ]

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

[ редактировать ]

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

минимизировать при условии

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

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

[ редактировать ]

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

минимизировать при условии

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

См. также

[ редактировать ]
  1. ^ Берцекас, Дмитрий П. (2015). Алгоритмы выпуклой оптимизации (второе изд.). Бельмонт, Массачусетс: Athena Scientific. ISBN  978-1-886529-28-1 .
  2. ^ Берцекас, Дмитрий П.; Недич, Ангелия; Оздаглар, Асуман (2003). Выпуклый анализ и оптимизация (второе изд.). Бельмонт, Массачусетс: Athena Scientific. ISBN  1-886529-45-0 .
  3. ^ Приблизительная сходимость субградиентного метода с постоянным размером шага (масштабированного) изложена в упражнении 6.3.14(a) в Берцекасе (стр. 636): Берцекас, Дмитрий П. (1999). Нелинейное программирование (Второе изд.). Кембридж, Массачусетс: Athena Scientific. ISBN  1-886529-00-0 . На странице 636 Берцекас приписывает этот результат Шору: Шор, Наум З. (1985). Методы минимизации недифференцируемых функций . Спрингер-Верлаг . ISBN  0-387-12763-1 .
  4. ^ 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 .
  5. ^ Jump up to: а б Кивиэль, Кшиштоф К.; Ларссон, Торбьёрн; Линдберг, ПО (август 2007 г.). «Лагранжева релаксация с помощью методов шарикового субградиента» . Математика исследования операций . 32 (3): 669–686. дои : 10.1287/moor.1070.0261 . МР   2348241 .
  6. ^ Берцекас, Дмитрий П. (1999). Нелинейное программирование (Второе изд.). Кембридж, Массачусетс: Athena Scientific. ISBN  1-886529-00-0 .
  7. ^ Кивил, Кшиштоф (1985). Методы спуска для недифференцируемой оптимизации . Берлин: Springer Verlag . п. 362. ИСБН  978-3540156420 . МР   0797754 .

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

[ редактировать ]
[ редактировать ]
  • EE364A и EE364B , последовательность курсов выпуклой оптимизации Стэнфорда.
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: e12322aec7a038b10d5ceda542c4046c__1706797980
URL1:https://arc.ask3.ru/arc/aa/e1/6c/e12322aec7a038b10d5ceda542c4046c.html
Заголовок, (Title) документа по адресу, URL1:
Subgradient method - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)