Теоретическая часть. Градиентные методы оптимизации
Градиентные методы оптимизации
Отчет о лабораторной работе
по курсу “Планирование и организация эксперимента”
ЯГТУ 200503.65 – 001 ЛР
Отчет выполнила
студентка гр. ЭСК-32
_______Бутусова А.О.
__________2011
Теоретическая часть
Метод градиента в чистом виде формирует шаг попеременным как функцию от градиента R(x) в текущей точке поиска. Простейший алгоритм поиска min R(x) записывается в векторной форме следующим образом:
Хi+1=Xi – h* gradR(x)j, или
Хi+1j=Xij – h* dR/dXj, j=1,2…n
Величина рабочего шага в направлении градиента h* gradR(x) зависит от величины градиента, который заранее учесть трудно, и от коэффициента пропорциональности шага h, с помощью которого можно управлять эффективностью метода.
Поиск каждой новой точки состоит из двух этапов:
1. Оценка градиента R(x) путем вычисления частных производных от R(x) по каждой переменной Xj
2. Рабочий шаг по всем переменным одновременно.
Величина h сильно влияет на эффективность метода.
Большей эффективностью обладает вариант метода, когда шаг по каждой переменной определяется направляющими косинусами градиента.
Хi+1j=Xij – h* cos(Wj), где cos(Wj)=dR/dXj/| gradR(x)j|
В этом случае величина рабочего шага не зависит от величины модуля градиента ей легче управлять изменением h. В районе оптимума могут возникать значительные «рысканья», поэтому используют различные алгоритмы коррекции h.
1. hj = const = h
2. hj = hj-1/2, если R(xi) > R(xi-1)
hj-1, если R(xi) < R(xi-1);
 |
3. hj= hj-1*2, если а<a1
hj, если а1<=a<=a2
hj/3, если а>a2
где а – угол между градиентами на предыдущем и текущем шаге, а1 и a2 – заданные пороговые значения. Вдали от оптимума значение градиента меняется мало, поэтому шаг можно увеличить, вблизи оптимума направление меняется резко(угол между градиентами большой), поэтому h сокращается.
Для оценки частных производных используются разностные методы:
· Алгоритм с центральной пробой
dR/dXj = [( X1,.., Xi, + gi,..,Xn) – R(X1,.., Xi,..,Xn)]/ gi
· Алгоритм с парными пробами
dR/dXj = [( X1,.., Xi, + gi,..,Xn) – R(X1,.., Xi,..,Xn)]/ gi*2
Первый алгоритм требует меньших затрат по сравнению со вторым, но позволяет получить решение менее точное, чем второй, и эта погрешность зависит от величины пробного шага.
Условием окончания поиска может являться малость модуля градиента R(x), т.е. /| gradR(x)|<e.
Основным недостатком градиентного метода является необходимость частого вычисления производных от R(x). Этого недостатка лишен метод наискорейшего спуска, который заключается в следующем.
В текущей точке вычисляется grad R(x), и затем в направлении градиента ищется min R(x). практически это может быть осуществлено любым методом одномерной оптимизации, в данной программе используется сканирование до первого локального минимума по направлению grad R(x).
В результате вдали от оптимума эффективность метода повышается, мы быстрее попадаем в район оптимума, в окрестности которого эффективность метода снижается из – за частой смены направления поиска и приближается к эффективности метода градиента.
Метод обладает небольшой эффективностью в овражных функциях. В ряде случаев можно повысить скорость выхода в район оптимума предъявлением невысоких требований к точности поиска min R(x) по направлению.
Условие окончания поиска - | gradR(x)| < e.
В ряде случаев используют уменьшение шага поиска оптимума по направлению после каждой смены направления. Это позволяет с большей точностью каждый раз находить оптимум, но резко снижает эффективность поиска в овражных функциях. Может использоваться для локализации «дна оврага» в специальных овражных методах. Условием окончания поиска в этом случае является достижение заданной малой величины шага.