Численные методы оптимизации. Рейзлин В.И. - 28 стр.

UptoLike

ВУЗ: 

ТПУ | Томск

Составители: 

Рубрика: 

28
1k k k k
x x s x
,
где
k
x
– текущее приближение к решению
*
x
,
k
– параметр, характеризующий
длину шага,
k
s
– направление поиска в
n
-мерном пространстве.
Рассмотрим метод первого порядка, использующий первые производные.
4.1. Градиентные методы
Градиент функции в любой точке x показывает направление наибольшего
локального увеличения
()fx
. Поэтому при поиске минимума можно попробо-
вать двигаться в направлении, противоположном градиенту в данной точке, то
есть в направлении наискорейшего спуска. Такой подход приведет к итерацион-
ной формуле, описывающей метод градиентного спуска:
1k k k k
x x f x
или
1
k
k k k k k k
k
fx
x x x s
fx
,
где
– норма градиента и, соответственно,
k
s
– единичный вектор.
(В качестве нормы вектора u можно выбрать так-называемую Гауссову норму
22
1
...
n
u u u
.)
В зависимости от выбора параметра
траектория спуска будет суще-
ственно различаться.
При большом значении
траектория будет представлять собой колеба-
тельный процесс, а при слишком больших
процесс может расходиться.
При малых
траектория будет плавной, но и процесс будет сходиться
медленно.
Параметр
k
можно принимать постоянным или выбирать различным на
каждой итерации. Иногда на каждом
k
-ом шаге параметр
k
выбирают, произ-
водя одномерную минимизацию вдоль направления
k
s
с помощью какого-либо
одномерного метода. Обычно такой процесс называют методом наискорейшего
спуска, или методом Коши.
Если
k
определяется в результате одномерной минимизации, то есть
min
k k k
arg f x s
, то градиент в точке очередного приближения будет
ортогонален направлению предыдущего спуска (рис. 19).

Страницы