10.1. Метод условного градиента

В этом методе идея выбора направления спуска состоит в следующем: в точке х_k линеаризуют функцию φ(x), строя линейную функцию φ_L(х) = φ(х_k) + <φ'(x_k), x-x_k> и затем минимизируя φ_L(x) на множестве _X, находят точку y_k. После этого полагают - s_k=y_k-x_k и далее вдоль этого направления осуществляют спуск. Таким образом, для отыскания направления - s_k следует решить задачу минимизации линейной функции на множестве X. В общем случае это задача того же порядка сложности, что и исходная, однако, когда допустимое множество задается линейными ограничениями, она становится задачей линейного программирования, конечномерные методы решения которой рассматривались в гл. 5.

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

Построение начинается с произвольной точки х₀∈Х. Предположим, что уже найден элемент х_k∈Х. Для построения элемента

необходимо определить y_k и β_k. Относительно y_k будем полагать, что

(10.3)

и, кроме того,

Пусть β_k удовлетворяет неравенствам

(10.5)

где

Теорема 10.1.Если на выпуклом и замкнутом множестве X выполняются условия:

4) последовательность {x_k} определяется условиями (10.1)-(10.5), то справедлива оценка

(10.6)

для любого положительного числа

где

Доказательство. Из условий (10.5) и леммы 9.3 получаем следующее неравенство, справедливое для всех β∈[0, 1]:

(10.7)

В частности, это неравенство справедливо для

(10.8)

где

(10.9)

Рассмотрим две возможности.

Если β = 1, то из (10.8) следует, что

Отсюда и из (10.7) получаем, учитывая (10.3) и условие 3), неравенство

(10.10)

Если

то из (10.7), с учетом условий, определяющих ρ_k, получаем

Пусть

(10.11)

Тогда из (10.10) и (10.11) приходим к неравенству

Поскольку в условиях настоящей теоремы справедлива и теорема 9.1, то последнее неравенство и оценка (9.2) приводят к (10.6).

Замечание. Условия 2) и 3) теоремы 10.1 и условие (10.3) можно заменить требованием ограниченности и замкнутости выпуклого множества X.

Следствие 1.Если в условиях теоремы 10.1 точка y_k такова, что

то из (10.6) следует оценка

(10.13)

Условия (10.12) позволяют при отыскании точки y_k приближенно решать задачу

При этом величина σ_k как раз и характеризует точность в определении приближенного решения этой задачи.

Если в условиях (10.5) и (10.12) λ_k и σ_k таковы, что λ_k≥λ>0, и _k≥σ>0, то из (10.13) получаем неравенство

(10.14)

Следствие 2.Если в условиях теоремы 10.1 параметр β_k определять не соотношениями (10.5), а условиями (10.8), (10.9), то оценки (10.6), (10.13) и (10.14) сохраняют силу при λ_k=1.

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

(10.15)

Схема 1.

(10.1)

(10.15)

(10.5)

Здесь величина ω_k является минимальным значением функции φ(x) на отрезке [х_k, y_k]. Заметим, что величину ω_k можно всюду дальше определять из условия

где

Все последующие результаты останутся при этом справедливыми. Однако дополнительные усилия для определения величины ζ_k на практике себя не оправдывают.

Сходимость. Так как выполнены все условия теоремы 10.1 и первого следствия при σ_k=1, то из (10.14) получаем оценку

(10.16)

Устойчивость. Если y_k удовлетворяет условию

(10.17)

при 0<σ_k≤1, а λ_k определяется соотношениями (10.5), го из следствия 1, поскольку выполняется условие 10.12), получаем, что справедлива оценка (10.13), а при λ_k≥λ>0 и σ_k≥σ>0 выполняется неравенство (10.14). Таким образом, метод устойчив к возможным вычислительным ошибкам в пределах, допускаемых соотношениями (10.17) и (10.5).

Схема 2.

(10.1)

(10.15)

(10.8)

(10.9)

Сходимость. Из следствия 2 получаем оценки скорости сходимости (10.13) и (10.14) при σ_k=1, справедливые для этой схемы.

Устойчивость. Если y_k удовлетворяет условию (10.17), а значит, и (10.12), то из следствий 1 и 2 приходим к выводу, что имеют место оценки (10.13) и (10.14) при λ_k=1. Таким образом, метод устойчив к возможным вычислительным ошибкам.

Схема 3.

(10.1)

(10.18)

где β_k-наибольшее из чисел, удовлетворяющих этим условиям.

Вначале покажем, что существуют β_k, удовлетворяющие условиям (10.18). Пусть β_k определяется соотношениями (10.8), (10.9). Тогда из неравенства (10.7) при λ_k=1 получаем, повторяя выкладки доказательства теоремы 10.1, для β_k=1 (аналогично (10.10))

А для

аналогично (10.11) получаем

И поскольку ε₂ должно удовлетворять неравенству 0<ε₂≤2, то условие (10.18) выполняется для любого 0<q≤ε₂/2<1.

Сходимость. Из (10.17) и (10.18) следует неравенство

Отсюда и из (9.2) получаем оценку

(10.19)

Пусть β̄_k наибольшее из чисел, удовлетворяющих условиям (10.18), а β_k = τ_kβ̄_k, где 0<τ_k≤1. В этом случае при β̄_k=1 получаем, что

где

Если же

то

и поэтому

Окончательно из (10.19) получаем оценку

(10.20)

справедливую для любого

Таким

образом, при 0<τ≤τ_k≤1 и 0<σ≤σ_k≤1 приходим к неравенству

(10.21)

Устойчивость метода следует с очевидностью из приведенных оценок.

Случай неограниченности множества X. В предыдущих схемах предполагалось существование решения экстремальной задачи (10.15), то есть задачи выбора направления. Однако это существенно сужает класс задач, к которым применим метод условного градиента. Рассмотрим схему, свободную от этого ограничения, то есть допускающую неограниченность множества X.

Схема 4.

(10.1)

(10.22)

(10.5)

Смысл условий 10.22 поясняется в разделе "обсуждение".

Ниже, из оценок скорости сходимости, станет ясным вопрос о выборе величин α_k.

Сходимость. Будем предполагать, что

где Х₀ = {х∈Х: φ(x)≤φ(x₀)}, и что существует такое число и, что

Если

то из (10.22) получаем неравенство

Если же

то

где

Пусть

тогда для y_k справедливо соотношение

Отсюда и из оценки (10.6) приходим при λ_k≥λ>0 к неравенству

где

Обсуждение. Ясно, что с уменьшением величины С ухудшается априорная оценка сходимости этого метода. Для того чтобы выяснить вопрос выбора α_k, оценим величину С: при некоторых естественных предположениях^* справедливо неравенство

где С₁= const > 0. Поскольку величина ||х_k-y_k|| зависит от выбора α и, следовательно, χ зависит от α, то соотношения, оценивающие величину С, показывают, что α_k целесообразно выбирать таким, чтобы отношение aα²_k/||x_k-y_k||² не убывало с увеличением числа k.

Рассмотрим наиболее перспективный случай применения метода условного градиента, а именно, когда множество X задается системой линейных равенств и неравенств, и задача отыскания y_k из условий (10.17) становится задачей линейного программирования. Условия (10.17) и (10.22) позволяют при решении задачи отыскания y_k в данном случае задачи линейного

программирования-ограничиться несколькими симплексными шагами, например, обрывая симплексную процедуру в тот момент, когда впервые выполнится (10.17) или (10.22).

^* (Например, при χ > 1, ₁ ≤1/γ и α/ηγ<1)