Метод субградиента

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

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

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

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

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

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

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

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

• Постоянный размер шага, ${\displaystyle \alpha _{k}=\alpha .}$
• Постоянная длина шага, что дает ${\displaystyle \alpha _{k}=\gamma /\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 }\alpha _{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 }\gamma _{k}=\infty .}$$

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

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

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

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

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

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

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

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

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

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

минимизировать при условии ${\displaystyle f(x)\ }$ $${\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 g^{(k)}}$ ${\displaystyle f\ }$ ${\displaystyle x^{(k)}.}$

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

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

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

где выпуклы. Алгоритм принимает ту же форму, что и случай без ограничений , где — размер шага, а — субградиент целевой или одной из функций ограничений в Возьмем , где обозначает субдифференциал Если текущая точка достижима, алгоритм использует целевой субградиент ; если текущая точка не достижима, алгоритм выбирает субградиент любого нарушенного ограничения. ${\displaystyle f_{i}}$ $${\displaystyle x^{(k+1)}=x^{(k)}-\alpha _{k}g^{(k)}\ }$$ ${\displaystyle \alpha _{k}>0}$ ${\displaystyle g^{(k)}}$ ${\displaystyle x.\ }$ $${\displaystyle 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}}}$$ ${\displaystyle \partial f}$ ${\displaystyle f.\ }$

Смотрите также

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

Ссылки

1. Берцекас, Димитрий П. (2015). Выпуклые алгоритмы оптимизации (второе издание). Belmont, MA.: Athena Scientific. ISBN 978-1-886529-28-1.
2. Bertsekas, Dimitri P.; Nedic, Angelia; Ozdaglar, Asuman (2003). Выпуклый анализ и оптимизация (второе издание). Belmont, MA.: Athena Scientific. ISBN 1-886529-45-0.
3. Приблизительная сходимость метода субградиента с постоянным размером шага (масштабированного) изложена в упражнении 6.3.14(a) в Bertsekas (стр. 636): Bertsekas, Dimitri P. (1999). Nonlinear Programming (Второе изд.). Cambridge, MA.: 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. MR  1900016. S2CID  9048698.
5. Kiwiel, Krzysztof C.; Larsson, Torbjörn; Lindberg, P. O. (август 2007 г.). «Лагранжева релаксация с помощью методов субградиента ballstep». Математика исследования операций . 32 (3): 669–686. doi :10.1287/moor.1070.0261. MR  2348241.
6. Берцекас, Димитрий П. (1999). Нелинейное программирование (второе изд.). Кембридж, Массачусетс: Athena Scientific. ISBN 1-886529-00-0.
7. Kiwiel, Krzysztof (1985). Методы спуска для недифференцируемой оптимизации . Берлин: Springer Verlag . стр. 362. ISBN 978-3540156420. МР  0797754.

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

• Берцекас, Димитрий П. (1999). Нелинейное программирование . Белмонт, Массачусетс: Athena Scientific. ISBN 1-886529-00-0.
• Bertsekas, Dimitri P.; Nedic, Angelia; Ozdaglar, Asuman (2003). Выпуклый анализ и оптимизация (второе издание). Belmont, MA.: Athena Scientific. ISBN 1-886529-45-0.
• Берцекас, Димитрий П. (2015). Выпуклые алгоритмы оптимизации . Белмонт, Массачусетс: Athena Scientific. ISBN 978-1-886529-28-1.
• Шор, Наум З. (1985). Методы минимизации недифференцируемых функций . Springer-Verlag . ISBN 0-387-12763-1.
• Ruszczyński, Andrzej (2006). Нелинейная оптимизация . Princeton, NJ: Princeton University Press . стр. xii+454. ISBN 978-0691119151. МР  2199043.

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

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