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

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

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

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

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

Правила классического субградиента

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

[math]\displaystyle{ x^{(k+1)}=x^{(k)} - \alpha_k g^{(k)} }[/math]

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

[math]\displaystyle{ f_{\rm{best}}^{(k)}=\min\{f_{\rm{best}}^{(k-1)} , f(x^{(k)}) \}. }[/math]

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

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

• Постоянный размер шага, [math]\displaystyle{ \alpha_k=\alpha }[/math].
• Постоянная длина шага, [math]\displaystyle{ \alpha_k=\gamma/\lVert g^{(k)} \rVert_2 }[/math], что даёт [math]\displaystyle{ \lVert x^{(k+1)} - x^{(k)} \rVert_2=\gamma }[/math].
• Суммируемый с квадратом, но не суммируемый размер шага, то есть любой размер шага, для которого выполняется

[math]\displaystyle{ \alpha_k\geqslant0,\qquad\sum_{k=1}^\infty \alpha_k^2 \lt \infty,\qquad \sum_{k=1}^\infty \alpha_k=\infty. }[/math]

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

[math]\displaystyle{ \alpha_k\geqslant0,\qquad \lim_{k\to\infty} \alpha_k=0,\qquad \sum_{k=1}^\infty \alpha_k=\infty. }[/math]

• Несуммируемая убывающая длина шага, то есть, [math]\displaystyle{ \alpha_k=\gamma_k/\lVert g^{(k)} \rVert_2 }[/math], где

[math]\displaystyle{ \gamma_k\geqslant0,\qquad \lim_{k\to\infty} \gamma_k=0,\qquad \sum_{k=1}^\infty \gamma_k=\infty. }[/math]

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

Сходимость

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

[math]\displaystyle{ \lim_{k\to\infty} f_{\rm{best}}^{(k)} - f^* \lt \epsilon }[/math] согласно Шору.

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

Проекции субградиента и методы пучков

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

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

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

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

минимизировать [math]\displaystyle{ f(x) }[/math] при условии

[math]\displaystyle{ x\in\mathcal{C} }[/math]

где [math]\displaystyle{ \mathcal{C} }[/math] является выпуклым множеством. Метод проекции субградиента использует итерации

[math]\displaystyle{ x^{(k+1)}=P \left(x^{(k)} - \alpha_k g^{(k)} \right) }[/math]

где [math]\displaystyle{ P }[/math] является проекцией на [math]\displaystyle{ \mathcal{C} }[/math], а [math]\displaystyle{ g^{(k)} }[/math] является любым субградиентом [math]\displaystyle{ f }[/math] в точке [math]\displaystyle{ x^{(k)} }[/math].

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

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

минимизировать [math]\displaystyle{ f_0(x) }[/math] при условии

[math]\displaystyle{ f_i (x) \leqslant 0,\quad i=1,\dots,m }[/math]

где функции [math]\displaystyle{ f_i }[/math] выпуклы. Алгоритм принимает ту же форму случая без ограничений

[math]\displaystyle{ x^{(k+1)}=x^{(k)} - \alpha_k g^{(k)} }[/math]

где [math]\displaystyle{ \alpha_k\gt 0 }[/math] является размером шага, а [math]\displaystyle{ g^{(k)} }[/math] является субградиентом целевой функции или одной из функций ограничений в точке [math]\displaystyle{ x }[/math]. Здесь

[math]\displaystyle{ g^{(k)}= \begin{cases} \partial f_0 (x) & f_i(x) \leqslant 0 \; \forall i=1 \dots m \\ \partial f_j (x) & \exists j : f_j(x) \gt 0 \end{cases} }[/math]

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

Литература

• Dimitri P. Bertsekas. Convex Optimization Algorithms. — Second. — Belmont, MA.: Athena Scientific, 2015. — ISBN 978-1-886529-28-1.
• Dimitri P. Bertsekas, Angelia Nedic, Asuman Ozdaglar. Convex Analysis and Optimization. — Second. — Belmont, MA.: Athena Scientific, 2003. — ISBN 1-886529-45-0.
• Naum Z. Shor. Minimization Methods for Non-differentiable Functions. — Springer-Verlag, 1985. — ISBN 0-387-12763-1.
• Dimitri P. Bertsekas. Nonlinear Programming. — Second. — Cambridge, MA.: Athena Scientific, 1999. — ISBN 1-886529-00-0.
• Krzysztof Kiwiel. Methods of Descent for Nondifferentiable Optimization. — Berlin: Springer Verlag, 1985. — ISBN 978-3540156420.
• Claude Lemaréchal. Lagrangian relaxation // Computational combinatorial optimization: Papers from the Spring School held in Schloß Dagstuhl, May 15–19, 2000 / Michael Jünger, Denis Naddef. — Berlin: Springer-Verlag, 2001. — Т. 2241. — (Lecture Notes in Computer Science). — ISBN 3-540-42877-1. — doi:10.1007/3-540-45586-8_4.
• Krzysztof C. Kiwiel, Torbjörn Larsson, Lindberg P. O. Lagrangian relaxation via ballstep subgradient methods // Mathematics of Operations Research. — 2007. — Август (т. 32, № 3). — С. 669–686. — doi:10.1287/moor.1070.0261.

Дополнительная литература

• Andrzej Piotr Ruszczyński. Nonlinear Optimization. — Princeton, NJ: Princeton University Press, 2006. — С. xii+454. — ISBN 978-0691119151.

Ссылки

• EE364A and EE364B, Stanford’s convex optimization course sequence.