ПЗ 6 15.10.25

1. Покоординатные стратегии поиска минимума

ИУС

2. 1. Метод циклического покоординатного спуска (раздел 2.4.1.)

Этот метод кратко уже рассматривался
при изучении ситуации заклинивания.
Решается задача построения
минимизирующей
i
последовательности
{x }.
ИУС
Дадим более точные формулировки.

3.

Для задания точной формулы метода достаточно
i
описать алгоритм перехода от вектора x к
вектору x i 1 (начальный вектор x 0 задан) :
i 1
1
i 1
2
i 1
l 1
i 1
l
J ( x , x ,..., x , x , x ,..., x )
i 1
1
i 1
2
i 1
l 1
i
l 1
i
n
i
l 1
i
n
min J ( x , x ,..., x , x, x ,..., x )
x R 1
ИУС
(поиск
l - ой компоненты)

4. Траектория метода циклического покоординатного спуска (ЦПС)

N
W
E
Минимум
S
x0
ИУС
Линии постоянного
уровня J(x1, x2)
Пример ЦПС - траектории для функции
двух переменных J(x1, x2)
(Точки излома траектории – точки касания с ЛУ)

5. Медленная сходимость

Линии
постоянного
уровня подобны
узкому глубокому
оврагу
ИУС
ЦПС траектория
Когда мы имеем больше
двух переменных
ситуация может быть
более сложной (в этом
случае мы можем иметь
многомерные овраги)

6. Область применимости

• Для решения простых задач без ярко
выраженных оврагов (рекомендуется
алгоритм GZ1, стр.197)
• Как стартовая поисковая процедура с
последующим переходом на более мощные
методы
• Метод имеет нулевой порядок (в схеме
метода ИУС
не участвуют производные от
минимизируемой функции) – это
достоинство иногда является определяющим

7. 2. Метод вращения осей Розенброка (стр.198)

Данная модификация метода ЦПС
была предложена Х. Розенброком для
ослабления явления заклинивания за
счет постоянного изменения системы
осей, в которых по-прежнему
ИУС
реализуется базовый метод ЦПС

8. Геометрическая иллюстрация

Метод Розенброка
Новые оси координат
1
x
x
0
ИУС
Одна из осей разворачивается вдоль
дна оврага
Исходные оси координат

9. Обсуждение

• Настраиваемой на овраг является
только одна ось – поэтому метод
эффективен только для одномерных
оврагов
• Одномерность оврага гарантируется
только при минимизации функций
двух переменных
ИУС
• Метод сохраняет нулевой порядок и в
этом его достоинство

10. Задание

• 1. Построить траекторию спуска ( 5
звеньев ломаной ) методом ЦПС из
заданной начальной точки (-1,0)
• 2. Построить траекторию спуска методом
Розенброка из той же начальной точки.
Проработать
ИУС в трех системах координат,
считая начальную.