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

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

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

Метод деформируемого симплекса (деформируемого многогранника), помимо «перекатывания» его в пространстве параметров, включает и изменение его формы (что объясняет еще одно его название – «метод амебы»). Если у метода правильного симплекса нет иных параметров, кроме длины ребра симплекса, то здесь вводится система из четырех выбираемых исследователем параметров: коэффициент отражения ? (обычно принимаемый равным 1), коэффициент растяжения ? (часто принимаемый равным 2), коэффициент сжатия ? (часто выбираемый равным 0,5), коэффициент редукции ? (также может быть выбран 0,5). Как показывает опыт, выбор значений коэффициентов может оказаться критическим для получения удовлетворительных результатов оптимизации. Иногда рекомендуют выбирать коэффициенты ? и ? так, чтобы они не были взаимно обратными, например 2/3 и 2.

Алгоритм метода Нелдера – Мида состоит из следующих шагов:

1. Выбираются n + 1 точка начального симплекса x₁, x₂ … x_n+1. Это могут быть любые точки, не принадлежащие n-мерной гиперплоскости. В двумерном случае, когда симплекс является треугольником, достаточно, чтобы три точки не лежали на одной прямой.

2. Точки упорядочиваются согласно значениям целевой функции (при условии, что ставится задача максимизации функции):

3. Вычисляется точка x₀, являющаяся центром тяжести фигуры, вершины которой совпадают с точками симплекса, за исключением «худшей» точки x_{n + 1}:

Для двумерной оптимизации x₀ располагается посредине отрезка, соединяющего лучшую и среднюю (по значениям целевой функции) точки треугольника.

4. Шаг отражения. Вычисляем отраженную точку:

Если значение целевой функции в отраженной точке лучше, чем во второй «худшей» точке x_n, но при этом не лучше, чем в наилучшей x₁, то отраженная точка заменяет в симплексе удаленную из него «худшую», и алгоритм возвращается на шаг 2 (симплекс «перекатился», уйдя от «худшей» точки в сторону увеличения целевой функции). Если значение целевой функции в «отраженной точке» лучше, чем во всех исходных точках, переходим к шагу 5.

5. Шаг растяжения. Производится вычисление «точки растяжения». Она находится на одном направлении с вектором, проведенным из «худшей» точки симплекса к центру тяжести, но дальше на величину, определяемую коэффициентом растяжения:

Содержательный смысл этой операции таков: если найдено направление, в котором целевая функция возрастает, симплекс растягивается в этом направлении. Если «точка растяжения» окажется лучше «отраженной точки», то последняя заменяется в симплексе «точкой растяжения», и он становится вытянутым в этом направлении. После этого возвращаемся в шаг 2. Если «точка растяжения» окажется не лучше «отраженной точки», то смысла в растяжении нет, в симплексе остается «отраженная точка», и форма его не меняется. Также следует возврат к шагу 2.

6. Шаг сжатия. На этот шаг мы попадаем, если отраженная точка не оказывается лучше хотя бы «второй худшей» точки. Производится вычисление «точки сжатия»:

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

7. Шаг редукции (reduction). Точка с наилучшим значением целевой функции остается на месте, а все остальные стягиваются к ней.

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

Рассмотрим практическое применение метода Нелдера – Мида для базовой дельта-нейтральной стратегии. Ограничим области допустимых значений параметров: 10–38 для параметра «число дней до экспирации» и 70–140 для параметра «период истории для расчета HV». Для выполнения алгоритма следует исполнить следующие процедуры:

1. Выбираем три точки начального симплекса. Предположим, что в качестве вершин симплекса были выбраны узлы с координатами 12 и 105, 18 и 110, 18 и 100.

2. Находим худший (по значению целевой функции) узел начального симплекса. Данный узел отмечен номером 1 на рис. 2.7.4.

3. Вычисляем центр тяжести отрезка с координатами 18 и 110, 18 и 100. Центром является узел с координатами 18 и 105.

4. Выполняем шаг отражения, используя коэффициент растяжения ? = 1. Отраженная точка, отмеченная номером 2 на рис. 2.7.4, имеет координаты 24 и 105. Поскольку значение целевой функции в отраженной точке лучше, чем во всех точках начального симплекса, переходим к шагу растяжения.

5. Вычисляем «точку растяжения», используя коэффициент растяжения ? = 2. Она находится путем удвоения расстояния между центром тяжести симплекса и второй точкой. Полученный узел (отмечен номером 3 на рис. 2.7.4) имеет более высокое значение целевой функции по сравнению с узлом номер 2 и поэтому заменяет последний, становясь новой вершиной симплекса.

6. Выполняем очередной шаг отражения. Отраженная точка отмечена номером 4 на рис. 2.7.4. Поскольку значение целевой функции в отраженной точке ниже, чем во второй худшей точке предыдущего симплекса, переходим к шагу сжатия.

7. Вычисляем «точку сжатия», используя коэффициент сжатия ? = 0,5. Получаем узел под номером 5. Поскольку этот узел лучше худшего в предыдущем симплексе, но не самый лучший, переходим к шагу отражения.

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

9. Вычислив «точку сжатия», получаем точку номер 7. Поскольку данная точка попадает между двумя узлами, дальнейшее выполнение стандартного алгоритма Нелдера – Мида для данного оптимизационного пространства невозможно. Для выбора окончательного оптимального решения можно пойти несколькими путями. Можно вычислить целевую функцию точки 7 путем интерполяции как среднее арифметическое целевых функций узлов с координатами 32 и 100, 34 и 100. После чего можно продолжить исполнение стандартного алгоритма, вычисляя таким же образом все точки, не попадающие на узлы оптимизационного пространства. Другой, более простой, путь состоит в выборе оптимального решения среди одной из вершин последнего симплекса (той, которая имеет наибольшее значение целевой функции).

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