$AlexLat$

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

Градиентные методы оптимизации относятся к численным методам поискового типа. Они универсальны, хорошо приспособлены для работы с современными цифровыми вычислительными машинами и в большинстве случаев весьма эффективны при поиске экстремального значения нелинейных функций с ограничениями и без них, а также тогда, когда аналитический вид функции вообще неизвестен. Вследствие этого градиентные, или поисковые, методы широко применяются на практике.Сущность указанных методов заключается в определении значений независимых переменных, дающих наибольшие изменения целевой функции. Обычно для этого двигаются вдоль градиента, ортогонального к контурной поверхности в данной точке.Различные поисковые методы в основном отличаются один от другого способом определения направления движения к оптимуму, размером шага и продолжительностью поиска вдоль найденного направления, критериями окончания поиска, простотой алгоритмизации и применимостью для различных ЭВМ. Техника поиска экстремума основана на расчетах, которые позволяют определить направление наиболее быстрого изменения оптимизируемого критерия.

Если критерий задан уравнением

F= F(x1,x2,...,x), (3)

то его градиент в точке (x1, x2,…, xn) определяется вектором:

. (4)

Частная производная  пропорциональна косинусу угла, образуемого вектором градиента с i-й осью координат. При этом

 (5)

Наряду с определением направления градиентного вектора основным вопросом, решаемым при использовании градиентных методов, является выбор шага движения по градиенту. Величина шага в направлении gradF в значительной степени зависит от вида поверхности. Если шаг слишком мал, потребуются продолжительные расчеты; если слишком велик, можно проскочить оптимум. Размер шага  ∆x1 должен удовлетворять условию, при котором все шаги от базисной точки лежат в том же самом направлении, что и градиент в базисной точке. Размеры шага по каждой переменной xi вычисляются из значений частных производных в базовой (начальной) точке:

 (6)

где К – константа, определяющая размеры шага и одинаковая для всех i-х направлений. Только в базовой точке градиент строго ортогонален к поверхности. Если же шаги слишком велики в каждом i-м направлении, вектор из базисной точки не будет ортогонален к поверхности в новой точке.

Если выбор шага был удовлетворительным, производная в следующей точке существенно близка к производной в базисной точке.

Для линейных функций градиентное направление не зависит от положения на поверхности, для которой оно вычисляется. Если поверхность имеет вид

F = c1x1 + c2x2 + c3x3

то

и компонента градиента в i-м направлении равна

. (7)

Для нелинейной функции направление градиентного вектора зависит от точки на поверхности, в которой он вычисляется.

Несмотря на существующие различия между градиентными методами, последовательность операций при поиске оптимума в большинстве случаев одинакова и сводится к следующему:

а) выбирается базисная точка;

б) определяется направление движения от базисной точки;

в) находится размер шага;

г) определяется следующая точка поиска;

д) значение целевой функции в данной точке сравнивается с ее значением в предыдущей точке;

е) вновь определяется направление движения и процедура повторяется до достижения оптимального значения.

Градиентный метод первого порядка

При оптимизации методом градиента оптимум исследуемого объекта ищут в направлении наиболее быстрого возрастания (убывания) выходной переменной, т.е. в направлении градиента. Но прежде чем сделать шаг в направлении градиента, необходимо его рассчитать. Градиент можно рассчитать либо по имеющейся модели

grad y(X)=  ,

моделирование динамический градиентный полиномиальный

где  - частная производная по i-му фактору;

i, j, k – единичные векторы в направлении координатных осей факторного пространства, либо по результатам n пробных движений в направлении координатных осей.

Если математическая модель статистического процесса имеет вид линейного полинома, коэффициенты регрессии b_i которого являются частными производными разложения функции y = f(X) в ряд Тейлора по степеням x_i, то оптимум ищут в направлении градиента с некоторым шагом h_i:

пкфв н(Ч)= и₁р₁+и₂р₂+…+и_тр_т

Направление корректируют после каждого шага.

Метод градиента вместе с его многочисленными модификациями является распространенным и эффективным методом поиска оптимума исследуемых объектов. Рассмотрим одну из модификаций метода градиента – метод крутого восхождения.

Метод крутого восхождения, или иначе метод Бокса-Уилсона, объединяет в себе достоинства трех методов - метода Гаусса-Зейделя, метода градиентов и метода полного (или дробного) факторного экспериментов, как средства получения линейной математической модели. Задача метода крутого восхождения заключается в том, чтобы шаговое движение осуществлять в направлении наискорейшего возрастания (или убывания) выходной переменной, то есть по grad y(X). В отличии от метода градиентов, направление корректируется не после каждого следующего шага, а при достижении в некоторой точке на данном направлении частного экстремума целевой функции, как это делается в методе Гаусса-Зейделя. В точке частного экстремума ставится новый факторный эксперимент, определяется математическая модель и вновь осуществляется крутое восхождение. В процессе движения к оптимуму указанным методом регулярно проводиться статистический анализ промежуточных результатов поиска. Поиск прекращается, когда квадратичные эффекты в уравнении регрессии становятся значимыми. Это означает, что достигнута область оптимума.

Опишем принцип использования градиентных методов на примере функции двух переменных

 (8)

при наличии двух дополнительных условий:

, .(9)

Этот принцип (без изменения) можно применить при любом числе переменных, а также дополнительных условий. Рассмотрим плоскость x₁, x₂ (Рис. 1). Согласно формуле (8) каждой точке соответствует некоторое значение F. На Рис.1 линии F = const, принадлежащие этой плоскости, представлены замкнутыми кривыми, окружающими точку M^*, в которой F минимально. Пусть в начальный момент значения x₁ и x₂ соответствуют точке M₀. Цикл расчета начинается с серии пробных шагов. Сначала величине x₁ дается небольшое приращение  ; в это время значение x₂ неизменно. Затем определяется полученное при этом приращение   величины F, которое можно считать пропорциональным значению частной производной

 (10)

(если величина  всегда одна и та же).

Рис.1

Далее дается приращение   величине x₂. В это время x₁ = const. Получаемое при этом приращение   величины F является мерой другой частной производной:

. (11)

Определение частных производных ( 10 ) и ( 11 ) означает, что найден вектор с координатами  и , который называется градиентом величины F и обозначается так:

. (12)

Известно, что направление этого вектора совпадает с направлением наиболее крутого возрастания величины F. Противоположное ему направление – это «наискорейший спуск», другими словами, наиболее крутое убывание величины F.

После нахождения составляющих градиента пробные движения прекращаются и осуществляются рабочие шаги в направлении, противоположном направлению градиента, причем величина шага тем больше, чем больше абсолютная величина вектора grad F. Эти условия осуществляются, если величины рабочих шагов  ∆x1и ∆x2 пропорциональны полученным ранее значениям частных производных:

, , (13)

После каждого рабочего шага оценивается приращение  ∆Fвеличины F. Если оно оказывается отрицательным, то движение происходит в правильном направлении и нужно двигаться в том же направлении M0M1 дальше. Если же в точке M1 результат измерения показывает, что ∆F > 0 , то рабочие движения прекращаются и начинается новая серия пробных движений. При этом определяется градиент gradF в новой точке M1, затем рабочее движение продолжается по новому найденному направлению наискорейшего спуска, т. е. по линии M1M2, и т.д. Этот метод называется методом наискорейшего спуска/крутого восхождения.

Когда система находится вблизи минимума, показателем чего является малое значение величины

  (14)

происходит переключение на более «осторожный» метод поиска, так называемый метод градиента. От метода наискорейшего спуска он отличается тем, что после определения градиента gradF делается лишь один рабочий шаг, а затем в новой точке опять начинается серия пробных движений. Такой метод поиска обеспечивает более точное установление минимума по сравнению с методом наискорейшего спуска, между тем как последний позволяет быстрее приблизиться к минимуму. Если в процессе поиска точка М доходит до границы допустимой области и хотя бы одна из величин М1, М2 меняет знак, метод меняется и точка М начинает двигаться вдоль границы области.

Эффективность метода крутого восхождения зависит от выбора масштаба переменных и вида поверхности отклика. Поверхность со сферическими контурами обеспечивает быстрое стягивание к оптимуму.

К недостаткам метода крутого восхождения следует отнести:

1. Ограниченность экстраполяции. Двигаясь вдоль градиента, мы основываемся на экстраполяции частных производных целевой функции по соответствующим переменным. Однако форма поверхности отклика может изменяться и необходимо изменять направление поиска. Другими словами, движение на плоскости не может быть продолжительным.

2. Трудность поиска глобального оптимума. Метод применим для отыскания только локальных оптимумов.