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


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

9.4. Методы спуска. Общая схема

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

Итак, решается задача минимизации функции φ(x) на всем пространстве Еn. Методы спуска состоят в следующей процедуре построения последовательности {xk}. В качестве начального приближения выбирается, вообще говоря, любая точка х0∈Еn. Последовательные приближения х1, х2, ... строятся по следующей схеме:

1) В точке xk выбирают направление спуска-sk;

2) находят (k + 1)-е приближение по формуле

xk+1=xkksk (9.7)

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

φ(xkksk)≤(1-λk)φ(xk)+kωk (9.8)

Здесь число λk - любое такое, что 0<λk≤1, а


На рис. 9.1 изображен путь от точки х0 к точке х1 от х1 к х2 и т. д.

Рис. 9.1
Рис. 9.1

Как правило, в большинстве методов спуска величина λk выбирается равной единице. Таким образом, для отыскания βk приходится решать задачу одномерной минимизации. Естественно, что в реальных ситуациях одномерный минимум вычисляют приближенно, пользуясь, например, одним из методов, рассмотренных в гл. 8. Сходимость релаксационного процесса (если она имеет место) при выборе βk из условия (9.8), во-первых, показывает устойчивость процедуры спуска к возможным вычислительным погрешностям*. С другой стороны, численные методы решения задачи одномерной минимизации требуют многократных вычислений значений минимизируемой функции, что часто бывает сопряжено со значительными трудностями, особенно если значение φ(х) определяется в результате некоторого эксперимента. В этой ситуации оказывается иногда целесообразным ограничиться несколькими шагами в сторону убывания φ(x). Именно это и допускает условие (9.8). В самом деле, из неравенства (9.8) следует, что


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


Эти оценки показывают, что до тех пор, пока отношение


остается сравнительно большим, число вычислений значений φ(х) можно сократить, понизив точность одномерной минимизации, то есть уменьшив допустимую величину λk.

* (Определение устойчивости см. в конце п. 9.1. )

Часто в процессе счета, несмотря на то, что априорные оценки (в предположении, что все λk=1) свидетельствуют о сходимости метода со скоростью, скажем, O(1/m), обнаруживается, что с увеличением числа итераций скорость сходимости либо уменьшается, либо вообще процесс перестает сходиться. Одной из причин этого может оказаться потеря точности при вычислении одномерного минимума. Из приведенных выше оценок видно, что неблагоприятная ситуация, когда


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


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

Обозначим через αk величину косинуса угла между направлением антиградиента -φ' (xk) в точке хk (то есть направлением наискорейшего убывания функции φ(x) в этой точке) и направлением спуска - sk из этой же точки:


Теорема 9.4.Если

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

2) diam X0 = η < ∞;

3) последовательность {хk} строится по формулам (9.7), (9.8), то справедлива оценка

(9.9)
(m=1, 2, ...)

для любого 0<С≤1/(2Lη2).

Доказательство. Из (9.7), (9.8) для любых значений параметра β получаем


Отсюда, пользуясь леммой 9.3 и определением величины αk, приходим к неравенству


справедливому для любых значений β. Выбирая


получаем, что

(9.10)

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

Замечание. Если существует такой номер m0, что αm0≠0, то из (9.9) (аналогично 9.4) следует неравенство

(9.11)

Теорема 9.6.Если

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

2) последовательность {хk} строится по формулам (9.7), (9.8), то справедливы оценки

(9.12)

и

(9.13)

Доказательство. Оценки (9.12) и (9.13) с очевидностью следуют из (9.5), (9.6) и (9.10).

Обсуждение. Если направление - sk выбирается таким образом, что |αk|≥α>0 для всех k = 0, 1 ..., a λk∈[λ, 1], где 0<λ≤1, то из (9.11) получаем, что


из (9.12) и (9.13) следуют оценки


и


Очевидно, что в смысле этих соотношений наиболее благоприятные оценки возникают при |αk| = 1 и λk = 1.

Заметим, что вычисление одномерного минимума с высокой степенью точности сопряжено обычно с большим числом вычислений минимизируемой функции (вспомним методы из гл. 8), что часто снижает эффективность выбранного процесса минимизации.

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

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

(9.14)

где числа qk-любые из полуинтервала (0, 1/2] , а


Роль чисел qk поясняется в конце настоящего пункта. Во-первых, покажем, что существует β̄k, удовлетворяющее неравенствам (9.14). Действительно, если выбрать


то, пользуясь леммой 9.3 и тем, что Δ2k=1, получаем соотношение


Задача отыскания наибольшего элемента, удовлетворяющего неравенствам (9.14), иногда оказывается более простой по сравнению с задачей одномерной минимизации, которую приходится решать, чтобы удовлетворить условиям (9.8). Например, можно воспользоваться следующим элементарным способом отыскания βk. Выбирают некоторое начальное значение βk0≥0. Если при этом первое из неравенств (9.14) нарушается, то уменьшают величину βk0, например, вдвое до тех пор, пока βki=1/2iβk0 не удовлетворит условиям (9.14). Этот процесс можно продолжить, увеличивая βki до тех пор, пока


не нарушит условия (9.14) и т. д.

Сходимость. Оценить скорость сходимости метода спуска при выборе величины βk из условий (9.14) не представляет труда.

Теорема 9.6.Если

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

2) diam X0 = η < ∞;

3) последовательность {xk} определяется соотношениями (9.7) и (9.14), то

(9.15)
(m=1, 2, ...)

Если, кроме того, функция φ(х) сильно выпукла*, то

(9.16)

и

(9.17)

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


как мы видели, удовлетворяет этим неравенствам, то βk≥β̄k, и из (9.14), учитывая определение αk, получаем


Ввиду этого из неравенств (9.3), (9.5) и (9.6) следуют искомые оценки.

* (Условие 2) при этом становится излишним (см. п. 2.13, свойство 2). )

Обсуждение. Если бы была известна L-константа Липшица, то условие, чтобы величина βk была наибольшей из всех, удовлетворяющих неравенствам (9.14), можно ослабить, потребовав, чтобы было


В частности, можно выбирать βk = β̄k. Однако, как правило, в реальных случаях определить величину L-задача слишком сложная, если вообще выполнимая.

Рассмотрим влияние точности в определении величины βk из условий (9.14) на скорость сходимости релаксационного процесса. Пусть qk=1/2, k = 0, 1, ...; предположим, что в результате процедуры поиска βk найдено такое его приближенное значение, что

βk =β̄kk≥0

Тогда, пользуясь леммой 9.3, получаем


Но


а


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


Если величина εk столь мала, что вторым слагаемым в правой части неравенства можно пренебречь, то условия (9.14) будут выполняться при


В свою очередь оценки (9.15) - (9.17) показывают существенную зависимость сходимости процесса от величины суммы


если направления спуска -sk выбираются таким образом, что все


то


и, следовательно, чем ближе к 1/2 все значения qk, то есть чем выше точность в определении величины βk, тем выше скорость сходимости, которую гарантируют наши оценки.

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





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


Диски от INNOBI.RU




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