Метод Нелдера–Мида

Алгоритм численной оптимизации

Итерация метода Нелдера-Мида в двумерном пространстве.

Поиск по функции банана Розенброка

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

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

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

Метод Нелдера–Мида был предложен Джоном Нелдером и Роджером Мидом в 1965 году ^[3] как развитие метода Спендли и др. ^[4].

Обзор

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

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

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

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

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

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

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

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

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

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

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

1. Упорядочить по значениям в вершинах:

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

   Проверьте, следует ли остановить метод. См. Завершение (иногда называемое «схождение»).

2. Вычислить центроид всех точек, кроме . ${\displaystyle \mathbf {x} _{o}}$ ${\displaystyle \mathbf {x} _{n+1}}$
3. Отражение
   Вычислить отраженную точку с помощью . ${\displaystyle \mathbf {x} _{r}=\mathbf {x} _{o}+\alpha (\mathbf {x} _{o}-\mathbf {x} _{n+1})}$ ${\displaystyle \alpha >0}$
   Если отраженная точка лучше второй худшей, но не лучше лучшей, т.е. ${\displaystyle f(\mathbf {x} _{1})\leq f(\mathbf {x} _{r})<f(\mathbf {x} _{n})}$

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

4. Расширение
   Если отраженная точка является лучшей точкой на данный момент , ${\displaystyle f(\mathbf {x} _{r})<f(\mathbf {x} _{1})}$

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

   Если расширенная точка лучше отраженной точки, , ${\displaystyle f(\mathbf {x} _{e})<f(\mathbf {x} _{r})}$

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

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

5. Сокращение
   Здесь определенно, что . (Обратите внимание, что это вторая или «следующая» за худшей точкой точка.) ${\displaystyle f(\mathbf {x} _{r})\geq f(\mathbf {x} _{n})}$ ${\displaystyle \mathbf {x} _{n}}$
   Если , ${\displaystyle f(\mathbf {x} _{r})<f(\mathbf {x} _{n+1})}$

   затем вычислите сжатую точку снаружи с помощью . ${\displaystyle \mathbf {x} _{c}=\mathbf {x} _{o}+\rho (\mathbf {x} _{r}-\mathbf {x} _{o})}$ ${\displaystyle 0<\rho \leq 0.5}$

   Если сжатая точка лучше отраженной точки, т.е. ${\displaystyle f(\mathbf {x} _{c})<f(\mathbf {x} _{r})}$

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

   В противном случае перейдите к шагу 6;

   Если , ${\displaystyle f(\mathbf {x} _{r})\geq f(\mathbf {x} _{n+1})}$

   затем вычислите сжатую точку внутри с помощью . ${\displaystyle \mathbf {x} _{c}=\mathbf {x} _{o}+\rho (\mathbf {x} _{n+1}-\mathbf {x} _{o})}$ ${\displaystyle 0<\rho \leq 0.5}$

   Если контрактная точка лучше худшей точки, т.е. ${\displaystyle f(\mathbf {x} _{c})<f(\mathbf {x} _{n+1})}$

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

   В противном случае перейдите к шагу 6;

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 \alpha =1}$ ${\displaystyle \gamma =2}$ ${\displaystyle \rho =1/2}$ ${\displaystyle \sigma =1/2}$

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

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

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

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

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

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

Прекращение

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

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

• Оптимизация без производных
• КОБИЛА
• NEWUOA
• ЛИНКООА
• Нелинейный метод сопряженных градиентов
• Алгоритм Левенберга–Марквардта
• Метод Бройдена–Флетчера–Гольдфарба–Шанно или BFGS
• Дифференциальная эволюция
• Поиск по шаблону (оптимизация)
• CMA-ES

Ссылки

1. • Powell, Michael JD (1973). «О направлениях поиска для алгоритмов минимизации». Математическое программирование . 4 : 193–201. doi :10.1007/bf01584660. S2CID  45909653.
   • МакКиннон, КИМ (1999). «Сходимость симплекс-метода Нелдера–Мида к нестационарной точке». Журнал SIAM по оптимизации . 9 : 148–158. CiteSeerX  10.1.1.52.3900 . doi :10.1137/S1052623496303482.(краткое изложение алгоритма онлайн).
2. • Ю, Вэнь Ци. 1979. «Позитивный базис и класс методов прямого поиска». Scientia Sinica [ Чжунго Кэсюэ ]: 53–68.
   • Ю, Вэнь Ци. 1979. «Конвергентное свойство симплексной эволюционной техники». Scientia Sinica [ Чжунго Кэсюэ ]: 69–77.
   • Колда, Тамара Г.; Льюис, Роберт Майкл; Торцон, Вирджиния (2003). «Оптимизация прямым поиском: новые перспективы некоторых классических и современных методов». SIAM Rev. 45 ( 3): 385–482. CiteSeerX  10.1.1.96.8672 . doi :10.1137/S003614450242889.
   • Льюис, Роберт Майкл; Шеперд, Энн; Торцон, Вирджиния (2007). «Реализация методов поиска генерирующих наборов для линейно ограниченной минимизации». SIAM J. Sci. Comput . 29 (6): 2507–2530. Bibcode : 2007SJSC...29.2507L. CiteSeerX  10.1.1.62.8771 . doi : 10.1137/050635432.
3. Нелдер, Джон А.; Р. Мид (1965). «Симплексный метод минимизации функций». Computer Journal . 7 (4): 308–313. doi :10.1093/comjnl/7.4.308.
4. Спендли, У.; Хекст, ГР; Химсворт, ФР (1962). «Последовательное применение симплексных конструкций в оптимизации и эволюционной работе». Технометрика . 4 (4): 441–461. doi :10.1080/00401706.1962.10490033.
5. Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Раздел 10.5. Метод симплекса вниз в многомерных пространствах". Numerical Recipes: The Art of Scientific Computing (3-е изд.). Нью-Йорк: Cambridge University Press. ISBN 978-0-521-88068-8.
6. Nash, JC (1979). Компактные численные методы: линейная алгебра и минимизация функций . Бристоль: Adam Hilger. ISBN 978-0-85274-330-0.

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

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

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

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