Материал: 862

30

Глава 3. ГРАДИЕНТНЫЕ МЕТОДЫ ПОИСКА ЭКСТРЕМУМА

В математике известна методика определения производной от рассматриваемой функции по заданному направлению. Так, если через l обозначить вектор заданного направления, то производная функции по этому направлению определяется по формуле

где R(xi) – рассматриваемая функция, зависящая от n неизвестных x1, x2, … xi, …, xn ; i – угол наклона l - го вектора к i -й оси координат.

3.1. Понятие градиента

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

Градиент функции имеет следующее обозначение

g grad R(xi ). (31)

Для функции многих переменных градиент определяется по следующей формуле:

где R(xi ) – координата вектора-градиента по i -й оси.

xi

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

31

3.2. Метод градиента

Сущность этого метода сводится к выполнению следующих операций:

1.В исходной точке определяется градиент рассматриваемой функции.

2.В направлении градиента осуществляют рабочий шаг.

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

а) определяются точки, откуда шагаем и куда шагаем; б) сравниваются отклики в этих точках и шаг считается удачным,

если величина целевой функции улучшилась, т.е. увеличилась при поиске максимума (max) и уменьшилась при определении минимума

(min).

В каждой новой точке вычисляется величина целевой функции. Алгоритм поиска следующий:

где i – номер текущей переменной; j – номер шага; hi – фактор шага по i - й переменной, который принимается постоянным,равным заданной точности поиска, если поиск ведется в стационарной области. При большом удалении от оптимума величина шага принимается пропорционально величине первой производной по каждой координате.

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

3.3. Метод релаксаций

Метод релаксаций заключается в следующем:

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

32

б) из всех вычисленных производных определяют наибольшую; в) в направлении наибольшей производной осуществляется первый шаг и если он оказался удачным, то величину последующего шага удваивают и осуществляют в этом же направлении еще один шаг. Если и он оказался удачным, то предыдущий шаг вновь удваивают. Эта последовательность применяется до тех пор, пока не будет произведен неудачный шаг. При неудачном шаге величина шага или фактор шага уменьшается в два раза и шаг осуществляется

из последней удачной точки.

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

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

Алгоритм поиска следующий:

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

33

3.4. Метод крутого восхождения

Метод крутого восхождения (наискорейшего спуска) вобрал в себя все лучшее предыдущих методов и сводится к следующему:

а) определяется градиент в исходной точке; б) в направлении градиента осуществляется не один шаг, как в

методе градиента, а несколько шагов, пока не будет достигнут экстремум в данном направлении. Причем, каждый последующий шаг удваивается после того, как предыдущий шаг окажется удачным. Шаг считается удачным, если в результате движения функция улучшается, т.е. увеличивается при поиске максимума и уменьшается при определении минимума;

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

г) в последней удачной точке вновь определяется градиент и движение по новому направлению продолжается;

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

Результаты решения по всем рассмотренным методам записываются в следующем виде (образец ответа):

Ответ:

34