Строительные исследования
страница - 0
ПОМЕХОУСТОЙЧИВОСТЬ МЕТОДА РАЗНОСТНОЙ АППРОКСИМАЦИИ ГРАДИЕНТА ПРИ РАСПАРАЛЛЕЛИВАНИИ
Перунова Ю.Н. (iperunova@aeroflot.ru)
МГУ, факультет ВМиК
1. Введение
Рассмотрим задачу
F (x) - min,(1.1)
где Rk -- k - мерное Евклидово пространство, функция цели F: Rk - R? непрерывно дифференцируема на Rk и ее градиент VF() удовлетворяет условию Липшица с некоторой константой L>0:
VF О e CLip (R к, L).(1.2)
Требуется найти приближенное решение задачи (1.1), т.е. точку xeXopt(s) для
достаточно малого s>0. Здесь
Xopt(s):= {x e R tF (x) < fopt +s}, fopt := mRnF(x).
Обычно, задача безусловной оптимизации выпуклой функции цели решается стандартными локальными алгоритмами, например, различными алгоритмами градиентного спуска [1]. Градиентные алгоритмы хорошо изучены и позволяют быстро находить единственный экстремум. Однако на практике большинство нелинейных задач являются многоэкстремальными. В таких случаях, для поиска глобального экстремума можно применить те же алгоритмы локальной оптимизации, используя не одну, а множество точек начального приближения. Этот подход носит название метода мультистарта [2].
Эффективность применения метода мультистарта зависит от свойств составляющих его локальных алгоритмов. Поэтому для выбора стартовых точек и
определения критерия остановки вычислений необходимо изучить траектории алгоритмов в условиях многоэкстремальности функции цели.
При решении многоэкстремальных задач глобальной оптимизации желательно, чтобы алгоритмы локального спуска рассматривали незначительные минимумы как помехи в вычислении значений функции цели и не обращали на них внимания. Другими словами, благодаря своей помехоустойчивости, алгоритмы приобретают некоторые глобальные свойства. На основании исследований, приведенных в главе 4 из [3] можно считать, что наименее чувствительны к разного рода помехам методы прямого поиска. В тоже время такие помехоустойчивые алгоритмы, обладая низкой скоростью сходимости и используя ограниченную информацию о функции цели, требуют при расчете траекторий больших временных затрат.
Один из путей решения современных задач повышенной вычислительной сложности в режиме реального времени состоит в применении параллельных версий алгоритмов оптимизации. Реализация алгоритмов на многопроцессорных или векторных системах позволяет проводить независимые расчеты для нескольких траекторий одновременно, а также сокращать затраты времени, используя дополнительные вычислительные мощности в рамках одной итерации [4] - [6].
В настоящей работе предложена параллельная версия модифицированного алгоритма градиентного спуска и рассмотрена его сходимость при наличие постоянного шума неопределенной природы при вычислении значений функции цели.
Изучение помехоустойчивости параллельных версий локальных алгоритмов спуска является продолжением анализа свойств конечно-разностных алгоритмов для решения задач оптимизации строго выпуклых функций [7].
2. Помехоустойчивость алгоритма градиентного спуска
Исследуем поведение траекторий алгоритма градиентного спуска при наличии шума при вычислении значений функции и градиента.
Классический алгоритм скорейшего градиентного спуска (ГС) с учетом погрешности будет иметь следующий вид:
xn+1 = xn -an(VF(xn +дг(хп)),n = 0,1,...;x0 eRk, где шаг an, n=0,1,... удовлетворяет условию
an = argmin (F~(xn) - a(VF(xn) + (xn))),
a =ia0,i=0,1,..., N0
ао>0, NogN -- параметры, ao<1/(2L), Noao>1;
. . . F( x ) = F ( x ) + S0( x), So(x} <so,\8x(x) < s1, VхeRt,
S0(x)e R1, S1(x)e Rk -- возмущения F(x) и VF(x) соответственно, s0, s1>0 -- размеры возмущений; x0 e Rk -- стартовая точка.
Для ограниченной последовательности {xn}, xne Rk, n=1,2,..., обозначим через It {xn} множество ее предельных точек и будем говорить, что {xn} сходится к Ac3RK, если It aA.
Свойства сходимости градиентного метода при s0= s1= 0 хорошо известны (см., например, [8]). В [3] без указания точных оценок представлены помехоустойчивость метода ГС при s0=0, s1>0 и скорость сходимости его траекторий к некоторой окрестности точки локального минимума.
Для описания параметров этой окрестности представим помехоустойчивость метода скорейшего спуска другим способом. Нам потребуется следующая лемма Лемма 2.1 Для любых x, SeRk и а, 0<а < 1/L, справедливы оценки:
F(x) - F(x - a(VF(x) + S)) > a(\VF(x)\\ +SX(1 - a L)\VF(x) - (a L)S).n
Следствие 2.2 Для каждого x,8 eRk и a0, No: 0<a0<1/(2L), a0N0<1/L, выполнено
F(x) - min F(x - ia0 (VF(x) + S))(VF(x)2 - Щ2),
□
где Co :=1 /(1-2Lao)>1.
Введем обозначение для s -окрестности множества стационарных точек функции F(x) как
XJ&):= {x e R t VF (x) <s}. Теорема 2.3 Каждая траектория {xn} метода ГС сходится к
XJs2, + 4 LC„s„)1/2).п
Введем несколько важных параметров для описания основных свойств
регулярных функций цели. Речь не идет о сужении класса рассматриваемых задач.
Введение параметров позволит изучать и сравнивать между собой численные
методы оптимизации.
Определение 2.4 Будем называть функцию F(x) регулярной функцией с параметрами ц, v, L>0 и Me{1,2,...}, если
содержание:
[стр.Введение] [стр.1] [стр.2] [стр.3]