Новости    Библиотека    Байки    Ссылки    О сайте


предыдущая главасодержаниеследующая глава

10.2. Метод проекции градиента

Как уже говорилось, в случае задач безусловной минимизации весьма распространенным релаксационным методом является метод градиентного спуска. Однако для задач с ограничениями направление спуска вдоль антиградиента не обязательно является возможным. Для отыскания возможного направления в точке хk напрашивается мысль спроектировать точку vk = xkkφ'(хk) (νk-некоторое фиксированное положительное число) на множество X и в качестве направления спуска взять - sk=p(vk)-xk где P(vk) - проекция vk на X, после чего осуществлять спуск вдоль этого направления.

Итак, метод проекции градиента состоит в вычислении проекции p(vk) точки

vk=xk-kφ'(xk)

на множество X и построении точки

(10.23)

Для отыскания направления sk = xk - p(vk) следует решить задачу минимизации квадратичной функции ||vk-x||2 на множестве X. В общем случае это задача того же порядка сложности, что и исходная, однако для задач, когда допустимое множество имеет простую геометрическую структуру, например, является многомерным параллелепипедом, отыскание p(vk) производится путем сравнения n чисел.

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

(10.24)

А из следствия к теореме 2.2 вытекает, что для любого vk > 0 справедливо неравенство

(10.25)

Наконец, напомним, что если функция φ(х) выпукла и дифференцируема на выпуклом и, замкнутом множестве X, то из условия xk=p(vk) следует экстремальность точки хk (теорема 2.16). При исследовании сходимости мы всегда будем предполагать, что xk≠p(vk), то есть φ(хk)≠φ(х*).

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

1) выпуклая функция φ(x) принадлежит классу С1,1(Х);

2) множество Х0 = {x∈Х: φ(x)≤φ(x0)} ограничено: diam Х0 = η < ∞;

3) числа vk таковы, что vk ≥ ν' > 0;

4) последовательность {хk} является релаксационной, то есть

φ(xk+1)≤φ(xk) (k = 0, 1, ...),

то справедлива оценка:

(10.26)

при любом


где


Доказательство. Для того чтобы получить неравенство (10.26), достаточно показать, что


и воспользоваться оценкой (9.2) из теоремы 9.1.

Сначала сделаем следующие тождественные преобразования:


Отсюда и из (10.24) получаем


Но из (10.25) следует неравенство


Учитывая, что


получаем окончательно


Отсюда и из неравенства (9.2):


получаем оценку (10.26). Теорема доказана.

Рассмотрим теперь последовательность {хk}, элементы которой строятся по формуле

xk+1 = xkk(xk-yk), (10.27)

а yk и k удовлетворяют следующим условиям:

yk∈X, (10.28)
φ[xkk(xk-yk)]≤(1-λk)φ(xk)+λkωk
0<λk≤1, 0≤βk≤1, (10.29)

где


Подчеркнем, что при построении элементов этой последовательности {хk} выбор yk, βk достаточно произволен, лишь бы выполнялись требования (10.28) и (10.29).

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

1) выпуклая функция φ(х) принадлежит классу С1,1(Х);

2) diam X0 = η < ∞;

3) последовательность {хk} определяется условиями (10.27) -(10.29);

А) числа vk таковы, что 0<ν'≤νk≤ν"<∞, то справедлива оценка

(10.30)

при любом


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

(10.31)

Отсюда и из условия (10.29) получаем, что для любого β∈[0, 1] выполняется неравенство

(10.32)

В частности, выбирая


получаем при β = 1 (с учетом того, что в этом случае L≤1.νk)


Если же


то


И окончательно приходим к неравенству

(10.33)

где


Из (10.33) и (10.26) получаем оценку (10.30).

Теперь обратимся к схемам метода проекций градиента.

Схема 1.

(10.23)

и, кроме того, 0<ν'≤νk≤ν"<∞.

Сходимость. Если в условиях (10.27) -(10.29) положить yk = p(vk) и λk = 1, то мы приходим к схеме 1. В силу теоремы 10.3 из (10.30) получаем оценку


Устойчивость. Если вместо р(vk) и βk схеме найдены yk и βk, удовлетворяющие условиям (10.27) - (10.29), то в силу теоремы 10.3 справедлива оценка (10.30). И если все λk≥λ>0, то

φ(xm)-φ(x*)<1/Cλm (m=1,2,....)

Следовательно, в пределах изменения yk и βk, допускаемых условиями (10.28), (10.29), скорость сходимости остается того же порядка O(1/m), хотя множитель при 1/m - в оценке скорости сходимости увеличивается в у раз.

Схема 2.

(10.23)

В качестве βk выбирается любое из чисел, удовлетворяющих условию


а величина νk может быть любой такой, что


Сходимость. Из (10.31), учитывая условия, определяющие βk и νk, получаем


Оценка (10.26) приводит теперь нас к неравенству


где


Устойчивость. Если при некотором βk∈[β̄, 1] вместо p(vk) найден элемент yk, удовлетворяющий условию (10.29), то из (10.32) при λk≥λ>0 получаем


Оценка (10.26) приводит к неравенству


Таким образом, множитель при 1/m в этой оценке увеличивается в 1/λ раз по сравнению с предыдущим.

Обсуждение. Эта схема не требует затрат на одномерную минимизацию и при βk=β̃∈[β̄, 1] представляет собой схему с постоянным шагом. В этом смысле она представляется весьма перспективной. Однако величина L-константа Липшица,- как правило, неизвестна, и сколько-нибудь удачно оценить ее в реальных ситуациях-задача настолько сложная, что обычно выбирают величину ν", намного меньшей предполагаемой величины 2/L, вследствие чего множитель 1/ν"-1/2 L в оценке величины С возрастет, существенно ухудшая априорную оценку скорости сходимости.

Схема 3. Здесь βk = 1 (k = 0, 1, ...), а варьируется выбор νk на отрезке 0<ν'≤νk≤ν"<2/L:


где р-оператор проектирования на множество X. Величина νk определяется соотношением


Сходимость. Из предлагаемого подхода к оценкам скорости сходимости следует, что эта схема представляет собой частный случай схемы 2 при βk=1 и νk∈[ν', ν"]. Таким образом, оценка скорости сходимости здесь та же, что и в предыдущей схеме.

Устойчивость. Если вместо р(хkkφ' (xk)) вычислен элемент x̃k+1 удовлетворяющий неравенствам

φ(x̃k+1)≤(1-λk)φ(xk)+λkφ(xk+1), 0<λ≤λk≤1

то так же, как и раньше, получаем, пользуясь тем, что xk+1=p(νk) и βk=1, оценку


вследствие чего


Обсуждение. Эту схему в смысле рассматриваемых априорных оценок скорости сходимости едва ли можно признать удачной: она не обладает преимуществами предыдущей схемы, поскольку требует проведения одномерной минимизации для определения величины νk и в то же время обладает худшей оценкой скорости сходимости по сравнению со схемой 1. Следует обратить внимание на оговорку: "в смысле рассматриваемых априорных оценок скорости сходимости". Эти слова означают, что при известных предположениях относительно исходной задачи скорость сходимости будет не хуже той, которую гарантируют наши оценки. И только. Но вполне возможно, что для конкретной задачи из рассматриваемого класса скорость сходимости может оказаться куда более высокой. Заметим, что все эти рассуждения предполагают некую идеализированную ситуацию в первую очередь в отношении точности вычислений, например, существование числа λ > 0, характеризующего эту точность.

Схема 4.

(10.23)

где


и


Сходимость. Из (10.31) получаем в результате элементарных выкладок, что


И неравенство (10.26) сразу приводит к оценке


где


Устойчивость. Если вместо p(vk) вычислена точка x̃k+1 такая, что φ(x̃k+1)≤(1-λk)φ(xk)+λkφ(xk+1), то, аналогично тому, как это делалось при анализе устойчивости предыдущей схемы, получаем, что в этом случае множитель при 1/m в оценке скорости сходимости возрастает в 1/λ раз.

Схема 5.

(10.23)
(10.34)

Сходимость. Из левой части (10.31) получаем при


соотношение

(10.35)

И так как согласно (10.25)


то, учитывая определение ρk, приходим к неравенству


Если же βk = 1, то


и, следовательно, из (10.31) получаем


Выбирая


приходим к оценке

(10.36)

Отсюда и из (10.26) приходим к той же самой оценке, что и в схеме 4.

Устойчивость. Здесь сохраняют силу те же соображения, что и в предыдущих двух схемах.

Схема 6.

(10.23)

в качестве βk выбирается наибольшее из чисел, удовлетворяющих неравенствам

(10.37)

Здесь число в может быть любым из интервала (0, 1): 0<ε<1, 0<ν≤νk≤ν"<∞.

Сходимость. Сначала покажем, .что существует β̄k, удовлетворяющее условиям (10.37). Действительно, выбирая β̄k по формуле (10.34), получаем из (10.35) и (10.36), что


Но 0<ε2<2, поэтому условия (10.37) выполняются.

Поскольку в,качестве βk выбирается наибольшее из чисел, удовлетворяющих (10.37), то с учетом (10.25)


и, следовательно, справедлива та же оценка, что и в схемах 4 и 5.

Устойчивость. Если вместо p(vk) вычислен yk такой, что выполняется неравенство


при некотором ε∈(0, 1], то ввиду того, что


получаем


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


при


Если при этом 0<β̃≤βk<1, то


Обсуждение. Соображения о возможных преимуществах при отыскании βk по этой схеме по сравнению со схемой 1 остаются теми же, что приводились при обсуждении схемы 2 метода градиентного спуска (см. п. 9.5).

Схема 7.

(10.23)

а в качестве βk выбирается наибольшее из чисел, удовлетворяющих неравенствам

(10.38)

Здесь число ε может быть любым из интервала (0, 1/ν"):


Сходимость и устойчивость. Из анализа сходимости предыдущей схемы ясно, что рд, определяемое формулой (10.34), удовлетворяет условиям (10.38). Таким образом, система (10.38) имеет решение. Доказательства сходимости и устойчивости здесь с очевидностью следуют из рассмотрений предыдущей схемы.

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


Оценка (10.26) показывает, что до тех пор, пока сохраняется ситуация


где величина ε определяется принятой точностью вычислений, процесс сходится со скоростью, порядок которой не ниже O(1/m).

предыдущая главасодержаниеследующая глава





Пользовательский поиск


Диски от INNOBI.RU




© Злыгостев Алексей Сергеевич, подборка материалов, оцифровка, статьи, оформление, разработка ПО 2001-2017
При копировании материалов проекта обязательно ставить активную ссылку на страницу источник:
http://informaticslib.ru/ "InformaticsLib.ru: Информатика"