Содержательный смысл этой операции таков: если найдено направление, в котором целевая функция возрастает, симплекс растягивается в этом направлении. Если «точка растяжения» окажется лучше «отраженной точки», то последняя заменяется в симплексе «точкой растяжения», и он становится вытянутым в этом направлении. После этого возвращаемся в шаг 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. После чего можно продолжить исполнение стандартного алгоритма, вычисляя таким же образом все точки, не попадающие на узлы оптимизационного пространства. Другой, более простой, путь состоит в выборе оптимального решения среди одной из вершин последнего симплекса (той, которая имеет наибольшее значение целевой функции).

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

2.7.2. Сравнение эффективности основных методов целенаправленного поиска

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

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

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

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

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

3. Процент неудовлетворительных оптимальных решений. Целевые функции этих решений имеют значения, не превышающие определенную пороговую величину.

4. Среднее значение целевой функции всех оптимальных решений, рассчитанное на основе 300 полных оптимизационных циклов.

5. Среднее количество вычислений, необходимых для выполнения полного оптимизационного цикла.

В таблице 2.7.1 показаны значения всех пяти показателей эффективности для четырех методов целенаправленного поиска. Когда в качестве целевой функции использовалась прибыль, метод Хука−Дживса оказался наиболее эффективным. В 69 % случаев в качестве оптимального решения был выбран узел, соответствующий глобальному максимуму (соответственно, в 31 % случаев алгоритм поиска остановился, не