Градиентные методы

1.5 Градиентные методы

Как следует из названия, эти методы решения нелинейных оптимизационных задач используют понятие градиента функции[3,5,7]. Градиентом функции  называется вектор

 (1.14)

где  - единичные вектора (орты).

Величина этого вектора определяется по выражению

 (1.15)

Из (1.14) и (1.15) видно, что функция, градиент которой определяется, должна быть дифференцируемой по всем n переменным.

Физический смысл градиента функции в том, что он показывает направление (1.14) и скорость (1.15) наибольшего изменения функции в рассматриваемой точке. Если в некоторой точке , функция в этой очке не изменяется (не возрастает и не убывает). Эта точка соответствует экстремуму функции.

1.5.1 Градиентный метод с постоянным шагом

Сущность градиентных методов решения нелинейных оптимизационных задач [1,5,7] поясним для случая отыскания абсолютного минимума функции двух переменных , иллюстрируемого рис. 1.2. этот минимум находится в точке с координатами х10 и х20.

Рисунок 1.2 – Иллюстрация градиентного метода с постоянным шагом

В соответствии с граничными условиями (1.3), в большинстве практических оптимизационных задач они принимают только положительные или нулевые значения, областью  допустимых значений переменных будет первый квадрант системы координат х1 и х2. в этой области произвольно выберем исходное (нулевое) приближение – точку с координатами х10, х20. значение целевой функции в этой точке составляет Z0. В соответствии с выражением (1.15) вычислим в этой точке величину градиента функции Z.

Выполним шаг единичной длины () в направлении убывание функции Z. В результате выполненного шага получим первое приближение – точки с координатами х11, х21. Значение целевой функции в этой точке составляет Z1.

Далее вычислительная процедура повторяется: последовательно получаем 2-е, 3-е и 4-е приближения – точки с координатами х12, х22; х13, х23 и х14, х24. Значения целевой функции в этих точках соответственно составляют Z2, Z3 и Z4.

Из рис. 1.2 видно, что в результате вычиcлительного процесса последовательно осуществляется "спуск" к минимуму функции Z. Вычислительная процедура заканчивается, когда относительное изменение целевой функции на предыдущем i-м и последующем (i+1)-м шагах оказывается меньше заданной точности вычислений :

 (1.16)

Рассмотренная вычислительная процедура носит название градиентного метода с постоянным шагом. В этом методе все шаги выполнялись одинаковой длины . Метод достаточно прост. Основной его недостаток – большая вероятность зацикливания вычислительного процесса в окрестности минимума функции Z. В соответствии с рис. 1.2 вычислительный процесс зациклится между точками с координатами х13, х23 и х14, х24. При этом в качестве искомого решения следует принять одну из этих точек.

Для получения более точного результата необходимо выбрать шаг меньшей длины. При этом объем вычислений (количество шагов) увеличится.

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

1.5.2 Метод скорейшего спуска

Как было отмечено выше, при увеличении длины шага объем вычислений (количество шагов) уменьшается, однако уменьшается и точность определения минимума целевой функции. При уменьшении длины шага точность увеличивается, однако объем вычислений (количество шагов) возрастает.

Поэтому вопрос о выборе рациональной длины шага в градиентных методах является своего рода оптимизационной задачей. Один из способов определения оптимальной длины шага  иллюстрируется на рис. 1.3 и носит название метода скорейшего спуска [1,7].

Рисунок 1.3 – Иллюстрация метода скорейшего спуска (а) и параболическая аппроксимация целевой функции для выбора оптимального шага (б)

В методе наискорейшего спуска желательно использовать рассмотренное свойство направления градиента. Поэтому, если мы находимся в точке хi на некотором шаге процесса оптимизации, то поиск минимума функции осуществляется вдоль направления -. Данный метод является итерационным. На шаге i точка минимума аппроксимируется точкой хi . Следующей аппроксимацией является точка

 (1.17)

где λi - значение λ, минимизирующее функцию.

. (1.18)

Значение λi может быть найдено с помощью одного из методов одномерного поиска (например, методом квадратичной интерполяции).

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

Для поиска минимума функции

 (1.19)

в направлении di из точки xi используется метод квадратичной интерполяции.

В точке , и мы выбираем длину шага λ такой, чтобы шаг "перекрыл " минимум функции φ(λ). Производная

. (1.20)

Данный оператор for(i=0;i<n;i++) g2+=g[i]*d[i]; - вычисляет выражение

. (1.21)

Оператор if (ff[2]>=ff[0] || g2>=0) проверяет условие "перекрытия" минимума, которое выполняется при выполнении либо одного, либо другого условия. Если минимум не попал в отрезок (0,λ), то λ удваивается, и это повторяется столько раз, сколько необходимо для выполнения условия "перекрытия".

Удостоверившись, что отрезок (0,λ) содержит минимум, в качестве третьей точки возьмем точку λ/ 2. Минимальную точку сглаживающего квадратичного полинома находим в соответствии с соотношением

 (1.22)

что отражено следующими операторами

l[3]=h*(ff[1]-.75*ff[0]-.25*ff[2]);

l[3]/=2*ff[1]-ff[0]-ff[2];

Оператор for(i=0;i<n;i++)

{ x[i]=y[i]+l[0]*d[i]; y[i]=x[i]; }

производит присваивание xi+1=xi, и если |g(xi+1)| достаточно мало, то процесс заканчивается. В процессе поиска предполагается сходимость к экстремуму, поэтому для эффективности процедуры разумно уменьшить длину шага. При этом деление шага пополам выбрано произвольно.

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