Метод Нелдера – Мида - Nelder–Mead method

Поиск по функции бананов Rosenbrock

Поиск по функции Химмельблау

Поиск минимума Нелдера – Мида функции Симионеску . Вершины симплекса упорядочены по их значению, где 1 имеет наименьшее (лучшее) значение.

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

Техника Нелдера-Мида была предложена Джоном Нелдером и Роджером Мидом в 1965 году как развитие метода Спендли и др.

Обзор

В методе используется концепция симплекса , который представляет собой специальный многогранник из n  + 1 вершин в n измерениях. Примеры симплексов включают отрезок прямой на прямой, треугольник на плоскости, тетраэдр в трехмерном пространстве и так далее.

Метод аппроксимирует локальный оптимум задачи с n переменными, когда целевая функция изменяется плавно и является унимодальной . Типичные реализации минимизируют функции, а мы максимизируем их минимизацией . ${\ Displaystyle е (\ mathbf {х})}$${\ Displaystyle -f (\ mathbf {х})}$

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

Нелдер – Мид в n измерениях поддерживает набор из n  + 1 контрольных точек, организованных в виде симплекса . Затем он экстраполирует поведение целевой функции, измеренной в каждой контрольной точке, чтобы найти новую контрольную точку и заменить одну из старых контрольных точек на новую, и таким образом методика прогрессирует. Самый простой подход - заменить наихудшую точку точкой, отраженной через центр тяжести оставшихся n точек. Если эта точка лучше, чем лучшая текущая точка, то мы можем попробовать экспоненциально растянуться вдоль этой линии. С другой стороны, если эта новая точка не намного лучше, чем предыдущее значение, тогда мы переходим через долину, поэтому мы сжимаем симплекс в сторону лучшей точки. Интуитивное объяснение алгоритма из «Численных рецептов»:

Симплексный метод спуска теперь включает серию шагов, большинство из которых просто перемещают точку симплекса, где функция наибольшая («самая высокая точка»), через противоположную сторону симплекса в нижнюю точку. Эти шаги называются отражениями, и они построены так, чтобы сохранить объем симплекса (и, следовательно, сохранить его невырожденность). Когда это возможно, метод расширяет симплекс в том или ином направлении, чтобы сделать более крупные шаги. Когда он достигает «дна долины», метод сжимается в поперечном направлении и пытается просочиться вниз по долине. Если возникает ситуация, когда симплекс пытается «пройти сквозь игольное ушко», он сжимается во всех направлениях, втягиваясь вокруг своей самой нижней (лучшей) точки.

В отличие от современных методов оптимизации, эвристика Нелдера – Мида может сходиться к нестационарной точке, если задача не удовлетворяет более строгим условиям, чем это необходимо для современных методов. Современные усовершенствования эвристики Нелдера – Мида известны с 1979 года.

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

Один из возможных вариантов алгоритма NM

(Это примерно соответствует процедуре, описанной в исходной статье Нелдера – Мида.)

Применение метода Нелдера – Мида к функции Розенброка

Мы пытаемся минимизировать функцию , где . Наши текущие контрольные точки . ${\ Displaystyle е (\ mathbf {х})}$${\ displaystyle \ mathbf {x} \ in \ mathbb {R} ^ {n}}$${\ displaystyle \ mathbf {x} _ {1}, \ ldots, \ mathbf {x} _ {n + 1}}$

1. Порядок согласно значениям в вершинах:

${\ Displaystyle е (\ mathbf {x} _ {1}) \ leq f (\ mathbf {x} _ {2}) \ leq \ cdots \ leq f (\ mathbf {x} _ {n + 1}). }$

Проверьте, должен ли метод останавливаться. См. Раздел « Прекращение действия» ниже. Иногда неадекватно называют «конвергенцией».

2. Вычислить , то медианы всех точек , за исключением . ${\ displaystyle \ mathbf {x} _ {o}}$${\ Displaystyle \ mathbf {х} _ {п + 1}}$

3. Отражение

Вычислить отраженную точку с помощью .${\ displaystyle \ mathbf {x} _ {r} = \ mathbf {x} _ {o} + \ alpha (\ mathbf {x} _ {o} - \ mathbf {x} _ {n + 1})}$${\ displaystyle \ alpha> 0}$

Если отраженная точка лучше , чем второй худший, но не лучше , чем самое лучшее, то есть , ${\ Displaystyle е (\ mathbf {x} _ {1}) \ leq f (\ mathbf {x} _ {r}) <f (\ mathbf {x} _ {n})}$

затем получите новый симплекс, заменив наихудшую точку отраженной точкой , и перейдите к шагу 1.${\ Displaystyle \ mathbf {х} _ {п + 1}}$${\ displaystyle \ mathbf {x} _ {r}}$

4. Расширение

Если отраженная точка лучшая точка до сих пор , ${\ Displaystyle е (\ mathbf {х} _ {г}) <е (\ mathbf {х} _ {1})}$

затем вычислите расширенную точку с помощью .${\ displaystyle \ mathbf {x} _ {e} = \ mathbf {x} _ {o} + \ gamma (\ mathbf {x} _ {r} - \ mathbf {x} _ {o})}$${\ displaystyle \ gamma> 1}$

Если расширенная точка лучше , чем отраженные точки, , ${\ Displaystyle е (\ mathbf {х} _ {е}) <е (\ mathbf {х} _ {г})}$

затем получить новый симплекс, заменив худшую точку развернутой, и перейти к шагу 1;${\ Displaystyle \ mathbf {х} _ {п + 1}}$${\ displaystyle \ mathbf {x} _ {e}}$

иначе получите новый симплекс, заменив худшую точку отраженной точкой и перейдите к шагу 1.${\ Displaystyle \ mathbf {х} _ {п + 1}}$${\ displaystyle \ mathbf {x} _ {r}}$

5. Сокращение

Вот это точно . (Обратите внимание, что это второй или "следующий" за высшим.)${\ Displaystyle е (\ mathbf {x} _ {r}) \ geq f (\ mathbf {x} _ {n})}$${\ displaystyle \ mathbf {x} _ {n}}$

Вычислить сжатую точку с помощью .${\ displaystyle \ mathbf {x} _ {c} = \ mathbf {x} _ {o} + \ rho (\ mathbf {x} _ {n + 1} - \ mathbf {x} _ {o})}$${\ Displaystyle 0 <\ rho \ leq 0,5}$

Если контракт точка лучше , чем худший момент, то есть , ${\ Displaystyle е (\ mathbf {х} _ {с}) <е (\ mathbf {x} _ {п + 1})}$

затем получить новый симплекс, заменив худшую точку сжатой точкой, и перейти к шагу 1;${\ Displaystyle \ mathbf {х} _ {п + 1}}$${\ displaystyle \ mathbf {x} _ {c}}$

6. Сжатие

Замените все точки, кроме лучшего ( ), на${\ displaystyle \ mathbf {x} _ {1}}$

${\ displaystyle \ mathbf {x} _ {i} = \ mathbf {x} _ {1} + \ sigma (\ mathbf {x} _ {i} - \ mathbf {x} _ {1})}$ и переходите к шагу 1.

Примечание : , , и , соответственно , отражение, расширение, сжатие и уменьшить коэффициенты. Стандартные значения , , и . ${\ displaystyle \ alpha}$${\ displaystyle \ gamma}$${\ displaystyle \ rho}$${\ displaystyle \ sigma}$${\ Displaystyle \ альфа = 1}$${\ displaystyle \ gamma = 2}$${\ Displaystyle \ rho = 1/2}$${\ Displaystyle \ sigma = 1/2}$

Для отражения , поскольку это вершина с более высоким ассоциированным значением среди вершин, мы можем ожидать найти более низкое значение при отражении на противоположной грани, образованной всеми вершинами, кроме . ${\ Displaystyle \ mathbf {х} _ {п + 1}}$${\ Displaystyle \ mathbf {х} _ {п + 1}}$${\ Displaystyle \ mathbf {х} _ {я}}$${\ Displaystyle \ mathbf {х} _ {п + 1}}$

Для расширения , если точка отражения является новым минимумом вдоль вершин, мы можем ожидать найти интересные значения вдоль направления от до . ${\ displaystyle \ mathbf {x} _ {r}}$${\ displaystyle \ mathbf {x} _ {o}}$${\ displaystyle \ mathbf {x} _ {r}}$

Что касается сжатия , если мы можем ожидать, что лучшее значение будет внутри симплекса, образованного всеми вершинами . ${\ Displaystyle е (\ mathbf {x} _ {r})> е (\ mathbf {x} _ {n})}$${\ Displaystyle \ mathbf {х} _ {я}}$

Наконец, усадка справляется с тем редким случаем, когда сжатие от самой большой точки увеличивается , что не может произойти достаточно близко к неособому минимуму. В этом случае мы приближаемся к самой низкой точке в ожидании более простого ландшафта. Однако Нэш отмечает, что арифметика с конечной точностью иногда может не сжимать симплекс, и реализовал проверку того, что размер действительно уменьшается. ${\ displaystyle f}$

Начальный симплекс

Начальный симплекс важен. Действительно, слишком маленький начальный симплекс может привести к локальному поиску, следовательно, NM может легко застрять. Итак, этот симплекс должен зависеть от характера проблемы. Однако в исходной статье был предложен симплекс, в котором начальная точка задается как , а остальные генерируются с фиксированным шагом по каждому измерению по очереди. Таким образом, метод чувствителен к масштабированию составляющих переменных . ${\ displaystyle \ mathbf {x} _ {1}}$${\ displaystyle \ mathbf {x}}$

Прекращение

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

Смотрите также

использованная литература

дальнейшее чтение

• Авриэль, Мардохей (2003). Нелинейное программирование: анализ и методы . Dover Publishing. ISBN 978-0-486-43227-4.
• Купе, ID; Прайс, CJ (2002). «Положительные основы численной оптимизации». Вычислительная оптимизация и приложения . 21 (2): 169–176. DOI : 10,1023 / A: 1013760716801 . S2CID  15947440 .
• Гилл, Филип Э .; Мюррей, Уолтер; Райт, Маргарет Х. (1981). «Методы многомерных негладких функций». Практическая оптимизация . Нью-Йорк: Academic Press. стр.  93 -96. ISBN 978-0-12-283950-4.
• Kowalik, J .; Осборн, MR (1968). Методы решения задач неограниченной оптимизации . Нью-Йорк: Эльзевир. С.  24–27 . ISBN 0-444-00041-0.
• Суонн, WH (1972). «Методы прямого поиска». В Мюррей, W. (ред.). Численные методы безусловной оптимизации . Нью-Йорк: Academic Press. С. 13–28. ISBN 978-0-12-512250-4.

внешние ссылки

• Объяснение и визуализация Нелдера – Мида (Downhill Simplex) с функцией банана Розенброка
• Джон Буркардт: Код Нелдера – Мида в Matlab - обратите внимание, что вариант метода Нелдера – Мида также реализуется функцией Matlab fminsearch.
• Оптимизация Нелдера-Мида в Python в библиотеке SciPy.
• nelder-mead - реализация Python метода Нелдера – Мида
• SOVA 1.0 (бесплатное ПО) - симплексная оптимизация для различных приложений
• [1] - HillStormer, практический инструмент для нелинейной, многомерной и линейной симплексной оптимизации с ограничениями от Нелдера Мида.