Написать программу на языке , реализующую алгоритм метода Нелдера –Мида на примерах целевой функции
ЛАБОРАТОРНАЯ РАБОТА № 2
ЧИСЛЕННЫЕ МЕТОДЫ ПОИСКА БЕЗУСЛОВНОГО ЭКСТРЕМУМА
ЛАБОРАТОРНАЯ РАБОТА № 2.1.
Методы нулевого порядка
МЕТОД ДЕФОРМИРУЕМЫХ СИМПЛЕКСОВ (Метод Нелдера-Мида)
Постановка задачи
Требуется найти безусловный минимум функции многих переменных т.е. найти такую точку
, что
,
.
Стратегия поиска
В основу метода деформируемых симплексов (метода Нелдера-Мида) положено построение последовательности систем точек
, которыеявляются вершинами выпуклого многогранника. Точки системы
на
итерации совпадают с точками системы
, кроме
, где точка
- наихудшая в системе
, т.е.
. Точка
заменяется на другую точку по специальным правилам, описанным ниже. В результате многогранники деформируются в зависимости от структуры линии уровня целевой функции, вытягиваясь вдоль длинных наклонных плоскостей, изменяя направление в изогнутых впадинах и сжимаясь в окрестности минимума. Построение последовательности многогранников заканчивается, когда значения функции в вершинах текущего многогранника отличаются от значения функции в центре тяжести системы
;
не более чем на
.
Алгоритм
Шаг 1. Задать координаты вершин многогранника ;
Параметры отражения , сжатия
, растяжения
; число
для остановки алгоритма. Положить
(последующие шаги 2-6 соответствуют текущему номеру
системы точек).
Шаг 2. Среди вершин найти «наилучшую» и «наихудшую»
, соответствующие минимальному и максимальному значению функции:
а также точку , в которой достигается второе по величине после максимального значение функции
.
Шаг 3. Найти «центр тяжести» всех вершин симплекса за исключением наихудшей
Шаг 4. Проверить условие окончания:
4.1. Если процесс поиска завершается (Конец) и в качестве приближенного решения можно взять наилучшую текущую точку симплекса
.
4.2. Если , процесс продолжается (переход на Шаг 5).
Шаг 5. Выполнить операцию отражения наихудшей вершины через центр тяжести
:
Шаг 6. Проверить выполнение условий:
6.1. Если , выполнить операцию растяжения:
Найти вершины нового многогранника:
6.1.1. Если , то вершина
заменяется на
. Затем
и переход на Шаг 2.
6.1.2. Если , то вершина
заменяется на
. Затем
и переход на Шаг 2.
6.2. Если , выполнить операцию сжатия:
Следует заменить вершину на
, положить
и переход на Шаг 2.
6.2.1. Если , то вершина
заменяется на
. При этом
и переход на Шаг 2.
6.2.2. Если , выполнить операцию редукции. Формируется новый симплекс с уменьшенными вдвое сторонами и вершиной
:
При этом следует положить и переход на Шаг 2.
Замечание 1. Нелдер и Мид рекомендовали использовать параметры Павиани -
Паркинсон и Хатчинсон -
В последнем случае в рамках операции отражения фактически выполняется растяжение.
ЗАДАНИЕ
Написать программу на языке , реализующую алгоритм метода Нелдера –Мида на примерах целевой функции.