Введение

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

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

Обзор

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

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

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

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

Прекращение

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