 |
 |
 |
 |
|
 |
 |
47
задающей последовательность точек, стремящихся к точке максимума.
В зависимости от способа ее решения различают различные варианты градиентного метода.
Остановимся на наиболее известных из них.
Метод наискорейшего спуска
Название метода можно было бы понимать буквально, если бы речь шла о минимизации целевой
функции. Тем не менее по традиции такое название используется и при решении задачи на максимум.
Пусть
f(x)=f(x1,x1,...x
n
)
—дифференцируемая функция, заданная на R
n
, а х
(q)
=
(x1
(q)
,x2
(q)
,...,x
n
(q)
) —
некоторая текущая точка. Оговоримся, что каких-либо общих рекомендаций, касающихся выбора
исходной точки (или, как еще говорят, начального приближения) х
(0)
, не существует, однако по
возможности она должна находиться близко от искомого оптимального плана х*. Как уже говорилось
выше, если х
(q)
— нестационарная точка (т. е. |
f(x
(q)
)|>0), то при движении в направлении
f(x
(q)
)
функция f(х) на некотором промежутке обязательно будет возрастать. Отсюда возникает естественная
идея такого выбора шага, чтобы движение в указанном направлении продолжалось до тех пор, пока
возрастание не прекратится. Для этого выразим зависимость значения f(x) от шагового множителя
? > 0.
полагая х = х
(q)
+ ?
f(x
(q)
)
или, в координатной форме,
Чтобы добиться наибольшего из возможных значений f при движении по направлению
f(x
(q)
),
нужно выбрать такое значение
~
, которое максимизирует функцию
?(?) (?(
~
)= max(?(?)).
Для
вычисления
~
, используется необходимое условие экстремума d?(?)/d? =
0. Заметим, что если для
любого
?>0
d?(
~
)/d?> 0, то функция f(х) не ограничена сверху (т. е. не имеет максимума). В противном
случае, на основе (2.10) получаем
что, в свою очередь, дает
Если считать, что следующая точка х
(q+1)
соответствует оптимальному значению
?=
~
, то в ней
должно выполняться условие d?(
~
)/d? = 0, и
~
следует находить из условия
f(x
(q+1)
)
f(x
(q)
)=0 или
Условие (2.13) означает равенство нулю скалярного произведения градиентов функции f точках x
(q+1)
и x
(q)
. Геометрически оно может быть интерпретировано как перпендикулярность векторов градиентов
функции f в указанных точках, что и показано на рис. 2.2. Продолжая геометрическую интерпретацию
метода наискорейшего спуска, отметим, что в точке
x
(q+1)
вектор
f(x
(q+1)
), будучи градиентом,
перпендикулярен линии уровня, проходящей через данную точку. Стало быть, вектор
f(x
(q)
) является
касательным к этой линии. Итак, движение в направлении градиента
f(x
(q)
) следует продолжать до тех
пор, пока он пересекает линии уровня оптимизируемой функции.