Строительные исследования
страница - 1
1)функция F(x), F: RkR1 непрерывно дифференцируема на Rk и выполнено условие (1.2);
2)множество стационарных точек функции F(x) конечно
Xstat=Xstat(0) = {xstat v-J x stat X X stat\ = M;
3)в некоторой -окрестности множества Xstat существует гессиан H=F"(x) функции F(x) и он невырожден
H-1 < 1/U Vxe Вц(Xstat);
4)для некоторого v>0 и для ц>0 из п.3) выполнено
Xstat( v) е B ц ( Xstat),
где
Bs(X) := { x e Rk 3 xeX :x-x\\ <s};
5)множество
Xstat() := {x e Rk VF(x) <s} ограничено для любого s>0.
Теорема 2.5 Пусть функция цели F() - регулярная функция с параметрами ц, v, и, L>0 и Me{1,2,...} в смысле определения 2.4, и величины возмущений s0, s1 удовлетворяют условию
si + 4LC0£0 <v2.
Тогда любая траектория {xn} метода ГС сходится к s -окрестности одной из стационарных точек функции F()), т.е.
м
lt{xn}е U Bs(xLt),
i =1
где
S= min(n,-(s12 + 4ZC0s0)1/2).□
U
Очевидно, что
t"22V21/2 \
s< max(-s13 --s0 ) .
Глобальный оптимум предлагается находить путем сравнения результатов решения Mзадач локальной оптимизации в B (x\tat), i = 1,...,M.
Параметр ц служит для описания величины окрестности стационарного множества Х5ш, в которой поведение F() близко к поведению квадратичной функции. Оценками величин гессиана и градиента F() в этой окрестности являются 1 и vсоответственно. Поиск решения задачи оптимизации в Вц(x\tat) не составляет
большого труда, так как задача оказывается одноэкстремальной. Более того, в Вц(xltat) эффективно работают методы квазиньютоновского типа, обладающие
высокой скоростью сходимости.
Другими словами, показателем "хорошей" регулярной функции являются достаточно большие значения параметров ц и v и не слишком большое значение параметра M, а нашей задачей становится построение методов, траектории которых сходятся к Bv( Xstat).
В рамках решения этой сложной задачи предлагается описание области предельных точек алгоритма ГС, использующего вместо точных производных конечные разности.
3. Параллельная версия алгоритма градиентного спуска с использованием конечных разностей
В случае, когда функция цели задачи оптимизации не задана явно, ее градиент не определен и применение метода градиентного спуска (ГС) невозможно. Для решения таких задач предлагается заменить значение точного градиента функции V F(x) в алгоритме ГС на его приближенное значение с использованием конечных разностей при шаге дискретизации h>0.
Точность аппроксимации градиента конечными разностями достаточно высока при малом значении параметра h. Поэтому, теорема 2.3 гарантирует сходимость траекторий метода градиентного спуска в некоторую небольшую окрестность локального минимума функции цели.
С другой стороны, выбирая h не очень маленьким, а в соответствии с глобальной структурой функции цели, можно значительно повысить эффективность каждой итерации метода [9].
При наличии нескольких процессоров расчет каждой итерации метода для различных значений h возможно осуществлять параллельно, выбирая затем лучший
результат. Тем самым обеспечивается оптимальный подбор параметра h без дополнительных временных затрат.
Пусть e0 -- стандартный ортонормированный базис в Rk, е°={е0,...,e0},
е0 =(1,0,...,°),..., e0 =(0,...,0,1), а G(x,h) = (G(x,h) 1 ,..,G(x,h)2)e Rk - аппроксимация градиента VF(x) конечными разностями
G(x,h)i: = (F(x+he0) - F(x))/h, i=1 ,...,k,
с параметром h>0.
Лемма 3.1 Для любого h>0 и x e Rk
I G(x,h)-V F(x) <VkLh/2.С
С учетом погрешности в вычислении значений функции F(x):
G (x,h) = (G (x,h) 1G (x,h)k)(3.1)
G (x,h)i = (F (x+he0) - (F (x)))/h, i=1,..., k, n=0,1,..., x e Rk,
где
F (x)= F(x) + d0(x).
Вычисления вектора приближенного градиента G (x,h) из (3.1) в точке x для различных значений параметра h будем выполнять независимо друг от друга. Таким образом, параллельные вычисления по модифицированному алгоритму градиентного спуска позволяют аппроксимировать направление поиска решения задачи оптимизации, затратив времени не больше, чем на вычисление точного градиента в последовательном алгоритме градиентного спуска.
Для распределения вычислений на несколько процессоров в данном случае используется топология звезды [4]. Общее число процессоров равно (p+1).
Для вычисления одной итерации алгоритма на каждом l-ом рабочем процессоре l=1,..,p в качестве возможного направления спуска функции F в точке x
используется вектор -G (x,hl ), где
h>0- различные значения параметра дискретизации h, l=1,..,p.
содержание:
[стр.Введение] [стр.1] [стр.2] [стр.3]