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

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