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

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

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

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

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

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

Позвольте быть выпуклой функцией с областью определения . Классический субградиентный метод повторяет ${\ displaystyle f: \ mathbb {R} ^ {n} \ to \ mathbb {R}}$${\ Displaystyle \ mathbb {R} ^ {п}}$

${\ Displaystyle х ^ {(к + 1)} = х ^ {(к)} - \ альфа _ {к} г ^ {(к)} \}$

где обозначает любую субградиент из в , и это итерация . Если дифференцируемый, то его единственный субградиент - это сам вектор градиента . Может случиться так, что это не направление спуска для at . Поэтому мы ведем список, в котором отслеживается наименьшее найденное значение целевой функции, т. Е. ${\ Displaystyle г ^ {(к)}}$ ${\ displaystyle f \}$${\ Displaystyle х ^ {(к)} \}$${\ Displaystyle х ^ {(к)}}$${\ displaystyle k ^ {th}}$${\ displaystyle x}$${\ displaystyle f \}$${\ displaystyle \ nabla f}$${\ Displaystyle -g ^ {(к)}}$${\ displaystyle f \}$${\ Displaystyle х ^ {(к)}}$${\ displaystyle f _ {\ rm {лучший}} \}$

${\ displaystyle f _ {\ rm {best}} ^ {(k)} = \ min \ {f _ {\ rm {best}} ^ {(k-1)}, f (x ^ {(k)}) \ }.}$

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

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

• Постоянный размер шага, ${\ Displaystyle \ альфа _ {к} = \ альфа.}$
• Постоянная длина шага , что дает ${\ Displaystyle \ альфа _ {к} = \ гамма / \ lVert g ^ {(k)} \ rVert _ {2}}$${\ displaystyle \ lVert x ^ {(k + 1)} - x ^ {(k)} \ rVert _ {2} = \ gamma.}$
• Суммируемый квадрат, но не суммируемый размер шага, т. Е. Любые размеры шага, удовлетворяющие

${\ displaystyle \ alpha _ {k} \ geq 0, \ qquad \ sum _ {k = 1} ^ {\ infty} \ alpha _ {k} ^ {2} <\ infty, \ qquad \ sum _ {k = 1} ^ {\ infty} \ alpha _ {k} = \ infty.}$

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

${\ displaystyle \ alpha _ {k} \ geq 0, \ qquad \ lim _ {k \ to \ infty} \ alpha _ {k} = 0, \ qquad \ sum _ {k = 1} ^ {\ infty} \ альфа _ {k} = \ infty.}$

• Несуммируемые уменьшающиеся длины шага, т. Е. Где ${\ displaystyle \ alpha _ {k} = \ gamma _ {k} / \ lVert g ^ {(k)} \ rVert _ {2}}$

${\ displaystyle \ gamma _ {k} \ geq 0, \ qquad \ lim _ {k \ to \ infty} \ gamma _ {k} = 0, \ qquad \ sum _ {k = 1} ^ {\ infty} \ гамма _ {k} = \ infty.}$

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

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

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

${\ displaystyle \ lim _ {k \ to \ infty} f _ {\ rm {best}} ^ {(k)} - f ^ {*} <\ epsilon}$ по результату Шора .

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

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

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

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

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

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

минимизировать при условии ${\ Displaystyle е (х) \}$

${\ displaystyle x \ in {\ mathcal {C}}}$

где - выпуклое множество . Прогнозируемый субградиентный метод использует итерацию ${\ displaystyle {\ mathcal {C}}}$

${\ displaystyle x ^ {(k + 1)} = P \ left (x ^ {(k)} - \ alpha _ {k} g ^ {(k)} \ right)}$

где - проекция на, а - любой субградиент при ${\ displaystyle P}$${\ displaystyle {\ mathcal {C}}}$${\ Displaystyle г ^ {(к)}}$${\ displaystyle f \}$${\ displaystyle x ^ {(k)}.}$

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

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

минимизировать при условии ${\ displaystyle f_ {0} (х) \}$

${\ Displaystyle F_ {я} (х) \ Leq 0, \ quad я = 1, \ точки, м}$

где выпуклые. Алгоритм имеет ту же форму, что и безусловный случай. ${\ displaystyle f_ {i}}$

${\ Displaystyle х ^ {(к + 1)} = х ^ {(к)} - \ альфа _ {к} г ^ {(к)} \}$

где - размер шага, а - субградиент целевой или одной из функций ограничения в Take ${\ displaystyle \ alpha _ {k}> 0}$${\ Displaystyle г ^ {(к)}}$${\ Displaystyle х. \}$

${\ displaystyle g ^ {(k)} = {\ begin {case} \ partial f_ {0} (x) & {\ text {if}} f_ {i} (x) \ leq 0 \; \ forall i = 1 \ dots m \\\ partial f_ {j} (x) & {\ text {для некоторых}} j {\ text {таких, что}} f_ {j} (x)> 0 \ end {cases}}}$

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

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

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

• Бертсекас, Дмитрий П. (1999). Нелинейное программирование . Бельмонт, Массачусетс: Athena Scientific. ISBN   1-886529-00-0 .
• Bertsekas, Dimitri P .; Недич, Анджелиа; Оздаглар, Асуман (2003). Выпуклый анализ и оптимизация (второе изд.). Бельмонт, Массачусетс: Athena Scientific. ISBN   1-886529-45-0 .
• Бертсекас, Дмитрий П. (2015). Алгоритмы выпуклой оптимизации . Бельмонт, Массачусетс: Athena Scientific. ISBN   978-1-886529-28-1 .
• Шор, Наум З. (1985). Методы минимизации недифференцируемых функций . Springer-Verlag . ISBN   0-387-12763-1 .

• Рущинский, Анджей (2006). Нелинейная оптимизация . Принстон, Нью-Джерси: Издательство Принстонского университета . С. xii + 454. ISBN   978-0691119151 . Руководство по ремонту   2199043 .

Внешние ссылки

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