Нет

??????????? ??

неравенство

f(x_n+3 ) < f(x_h ) ?

	Да

Растяжение: вычислить

x_n+4 = x_n+2 + g(x_n+3 - x_n+2 )

Вычислить f(x_n+4 )

Выполняется ли

неравенство

f(x_n+4 ) < f(x_l ) ?

Заменить

x_h на x_n+4

Нет

??????????? ??

неравенство f(x_n+3 ) < f(x_i )

для всех i ¹ h ?

	Нет
Нет
Да
Нет

Заменить

x_h на x_n+3

Нет

Схема 1. Информационная блок-схема поиска методом деформируемого многогранника.

Выполняется ли

неравенство

f(x_n+3 ) < f(x_h ) ?

Да
		Да

Заменить

x_h на x_n+3

Сжатие: вычислить

x_n+5 = x_n+2 + b(x_h - x_n+2 )

Вычислить f(x_n+5 )

Выполняется ли

неравенство

f(x_n+5 ) > f(x_h ) ?

Заменить

Да

x_h ?? x_n+5

Редукция: заменить

все x_i на x_l + ¹ /₂ (x_i - x_l )

Да

Останов

Рисунок 3.
Поиск минимума функции Розенброка методом деформируемого многогранника, начиная с точки x(0)=[-1,2 1,0]T (числа указывают номер шага).

Коэффициент отражения a используется для проектирования вершины с наибольшим значением f(x) через центр тяжести деформируемого многогранника. Коэффициент g вводится для растяжения вектора поиска в случае, если отражение даёт вершину со значением f(x), меньшим, чем наименьшее значение f(x), полученное до отражения. Коэффициент сжатия b используется для уменьшения вектора поиска, если операция отражения не привела к вершине со значением f(x), меньшим, чем второе по величине (после наибольшего) значение f(x), полученное до отражения. Таким образом, с помощью операций растяжений или сжатия размеры и форма деформируемого многогранника масштабируются так, чтобы они удовлетворяли топологии решаемой задачи.

Естественно возникает вопрос, какие значения параметров a, b и g должны быть выбраны. После того как деформируемый многогранник подходящим образом промасштабирован, его размеры должны поддерживаться неизменными, пока изменения в топологии задачи не потребуют применения многогранника другой формы. Это возможно реализовать только при a=1. Кроме того, Нелдер и Мид показали, что при решении задачи с a=1 требуется меньшее количество вычислений функции, чем при a<1. С другой стороны, a не должно быть много больше единицы, поскольку

1) деформируемый многогранник легче адаптируется к топологии задачи при меньших значениях a, особенно когда необходимо изменять направление поиска, столкнувшись с изогнутой впадиной, и

2) в области локального минимума размеры многогранника должны уменьшаться и большое a в этих условиях замедлит сходимость.

Таким образом, значение a=1 выбирается как компромисс.

Чтобы выяснить, какое влияние на процедуру поиска имеет выбор b и g, Нелдер и Мид (а также Павиани) провели решение нескольких тестовых задач, используя большое число различных комбинаций значений b и g. В качестве удовлетворительных значений этих параметров при оптимизации без ограничений Нелдер и Мид рекомендовали a=1, b=0,5 и g=2. Размеры и ориентация исходного многогранника в некоторой степени влияли на время решения, а значения a, b и g оказывали значительно большее влияние. Павиани отмечает, что нельзя чётко решить вопрос относительно выбора b и g и что влияние выбора b на эффективность поиска несколько более заметно, чем влияние g. Павиани рекомендует следующие диапазоны значений для этих параметров:

0,4 £ b £ 0,6,

2,8 £ g £ 3,0.

При 0<b<0,4 существует вероятность того, что из-за уплощения многогранника будет иметь место преждевременное окончание процесса. При b>0,6 может потребоваться избыточное число шагов и больше машинного времени для достижения окончательного решения.

Пример

Поиск методом деформируемого многогранника.

Для иллюстрации метода Нелдера и Мида рассмотрим задачу минимизации функции f(x)=4(x₁ –5)² +(x₂ –6)² , имеющей минимум в точке x^* =[5 6]^T . Поскольку f(x) зависит от двух переменных, в начале поиска используется многоугольник с тремя вершинами. В этом примере в качестве начального многогранника взят треугольник с вершинами x₁ ⁽⁰⁾ =[8 9]^T , x₂ ⁽⁰⁾ =[10 11]^T и x₃ ⁽⁰⁾ =[8 11]^T , хотя можно было бы использовать любую другую конфигурацию из трёх точек.

На нулевом этапе поиска, k=0, вычисляя значения функции, получаем f(8,9)=45, f(10,11)=125 и f(8,11)=65. Затем отражаем x₂ ⁽⁰⁾ =[10 11]^T через центр тяжести точек x₁ ⁽⁰⁾ и x₃ ⁽⁰⁾ [по формуле (1)], который обозначим через x₄ ⁽⁰⁾ :

,

с тем, чтобы получить x₅ ⁽⁰⁾ .

,

,

f(6,9)=13.

Поскольку f(6,9)=13<f(8,9)=45, переходим к операции растяжения:

,

,

f(4,8)=8.

Поскольку f(4,8)=8<f(8,9)=45, заменяем x₂ ⁽⁰⁾ на x₆ ⁽⁰⁾ и полагаем x₆ ⁽⁰⁾ =x₂ ⁽¹⁾ на следующем этапе поиска.

Наконец, поскольку

,

начинаем этап поиска k=1. На рисунке 4 приведена траектория поиска на начальных этапах, а в таблице 2 приведены координаты вершин и значения f(x) для четырёх дополнительных этапов. На рисунке 5 изображена полная траектория поиска до его окончания. Для уменьшения f(x) до значения потребовалось 32 этапа.

Рисунок 4.
Метод Нелдера и Мида при отсутствии ограничений.

Рисунок 5.
Траектория поиска с помощью алгоритма Нелдера и Мида.

Содержание