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

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

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

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

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

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

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

x ( k + 1 ) = x ( k ) − α k g ( k )   {displaystyle x^{(k+1)}=x^{(k)}-alpha _{k}g^{(k)} }

где g ( k ) {displaystyle g^{(k)}} это любой субдифференциал функции f   {displaystyle f } в точке x ( k ) {displaystyle x^{(k)}} , а x ( k ) {displaystyle x^{(k)}} — k-ая итерация переменной x {displaystyle x} . Если f   {displaystyle f } дифференцируемая, то его единственным субградиентом является градиент ∇ f {displaystyle abla f} . Может случиться, что − g ( k ) {displaystyle -g^{(k)}} не является направлением убывания для f   {displaystyle f } в точке x ( k ) {displaystyle x^{(k)}} . Мы поэтому содержим список f b e s t   {displaystyle f_{ m {best}} } , в котором храним найденные наименьшие значения целевой функции, то есть,

f b e s t ( k ) = min { f b e s t ( k − 1 ) , f ( x ( k ) ) } . {displaystyle f_{ m {best}}^{(k)}=min{f_{ m {best}}^{(k-1)},f(x^{(k)})}.}

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

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

• Постоянный размер шага, α k = α . {displaystyle alpha _{k}=alpha .}
• Постоянная длина шага, α k = γ / ‖ g ( k ) ‖ 2 {displaystyle alpha _{k}=gamma /lVert g^{(k)} Vert _{2}} , что даёт ‖ x ( k + 1 ) − x ( k ) ‖ 2 = γ . {displaystyle lVert x^{(k+1)}-x^{(k)} Vert _{2}=gamma .}
• Суммируемый с квадратом, но не суммируемый размер шага, то есть любой размер шага, для которого выполняется

α k ⩾ 0 , ∑ k = 1 ∞ α k 2 < ∞ , ∑ k = 1 ∞ α k = ∞ . {displaystyle alpha _{k}geqslant 0,qquad sum _{k=1}^{infty }alpha _{k}^{2}<infty ,qquad sum _{k=1}^{infty }alpha _{k}=infty .}

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

α k ⩾ 0 , lim k → ∞ α k = 0 , ∑ k = 1 ∞ α k = ∞ . {displaystyle alpha _{k}geqslant 0,qquad lim _{k o infty }alpha _{k}=0,qquad sum _{k=1}^{infty }alpha _{k}=infty .}

• Несуммируемая убывающая длина шага, то есть, α k = γ k / ‖ g ( k ) ‖ 2 {displaystyle alpha _{k}=gamma _{k}/lVert g^{(k)} Vert _{2}} , где

γ k ⩾ 0 , lim k → ∞ γ k = 0 , ∑ k = 1 ∞ γ k = ∞ . {displaystyle gamma _{k}geqslant 0,qquad lim _{k o infty }gamma _{k}=0,qquad sum _{k=1}^{infty }gamma _{k}=infty .}

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

Сходимость

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

lim k → ∞ f b e s t ( k ) − f ∗ < ϵ {displaystyle lim _{k o infty }f_{ m {best}}^{(k)}-f^{*}<epsilon } согласно Шору..

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

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

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

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

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

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

минимизировать f ( x )   {displaystyle f(x) } при условиях x ∈ C {displaystyle xin {mathcal {C}}}

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

x ( k + 1 ) = P ( x ( k ) − α k g ( k ) ) {displaystyle x^{(k+1)}=Pleft(x^{(k)}-alpha _{k}g^{(k)} ight)}

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

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

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

минимизировать f 0 ( x )   {displaystyle f_{0}(x) } при условиях f i ( x ) ⩽ 0 , i = 1 , … , m {displaystyle f_{i}(x)leqslant 0,quad i=1,dots ,m}

где функции f i {displaystyle f_{i}} выпуклы. Алгоритм принимает ту же форму случая без ограничений

x ( k + 1 ) = x ( k ) − α k g ( k )   {displaystyle x^{(k+1)}=x^{(k)}-alpha _{k}g^{(k)} }

где α k > 0 {displaystyle alpha _{k}>0} является размером шага, а g ( k ) {displaystyle g^{(k)}} является субградиентом целевой функции или одной из функций ограничений в точке x .   {displaystyle x. } Здесь

g ( k ) = { ∂ f 0 ( x ) f i ( x ) ⩽ 0 ∀ i = 1 … m ∂ f j ( x ) ∃ j : f j ( x ) > 0 {displaystyle g^{(k)}={egin{cases}partial f_{0}(x)&f_{i}(x)leqslant 0;forall i=1dots mpartial f_{j}(x)&exists j:f_{j}(x)>0end{cases}}}

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