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

Субградієнтні методи - це ітераційні методи вирішення задач мінімізації опуклості . Спочатку розроблений Наумом Шором та іншими у 1960-70-і роки, субградієнтні методи є збіжними, коли застосовуються навіть до недиференційованої цільової функції. Коли цільова функція є диференційованою, методи субградієнта для необмежених задач використовують той самий напрямок пошуку, що і метод найкрутішого спуску.

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

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

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

Припустим ${\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]} Однак вони все ще широко використовуються в спеціалізованих програмах, оскільки вони прості і їх можна легко адаптувати, щоб скористатися особливою структурою проблеми, що існує.

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

Одним з розширень методу субградієнта є прогнозований метод субградієнта, який вирішує обмежену задачу оптимізації.

мінімізувати ${\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,\dots ,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. ↑ Bertsekas, Dimitri P. (2015). Convex Optimization Algorithms (вид. Second). Belmont, MA.: Athena Scientific. ISBN 978-1-886529-28-1.
2. ↑ Bertsekas, Dimitri P.; Nedic, Angelia; Ozdaglar, Asuman (2003). Convex Analysis and Optimization (вид. Second). Belmont, MA.: Athena Scientific. ISBN 1-886529-45-0.
3. ↑ ^{а б} Lemaréchal, Claude (2001). Lagrangian relaxation. У Michael Jünger and Denis Naddef (ред.). Computational combinatorial optimization: Papers from the Spring School held in Schloß Dagstuhl, May 15–19, 2000. Lecture Notes in Computer Science. Т. 2241. Berlin: Springer-Verlag. с. 112—156. doi:10.1007/3-540-45586-8_4. ISBN 3-540-42877-1. MR 1900016.
4. ↑ ^{а б} Kiwiel, Krzysztof C.; Larsson, Torbjörn; Lindberg, P. O. (August 2007). Lagrangian relaxation via ballstep subgradient methods. Mathematics of Operations Research. 32: 669—686. doi:10.1287/moor.1070.0261. MR 2348241. Архів оригіналу за 26 липня 2011. Процитовано 24 грудня 2019.
5. ↑ Bertsekas, Dimitri P. (1999). Nonlinear Programming (вид. Second). Cambridge, MA.: Athena Scientific. ISBN 1-886529-00-0.
6. ↑ Kiwiel, Krzysztof (1985). Methods of Descent for Nondifferentiable Optimization. Berlin: Springer Verlag. с. 362. ISBN 978-3540156420. MR 0797754.

• Bertsekas, Dimitri P. (1999). Nonlinear Programming. Belmont, MA.: Athena Scientific. ISBN 1-886529-00-0.
• Bertsekas, Dimitri P.; Nedic, Angelia; Ozdaglar, Asuman (2003). Convex Analysis and Optimization (вид. Second). Belmont, MA.: Athena Scientific. ISBN 1-886529-45-0.
• Bertsekas, Dimitri P. (2015). Convex Optimization Algorithms. Belmont, MA.: Athena Scientific. ISBN 978-1-886529-28-1.
• Shor, Naum Z. (1985). Minimization Methods for Non-differentiable Functions. Springer-Verlag. ISBN 0-387-12763-1.

• Ruszczyński, Andrzej (2006). Nonlinear Optimization. Princeton, NJ: Princeton University Press. с. xii+454. ISBN 978-0691119151. MR 2199043.

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