Написать программу на языке, реализующую алгоритм метода Нелдера –Мида на примерах целевой функции

ЛАБОРАТОРНАЯ РАБОТА № 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. Нелдер и Мид рекомендовали использовать параметры Павиани - Паркинсон и Хатчинсон - В последнем случае в рамках операции отражения фактически выполняется растяжение.

ЗАДАНИЕ

Написать программу на языке, реализующую алгоритм метода Нелдера –Мида на примерах целевой функции.