Методы Оптимизации Систем Автоматизированного Проектирования

Метод деформируемого многогранника (метод Нелдера—Мида)

Стратегия поиска.Идея метода состоит в сравнении значений функции в (n+1)вершинах многогранника (симплекса) , i=1,…, n+1, k- номер итерации и перемещении в направлении оптимальной точки с помощью следующей итерационной процедуры. Точки многогранника на k+1 итерации совпадают с точками , за исключением худшей точки многогранника, т.е. той точки, в которой исходная функция принимает наибольшее значение. Точка заменяется на другую с помощью трех основных операций: отражения, растяжения, сжатия и редукции. В процессе выполнения данных операций многогранник изменяет свои размеры, что и обусловило название метода. Построение последовательности многогранников заканчивается, когда значения функции в вершинах многогранника отличается от значения функции в центре тяжести многогранника не более, чем на заданную величину.
Важный вопрос – построение начального симплекса. Задается некото-рая базовая точка , а координаты остальных n вершин симплекса получаются следующим образом:
где
, а a – масштабный множитель.
Например, если и остальные две вершины симплекса равны:
Начальный симплекс можно построить иначе:

где- единичный вектор.
Например, если
Алгоритм метода.
Начальный этап
Задать начальную точку и коэффициенты отражения, растяженияи сжатия. Сформировать начальный симплекс. Перейти к основному этапу.
Начальный этап

Шаг 1. Вычислить значение функции во всех точках многогранника и выбрать лучшую и худшую точки и . Вычислить центр тяжести многогранника за исключением худшей точки:

Здесь h – номер худшей точки.(для функции 2-х переменных точка- середина отрезка, соединяющего точки за исключением худшей).

Шаг 2. Проверить условие окончания счета:
а) если

то поиск закончить;
б) иначе перейти к шагу 3.

Стр.: ..., 2, 3