Численные методы расчёта, моделирования и проектирования технологических процессов и оборудования. Майстренко А.В - 126 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

126
13.4. МЕТОД СОПРЯЖЁННЫХ НАПРАВЛЕНИЙ ПАУЭЛЛА
Наиболее эффективным из алгоритмов прямого поиска является
метод, разработанный Пауэллом. При работе этого метода информа-
ция, полученная на предыдущих операциях, используется для по-
строения векторов направлений поиска, а также для устранения зацик-
ливания последовательности координатных поисков. Метод ориенти-
рован на решение задач с квадратичными целевыми функциями и ос-
новывается на фундаментальных теоретических результатах.
Задачи с квадратичными целевыми функциями занимают важное
место в теории оптимизации по двум причинам. Во-первых, квадратич-
ная функция представляет собой простейший тип нелинейных функций,
для которых может быть сформулирована задача безусловной оптими-
зации. А во-вторых, в окрестности точки оптимума любую нелинейную
функцию можно аппроксимировать квадратичной функцией.
Основная идея алгоритма заключается в том, что если квадратич-
ная функция N переменных приведена к виду суммы полных квадратов
(
edxcxbxaxy ++++=
21
2
2
2
1
– для функции двух переменных), то её
оптимум может быть найден в результате реализации
2
N
одномерных
поисков по преобразованным координатным направлениям. В общем
же случае, когда целевая функция не является квадратичной, необхо-
димо провести более чем
2
N
одномерных поисков.
Для проведения одномерных поисков строится система сопря-
жённых направлений.
Определение: Пусть задана квадратичная функция
)(xf
, две
произвольные несовпадающие точки
1
x
и
2
x
, а также направление S.
Тогда, если
(
)
Sxfy
*
11
min~ λ+
, то направление
(
)
12
yy −
будет со-
пряжено с S (рис. 13.4).
Рассмотрим алгоритм метода сопряжённых направлений Пауэлла.
Шаг 1: Задаётся начальная точка
(
)
0
)0(
=kx
и система N линейно
независимых направлений. Обычно на этом шаге в качестве начальных
направлений
)0(
i
S
выбираются единичные вектора, т.е.
,
)0(
ii
eS =
Ni ...,,2,1
=
, совпадающие с направлениями координатных осей.
Шаг 2: Проводится последовательно N + 1 одномерный поиск це-
левой функции
)(
xf
по направлениям
;,,...,,,,
1221 NNNN
SSSSSS
−−
,min
)()(
λ→λ+
k
i
k
i
Sfx
NNNi ,1...,,1,
−
=
. При этом полученная ра-
нее точка оптимума берётся в качестве исходной для следующего од-
номерного поиска, а направление
N
S
используется как при первом,
так и последнем поиске.

Страницы