Курсовая работа «Метод Нелдера-Мида»

В технике, экономике, естественных науках часто возникают задачи оптимизации сложной совокупности оборудования, операций, ценней или процессов. Требуется минимизировать или максимизировать некоторую функцию, называемую целевой, которая характеризует цену, вес, общую эффективность или нечто подобное при определенных ограничениях. Подобные задачи оптимизации, сформулированные математически, относятся к задачам нелинейного программирования.

Формула нелинейного программирования может быть сформулирована следующим образом: минимизировать f(x), x , при m линейных или нелинейных ограничения в виде равенств h¬j(x) = 0, j = 1, … , m , и p – m линейных или нелинейных ограничениях в виде неравенств gj(x) ? 0, j = m+1, …, p. Существуют задачи нелинейного программирования без ограничений.

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

Метод Нелдера-Мида является развитием симплексного метода Спендли, Хекста и Химсворта. Выпуклая оболочка множества (n+1)-й равноудаленной точки в n-мерном пространстве называется регулярным симплексом. Эта конфигурация рассматривается в методе Спендли, Хекста и Химсворта. В двухмерном пространстве регулярным симплексом является правильный треугольник, а в трехмерном - правильный тетраэдр. Идея метода состоит в сравнении значений функции в вершинах симплекса и перемещении симплекса в направлении оптимальной точки с помощью итерационной процедуры. В симплексном методе, предложенном первоначально, регулярный симплекс использовался на каждом этапе. Нелдер и Мид предложили несколько модификаций этого метода, допускающих, чтобы симплексы были неправильными. В результате получился очень надежный метод прямого поиска, являющийся одним из самых эффективных при n?6.

Главными особенностями алгоритма можно назвать следующие:

- метод Нелдера-Мида не накладывает ограничений на гладкость функции;

- данный метод является эффективным при низкой скорости вычисления минимизируемой функции. Как правило, на каждой итерации происходит вычисление значения функции не более чем в 3 точках;

- отсутствие теории сходимости. Алгоритм может расходиться даже на гладких функциях.

1 Постановка математической задачи

Задачей оптимизации называется задача поиска экстремума функции, заданной на некотором множестве.

Как правило, под задачей оптимизации также подразумевается поиск элемента x, при котором целевая функция f(x) достигает экстремума.

Для того, чтобы корректно поставить задачу оптимизации необходимо задать:

- Допустимое множество

- Целевую функцию

- Критерий поиска (max или min)

Тогда решить задачу означает одно из:

- Показать что

- Показать, что целевая функция f(x) не ограничена.

- Найти

- Если не существует , то найти

Если допустимое множество , то такая задача называется задачей безусловной оптимизации, в противном случае — задачей условной оптимизации.

Метод Нелдера-Мида, также известный как метод поиска по деформируемому многограннику, — метод безусловной оптимизации вещественной функции от нескольких переменных. Иными словами на допустимое множество накладываются следующие ограничения: .

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

Множество называется выпуклым, если .

Выпуклой оболочкой множества X называется наименьшее выпуклое множество C такое, что

Симплексом или n-симплексом называется выпуклая оболочка множества (n+1) точек.

Например:

1-симплексом является отрезок

2-симплексом является треугольник

3-симплексом является тетраэдр.

Параметрами метода являются:

- коэффициент отражения ?>0, обычно выбирается равным 1.

- коэффициент сжатия ?>0, обычно выбирается равным 0.5.

- коэффициент растяжения ?>0 обычно выбирается равным 2.

3.1 Инициализация

Произвольным образом выбирается n+1 точка xi=( , ,…, ) , образующие симплекс n-мерного пространства. В этих точках вычисляются значения функции: f1=f( ), f2= f( ), … , fn+1= f( ).

1. Сортировка. Из вершин симплекса выбираем три точки: xh с наибольшим (из выбранных) значением функции fh, xg со следующим по величине значением fg и xl с наименьшим значением функции fl. Целью дальнейших манипуляций будет уменьшение по крайней мере fh.

2. Найдём центр тяжести всех точек, за исключением xh:xc= i. Вычислять fc=f(xc) не обязательно.

3. Отражение. Отразим точку xh относительно xc с коэффициентом ? (при ?=1 это будет центральная симметрия, в общем случае — гомотетия), получим точку xr и вычислим в ней функцию: fr=f(xr). Координаты новой точки вычисляются по формуле xr=(1+ ? )xc- ? xh.

4. Далее сравниваем значение fr со значениями fh,fg,fl:

4а). Если fr