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

UptoLike

ВУЗ: 

ТПУ | Томск

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

Рубрика: 

23
Все эффективные методы поиска минимума сводятся к построению траек-
торий, вдоль которых функция убывает; разные методы отличаются способами
построения таких траекторий. Метод, приспособленный к одному типу рельефа,
может оказаться плохим на рельефе другого типа.
3.2. Метод покоординатного спуска (Метод Гаусса)
Изложим этот метод на примере функции трех переменных
( , , )F x y z
.
Выберем нулевое приближение
0 0 0
, , .x y z
Фиксируем значение двух коор-
динат
00
, y y z z
. Тогда функция будет зависеть только от одной перемен-
ной
x
; обозначим ее через
1 0 0
( ) ( , , )f x F x y z
. Используя какой-либо способ од-
номерной оптимизации, отыщем минимум функции
1
()fx
и обозначим его через
1
x
. Мы сделали шаг из точки
0 0 0
( , , )x y z
в точку
по направлению, па-
раллельному оси
x
; на этом шаге значение функции уменьшилось.
Теперь из новой точки сделаем спуск по направлению, параллельному оси
y
, то есть рассмотрим функцию
2 1 0
( ) ( , , ),f y F x y z
найдем ее минимум и обо-
значим его через
1
y
. Второй шаг приводит нас в точку
1 1 0
( , , )x y z
. Из этой точки
делаем третий шаг – спуск параллельно оси
z
и находим минимум функции
3 1 1
( ) ( , , )f z F x y z
. Приход в точку
1 1 1
( , , )x y z
завершает цикл спусков или
первую итерацию.
Далее будем повторять циклы. На каждом спуске функция не возрастает, и
при этом значение функции ограничено снизу ее значением в минимуме
* * * *
( , , )F F x y z
. Следовательно, итерации сходятся к некоторому пределу
*
FF
. Будет ли здесь иметь место равенство, то есть сойдутся ли спуски к ми-
нимуму и как быстро? Это зависит от функции и выбора нулевого приближения.
На примере функции двух переменных легко убедиться, что существуют
случаи сходимости спуска по координатам к минимуму и случаи, когда этот
спуск к минимуму не сходиться.
В самом деле, рассмотрим геометрическую трактовку этого метода
(рис.°16 и 17):
Рис. 16. Метод Гаусса для Рис. 17. Метод Гаусса для
котловинного рельефа истинного оврага

Страницы