Строительные исследования
страница - 2
Выбор наиболее подходящего параметра h>0 осуществляет управляющий (р+1)-ый процессор по результатам спуска в рамках одной итерации.
Алгоритм A(p).
Параметры: h о, ао > 0, So, No e N, 0<6<1, sstop > 0,
11
ао < -, Nao > -, pe N.
4L L
Входные данные: x0 e Rk
Результат: Nstop e N,xNstope Rk $
Обозначим:
И - инициализация: n := 0; xn := x0.
П - подготовка к работе: n := n+1; xn : = xn-1.
Р -- вычисления на /-ом рабочем процессоре, l=1,..,p:
(ai,hi) := arg
min
1 AT
F (xn -a G (xn,h));
a=ia„,i=0,...,N„ ;
h = h„6j, j = (l-1) So,...,fao-1
У -- вычисления на (p+-ом управляющем процессоре:
(an,hn) := arg min F (xn -a,G (xn,h/));
l =1,..., p
xn := xn
an G (xn,hn);
К -- критерий остановки:
F~ (xn-1)
F (xn) < sstop,
О -- остановка вычислений: Nstop := n; xNstop := xn.
Блок-схема метода изображена на Рисунке 1.
Рисунок 1. Блок-схема алгоритма разностной аппроксимации градиента при распараллеливании.
Нетрудно заметить, что для любой траектории {xn} алгоритма A(p) мы получаем
F (xn) -F (xn+1) > Sstop >0, n = 0,1,...,Nstop- 1.
Так как F (x) близка к регулярной функции F(x), то
min F (x) > - 00,
следовательно
Nstop < + 00.
Теорема 3.2 Каждая траектория {xn } метода A(p) сходится к
Xstat(4k (Lh0/2+2s0/ф0вр3о-1))+2л1 LC{)s{) ).
Для последовательного алгоритма А(1), в случае постоянного значения параметра hn = 2.yje0 /L , n=0,1,...,Nstop, при k>1, s0 <v2/(16/Lk) выполнено
M
lk {xn} e U Bs(x),
=1
где
s = min(/7, -s0/2).
Предложенный параллельный алгоритм был реализован на системе Parsytec Supercluster ВЦ РАН для поиска решения ряда тестовых задач, а также реальной задачи структурной химии - задачи конформации многоатомных молекул.
Для практического сравнения результатов работы последовательной и параллельной версий модифицированного алгоритма градиентного спуска рассматривался алгоритм с применением конечных разностей A(1) и A(p),p>1, а также обычный последовательный точный градиентный алгоритм скорейшего спуска [10] (стр. 261).
4. Заключение
В результате проведенных исследований было показано, что классический алгоритм скорейшего спуска обладает свойством устойчивости к помехам в вычислении градиента функции цели задачи оптимизации. Приведено описание области предельных точек траекторий алгоритма скорейшего спуска и параллельной версии алгоритма разностной аппроксимации градиента.
Использование параллельных вычислений значительно сокращает временные затраты при подборе оптимального значения параметра конечных разностей h. Параллельная версия разностного алгоритма градиентного спуска по сравнению со своим последовательным аналогом обладает большей вычислительной мощностью и в p раз (где p - количество используемых рабочих процессоров) тщательнее исследует область текущего значения аргумента xn.
содержание:
[стр.Введение] [стр.1] [стр.2] [стр.3]