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

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

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

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

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

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

Позволять $f:\mathbb {R} ^{n}\to \mathbb {R}$ быть выпуклой функцией с областью определения $\mathbb {R} ^{n}.$ Классический субградиентный метод повторяет $$x^{(k+1)}=x^{(k)}-\alpha _{k}g^{(k)}\$$ где $g^{(k)}$ обозначает любой субградиент ​ $f\$ в $x^{(k)},\$ и $x^{(k)}$ это $k^{th}$ итерация $x.$ Если $f\$ дифференцируема, то ее единственным субградиентом является вектор градиента $\nabla f$ сам. Может случиться так, что $-g^{(k)}$ не является направлением спуска для $f\$ в $x^{(k)}.$ Поэтому мы ведем список $f_{\rm {best}}\$ который отслеживает наименьшее найденное на данный момент значение целевой функции, т.е. $$f_{\rm {best}}^{(k)}=\min\{f_{\rm {best}}^{(k-1)},f(x^{(k)})\}.$$

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

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

• Постоянный размер шага, $\alpha _{k}=\alpha .$
• Постоянная длина шага, $\alpha _{k}=\gamma /\lVert g^{(k)}\rVert _{2},$ что дает $\lVert x^{(k+1)}-x^{(k)}\rVert _{2}=\gamma .$
• Квадратно суммируемый, но не суммируемый размер шага, т.е. любой размер шага, удовлетворяющий $$\alpha _{k}\geq 0,\qquad \sum _{k=1}^{\infty }\alpha _{k}^{2}<\infty ,\qquad \sum _{k=1}^{\infty }\alpha _{k}=\infty .$$
• Несуммируемое убывающее, т.е. любой размер шага, удовлетворяющий $$\alpha _{k}\geq 0,\qquad \lim _{k\to \infty }\alpha _{k}=0,\qquad \sum _{k=1}^{\infty }\alpha _{k}=\infty .$$
• Несуммируемые убывающие длины шагов, т.е. $\alpha _{k}=\gamma _{k}/\lVert g^{(k)}\rVert _{2},$ где $$\gamma _{k}\geq 0,\qquad \lim _{k\to \infty }\gamma _{k}=0,\qquad \sum _{k=1}^{\infty }\gamma _{k}=\infty .$$

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

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

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

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

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

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

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

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

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

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

минимизировать $f(x)\$ при условии $$x\in {\mathcal {C}}$$

где ${\mathcal {C}}$ представляет собой выпуклое множество . Метод проецируемого субградиента использует итерацию $$x^{(k+1)}=P\left(x^{(k)}-\alpha _{k}g^{(k)}\right)$$ где $P$ это проекция на ${\mathcal {C}}$ и $g^{(k)}$ любой субградиент $f\$ в $x^{(k)}.$

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

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

минимизировать $f_{0}(x)\$ при условии $$f_{i}(x)\leq 0,\quad i=1,\ldots ,m$$

где $f_{i}$ являются выпуклыми. Алгоритм принимает ту же форму, что и случай без ограничений. $$x^{(k+1)}=x^{(k)}-\alpha _{k}g^{(k)}\$$ где $\alpha _{k}>0$ - это размер шага, и $g^{(k)}$ является субградиентом цели или одной из функций ограничений в точке $x.\$ Брать $$g^{(k)}={\begin{cases}\partial f_{0}(x)&{\text{ if }}f_{i}(x)\leq 0\;\forall i=1\dots m\\\partial f_{j}(x)&{\text{ for some }}j{\text{ such that }}f_{j}(x)>0\end{cases}}$$ где $\partial f$ обозначает субдифференциал ​ $f.\$ Если текущая точка осуществима, алгоритм использует целевой субградиент; если текущая точка невозможна, алгоритм выбирает субградиент любого нарушенного ограничения.

См. также

• Стохастический градиентный спуск – алгоритм оптимизации

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

• Берцекас, Дмитрий П. (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 .

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

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