15.05.2013
В статье А.В. Ершовой и И.М. Соколинской (Южно-Уральский государственный университет) рассматривается задача о портфеле ценных бумаг, целью которой является формирование портфеля активов, сочетающего в себе разумный риск и приемлемую доходность. Предлагается новый масштабируемый метод, основанный на использовании фейеровских отображений, допускающий эффективную программную реализацию на суперкомпьютере. Применение суперкомпьютерных технологий позволяет создать устойчивый финансовый инструмент для работы с ценными бумагами в режиме реального времени.
Как отмечают авторы, суперкомпьютерные технологии можно использовать для решения задач в области экономико-математического моделирования, например, задач линейного программирования. В свою очередь методы линейного программирования можно применять для решения задачи о портфеле ценных бумаг. Портфель ценных бумаг является инвестированным в ценные бумаги капиталом, приносящим доход и имеющим всевозможные риски, присущие рынку, а значит им необходимо управлять. В противном случае возрастает вероятность его потери или крупных убытков.
В описании своего исследования авторы описывают задачу о портфеле ценных бумаг системой линейных неравенств. В этой математической модели портфель ценных бумаг – это точка n-мерного пространства, т.е. вектор, каждая координата которого – это ценная бумага, или акция какой-нибудь компании. Количество ценных бумаг в портфеле определяет размерность этого пространства. Неравенства задают в n-мерном пространстве область в форме n-мерного многогранника, внутри которого находятся допустимые решения. Эту систему неравенств задает эксперт брокерской фирмы или инвестиционный консультант. Эксперт говорит, что за пределы этого многогранника выходить опасно, это риск, лучше искать решение в пределах многогранника. Это обеспечивает надежность и стабильность портфеля ценных бумаг. Далее составляется целевая функция (каждая координата, или ценная бумага, умножается на ее стоимость, и все такие произведения складываются). Искомым решением задачи максимизации стоимости портфеля ценных бумаг является n-мерная точка, находящаяся в одной из вершин многогранника, в которой значение целевой функции является максимальным. Это и есть задача линейного программирования.
Классическим методом решения задачи линейного программирования является симплекс-метод. Но он имеет ряд существенных недостатков. Во-первых, симплекс-метод плохо распараллеливается. Этот метод является последовательным методом, и задача хорошо решается им только на одном процессоре. Во-вторых, он неприменим к задачам, в которых изменяются исходные данные, что характерно для задачи о портфеле ценных бумаг, так как стоимость акций меняется ежесекундно.
По мнению авторов, в этих условиях лучше применить другой метод решения, основанный на использовании фейеровских отображений. Его главные преимущества в том, что он хорошо распараллеливается, а значит допускает эффективную программную реализацию на суперкомпьютере, и, что самое важное, он устойчив по отношению к изменяющимся исходным данным. Фейеровские отображения представляют собой обобщение понятия проектирования на плоскость и работают в некотором смысле, как самонаводящаяся ракета. Даже если цель сдвигается со временем, фейеровский метод все равно ее настигнет.
Применение нового метода на базе фейеровских отображений для решения задачи о портфеле ценных бумаг рассмотрим на простом двумерном примере на рис.1. Использование суперкомпьютера позволяет принимать оперативное решение в реальном времени. Метод выдает точные рекомендации – сколько и каких акций нужно докупить или продать. Рассмотренный пример очень упрощенный, двумерный, в нем всего две ценные бумаги. Реально портфель ценных бумаг может содержать 100 и более различных акций. В этом случае задача становится чрезвычайно ресурсоемкой. Например, задача, в которой просчитывается 20 ценных бумаг, и допустимая область описывается 42-мя неравенствами, на обычном компьютере решается за 10 часов, а на суперкомпьютере, имеющем 384 процессорных ядра, всего за одну минуту.
Рис. 1. Пример работы метода для двумерной задачи о портфеле ценных бумаг
Задача о портфеле ценных бумаг предполагает их фиксированный набор в портфеле и совершенно не говорит о том, как можно добавить или убрать ценную бумагу. Как определить, какую ценную бумагу лучше выбрать из всего их многообразия? Для этого нужно разделить все бумаги на две части: те, которые будут дорожать (прибыльные), и те, которые в будущем будут дешеветь (убыточные). Если какая-то бумага в формирующемся портфеле стала убыточной, то ее надо убрать, а вместо нее добавить в портфель более прибыльную. Как определить, какая бумага будет дорожать, а какая дешеветь? Для этого авторами использовалась специальная математическую модель.
Каждая ценная бумага представляется в виде многомерной точки, координаты которой – это параметрическое описание конкретной бумаги. Эксперт брокерской компании определяет набор параметров, исходя из которых, он может предсказать, будет дорожать или дешеветь бумага, например, положение бумаги в тренде, средний оборот торгов, спрэд между ценами спроса и предложения и т.д. Чем больше координат и статистических данных, тем достовернее результат. Соответственно, параметры ценных бумаг будут задавать размерность пространства нашей задачи. Далее эксперт формирует две системы неравенств, которые задают два многогранника. Те бумаги, которые попадают в многогранник, четко характеризуются, т.е. точки внутри зеленого многогранника будут прибыльными бумагами, а точки внутри красного многогранника будут убыточными бумагами. Кроме этих точек, еще интересно узнать и про те точки-бумаги, которые не попали в многогранники. Какими они будут?
Данную проблему можно свести к задаче, известной в математике как задача сильной отделимости, т.е. нахождение слоя наибольшей толщины, разделяющего два многогранника. На рис. 2(а) рассмотрим работу алгоритма решения этой задачи на двумерном примере.
Из произвольной точки строятся проекции на оба многогранника, а далее соединяются полученные точки на многогранниках в отрезок, затем берется середина этого отрезка, проецируется точка на многогранники, снова соединяется, берется середина … и так происходит до тех пор, пока не получится отрезок, середина которого будет проецироваться в его концы. Полученный отрезок будет толщиной разделяющего слоя. Через концы отрезка проводятся прямые, перпендикулярные этому отрезку. Таким образом, получается слой наибольшей толщины, разделяющий многогранники и вместе с ними разделяющий пространство. Все точки, входящие в полупространство с зеленым многогранником, считаются прибыльными бумагами. Все точки, входящие в полупространство с красным многогранником, считаются убыточными бумагами. А те точки, которые попали в разделяющий слой, считаются бумагами на данный момент времени с нулевой прибылью.
Так находится проекция точки на прямую и на плоскость, а вот как находить проекцию на многомерный многогранник до сих пор не известно. Чтобы решить задачу сильной отделимости, можно заменить операцию проектирования на фейеровские отображения.
На рис. 2(б) видно как работают фейеровские отображения на том же примере. Берется произвольная точка, вместо проекций из этой точки строятся последовательные приближения на оба многогранника, полученные точки на многогранниках соединяются в отрезок, а потом берется середину этого отрезка… И так происходит до тех пор, пока не получается отрезок, определяющий толщину разделяющего слоя.
Рис. 2. Алгоритмы решения задачи сильной отделимости: а – с проекциями; б – с фейеровскими отображениями
Рассмотренный алгоритм работает медленнее алгоритма с проекциями, но фейеровские отображения хорошо распараллеливаются. И здесь на помощь приходит суперкомпьютер. Уже написана программа, реализующая этот алгоритм разделения многогранников на суперкомпьютере [см. Ершова А.В., Соколинская И.М. Параллельный алгоритм разделения двух выпуклых непересекающихся многогранников с использованием фейеровских отображений // Научный сервис в сети Интернет: суперкомпьютерные центры и задачи: Труды международной научной конференции (Новороссийск, 20–25 сентября 2010 г.). – М. : Изд-во МГУ, 2010.]. Что это дает? Допустим, что есть задача, в которой просчитывается 512 различных параметров ценных бумаг. На обычном компьютере эта задача решается за 16 часов, что в принципе превышает рабочее время биржи. А на суперкомпьютере, имеющем 256 процессорных ядра, она решается за минуту.
Для получения таких результатов был проведен ряд вычислительных экспериментов [см. Соколинская И.М., Соколинский Л.Б. Параллельный алгоритм решения задачи линейного программирования с неформализованными ограничениями // Системы управления и информационные технологии. – 2008. – № 1(31).], для которых была сконструирована модельная задача. Для такого типа задач можно легко аналитически вычислить точное значение толщины максимального разделяющего слоя. Поэтому они хорошо подходят для проверки корректности алгоритма и изучения его масштабируемости. Кроме того, модельные задачи дают хорошую возможность для подбора оптимальных значений параметров алгоритма. Проиллюстрируем одну из модельных задач, заданную в виде систем линейных неравенств, где n – размерность задачи. На рис. 3 изображены два многогранника и итерации алгоритма, приводящие к разделяющему отрезку. Для проведения экспериментов был использован вычислительный кластер «СКИФ-Урал» (Южно-Уральский государственный университет, г. Челябинск).
Рис. 3. Пример работы алгоритма для трехмерной модельной задачи
Таким образом, применение суперкомпьютерных технологий в обозначенной выше задаче позволяет создать финансовый инструмент для работы с ценными бумагами в режиме реального времени. Тем самым, описанный алгоритм может быть использован для создания программы-робота, которая будет в автоматическом режиме совершать биржевые операции, обеспечивая стабильную доходность.
В настоящее время на мировых биржах уже трудятся сотни программ-роботов. Это явление получило название «роботрейдинг». Такой алгоритм позволит создать программу-робота нового поколения, которая может быстро реагировать на изменяющиеся условия рынка ценных бумаг и валют, обеспечивая владельцу преимущество в конкурентной борьбе.
Более подробно про описанное исследования можно прочитать в следующих публикациях:
1. Соколинская И.М., Соколинский Л.Б. Параллельный алгоритм решения задачи линейного программирования с неформализованными ограничениями // Системы управления и информационные технологии. – 2008. – № 1(31). – С. 37–43.
2. Ершова А.В. Алгоритм разделения двух выпуклых непересекающихся многогранников с использованием фейеровских отображений // Системы управления и информационные технологии. – 2009. – № 1(35). – С. 53–56.
3. Ершова А.В., Соколинская И.М. Параллельный алгоритм разделения двух выпуклых непересекающихся многогранников с использованием фейеровских отображений // Научный сервис в сети Интернет: суперкомпьютерные центры и задачи: Труды международной научной конференции (Новороссийск, 20–25 сентября 2010 г.). – М. : Изд-во МГУ, 2010. – С. 242–248.
4. Соколинская И.М., Соколинский Л.Б. Параллельный алгоритм решения задачи линейного
программирования с неформализованными ограничениями // Системы управления и информационные технологии. – 2008. – № 1(31). – С. 37–43.
5. Ершова А.В. Алгоритм разделения двух выпуклых непересекающихся многогранников с использованием фейеровских отображений // Системы управления и информационные технологии. – 2009. – № 1(35). – С. 53–56.
6. Ершова А.В., Соколинская И.М. Масштабируемый параллельный алгоритм построения псевдопроекций в задачах сильной отделимости // Научный сервис в сети Интернет: экзафлопсное будущее: Труды международной научной конференции (Новороссийск, 19–24 сентября 2011 г.). – М.: Изд-во МГУ, 2011. – С. 132–138.
2. Ершова А.В. Алгоритм разделения двух выпуклых непересекающихся многогранников с использованием фейеровских отображений // Системы управления и информационные технологии. – 2009. – № 1(35). – С. 53–56.
3. Ершова А.В., Соколинская И.М. Параллельный алгоритм разделения двух выпуклых непересекающихся многогранников с использованием фейеровских отображений // Научный сервис в сети Интернет: суперкомпьютерные центры и задачи: Труды международной научной конференции (Новороссийск, 20–25 сентября 2010 г.). – М. : Изд-во МГУ, 2010. – С. 242–248.
4. Соколинская И.М., Соколинский Л.Б. Параллельный алгоритм решения задачи линейного
программирования с неформализованными ограничениями // Системы управления и информационные технологии. – 2008. – № 1(31). – С. 37–43.
5. Ершова А.В. Алгоритм разделения двух выпуклых непересекающихся многогранников с использованием фейеровских отображений // Системы управления и информационные технологии. – 2009. – № 1(35). – С. 53–56.
6. Ершова А.В., Соколинская И.М. Масштабируемый параллельный алгоритм построения псевдопроекций в задачах сильной отделимости // Научный сервис в сети Интернет: экзафлопсное будущее: Труды международной научной конференции (Новороссийск, 19–24 сентября 2011 г.). – М.: Изд-во МГУ, 2011. – С. 132–138.
Партнеры
