многих переменных

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

2.4.1 Метод координатного спуска

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

Основные этапы поиска

min f (х ₁, х ₂ ,..., х_n) методом координатного спуска:

1) выбор начального приближения ;

2) выбор направления поиска, т.е. номера i Î (1, 2,..., n) компоненты вектора

(x ₁, x ₂ ..., x_n), которая подлежит изменению;

3) вычисление значения частной производной целевой функции по выбранному аргументу , если f ^¢ _i > 0, то с ростом x_i значение функции f (х ₁, х ₂ ,..., х_n) увеличивается, а если f ^¢ _i < 0, то уменьшается;

4) изменение значений х ₁, х ₂ ,..., х_n в соответствии с выражением:

(2.3)

до тех пор, пока f (х ₁^{(k +1)}, х ₂^{(k +1)},..., х_n ^{(k +1)})< f (х ₁^(k), х ₂^(k),..., х_n ^(k)); в противном случае производится возврат на п. 2) и выбор следующего направления поиска, при этом x _i ⁽⁰⁾ = x _i ^(k), i = 1, 2,... n (h - шаг поиска, sign (z) - знак выражения z);

5) если движение с шагом h в любом из n возможных направлений приво-

дит к ситуации f (х ₁^{(k+ 1)}, х ₂^{(k+ 1)},..., х_n ^{(k+ 1)}) ³ f (х ₁^(k), х ₂^(k),..., х_n ^(k)), то осуществляется дробление шага: h = h/p (p > 1) и вновь выполняется п. 4);

6) поиск считается законченным, когда значение h становится меньше заданной точности e.

2.4.2 Методы градиента

Определение: градиент функции f (x ₁, x ₂ ,..., x_n) в точке (x ₁⁽⁰⁾, x ₂⁽⁰⁾,..., x_n ⁽⁰⁾) - это вектор, длина которого (2.4)

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

Идея методов: каждая следующая точка поиска min f (x ₁, x ₂ ,..., x_n) (каждый новый член минимизирующей последовательности) получается в результате перемещения из предыдущей точки по направлению антиградиента целевой функции. Если в результате этого перемещения наблюдается увеличение значения целевой функции, то значение рабочего шага поиска h уменьшается. Поиск прекращается, когда выполняется необходимое условие ext f (x ₁, x ₂ ,..., x_n), например длина градиента становится меньше требуемой точности: , (2.5)

либо меньше требуемой точности становится величина шага поиска: h < e. (2.6)

Различают методы градиента с переменным шагом и с постоянным шагом. При использовании метода градиента с переменным шагом изменение значений x ₁, x ₂ ,..., x_n производится согласно выражению:

, i =1, 2,..., n, k =0, 1, 2…, (2.7)

а останов поиска - при выполнении неравенства (2.5). При возникновении ситуации f (х ₁^{(k +1)}, х ₂^{(k +1)},..., х_n ^{(k +1 )} ) ³ f (х ₁^(k), х ₂^(k),..., х_n ^(k)) значение h уменьшается, например делится на число р > 1. Характер изменения значений x ₁, x ₂ ,..., x_n согласно (2.7) зависит от величины и знака соответствующих частных производных целевой функции. По мере приближения к точке min f (x ₁, x ₂ ,..., x_n) абсолютные величины частных производных уменьшаются, следовательно и шаг поиска является переменным - уменьшается по мере приближения к искомой точке.

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

, i =1, 2,..., n; k =0, 1, 2,..., (2.8)

т.е. расстояние между точками (x ₁^(k), x ₂^(k),..., x_n ^(k)) и (x ₁^{(k+ 1)}, x ₂^{(k+ 1)},..., x_n ^{(k+ 1)}) равно

,

следовательно величина шага поиска в данном случае постоянна и равна выбран-

ному значению h. Если изменение аргументов целевой функции в соответствии с (2.8) приводит к увеличению ее значения, шаг поиска уменьшается. Останов поиска min f (x ₁, x ₂ ,..., x_n) по методу градиента с постоянным шагом осуществляется при выполнении неравенства (2.6).

2.4.3 Метод наискорейшего спуска

Это модификация метода градиента с постоянным шагом, позволяющая сократить общий объем вычислений при некотором увеличении числа членов минимизирующей последовательности за счет меньшего количества вычислений частных производных целевой функции. При использовании этого метода аргументы целевой функции изменяются в соответствии с выражением (2.8), но значения ее частных производных и длины градиента не пересчитываются до тех пор, пока не сложится ситуация f (х ₁^{(k +1)}, х ₂^{(k +1)},..., х_n ^{(k +1)}) ³ f (х ₁^(k), х ₂^(k),..., х_n ^(k)). Дробление шага поиска производится, когда во вновь выбранном направлении (после пересчета значений частных производных) не удается сделать ни одного результативного шага, останов поиска - при выполнении неравенства (2.6).

Основные этапы поиска min f (x ₁, x ₂ ,..., x_n) методом наискорейшего спуска:

1) выбор начального приближения (x ₁⁽⁰⁾, x ₂ ⁽⁰⁾,..., x_n ⁽⁰⁾);

2) определение значений частных производных f (x ₁, x ₂ ,..., x_n) в этой точке;

3) изменение значений x_i, i =1, 2,..., n в соответствии с выражением (2.8) без пересчета частных производных до начала возрастания целевой функции;

4) если ситуация f (х ₁^{(k +1)}, х ₂^{(k +1)},..., х_n ^{(k +1)}) ³ f (х ₁^(k), х ₂^(k),..., х_n ^(k)) возникает при

k > 0, то начальным приближением становится предыдущая точка: x_i ⁽⁰⁾ = x_i ^(k),

i =1, 2,..., n и вновь выполняются п.п. 2), 3);

5) если f (х ₁^{(k +1)}, х ₂^{(k +1)},..., х_n ^{(k +1 )} ) ³ f (х ₁^(k), х ₂^(k),..., х_n ^(k)) уже при k =0, то осуществляется дробление шага h = h/p (p > 1); при h ³ e (заданная точность) выполняется п. 3), иначе поиск заканчивается: x_i ^*= x_i ^(k), i =1, 2,..., n.

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

1) Нахождение локального

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

2) Использование значений частных производных целевой функции. Это, с одной стороны, увеличивает объем вычислений (количество вычислений значений целевой функции), а с другой - увеличивает погрешность решения, т. к. производные чаще всего вычисляются через разностные соотношения.

3) “Застревание в овраге” целевой функции, т.е. в области значений

x_i, i =1, 2,..., n, в которой значения

f (x ₁, x ₂ ,..., x_n) почти не меняются. Градиентные методы с остановкой по условию (2.6) “застревают в овраге”, т.е. наблюдается иллюзия достижения минимума. Если же в качестве условия останова используется длина градиента, то поиск в “овраге” будет продолжаться бесконечно долго: значения частных производных целевой функции на “дне оврага” достаточно велики, но продвижения к точке минимума функции почти нет.

Замечание: если результирующие точки поиска min f (x ₁, x ₂ ,..., x_n) с различных, достаточно далеко отстоящих друг от друга начальных точек не совпадают, а значения функции в них близки, значит она имеет “овраг”, а если значения функции отличаются существенно, значит она имеет несколько экстремумов.