Глава 2. Оптимизация

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

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

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

Постановка задачи оптимизации может быть безусловной или содержать определенные ограничения. В частности, не все возможные комбинации значений параметров являются допустимыми. В силу существующих ограничений некоторые из них могут быть неприемлемы либо нереализуемы. Такие узлы исключаются из оптимизации. В этом случае говорят об условной оптимизации. Такого рода ограничения могут иметь вид равенств:

где х принимает значение 0 или 1 в зависимости от того, открывается ли торговая позиция для i-го базового актива. Смысл ограничения в том, что общее число базовых активов в точности равно M.

Ограничения могут принимать вид неравенств:

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

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

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

• Оптимизационное пространство (иногда называемое сеткой) – совокупность всех возможных комбинаций значений параметров формирует полное оптимизационное пространство.

• Узел (junction) – наименьшая структурная единица оптимизационного пространства, определяемая уникальной комбинацией значений параметров.

• Вычисление – все процедуры, необходимые для расчета целевой функции для одного узла оптимизационного пространства.

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

• Целевая функция – количественный показатель, выражающий меру полезности определенной комбинации значений параметров с точки зрения разработчика торговой системы (может рассчитываться аналитически или алгоритмически).

• Глобальный максимум – узел, имеющий наибольшее значение целевой функции. Глобальных максимумов может быть несколько.

• Локальный максимум – узел, расположенный на одной из вершин оптимизационного пространства, но имеющий меньшее значение целевой функции, чем глобальный максимум. Локальных максимумов может быть несколько.

• Оптимальное решение – значение параметров и целевой функции узла, на котором остановился алгоритм оптимизации. Оптимальное решение не всегда совпадает с глобальным максимумом. Чем эффективнее методика, тем ближе оптимальное решение к глобальному максимуму.

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

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

Оптимизационное пространство представляет собой совокупность всех возможных комбинаций значений параметров. Оно определяется тремя факторами:

1. Количеством оптимизируемых параметров (размерность);

2. Диапазоном допустимых значений для каждого параметра;

3. Шагом оптимизации.

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

Диапазон допустимых значений определяется теми ограничениями, которые разработчик торговой системы накладывает на параметры, участвующие в расчете целевой функции. Например, в главе 1 нами исследовались два параметра – порог критерия и диапазон страйков. В качестве диапазона допустимых значений для первого параметра использовался интервал от нуля до бесконечности. Логика выбора именно такого диапазона заключается в следующем. Поскольку в качестве критерия мы использовали математическое ожидание прибыли, то было вполне естественным не рассматривать ту часть диапазона значений параметра, где ожидаемая прибыль отрицательна. Для параметра «порог критерия» диапазон значений был определен от 0 до 50 %. Нижний предел обусловлен тем, что данный параметр не может быть отрицательным. Верхний же предел объясняется невозможностью практического использования страйков, отстоящих слишком далеко от текущей цены базового актива (в силу их низкой ликвидности и широких спредов).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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