|
|
|
содержание .. 24 25 26 27 ..
шину
X
1
.
Если
оказывается
,
что
X
4
имеет
лучшее
значение
целевой
функции
среди
вершин
много
-
гранника
,
то
расстояние
d
увеличивают
.
На
ри
-
сунке
именно
эта
ситуация
имеет
место
и
увели
-
чение
d
дает
точку
X
5
.
В
новом
многограннике
с
вершинами
X
2
,
X
3
,
X
5
худшей
является
вершина
X
2
,
аналогично
получают
вершину
X
6
,
затем
вер
-
шину
X
7
и
т
.
д
.
Если
новая
вершина
окажется
худ
-
шей
,
то
в
многограннике
нужно
сохранить
луч
-
шую
вершину
,
а
длины
всех
ребер
уменьшить
,
например
вдвое
(
стягивание
многогранника
к
лучшей
вершине
).
Поиск
прекращается
при
вы
-
полнении
условия
уменьшения
размеров
много
-
гранника
до
некоторого
предела
.
:471);*.$
/$&#-.
поиска
характеризуют
-
ся
тем
,
что
направления
поиска
g
выбирают
случайным
образом
.
Особенностью
/$&#-)
*)’+%#"$;>$8#
+07+%)
является
выполнение
шагов
поиска
в
градиентном
направлении
X
k
+
1
=
X
k
+
h
grad
F
(
X
) / |
grad
F
(
X
)|,
шаг
h
выбирается
оптимальным
с
помощью
одномерной
оптимизации
.
При
использовании
метода
наискорейшего
спуска
,
как
и
большинства
других
методов
,
эффек
-
тивность
поиска
существенно
снижается
в
овражных
ситуациях
.
Траектория
поиска
приобретает
зиг
-
загообразный
вид
с
медленным
продвижением
вдоль
дна
оврага
в
сторону
экстремума
.
Чтобы
повы
-
сить
эффективность
градиентных
методов
,
используют
несколько
приемов
.
Один
из
приемов
,
использованный
в
/$&#-$
+#0"9@$**.,
8")-’$*&#(
(
называемом
также
ме
-
тодом
Флетчера
-
Ривса
),
основан
на
понятии
сопряженности
векторов
.
Векторы
C
и
(
называют
Q
-
со
-
пряженными
,
если
A
T
QB
= 0,
где
Q
—
положительно
определенная
квадратная
матрица
того
же
по
-
рядка
,
что
и
размер
N
векторов
C
и
(
(
частный
случай
сопряженности
—
ортогональность
векторов
,
когда
Q
является
единичной
матрицей
порядка
N
),
A
T
-
вектор
-
строка
,
B —
вектор
-
столбец
.
Особенность
сопряженных
направлений
для
Q =
K
,
где
K
—
матрица
Гессе
,
при
в
задачах
с
ква
-
дратичной
целевой
функцией
F
(
X
)
заключается
в
следующем
:
одномерная
минимизация
F
(
X
)
после
-
довательно
по
N
сопряженным
направлениям
позволяет
найти
экстремальную
точку
не
более
,
чем
за
N
шагов
.
+-0B.
F690.
.
L)&"’=$;
V$++$
называют
матрицу
вторых
частных
производных
целевой
функции
по
управля
-
емым
параметрам
.
Основанием
для
использования
поиска
по
K
-
сопряженным
направлениям
является
то
,
что
для
функций
F
(
X
)
общего
вида
может
быть
применена
квадратичная
аппроксимация
,
что
на
практике
вы
-
ливается
в
выполнение
поиска
более
,
чем
за
N
шагов
.
+-0B.-
.
Поиск
экстремума
выполняют
в
соответствии
с
формулой
X
i
=
X
i
-
1
+
h
S
i
.
(4.8)
Направление
S
i
+
1
поиска
на
очередном
шаге
связано
с
направлением
поиска
S
i
на
предыдущем
шаге
соотношением
S
i
+
1
= -
grad
F
(
X
i
) +
w
i
S
i
,
(4.9)
где
w
i
—
коэффициент
.
Кроме
того
,
учитывают
условие
сопряженности
S
i
+
1
Т
K
S
i
= 0
(4.
1
0)
и
линейную
аппроксимацию
grad
F
(
X
)
в
окрестностях
точки
N
i
grad
F
(
X
i
+
1
) =
grad
F
(
X
i
) +
K
(
X
i
+
1
-
X
i
).
(4.
11
)
Поскольку
шаг
h
рассчитывается
исходя
из
условия
одномерной
оптимизации
,
то
,
во
-
первых
,
справедливо
соотношение
S
i
Т
grad
F
(
X
i
) = 0,
(4.
1
2)
%
!#*%!#&
F
*:,$* $I*:+*
F
*)&* :&)#*’! +($*,#)KH (*L*)&M
5
@!"!
4
&
.
+
.
)
"#$%!#&’&($"!))$* +($*,#&($"!)&*
103
%+,
. 4.8.
Иллюстрация
метода
деформируемого
многогранника
во
-
вторых
,
имеем
X
i
=
X
i-
1
+
hw
i-
1
S
i-
1
-
h
grad
F
(
X
i-
1
),
откуда
получаем
∂
F
/
∂
h
= (
∂
F
(
X
)/
∂
X
)(
∂
X
/
∂
h
) =
grad
F
(
X
i
)
grad
F
(
X
i-
1
) = 0.
(4.
1
3)
Алгоритм
поиска
сводится
к
применению
формулы
(4.9),
пока
не
будет
выполнено
условие
окончания
вычислений
|
grad
F
(
X
k
)| <
ε
.
Чтобы
определить
коэффициент
w
i
решают
систему
уравнений
(4.8)-(4.
1
3)
путем
подстановки
в
(4.
1
0)
величин
S
i
+
1
из
(4.9)
и
S
i
из
(4.8)
S
i
+
1
T
K
S
i
= (
w
i
S
i
-
grad
F
(
X
i
))
T
K
(
X
i
—
X
i
-
1
) /
h
=
= (
w
i
S
i
-
grad
F
(
X
i
))
T
KK
-
1
(
grad
F
(
X
i
) -
grad
F
(
X
i
-
1
)) /
h
= 0;
или
(
w
i
S
i
-
grad
F
(
X
i
))
T
(
grad
F
(
X
i
) -
grad
F
(
X
i
-
1
)) = 0,
откуда
w
i
S
i
T
(
grad
F
(
X
i
) -
grad
F
(
X
i
-
1
)) -
grad
F
(
X
i
)
T
grad
F
(
X
i
) +
grad
F
(
X
i
)
T
grad
F
(
X
i
-
1
) = 0
и
с
учетом
(4.
1
2)
и
(4.
1
3)
w
i
S
i
T
grad
F
(
X
i
-
1
) +
grad
F
(
X
i
)
T
grad
F
(
X
i
) = 0.
Следовательно
,
w
i
=
grad
F
(
X
i
)
T
grad
F
(
X
i
) /
S
i
T
grad
F
(
X
i
-
1
)
(4.
1
4)
На
первом
шаге
поиска
выбирают
S
1
= —
grad
F
(
X
0
)
и
находят
точку
N
1
.
На
втором
шаге
по
формуле
(4.
1
4)
рассчи
-
тывают
w
1
,
по
формулам
(4.9)
и
(4.8)
определяют
S
2
и
N
2
и
т
.
д
.
L$&#-
0$"$/$**#;
/$&"’%’
(
иначе
метод
Девидона
-
Флетчера
-
Пауэлла
)
можно
рассматривать
как
результат
усовершенствования
метода
второго
порядка
—
метода
Ньютона
.
L$&#-
G5<&#*)
основан
на
использовании
необходимых
условий
безусловного
экстремума
целе
-
вой
функции
F
(
X
)
grad
F
(
X
) = 0.
(4.
1
5)
Выражение
(4.
1
5)
представляет
собой
систему
алгебраических
уравнений
,
для
решения
которой
можно
применить
известный
численный
метод
,
называемый
методом
Ньютона
.
Корень
системы
(4.
1
5)
есть
стационарная
точка
,
т
.
е
.
возможное
решение
экстремальной
задачи
.
Метод
Ньютона
явля
-
ется
итерационным
,
он
основан
на
линеаризации
(4.
1
5)
в
окрестности
текущей
точки
поиска
N
k
grad
F
(
X
) =
grad
F
(
X
k
) +
K
(
X
-
X
k
) = 0.
(4.
1
6)
Выражение
(4.
1
6) —
это
система
линейных
алгебраических
уравнений
.
Ее
корень
есть
очеред
-
ное
приближение
N
k
+
1
к
решению
X
k
+
1
=
X
k
-
K
-
1
(
X
k
)
grad
F
(
X
k
).
Если
процесс
сходится
,
то
решение
достигается
за
малое
число
итераций
,
окончанием
которых
служит
выполнение
условия
|
X
k
+
1
-
X
k
| <
ε
.
Главный
недостаток
метода
—
высокая
трудоемкость
вычисления
и
обращения
матрицы
K
,
к
то
-
му
же
ее
вычисление
численным
дифференцированием
сопровождается
заметными
погрешностями
,
что
снижает
скорость
сходимости
.
В
методе
переменной
метрики
вместо
трудно
вычисляемой
обратной
матрицы
Гессе
использу
-
ют
некоторую
более
легко
вычисляемую
матрицу
N
,
т
.
е
.
X
k
+
1
=
X
k
+
N grad
F
(
X
k
).
Введем
обозначения
:
d
g
k
=
grad
F
(
X
k
) -
grad
F
(
X
k
-
1
);
d
X
k
=
X
k
-
X
k
-
1
;
E
—
единичная
матрица
.
Начальное
значение
матрицы
N
0
=
E
.
Матрицу
N
корректируют
на
каждом
шаге
,
т
.
е
.
%
!#*%!#&
F
*:,$* $I*:+*
F
*)&* :&)#*’! +($*,#)KH (*L*)&M
5
@!"!
4
&
.
+
.
)
"#$%!#&’&($"!))$* +($*,#&($"!)&*
104
|