ВУЗ:
Составители:
Рубрика:
Методами нулевого порядка называют методы поиска экстремума, использующие только значения целе-
вой функции и не требующие вычисления производных. К числу наиболее эффективных методов этой группы
относятся модифицированный метод покоординатного спуска Пауэлла и симплексный метод Нелдера-Мида.
Метод покоординатного спуска. Рассмотрим вначале метод покоординатного спуска Гаусса-Зейделя на
примере функции двух переменных, линии равного уровня которой изображены на рис. 2.6. Из некоторой на-
чальной точки
X
0
= (x
1
0
, x
2
0
) производится
поиск минимума вдоль направления оси х
1
с получением точки X
0
. В
этой точке касательная к линии равного уровня параллельна оси
х
1
. Затем из точки X
0
производится поиск ми-
нимума вдоль направления оси
х
2
с получением точки X
1
.
Следующие итерации выполняются аналогично. Для минимизации функции
f
0
(X) вдоль осевых направле-
ний может быть использован любой из методов одномерной минимизации. Для локализации отрезка, содержа-
щего точку минимума в осевом направлении, может быть использована, например, следующая процедура. Обо-
значим через
у
1
значение
0
1
х , а через y
2
– значение
0
1
х + δ
1
, где δ
1
> 0. Вычислим значения f
0
(у
1
,
0
2
х ); f
0
(у
2
,
0
2
х ).
Пусть, например,
f
0
(y
1
,
0
2
х
) > f
0
(y
2
,
0
2
х
). Тогда следует вычислять значения f
0
(y
i
, х
2
0
), y
i
= y
i–1
+ δ
i–1
, i = 3, 4,
… до тех пор, пока не будет найдена такая точка
у
i
, что f
0
(y
i
,
0
2
х ) ≥ f
0
(y
i–1
,
0
2
х ). В этом случае отрезком локали-
зации минимума функции
f
0
вдоль направления оси х
1
, проходящего через точку Х
0
, будет являться отрезок [y
i–2
,
y
i
]. При этом можно выбирать δ
i
= const или δ
i+1
= 2δ
i
, i > 0. В том случае, если f
0
(y
1
,
0
2
х ) ≤ f
0
(y
2
,
0
2
х ), то y
1
= y
2
,
δ
1
= –δ
1
, y
2
= y
1
+ δ
1
, и процедура локализации отрезка выполняется подобно описанной выше. В этом случае
отрезком локализации будет являться отрезок [
y
i
, y
i–2
].
Аналогичным образом определяется отрезок локализации функции
f
0
вдоль направления оси х
2
.
X
*
X
1
X
1
X
0
X
0
= (x
1
0
, x
2
0
)
x
1
Рис. 2.6. Метод покоординатного спуска Гаусса-Зейделя
Х
1
Х
1
Х
0
Х
0
= (х
1
0
, х
2
0
)
х
1
х
2
Рис. 2.7. Метод Пауэлла
Критерием окончания поиска является выполнение условия:
∑
=
+
++
−=−ε≤−
n
i
k
i
k
i
kkkk
xxxxxx
1
2
1
11
)(где,
.
Для минимизации функций многих переменных М. Пауэлл предложил использовать следующую модифи-
кацию метода Гаусса-Зей-деля. После получения точки
0
Х
локальным поиском вдоль координатных осей вы-
полняется поиск вдоль направления, соединяющего точки
Х
0
и
0
Х
(рис. 2.7) с получением точки X
1
, т.е. Х
1
= X
0
+
h
0
(
0
Х
–Х
0
), где h
0
вычисляется из условия того, что точка Х
1
является точкой минимума функции f
0
вдоль на-
правления
х
2
х
1
х
2
х
1
Страницы
- « первая
- ‹ предыдущая
- …
- 42
- 43
- 44
- 45
- 46
- …
- следующая ›
- последняя »
