Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Метод Нелдера-Мида.

Читайте также:
  1. I. 2.3. Табличный симплекс-метод.
  2. I. 3.2. Двойственный симплекс-метод.
  3. I. Передача параметров запроса методом GET.
  4. II. Методика работы
  5. II. Методика работы.
  6. II. Методика работы.
  7. II. Методика работы.

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

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

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

Метод находит локальный экстремум и может «застрять» в одном из них. Если всё же требуется найти глобальный экстремум, можно пробовать выбирать другой начальный симплекс.

Опишем идею этого метода применительно к функции двух переменных для поиска максимума функции z = f(x, y).

В начале расчета задается начальный симплекс – для 2-мерного случая – правильный треугольник, и вычисляются значения функции в вершинах треугольника, рис.13.3, а.

а) б) в) г)
Рисунок 13.3 – Пояснения к алгоритму поиска экстремума Нелдера-Мида.

Отделяется вершина с наименьшим значением функции zmin. Для оставшихся двух вершин треугольника находим центр тяжести (рис.13.3, б) и проводим прямую через неудачную вершину и центр тяжести. От найденного центра тяжести в найденном направлении делаем шаг поиска, находим координаты новой точки z4 (рис.13.3, в). Если в точке z4 найдено новое максимальное значение, то делаем очередной шаг в этом же направлении. Если очередной шаг приводит к уменьшению функции, то в той точке производится отражение симплекса, выбирается новое направление движения (рис.13.3, г).

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

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

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

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

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


Дата добавления: 2015-10-29; просмотров: 134 | Нарушение авторских прав


Читайте в этой же книге: Прямые методы решения СЛАУ. | Итерационные методы. | Метод половинного деления (метод дихотомии). | Лекция 9. Численное интегрирование и дифференцирование. | Метод прямоугольников. | Численное дифференцирование. | Лекция 10. Решение систем обычных дифференциальных уравнений (ОДУ). | Визуализация решений ОДУ. | Лекция 11. Визуальное моделирование динамических систем. | Уравнения параболического типа. |
<== предыдущая страница | следующая страница ==>
Метод половинного деления| Метод пчелиного роя.

mybiblioteka.su - 2015-2024 год. (0.005 сек.)