3. Зафиксировав параметр «период истории для расчета HV» на значении 240, вычисляем целевую функцию для всех значений параметра «число дней до экспирации». Максимум функции приходится на узел с координатами 36 и 240 (третья точка).
4. Выполняем процедуру поиска по образцу. Определяем направление от стартового узла (номер 1) на узел 3 (правая верхняя стрелка на рис. 2.7.3) и вычисляем значение целевой функции во всех узлах, пересекаемых данным направлением.
5. Находим узел с максимальным значением целевой функции (четвертая точка с координатами 40 и 230) и строим направление, перпендикулярное к ранее найденному направлению.
6. Производим поиск в новом (перпендикулярном) направлении и находим узел с наибольшим значением целевой функции (пятая точка с координатами 34 и 215).
7. Начиная с этого узла, повторяем цикл исследующего поиска методом покоординатного подъема. Фиксируем значение параметра «число дней до экспирации» на значении 34 и вычисляем целевую функцию для всех значений параметра «период истории для расчета HV». Максимальное значение функции оказалось в узле с координатами 34 и 140 (шестая точка).
8. Фиксируем период истории на значении 140 и вычисляем целевую функцию для всех дней до экспирации. Максимум функции приходится на узел с координатами 30 и 140 (седьмая точка).
8. Фиксируем период истории на значении 140 и вычисляем целевую функцию для всех дней до экспирации. Максимум функции приходится на узел с координатами 30 и 140 (седьмая точка).
9. Повторяем процедуру поиска по образцу. Определяем направление от пятой точки на седьмую точку (левая нижняя стрелка на рис. 2.7.3) и вычисляем значение целевой функции во всех узлах, пересекаемых данным направлением. Оказывается, что ни в одном из узлов указанного направления значение целевой функции не превосходит значение седьмой точки.
10. Строим направление, перпендикулярное направлению, указанному левой стрелкой (не показано на рисунке), и производим поиск вдоль этого направления. Оказывается, что и в этом направлении не находится ни одного узла, превосходящего по величине целевой функции седьмой узел.
11. Повторяем цикл исследующего поиска. Фиксируем значение параметра «число дней до экспирации» на значении 30 и вычисляем целевую функцию для всех значений параметра «период истории для расчета HV». Максимальное значение функции оказывается в узле с координатами 30 и 105 (восьмая точка).
12. Как мы уже видели в предыдущих примерах (метод ХукаДживса), дальнейшего улучшения не происходит и, следовательно, алгоритм останавливается. Оптимальным решением является узел номер 8.
Метод Розенброка представляет собой усовершенствование методов покоординатного подъема и ХукаДживса. В некоторых случаях он может заметно улучшить эффективность поиска, однако это происходит далеко не всегда. В определенных условиях, зависящих в основном от формы и структуры оптимизационного пространства, эффективность поиска может не только не повыситься, но даже снизиться.
Метод Нелдера Мида
Существуют две разновидности метода Нелдера Мида (называемый также методом деформируемого многогранника, симплексным поиском, поиском методом амебы) первоначальная, с использованием правильного симплекса, и усовершенствованная, с использованием деформируемого симплекса (в этом разделе мы рассмотрим усовершенствованную разновидность). Название отчасти может вводить в заблуждение, поскольку известен симплекс-метод линейного программирования, решающий задачу оптимизации с линейной целевой функцией при линейных ограничениях, с которым описываемый метод не имеет почти ничего общего. Под симплексом понимается многогранник в n-мерном пространстве, имеющий n + 1 вершину. Его можно рассматривать как обобщение треугольника на случай более чем двух измерений. Треугольник, в свою очередь, является примером симплекса в двумерном пространстве.
В процессе оптимизации симплекс, образно говоря, перекатывается в пространстве параметров, приближаясь к экстремуму. Вычислив значения целевой функции в его вершинах, находим худшее из них и перемещаем симплекс так, чтобы прочие вершины остались на месте, а взамен вершины с худшим значением была бы включена вершина, симметричная «худшей» относительно центра тяжести симплекса. Особенно наглядно это можно представить в двумерном случае, когда симплекс, а им в этом случае является треугольник, перекатывается через сторону треугольника, противолежащую к «худшей» вершине. Таким образом симплекс приближается к экстремуму, пока такие движения не перестанут улучшать целевую функцию. Наилучшая из полученных вершин является оптимальным решением. Однако у такого метода есть очевидный недостаток. Когда мы окажемся в непосредственной близости экстремума, так что расстояние от центра симплекса до экстремума станет меньше стороны симплекса, он потеряет способность приближаться к экстремуму. В этом случае можно уменьшить размер симплекса, при том, что он сохранит исходную форму, и продолжить поиск, повторяя это уменьшение размеров при потере способности приближаться к экстремуму, пока длина стороны не станет меньше шага оптимизации.
Метод деформируемого симплекса (деформируемого многогранника), помимо «перекатывания» его в пространстве параметров, включает и изменение его формы (что объясняет еще одно его название «метод амебы»). Если у метода правильного симплекса нет иных параметров, кроме длины ребра симплекса, то здесь вводится система из четырех выбираемых исследователем параметров: коэффициент отражения α (обычно принимаемый равным 1), коэффициент растяжения σ (часто принимаемый равным 2), коэффициент сжатия γ (часто выбираемый равным 0,5), коэффициент редукции ρ (также может быть выбран 0,5). Как показывает опыт, выбор значений коэффициентов может оказаться критическим для получения удовлетворительных результатов оптимизации. Иногда рекомендуют выбирать коэффициенты γ и σ так, чтобы они не были взаимно обратными, например 2/3 и 2.
Алгоритм метода Нелдера Мида состоит из следующих шагов:
1. Выбираются n + 1 точка начального симплекса x1, x2 xn+1. Это могут быть любые точки, не принадлежащие n-мерной гиперплоскости. В двумерном случае, когда симплекс является треугольником, достаточно, чтобы три точки не лежали на одной прямой.
2. Точки упорядочиваются согласно значениям целевой функции (при условии, что ставится задача максимизации функции):
3. Вычисляется точка x0, являющаяся центром тяжести фигуры, вершины которой совпадают с точками симплекса, за исключением «худшей» точки xn + 1:
Для двумерной оптимизации x0 располагается посредине отрезка, соединяющего лучшую и среднюю (по значениям целевой функции) точки треугольника.
4. Шаг отражения. Вычисляем отраженную точку:
Если значение целевой функции в отраженной точке лучше, чем во второй «худшей» точке xn, но при этом не лучше, чем в наилучшей x1, то отраженная точка заменяет в симплексе удаленную из него «худшую», и алгоритм возвращается на шаг 2 (симплекс «перекатился», уйдя от «худшей» точки в сторону увеличения целевой функции). Если значение целевой функции в «отраженной точке» лучше, чем во всех исходных точках, переходим к шагу 5.
5. Шаг растяжения. Производится вычисление «точки растяжения». Она находится на одном направлении с вектором, проведенным из «худшей» точки симплекса к центру тяжести, но дальше на величину, определяемую коэффициентом растяжения:
Содержательный смысл этой операции таков: если найдено направление, в котором целевая функция возрастает, симплекс растягивается в этом направлении. Если «точка растяжения» окажется лучше «отраженной точки», то последняя заменяется в симплексе «точкой растяжения», и он становится вытянутым в этом направлении. После этого возвращаемся в шаг 2. Если «точка растяжения» окажется не лучше «отраженной точки», то смысла в растяжении нет, в симплексе остается «отраженная точка», и форма его не меняется. Также следует возврат к шагу 2.
6. Шаг сжатия. На этот шаг мы попадаем, если отраженная точка не оказывается лучше хотя бы «второй худшей» точки. Производится вычисление «точки сжатия»:
Если полученная точка оказывается лучше «худшей» точки, то она заменяет ее в симплексе, и мы переходим в шаг 2. Симплекс при этом сожмется в этом направлении. Если же полученная точка окажется хуже и «худшей» точки, то это может свидетельствовать не о неудачном выборе направления, а о том, что мы уже находимся в непосредственной близости экстремума и для его нахождения необходимо уменьшить размер симплекса, чтобы не проскочить мимо него. Переходим к шагу 7.
7. Шаг редукции (reduction). Точка с наилучшим значением целевой функции остается на месте, а все остальные стягиваются к ней.
Если размер симплекса (ввиду его неправильной формы, нужно определить это понятие особо, например как максимальное расстояние от центра тяжести среди всех вершин) окажется меньше заданной величины, то алгоритм заканчивается. В противном случае переходим на шаг 2.
Рассмотрим практическое применение метода Нелдера Мида для базовой дельта-нейтральной стратегии. Ограничим области допустимых значений параметров: 1038 для параметра «число дней до экспирации» и 70140 для параметра «период истории для расчета 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. Поскольку значение целевой функции в отраженной точке лучше, чем во всех точках начального симплекса, переходим к шагу растяжения.
2. Находим худший (по значению целевой функции) узел начального симплекса. Данный узел отмечен номером 1 на рис. 2.7.4.
3. Вычисляем центр тяжести отрезка с координатами 18 и 110, 18 и 100. Центром является узел с координатами 18 и 105.