Методы оптимизации. Азарнова Т.В - 38 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

40
Утверждение ( свойство парал - лельного подпространства). Если
точка
1
y найдена в результате поиска из точки
1
x
вдоль каждого из m (m<n)
сопряженных направлений, а точка
2
y получена в результате поиска из
точки
2
x
вдоль каждого из тех же m сопряженных направлений
m
qqq ..,
21
,
то вектор
12
yy − задает направление, сопряженное со всеми выбранными m
направлениями .
Алгоритм может быть организован следующим образом. Изначально
полагается
j
q nje
j
,1, == (затем эти направления будут последовательно
заменяться построенными сопряженными направлениями ). Вводится
вспомогательное направление
n
eq =
0
. Находится минимум функции
)
(
x
f
при последовательном движении из некоторой начальной точки
0
x
по (n+1)
направлениям
n10
qqq ,..,, , при этом каждая получаемая точка используется в
качестве исходной для поиска по следующему направлению . По свойству
параллельного подпространства, направление, проходящее через точки ,
полученные при первом и последнем поиске, будет H- сопряжено с
n
q . Далее
заменяется
1
q на
2
q ,
2
q на
3
q и т. д. В качестве направления
n
q выбирается
полученное сопряженное направление, после чего повторяется поиск по
(n+1) направлениям (уже не содержащим старого направления
1
q
). Для
квадратичных функций последовательность
2
n
одномерных поисков
приводит к точке минимума.
Алгоритм метода сопряжённых направлений.
Шаг 0. Задать параметр точности
ε
, выбрать х
0
n
R
∈
, положить к =0, i=0 ,
j
q
n0j
eqn1je === ,,, ,
00
xy = .
Шаг 1. Найти y
i+1
=y
i
+ α
i
q
i
, где
i
=
)(minarg
ii
qyf α
α
+
Шаг 2. Проверить условие i=n .
а) Если оно выполняется , то выяснить успешность поиска по n
последним направлениям. Если y
n+1
=y
1
, поиск завершить, полагая
x*= y
n+1
.
b) Если i<n, положить i=i+1 и перейти к шагу 1.
Шаг 3. Положить х
k+1
=y
n+1
и проверить критерий останова
(например, ||x
0
-x
1
||<
ε
или |f(x
0
)-f(x
1
)|<
ε
).
Если он выполнен, то вычисления завершить, полагая x*=x
k+1
.
Шаг 4. Положить
j
q
1101
,1,1, yyqqnjq
nnj
−==−==
++
,
1k0
xy
+
= ,
i=0 , к =к +1 и перейти к шагу 1.
Пример 2. Решить задачу min2)(
21
2
2
2
1
→++= xxxxxf методом
сопряженных направлений.
Решение.
0. Выберем ),( 1x
2
1
0
= , положим
20
eq = ,
2211
eqeq == , , ),( 1xy
2
1
00
== .
1. ),(),(),(
0
2
1
0
2
1
1
1101y αα +=+= . 
                                                40
Утверждение ( свойство парал- лельного подпространства). Если
точка y 1 найдена в результате поиска из точки x 1 вдоль каждого из m (m

Страницы