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

UptoLike

ВУЗ: 

ТПУ | Томск

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

Рубрика: 

24
Будем двигаться по выбранному направлению, то есть вдоль некоторой
прямой в плоскости
,xy
.
В тех участках, где прямая пересекает линии уровня, мы при движении пе-
реходим от одной линии уровня к другой, так что при этом движении функция
меняется (возрастает или убывает, в зависимости от направления движения).
Только в той точке, где данная прямая касается линии уровня (рис. 16), функция
имеет экстремум вдоль этого направления. Найдя такую точку, мы завершаем в
ней спуск по первому направлению и должны начать спуск по второму.
Пусть линии уровня образуют истинный овраг. Тогда возможен случай
(рис. 17), когда спуск по одной координате приводит нас на «дно оврага», а лю-
бое движение по следующей координате (пунктирная линия) ведет нас на подъ-
ем. Никакой дальнейший спуск по координатам невозможен, хотя минимум еще
не достигнут. В данном случае процесс спуска по координатам не сходится к
минимуму.
Наоборот, если функция достаточно гладкая, то в некоторой окрестности
минимума процесс спуска по координатам сходится к этому минимуму. Однако
скорость сходимости сильно зависит от формы линий уровня. Так, если рельеф
функции имеет тип «разрешимый овраг», то при попадании траектории спуска в
такой овраг сходимость становится настолько медленной, что расчет практиче-
ски вести невозможно.
Обычно метод покоординатного спуска используют в качестве первой по-
пытки при нахождении минимума.
3.3. Метод оврагов
Выберем произвольную точку
0
и спустимся из нее (например, по коор-
динатам), делая не очень много шагов, то есть, не требуя высокой точности. Ко-
нечную точку спуска обозначим
0
r
. Если рельеф овражный, эта точка окажется
вблизи дна оврага (рис. 18).
Рис. 18. Иллюстрация к методу оврагов
Теперь выберем другую точку
1
не слишком далеко от первой. Из нее
также сделаем спуск и попадем в некоторую точку
1
r
. Эта точка тоже лежит
вблизи дна оврага. Проведем через точки
0
r
и
1
r
на дне оврага прямую – прибли-
зительную линию дна оврага, передвинемся по этой линии в сторону убывания
функции и выберем новую точку
2
на этой прямой, на расстоянии
h
от точки
1
r
. Величина
h
называется овражным шагом и для каждой функции подбирается
в ходе расчета.

Страницы