Методы прямого поиска в гибридных алгоритмах…
5
ограничений на переменные управления. В общем случае необходимо
учитывать возможную высокую трудоемкость вычисления критери-
альных функций, что может потребовать значительных вычислитель-
ных ресурсов.
Методы прямого локального поиска.
Рассмотрим задачу опти-
мизации (1), (3), ограничившись поиском локального решения. Во
многих практических приложениях физические условия задачи
вычислительной диагностики могут налагать ограничения на моде-
лирование. Поэтому критериальные функции обычно не обладают
сильными математическими свойствами, такими как липшицева не-
прерывность, дифференцируемость и др. Так, наличие шума означа-
ет, что вычисление производных является затруднительным и нена-
дежным. Кроме того, критериальные функции, вычисление которых
проводится с использованием стандартных коммерческих кодов, сле-
дует рассматривать как заданные в форме «черного ящика». Указан-
ные причины приводят к необходимости использования методов
прямого поиска (без вычисления производных).
Для решения задачи локальной минимизации, как и в работе [14],
используется метод Хука — Дживса. Одна из его особенностей со-
стоит в том, что при определении нового направления поиска учиты-
вается информация, полученная при вычислениях на предыдущих
итерациях. В методе объединены две фазы: исследующий поиск с
циклическим изменением переменных задачи и ускоряющий поиск
по образцу. На предварительном (инициирующем) шаге алгоритма
Хука — Дживса при решении задачи локальной оптимизации выпол-
няются следующие действия: определяются направления вдоль коор-
динат
1
, . . . ,
n
h
h
; выбираются скалярный параметр окончания поиска
0
, начальный размер шага
, коэффициент уменьшения шага
1
; выбирается начальная точка
i
x
, полагается
i
i
y x
, задается
1
k j
и происходит переход к основному шагу, который включает
в себя приведенную ниже последовательность частных шагов.
1. Если
(
) ( )
i
i
i
f y h f y
, то попытка успешна; положить
1
i
i
i
y y h
и перейти к шагу 2. Если
(
)
( )
i
i
i
f y h f y
, то попыт-
ка неудачна, при этом: если
(
)
( )
i
i
i
f y h f y
, то
1
i
i
i
y y h
и
перейти к шагу 2; если же
(
)
( )
i
i
i
f y h f y
, то положить
1
i
i
y y
.
2. Если
j n
, то задать
1
j j
и повторить шаг 1. Иначе пе-
рейти к шагу 3, если
1
(
)
( )
n
k
f y
f x
, или перейти к шагу 4, если
1
(
)
( )
n
k
f y
f x
.
3. Задать
1
1
k
n
x y
и
1
1
(
)
i
k
k
k
y x
x x
. Заменить
k
на
1
k
,
положить
1
j
и перейти к шагу 1.
