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


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

9.8. Циклический покоординатный спуск

В этом методе выбор направления спуска не зависит от информации о градиенте минимизируемой функции: сначала спускаются по направлению e1 затем-по е2 и т. д., вплоть до еn, после чего весь цикл повторяют снова.

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

Существует и другая сторона целесообразности использования метода циклического покоординатного спуска, а именно получение масштабных множителей для преобразования переменных. Поясним это подробнее.-Рассмотрим простой пример. Пусть


Если числа αi сильно различающиеся, то линии (поверхности) уровня функции φ(x) сильно вытянуты по тем направлениям еi которым соответствуют малые значения αi. Тогда при движении вдоль направления антиградиента (метод градиентного спуска) смещение в направлении точки минимума будет довольно медленным Заменой переменных xi = μiyi можно добиться того, чтобы в новых переменных yi линии уровня стали сферами.

Для этого нужно взять μii-1/2 В новых переменных точка минимума для квадратичной функции находится градиентным методом за одну итерацию. Преобразование xii-1/2yi называют изменением масштабов.

В случае, если φ(x) гладкая выпуклая функция выбирают


в точке х одномерного минимума вдоль направления ei. Множитель μi пропорционален радиусу кривизны линии уровня в точке х. И хотя это преобразование не превратит в сферы линии уровня, но уменьшит их вытянутость и тем самым облегчит применение градиентных методов минимизации.

Величины


вычисляют приближенно, пользуясь

их конечно-разностной аппроксимацией. Метод циклического покоординатного спуска как раз и позволяет получать последовательные приближения величин масштабных множителей μi.

Опишем схему метода.

Первый цикл.

Исходя из произвольной точки х0, строят


Второй цикл.


l-й цикл.


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

Сходимость метода для выпуклых функций из класса С1,1n) со скоростью порядка O(1/m) можно гарантировать, ввиду оценок предыдущего пункта, лишь для n=2. В то же время нетрудно доказать, что если последовательность {xk} сходится, то в ее предельной точке х будет φ' (x) = 0.

Теорема 9.8.Если функция φ(x) принадлежит классу С1,1n), а последовательность {хk}, построенная методом циклического покоординатного спуска, сходится при k→∞ к точке х, то φ'(x̄) = 0 и, следовательно, точка х является стационарной*.

Доказательство. Запишем последовательность {xk} следующим образом:

xk+1=xkkej(k)

где j(k) принимает соответствующие значения 1, 2, ..., n. Пользуясь леммой 9.3 и определением βk, получаем (аналогично тому, как это делалось в предыдущем пункте)


Так как последовательность {xk} сходится, то φ(xk)-φ(xk+1)→0 при k→∞ и ∂φ(xk)/∂xj(k)→0 при k→∞.

* (Для выпуклой функции φ'(x) точка х будет точкой минимума. )

В предельной точке х̄ будет φ' (х̄) = 0. В самом деле, если предположить, что по некоторому направлению ei будет


то в достаточно малой окрестности этой точки будет


Но так как, начиная с некоторого номера k0, все точки xk попадут в нашу окрестность, то последнее неравенство противоречит тому, что


при k→∞.

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

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





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


Диски от INNOBI.RU




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