Методы безусловной многомерной оптимизации. Шипилов С.А. - 6 стр.

                                      6
            4.1.2. Метод Хука и Дживса (метод конфигураций)

      Этот метод можно рассматривать как модификацию метода Гаусса-
Зейделя. Идея метода заключается в следующем: из начальной (базовой) точки
выполняется одна итерация метода Гаусса-Зейделя; там, где получено уточнен-
ное значение функции, помещается временная базовая точка. После этого даль-
нейший поиск проводят вдоль прямой, соединяющий две базовые точки. Этот
поиск проводится любым методом одномерного поиска. Найдя точку с мини-
мальным значением целевой функции, из нее снова выполняют одну итерацию
метода Гаусса-Зейделя, и дальнейший поиск снова проводят вдоль прямой, со-
единяющий две последние базовые точки т.д.
      Рассмотрим простейшую модификацию метода Хука и Дживса. Процеду-
ра включает в себя два циклически повторяющихся этапа: исследующий поиск
вокруг базисной точки и поиск по образцу.
      1. Исследующий поиск. Задается начальная базисная точка x(0) и прира-
щения по каждой координате Δxi . Рассчитывается значение целевой функции в
базисной точке. Затем в циклическом порядке изменяется каждая координата:
      xi(1) = xi(0) + Δxi
      Если приращение улучшает целевую функцию, то шаг считается
"удачным" и дается приращение по другой координате. В противном случае-
"неудачным" и делается шаг в противоположном направлении:
      xi(1) = xi(0) - Δxi
      Если он также оказывается "неудачным", то значение xi(0) оставляют
неизменным, и дается приращение по следующей координате и т.д., пока не
будут изменены все координаты. На этом заканчивается исследующий поиск,
найдена точка x(1).
      Если "неудачными" оказались шаги по всем направлениям производится
уменьшение приращений Δxi (обычно в два раза) и исследующий поиск повто-
ряется. Процедура заканчивается, когда величина приращений не станет мень-
ше заданной точности.
       2. Поиск по образцу осуществляется вдоль направления, соединяющего
точки x(0) и x(1). Совершается один или несколько шагов до тех пор, пока шаги
будут "удачными", т.е. приводят к улучшению целевой функции. Величина ша-
гов обычно равна расстоянию между x(0) и x(1), т.е.
       x(2) = x(1) + (x(1)-x(0))= 2⋅x(1)-x(0).
       Если после последнего "удачного" шага условие окончания поиска не
выполнено, т.е. Δxi > ε, то эту точку принимают в качестве новой базисной точ-
ки, и всю процедуру повторяют.
       Недостатком метода Хука – Дживса, как и метода Гаусса- Зейделя, явля-
ется его плохая сходимость при оптимизации “овражных” функций, что на ста-
дии исследующего поиска может привести к неоправданной остановке алго-
ритма.