Теоретическая часть. Градиентные методы оптимизации

Градиентные методы оптимизации

 

Отчет о лабораторной работе

по курсу “Планирование и организация эксперимента”

 

ЯГТУ 200503.65 – 001 ЛР

 

Отчет выполнила

студентка гр. ЭСК-32

_______Бутусова А.О.

__________2011

 

 

Теоретическая часть

 

Метод градиента в чистом виде формирует шаг попеременным как функцию от градиента R(x) в текущей точке поиска. Простейший алгоритм поиска min R(x) записывается в векторной форме следующим образом:

Хⁱ⁺¹=Xⁱ – h* gradR(x)^j, или

Хⁱ⁺¹_j=Xⁱ_j – h* dR/dX_j, j=1,2…n

Величина рабочего шага в направлении градиента h* gradR(x) зависит от величины градиента, который заранее учесть трудно, и от коэффициента пропорциональности шага h, с помощью которого можно управлять эффективностью метода.

Поиск каждой новой точки состоит из двух этапов:

1. Оценка градиента R(x) путем вычисления частных производных от R(x) по каждой переменной X_j

2. Рабочий шаг по всем переменным одновременно.

Величина h сильно влияет на эффективность метода.

Большей эффективностью обладает вариант метода, когда шаг по каждой переменной определяется направляющими косинусами градиента.

Хⁱ⁺¹_j=Xⁱ_j – h* cos(W_j), где cos(W_j)=dR/dX_j/| gradR(x)^j|

В этом случае величина рабочего шага не зависит от величины модуля градиента ей легче управлять изменением h. В районе оптимума могут возникать значительные «рысканья», поэтому используют различные алгоритмы коррекции h.

1. h^j = const = h

2. h^{j =} h^j-1/2, если R(xⁱ) > R(x^i-1)

h^j-1, если R(xⁱ) < R(x^i-1);

 

3. h^j= h^j-1*2, если а<a₁

h^j, если а₁<=a<=a₂

h^j/3, если а>a₂

 

где а – угол между градиентами на предыдущем и текущем шаге, а₁ и a₂ – заданные пороговые значения. Вдали от оптимума значение градиента меняется мало, поэтому шаг можно увеличить, вблизи оптимума направление меняется резко(угол между градиентами большой), поэтому h сокращается.

Для оценки частных производных используются разностные методы:

· Алгоритм с центральной пробой

dR/dX_j = [(X₁,.., X_i, + g_i,..,X_n) – R(X₁,.., X_i,..,X_n)]/ g_i

· Алгоритм с парными пробами

dR/dX_j = [(X₁,.., X_i, + g_i,..,X_n) – R(X₁,.., X_i,..,X_n)]/ g_i*2

Первый алгоритм требует меньших затрат по сравнению со вторым, но позволяет получить решение менее точное, чем второй, и эта погрешность зависит от величины пробного шага.

Условием окончания поиска может являться малость модуля градиента R(x), т.е. /| gradR(x)|<e.

Основным недостатком градиентного метода является необходимость частого вычисления производных от R(x). Этого недостатка лишен метод наискорейшего спуска, который заключается в следующем.

В текущей точке вычисляется grad R(x), и затем в направлении градиента ищется min R(x). практически это может быть осуществлено любым методом одномерной оптимизации, в данной программе используется сканирование до первого локального минимума по направлению grad R(x).

В результате вдали от оптимума эффективность метода повышается, мы быстрее попадаем в район оптимума, в окрестности которого эффективность метода снижается из – за частой смены направления поиска и приближается к эффективности метода градиента.

Метод обладает небольшой эффективностью в овражных функциях. В ряде случаев можно повысить скорость выхода в район оптимума предъявлением невысоких требований к точности поиска min R(x) по направлению.

Условие окончания поиска - | gradR(x)| < e.

В ряде случаев используют уменьшение шага поиска оптимума по направлению после каждой смены направления. Это позволяет с большей точностью каждый раз находить оптимум, но резко снижает эффективность поиска в овражных функциях. Может использоваться для локализации «дна оврага» в специальных овражных методах. Условием окончания поиска в этом случае является достижение заданной малой величины шага.