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

РГо ОЛ

2 1 Ш Ш

На правах рукописи

ШОМПОЛОВ АНДРЕЙ ИГОРЕВИЧ

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

Специальность 05.13.13 Теоретические основы матемзтитеского моделирования, численные методы и конпл^хси программ

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидзта физике-,-«тематических наук

Москва 2000

Работа выполнена в Московском физико-техническом институте (государственном университете).

Научный руководитель:

доктор физико-математических наук, профессор Дикусар В.В.

Официальные оппоненты:

ведущая организация:

доктор физико-математических наук, профессор Жадан В. Г.

кандидат физико-математических наук, доцент Бирюков А.Г.

Центральный Экономико-Математический Институт РАН

Защита состоится

¿■/ЕЗ^У 2000 г. в ^ ч. на заседании диссертационного совета К 063.91.03 при МФТИ в Московском физико-техническом институте по адресу: 141700, г. Долгопрудный, Московская обл. Институтский пер., 9

С диссетацией можно ознакомится в библиотеке МФТИ. Автореферат разослан ¿^<4У 2000 г.

Ученый секретарь диссертационного совета, кандидат физико-математических наук

Федько О.С.

у^гс, -2 -г Ос О

У- о

Общая характеристика работы. Актуальность темы. Финансовая инженерия связана с разработкой и творческим применением финансовой технологии к решению финансовых проблем и к использованию финансовых возможностей. Теория финансовой инженерии представляет собой совокупность знаний, которая включает в себя теорию финансов, математические и статистические методы, правила и традиции бухгалтерского учета, юридические законы и налоговые кодексы. Кроме акций и облигаций в состав инструментария финансовой инженерии входит все возрастающее количество производных инструментов (разные виды опционов, фьючерсных контрактов и т.д.). Превращение финансовой науки из описательной в аналитическую началось с работы Гарри Марковица (1952), который заложил формальные основы современной теории портфеля ценных бумаг. На развитие финансовой науки влияли такие факторы, как повышение изменчивости валютных курсов, процентных ставок и товарных цен, глобализация рынков и усиление конкуренции одновременно в промышленом и финансовом секторах. Следует отметить, что подобное развитие стало возможным благодаря быстрому развитию технических средств обработки информации. Вначале информационные технологии ограничивались обработкой информации и отслеживанием сделок, а затем центр их приложения сместился в сторону проведения анализа данных и выполнения сложных вычислений. Крупные финансовые учреждения инвестировали большие суммы на разработку методов анализа информации, а также на приобретение у сторонних разработчиков необходимого для анализа программного обеспечения. До сих пор классическая постановка задачи Марковица об оптимальном портфеле представляет большой интерес. Ее различные модификации позволяют, например, учесть такие особенности российского рынка, как нестационарносгь и арбитраж. Выбор оптимального портфеля по Марковичу требует решения задачи линейного или квадратичного программирования. Как правило,такие задачи являются некорректными и требуют для своего решения специальных методов. Поэтому создание методики численного решения плохо обусловленных задач квадратичного и линейного программирования представляет собой актуальную научно-техническую задачу.

Цель работы. Разработка приближенных методов решения некорректных задач линейного и квадратичного программирования в реальном режиме в рамках задач финансовой инженерии. Для достижения указанной цели необходимо рассмотреть следующие вопросы:

1. Исследовать различные методы решения задач линейного и квадратичного программирования.

2. Разработать методы прогноза соответствующих параметров на базе методов факторного анализа и полиномов Чебышева.

3. Разработать методы вычисления собственных значений симметричной мартицы для больших размерностей.

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

1. Разработан метод оценки решения некорректной задачи линейного программирования на базе методов факторного анализа.

2. Предложен приближенный метод решения некорректной задачи квадратичного программирования с использованием системы базисов.

3. Предложены различные методы получения первого приближения при решении симметричной проблемы собственных значений.

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

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

Апробация работы. Основные результаты диссертационной работы докладывались и обсуждались на научной конференции Московского физико-технического института "Современные проблемы фундаментальной и прикладной физики и математики (Долгопрудный, 1998) на семинарах Института системного анализа РАН, ВЦ РАН, ЦЭМИ РАН, Института проблем управления РАН.

Публикации. По теме диссертации опубликовано 4-е печатные работы. Структура и объем работы. Диссертация состоит из введения и четырех глав, изложенных на 165 страницах, содержит £ таблиц, список литературы, включающий 60 наименований, 2 приложения.

В первой главе приводятся параметрические модели рынка. Сначала рассматривается параметрическая модель рынка по Марковицу, которая описывается тройкой:

(А,т,С) (1)

Здесь А-{а1, ог,... а г} - конечный набор активов, составляющих рынок; т-{т1, тг, ...т>} - вектор ожидаемых доходностей, где п\1*М[!{>] математическое ожидание случайной величины Л, представляющей собой доходность актива о/ за данный инвестиционный период Г; символ С обозначает ковариационную матрицу порядка л (СсЛ"*") ; диагональные элементы в матрице С задают дисперсию (риск) активов. Параметрическая модель (1) допускает эффектную статистическую оценку по имеющимся статистическим данным за прошлые периоды. По временным рядам доходностей оценивается матиматическое ожидание и матрица ковариаций. Нормальность доходности рассматриваемых активов принимается в качестве основного допущения. Именно нормальная случайная величина полностью определяется своим математическим ожиданием и стандартным отклонением. Модель Марковича включает понятие портфеля. Простейший способ описания портфеля состоит в указанияя количества активов того или иного вида, входящего в портфель. Под понятием актив мы имеем в виду акцию, облигацию и т.п. В задаче Марковича требуется определить минимум У(х) при условиях

У(х) = (СЗД>0 (2)

(е,х)= 1 (т,х) = т0 х>0 е=(1,1,..Л) (3) хеЯп С с Л" х " шеЛ" ееЛ" т0 е Я1

Здесь ш - вектор математического ожидания, С - матрица ковариаций,х - вектор относительных весов всех активов.

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

В модели Блека портфель с наименьшим риском сводится к решению следующей оптимизационной задачи

V(x)->min F(;t) = Сх) (4) (е,х) = 1 (т,х) = т0 (5)

Из формулировки задачи (4) - (5) следует, что допустимы любые портфели, так как на знаки = 1." никаких ограничений не накладывается. Для случая положительно определенной матирцы С, квадратичная форма V(xj (4) выпукла. Отказ от условия выпуклости в задачах Блека и Марковича приводит сообще говоря, к многоэкстремальности решений.

Решение задач Блека и Марковича требует обращения матрицы С. Таким образом, здесь возникают проблемы при плохо обусловленной матрице С. Кроме того требует своего рассмотрения также задачи большой размерности.

Для решения указанных проблем предлагается метод выбора системы базисов. Проиллюстрируем эту идею на конкретном примере. Рассмотрим три вектора т, е, Се. Здесь предполагается, что они не являются компланарными. Искомый вектор решений х выразим через выбранный базис

х = ctj/я + а2е + а3Се (б)

Для определения коэффициентов разложения °Ч> «2> аз используем систему(5) (е,х)= 1 {т,х)~ т0

В результате решение х (6) зависит от одного параметра, который определяем из условия минимума V(x) (4) в задаче Блека.

В задаче Марковича (2), (3) выберем базис из 4-х векторов т, е, Cm, Се. По аналогии с (6) имеем

х = а1т + а2е + а3Се + а.4Се (7)

С учетом равенств (3) решение (7) зависит от двух параметров. Их выбор определяется условием и минимумом квадратичной формы (2).

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

Cj = С + <хЕ а>0 а е R1 (8)

где Е- единичная матрица. Матрица Ci является невырожденной. В качестве нового базиса выберем систему т, е, Gm, Cíe.

Для оценки решения типа (6) или (7) используем доказанную в работе лемму. Лемма 1. Минимум квадратичной формы с симметричной матрицей С оценивается неравенством

О < min[(Cx¿c)] ^ min[(Cxjc) + а[(х, д:)] - umin[(x, х)]] (9)

где а > О - параметр.

Получение оценки (9) основывается на решении двух задач

minVj(x) F,(x) = (Cxjc) + a(x, x)

(m,x) = m0 (e,x)= 1 x20 (10)

minV2(x) F2(x) = ct(x, x)

(m,x) = m0 (e,x)= 1 xSO (11)

Решение задач (10) и (31) не представляет никаких трудностей, так как матрицы квадратичных форм С + аЕ,аЕ являются хорошо обусловленными при большом а . Наиболее просто получается решение для задачи (11). С помощью множителей Лагранжа.

Более точная оценка решения задачи Марковича следует из эквивалентности задачи Марковича и задачи ЛП(§1.9). Для задачи ЛП во 11-ой главе получена оценка решения методом факторного анализа.

Дальнейший метод улучшения решения связан с заменой базиса без увеличения размерности подпространства либо с увеличением числа базисных векторов. Во второй главе рассмотрены различные методы решения задач ЛП. Основным методом решения задач ЛП является так называемый симплекс-метод. В 1939 г. Л.В.Канторович сформулировал ряд задач ЛП и предложил метод их решения, который в идейном плане близок к симллекс-методу. Симплекс-метод разработан Д.Данцигом в 1943 г. при дальнейшем участии А.Чарнса, Л.Форда и Д.Фалкерсона. В настоящее время теоретические и практические аспекты этого метода хорошо разработаны. Широкое распространение получили соответствующие стандартные программы. Основным элементом в симплекс-методе выступает понятие базиса. Значительную трудность в методе составляют вырожденные задачи. В этом случае принимаются специальные меры, без которых алгоритм может оказаться неэффективным. Реализация симплекс-метода связана со следующими основными

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

В 1972 г. американские ученые В.Кли и Дж.Минти построили пример задачи ЛП с л переменными и 2п ограничениями, для решения которых требутеся не менее 2 итераций симплекс-метода. Тем самым было показано, что симплекс-метод на классе всех линейных задач является алгоритмом экспоненциальной трудоемкости. В1979 г. появилась работа Л.Г.Хачияна, в которой к задачам ЛП был применен принципиально новый алгоритм (так называемый метод эллипсоидов). Метод эллипсов был разработан А.С.Немировским, Н.З.Шором и Д.Б.Юдиным. Для указанного метода объем вычислений при решении любой задачи ЛП выражается полиномом от параметров задачи. Несмотря на усилия, предпринятые для реализации метода эллипсоидов на практике, он оказался неконкурентно-способным с симплекс-методом.

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

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

авторов в 1973 г. Отметим, что барьерно-проективные методы обладают свойством устойчивости, причем для них не требуется допустимость начального приближения. Самый важный аспект задачи ЛП связан с ее устойчивостью. В рамках общей методологии регуляризации некорректных задач принадлежащей А.Н.Тихонову построены методы, позволяющие решать произвольную задачу ЛП с любой степенью точности безотносительно к тому, устойчива она или нет. Подробно эти вопросы освещены в работах Ф.П.Васильева и А.Ю.Иваницкого, а также О.А.Ашманова. В.В.Дикусар предложил приближенный метод решения задачи ЛП за счет специальной параметризации задачи. Получение приближенного решения требует рассмотрения обобщенного решения линейной системы в рамках метода регуляризации А.Н.Тихонова.

В диссертации предложен метод оценки решения задачи ЛП на базе методов факторного анализа. Для этой цели рассматривается каноническая задача ЛП

(С, х) -» тах Се Л" х е Я" (12) Ах = В х>0 Ае11тх" В е Лт

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

Р1 = аиа1+а12а2 + ... + а1в1аи (13)

Рк= аЫа1 + ак2а2 + --+актат

Здесь РГ1 = 1,к - факторы, ау = 1,и - вектор-строки. Факторы А удовлетворяют условию

0 /*/ (Л-Л) = 1 (14>

Считаем, что вектор Сявляется линейной комбинацией выделенных факторов

С = Р1Р1 + Р2Р2 + ... + рЛ р,- = (С, Р.) (15)

В силу единственности факторного решения, коэффициенты Р, , ¡—],¿определяются однозначно. Из (13), (15) следует

т от

= х ауЦ>х) = X а'А

}ш 1 у = 1

от от

(С,*) = р1£аиР,. + ...+р,£аА,|}у (16)

где Ру компоненты вектора В (12). Справедлива следующая теорема.

Теорема (2.9.1). Если в задаче (12) матрицу Л трактовать как матрицу наблюдений в методе главных компонент факторного анализа, то в результате получаем оценку для значения функционала (&) вида (16). Оценка типа (16) распространяется и на несовместную систему (12).

Третья глава посвящена факторному анализу (ФА). В ФА рассматривается группа объектов (экономические показатели, социально-экономические показатели и т.д.). Измерения признаков объектов называются значениями их параметров. Значения параметра дгудля объекта / обозначим х¡¡. Выборочные значения параметров при фиксированном начале координат и выборе единицы измерения обычно преобразуются по формулам

'Л = ^ (17)

где Xj среднее значение, среднеквадратичное отклонение. Модель компонентного анализа (метод главных компонент) имеет вид

2] = а}\Р\ + а)2Р2 + - + а]трт / = 1> п (18>

Здесь каждый из наблюдаемых параметров линейно зависит от m некоррелированных между собой факторов (новых компонент) Fi,...F. причем

{FpFj)* 0 (Fi,Fj)=l i=J (19)

В методе (18) каждая последующая компонента дает максимально возможный вклад в дисперсию параметров. В матричном виде уравнение (18) имеет вид

Z = AF (20)

Из (19), (20) следует

R = ZZ = AFFÄ = AÄ (21)

Соотношение (21) представляет основную теорему факторного анализа, которая позволяет оценить коэффииенты линейной формы (18). Математически вычисление коэффициентов сводится к проблеме собственных значений для симметричной матрицы R.

Для эрмитовых матриц при вычислении собственных значений наиболее известен итерационный метод вращений, предложенный Якоби в 1846 г. Хотя теоретически в методе Якоби могут накапливаться ошибки, фактически устойчивость и точность высоки. Кратные собственные значения получаются стольже точно, как и простые, а собственные векторы практически ортогональны друг другу. Итерационный метод применяется там, где важна точность, надежность и простота расчета и менее существенен объем вычислений.

Для ускорения сходимости метода Якоби важно иметь хорошее начальное приближение. Для этой цели в диссертации предлагается использовать метод интерполяции (предложенный, по видимому, Ш.Е.Микеладзе в 1943 г.). Известно, что многочлен к степени однозначно определяется своими значениями в к+1 узле. Произвольно выберем к+1 значение X в качестве таких узлов. Вычислим в них значение

ДХ) = det(R - ХЕ) и построим по этим значениям интерполяционный многочлен Ньютона или Лагранжа, Тогда нахождение собственных значений матрицы сводится к нахождению корней

тШ

Практика расчетов по методу факторного анализа показывает, что число факторов не превосходит четырех с достаточной степенью точности. Этот факт и лежит в основе построения первого приближения в методе Якоба для 50 (л - число строк

матрицы Я). Для надежности расчетов строим полиномы к и к+1 степени. Наиболее приемлемым для расчетов оказался полином Лагранжа.

Кроме метода интерполяции в диссертации предлагается метод продолжения решений по параметру. Для этого рассматривается семейство матриц

Д,(а) = (1-а)£+аД (22)

Процесс итерации начинается при ао = 0 .в этом случае ^(0) = Е . Далее полагаем а1 = а0 + Да и используем в качестве первого приближения собственные значения ^(0) . Так как мало, то скорость сходимости к решению будет квадратичной. В результате получим решение проблемы собственных значений для ^¡(йО . Этот процесс можно продолжить. Достаточно вычислить Л^а»),«*. = 0,1 , в этом случае собственные значения определяются по формуле

Л*-(1-а.)£

Л = -

а*

где Л. диагональная матрица собственных значений для ЯДа.) Четвертая глава диссертации посвящена методам прогноза данных и проверки нормальности распределения случайных величин. Для проверки случайности и нормальности используются стандартные программы и алгоритмы, которые очень широко представлены в литературе по статистическим методам. Отметим, что существуют различные критерии нормальности. В большинстве они учитывают специфику явлений в определенной области знаний.

В диссертации в результате анализа различных методов прогноза наиболее приемлемыми оказались методы факторного анализа. Для этой цели прогнозируются значения факторов с использованием уравнения регрессии, а значения прогнозируемых параметров вычисляются через значения полученных факторов. В качестве уравнений регрессии используются полиномы Лагранжа и Чебышева. В работе излагается методика построения полиномов Чебышева для прогноза факторов. Оказалось, что полиномы Чебышева дают более точный прогноз. Более высокая точность прогноза методами факторного анализа объясняется некоррелированностью факторов. Основные выводы и результаты работы.

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

1. Получена оценка для решения некорректной задачи квадратичного программирования.

2. С помощью методов факторного анализа предложена оценка решения задачи ЛП.

3. Предложен приближенный метод решения задачи КП на основе выбора базисной системы векторов.

4. Для ускорения сходимости метода Якоби в проблеме собственных значений симметричной матрицы предложено два метода: 1. метод интерполяции; 2. метод продолжения решений по параметру.

5. Разработан метод прогноза данных на базе методов факторного анализа и полиномов Лагранжа и Чебышева.

6. Предложенные методы существенно облегчают процесс поиска параметров регуляризации в некорректных задачахЛП и КП.

Основные положения работы изложены в следующих публикациях:

1. А.И. Шомполов. О некоторых моделях управления инвестициями. Ц Межведомственный сборник научных трудов "Некоторые проблемы фундаментальной и прикладной математики". Изд. МФТИ, 1997, с. 154-163.

2. В.В. Дицусар, А.И. Шомполов. Некорректные задачи математического программирования. // Межведомственный сборник научных трудов "Некоторые проблемы фундаментальной и прикладной математики". Изд. МФТИ, 1997, с. 73-83.

3. В.В. Дикусар, А.И. Шомполов. Приближенные методы в задачах управления инвестиционной деятельностью. В кн. "Нелинейная динамика и управление." Изд. Эдиториал УРСС, Москва, 1999. стр. 23-36.

4. V.V. Oikoussar, A.I. Shompotov. Some Control Investment Problems. In book "Dynamics of Non-Homogeneous Systems. Proceedings of ISA, Moscow, URSS, 1999. pp. 233-245.

Актуальность темы. Финансовая инженерия связана с разработкой и творческим применением финансовой технологии к решению финансовых проблем и к использованию финансовых возможностей. Теория финансовой инженерии представляет собой совокупность знаний, которая включает в себя теорию финансов, матаматические и статистические методы, правила и традиции бухгалтерского учета, юридические законы и налоговые кодексы. Кроме акций и облигаций в состав инструментария финансовой инженерии входит все возрастающее количество производных инструментов (разные виды опционов, фьючерсных контрактов и т.д.). Превращение финансовой науки из описательной в аналитическую началось с работы Гарри Марковича (1952), который заложил формальные основы современной теории портфеля ценных бумаг. На развитие финансовой науки влияли такие факторы, как повышение изменчивости валютных курсов, процентных ставок и товарных цен, глобализация рынков и усиление конкуренции одновременно в промышленом и финансовом секторах. Следует отметить, что подобное развитие стало возможным благодаря быстрому развитию технических средств обработки информации. Вначале информационные технологии ограничивались обработкой информации и отслеживанием сделок, а затем центр их приложения сместился в сторону проведения анализа данных и выполнения сложных вычислений. Крупные финансовые учреждения инвестировали большие суммы на разработку методов анализа информации, а также на приобретение у сторонних разработчиков необходимого для анализа программного обеспечения. До сих пор классическая постановка задачи Марковича об оптимальном портфеле представляет большой интерес. Ее различные модификации позволяют, например, учесть такие особенности российского рынка, как нестационарность и арбитраж. Выбор оптимального портфеля по Марковицу требует решения задачи линейного или квадратичного программирования. Как правило, такие задачи являются некорректными и требуют для своего решения специальных методов. Поэтому создание методики численного решения плохо обусловленных задач квадратичного и линейного программировании представляет собой актуальную научно-техническюу задачу.

Цель работы. Разработка приближенных методов решения некорректных задач линейного и квадратичного программирования в реальном режиме в рамках задач финансовой инженерии. Для достижения указанной цели необходимо рассмотреть следующие вопросы:

1. Исследовать различные методы решения задач линейного и квадратичного программирования.

2. Разработать методы прогноза соответствующих параметров на базе методов факторного анализа и полиномов Чебышева.

3. Разработать методы вычисления собственных значений симметричной мартицы для больших размерностей.

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

Научная ценность.

1. Разработан метод оценки решения некорректной задачи линейного программирования на базе методов факторного анализа.

2. Предложен приближенный метод решения некорректной задачи квадратичного программирования с использованием системы базисов.

3. Предложены различные методы получения первого приближения при решении симметричной проблемы собственных значений.

4. Получена оценка решения некоррекной задачи квадратичного программирования.

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

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

Апробация работы. Основные результаты диссертационной работы докладывались и обсуждались на научной конференции Московского физико-технического института "Современные проблемы фундаментальной и прикладной физики и математики (Долгопрудный, 1998) на семинарах Института системного анализа РАН, ВЦ РАН, ЦЭМИ РАН, Института проблем управления РАН.

Публикации. По теме диссертации опубликовано 4-е печатные работы.

Структура и объем работы. Диссертация состоит из введения и четырех глав, изложенных на 165 страницах, содержит 6 таблиц, список литературы, включающий 60 наименований, 2 приложения.

В первой главе приводятся параметрические модели рынка. Сначала рассматривается параметрическая модель рынка по Марковичу, которая описывается тройкой:

Л,т,0 (1)

Здесь А={ш, а2, . ап} - конечный набор активов, составляющих рынок; т - {гт, тг, .пи) - вектор ожидаемых доходностей, где гт=М[Я1] математическое ожидание случайной величины представляющей собой доходность актива ш за данный инвестиционный период Т; символ С обозначает ковариационную матрицу порядка п (С<-яп хп) ; диагональные элементы в матрице С задают дисперсию (риск) активов. Параметрическая модель (1) допускает эффектную статистическую оценку по имеющимся статистическим данным за прошлые периоды. По временным рядам доходностей оценивается матиматическое ожидание и матрица ковариаций. Нормальность доходности рассматриваемых активов принимается в качестве основного допущения. Именно нормальная случайная величина полностью определяется своим математическим ожиданием и стандартным отклонением.

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

В задаче Марковича требуется определить минимум У(х) при условиях

Г(х) = -(С**) (СхХ) > 0 (2) е,х)= 1 (т,х) = т0 х>0 е= (1,1,. 1) (3) хеЯп С^Япхп т<=Кп е е Я" тп е Я

Здесь т - вектор математического ожидания, С - матрица ковариаций, х - вектор относительных весов всех активов.

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

В модели Блека портфель с наименьшим риском сводится к решению следующей оптимизационной задачи

V(x) min V(x) = l(x, Сх) (4) е, х) = 1 (т,х) = т0 (5)

Из формулировки задачи (4) - (5) следует, что допустимы любые портфели, так как на знаки = i,п никаких ограничений не накладывается. Для случая положительно определенной матирцы С, квадратичная форма V(x) (4) выпукла. Отказ от условия выпуклости в задачах Блека и Марковица приводит сообще говоря, к многоэкстремальности решений.

Решение задач Блека и Марковица требует обращения матрицы С. Таким образом, здесь возникают проблемы при плохо обусловленной матрице С. Кроме того требует своего рассмотрения также задачи большой размерности.

Для решения указанных проблем предлагается метод выбора системы базисов.

Проиллюстрируем эту идею на конкретном примере. Рассмотрим три вектора т, е, Се.

Здесь предполагается, что они не являются компланарными. Искомый вектор решений х выразим через выбранный базис х = агт + а2е + а3Се (6)

Для определения коэффициентов разложения <*i> а2> аз используем систему(5) е,х)= 1 (т, х)= mQ

В результате решение х (6) зависит от одного параметра, который определяем из условия минимума V(x) (4) в задаче Блека.

В задаче Марковица (2), (3) выберем базис из 4-х векторов т, е, Ст, Се. По аналогии с (6) имеем х = о,]/и + аге + а 3Се + а ¿Ce (7)

С учетом равенств (3) решение (7) зависит от двух параметров. Их выбор определяется условием х>о и минимумом квадратичной формы (2).

Непосредственно видно, что предложенный метод не требует обращения матрицы С. Кроме того, наличие несложных вычилительных процедур, делает его эффективным для решения задач большой рамерности даже в случае вырожденности матрицы С. При вырожденности матрицы С рассматриваем новую матрицу С} = С + аЕ а >0 а е R1 (8) где Е - единичная матрица. Матрица С/ является невырожденной. В качестве нового базиса выберем систему т, е, С im, Cíe.

Для оценки решения типа (6) или (7) используем доказанную в работе лемму.

Лемма 1. Минимум квадратичной формы с симметричной матрицей С оценивается неравенством

О < ттЦСх^с)] < тш[(Сх,х) + а[(х,х)]] - атгп[{х,х)] (9) где а > о - параметр.

Получение оценки (9) основывается на решении двух задач ттУ^х) У^х) = (СХуХ) + а(х, х) т,х) = т0 (е,х)= 1 х>0 (10) тт¥2(х) = а(х>х) т,х) = т0 (е,х)= 1 х>0 (И)

Решение задач (10) и (11) не представляет никаких трудностей, так как матрицы квадратичных форм С+аЕ,аК являются хорошо обусловленными при большом а . Наиболее просто получается решение для задачи (11). С помощью множителей Лагранжа.

Более точная оценка решения задачи Марковича следует из эквивалентности задачи Марковича и задачи ЛП

§1.9). Для задачи ЛП во П-ой главе получена оченка решения методом факторного анализа.

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

Во второй главе рассмотрены различные методы решения задач ЛП. Основным методом решения задач ЛП является так называемый симплекс-метод. В 1939 г. Л.В.Канторович сформулировал ряд задач ЛП и предложил метод их решения, который в идейном плане близок к симплекс-методу. Симплекс-метод разработан Д.Данцигом в 1943 г. при дальнейшем участии А.Чарнса, Л.Форда и Д.Фалкерсона. В настоящее время теоретические и практические аспекты этого метода хорошо разработаны. Широкое распространение получили соответствующие стандартные программы. Основным элементом в симплекс-методе выступает понятие базиса. Значительную трудность в методе составляют вырожденные задачи. В этом случае принимаются специальные меры, без которых алгоритм может оказаться неэффективным. Реализация симплекс-метода связана со следующими основными вопросами. Первый связан с выбором начального приближения. Второй вопрос связан с численной реализацией метода. В основном варианте симплекс-метода необходимо вычислять и хранить соответствующую матрицу на каждом шаге. Метод искусственного базиса не требует обращения матриц. Третьим аспектом является проблема вырождения. Последний вопрос касается эффективности симплекс-метода для задач большой размерности.

В 1972 г. американские ученые В.Кли и Дж.Минти построили пример задачи ЛП с п переменными и 2п ограничениями, для решения которых требутеся не менее 2 итераций симплекс-метода. Тем самым было показано, что симплекс-метод на классе всех линейных задач является алгоритмом экспоненциальной трудоемкости. В 1979 г. появилась работа Л.Г.Хачияна, в которой к задачам ЛП был применен принципиально новый алгоритм (так называемый метод эллипсоидов). Метод эллипсов был разработан А.С.Немировским, Н.З.Шором и Д.Б.Юдиным. Для указанного метода объем вычислений при решении любой задачи ЛП выражается полиномом от параметров задачи. Несмотря на усилия, предпринятые для реализации метода эллипсоидов на практике, он оказался неконкурентно-способным с симплекс-методом.

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

Одним из первых численных методов решения задач ЛП и НП (нелинейного программирования) был метод проекции градиента. Позже возник подход, в котором объединили идеи проектирования градиента и метода барьерных функций. В работах Дикина И.И. данный подход был использован для решения задач ЛП и НП. Ю.Г.Евтушенко и В.Г.Жадан распространили этот подход на общие задачи НП. Несколько вариантов метода были реализованы программно и включено в библиотеку ДИСО (диалоговая система оптимизации). Эти варианты оказались наиболее эффективны для задач с линейными ограничениями типа равенства. Следует отметить, что метод внутренней точки для задач ЛП следует из работ Ю.Г.Евтушенко и В.Г.Жадана как частный случай, что подтверждается публикацией упомянутых авторов в 1973 г. Отметим, что барьерно-проективные методы обладают свойством устойчивости, причем для них не требуется допустимость начального приближения.

Самый важный аспект задачи ЛП связан с ее устойчивостью. В рамках общей методологии регуляризации некорректных задач принадлежащей А.Н.Тихонову построены методы, позволяющие решать произвольную задачу ЛП с любой степенью точности безотносительно к тому, устойчива она или нет. Подробно эти вопросы освещены в работах Ф.П.Васильева и А.Ю.Иваницкого, а также О. А. Ашманова.

В.В.Дикусар предложил приближенный метод решения задачи ЛП за счет специальной параметризации задачи. Получение приближенного решения требует рассмотрения обобщенного решения линейной системы в рамках метода регуляризации А.Н.Тихонова.

В диссертации предложен метод оценки решения задачи ЛП на базе методов факторного анализа. Для этой цели рассматривается каноническая задача ЛП (]С,х)->тах Се Я" х е Яп (12)

Ах = В х>0 А $ Ятхп ВеЯт

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

Рх = апах + апа2 +. + а ыат (13)

Рк = ак\а 1 + ак2а2 + ••• + актат

Здесь /у = 1Д - факторы, «у = ТГ»» - вектор-строки. Факторы Р< удовлетворяют условию

Р^)= О = 1 (14)

Считаем, что вектор С является линейной комбинацией выделенных факторов С = р1Р1 + Р2Р2 + . + РЛ Р/ = Р/) (15)

В силу единственности факторного решения, коэффициенты & , 1=1,к определяются однозначно. Из (13), (15) следует рРх) = £ ссуС^х) = ^а^р,

7 =1 7=

С,*) = Р, X +. + (16)

7=1 7= где (3; компоненты вектора В (12). Справедлива следующая теорема.

Теорема (2.9.1). Если в задаче (12) матрицу А трактовать как матрицу наблюдений в методе главных компонент факторного анализа, то в результате получаем оценку для значения функционала (С,х) вида (16). Оценка типа (16) распространяется и на несовместную систему (12).

Третья

глава посвящена факторному анализу (ФА). В ФА рассматривается группа объектов (экономические показатели, социально-экономические показатели и т.д.). Измерения признаков объектов называются значениями их параметров. Значения параметра х^ для объекта / обозначим хр. Выборочные значения параметров при фиксированном начале координат и выборе единицы измерения обычно преобразуются по формулам = ^ (П) где среднее значение, - среднеквадратичное отклонение. Модель компонентного анализа (метод главных компонент) имеет вид

Здесь каждый из наблюдаемых параметров линейно зависит от ш некоррелированных между собой факторов (новых компонент) р1,.рт причем (^) = о 1Ф] (р„ = 1 ¿=у (19)

В методе (18) каждая последующая компонента дает максимально возможный вклад в дисперсию параметров. В матричном виде уравнение (18) имеет вид г = АР (20)

Из (19), (20) следует

Я = г? = АРРА = АА (21)

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

Для эрмитовых матриц при вычислении собственных значений наиболее известен итерационный метод вращений, предложенный Якоби в 1846 г. Хотя теоретически в методе Якоби могут накапливаться ошибки, фактически устойчивость и точность высоки. Кратные собственные значения получаются стольже точно, как и простые, а собственные векторы практически ортогональны друг другу. Итерационный метод применяется там, где важна точность, надежность и простота расчета и менее существенен объем вычислений.

Для ускорения сходимости метода Якоби важно иметь хорошее начальное приближение. Для этой цели в диссертации предлагается использовать метод интерполяции (предложенный, по видимому, ШЕ.Микеладзе в 1948 г.). Известно, что многочлен к степени однозначно определяется своими значениями в к+1 узле. Произвольно выберем к+1 значение х в качестве таких узлов. Вычислим в них значение

X) = с!е1(К - ХЕ) и построим по этим значениям интерполяционный многочлен Ньютона или Лагранжа. Тогда нахождение собственных значений матрицы сводится к нахождению корней А*-)

Практика расчетов по методу факторного анализа показывает, что число факторов не превосходит четырех с достаточной степенью точности. Этот факт и лежит в основе построения первого приближения в методе Якоба для « < 50 (п - число строк матрицы Я), Для надежности расчетов строим полиномы к и к+1 степени. Наиболее приемлемым для расчетов оказался полином Лагранжа.

Кроме метода интерполяции в диссертации предлагается метод продолжения решений по параметру. Для этого рассматривается семейство матриц

Щ(а) = (1-а)Е + аЯ (22)

Процесс итерации начинается при ао = 0 .в этом случае ^(0 ) = £ . Далее полагаем а1 = а0 + Да и используем в качестве первого приближения собственные значения я 1(0) , Так как Да мало, то скорость сходимости к решению будет квадратичной. В результате получим решение проблемы собственных значений для ^(а,) . Этот процесс можно продолжить. Достаточно вычислить («*),<** = 0,1 .В этом случае собственные значения определяются по формуле

А* -(1 - а *)£ А = где л, диагональная матрица собственных значений для Д^а»)

Четвертая

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

В диссертации в результате анализа различных методов прогноза наиболее приемлемыми оказались методы факторного анализа. Для этой цели прогнозируются значения факторов с использованием уравнения регрессии, а значения прогнозируемых параметров вычисляются через значения полученных факторов. В качестве уравнений регрессии используются полиномы Лагранжа и Чебышева. В работе излагается методика построения полиномов Чебышева для прогноза факторов. Оказалось, что полиномы Чебышева дают более точный прогноз. Более высокая точность прогноза методами факторного анализа объясняется некоррелированностью факторов.

1. Markowitz 1..M. Portfolio Selection. Journal of Finance 7(1). March, ¡ 952, pp.7791.

2. Markowitz IF.M. о TA Selection. Efficient L»iversisi-cati«n of Investment. Wiley, New York, 1959.

3. Markowitz II.M. Mean Variance Analysis in Porttolio Choice and Capital Markets. Basil, Blackwell, 19904. Sharae W. F. A Simplified Mode! * Portfolio Analysis. Management Science, February, 1963.

4. Tohin J. The Theory of Portfolio Selection. In F.I I. Ilahn and F.R.P. Brechling feds.). The Theory of mterest Rateo London< Macmillan, 1965, pp. 3-51.

5. Strarpe W.F. Capital Assets Priee: A Thetrty of Market Equilibrium under Condi-tiOBSofRisk. Зошпа! of Finance, 29(3) September 1964, pp. 425-442.

6. Rubinstein ; Mean Variance Synthesis of Corporate Financial Theory, Journal of Finance 28(1), March 1973.

7. Black F. & Shotez M. The Pricing of Options and Corporate Liabilities, Journal of Political Economy 81(3), May/Jwiie 1973.

8. Алехин Б.И. Рынок ценных бумаг. Введение в фондовые операции. М., Финансы и статистика, 1993.

9. Алексеев M.IC). Рынок ценных бумаг.'.' Финансы и статистика, 1992.

10. Мйркин Я.М. Ценные бумаги и фондовый рынок. М., Перспектива, 1995.

11. Чесноков A.M. * стратегия и финансовые игры. М., Финансы и статистика, ! 994.

12. Четыркин Е.М. Методы финансовых и коммерческих расчетов. . Дело, 1995.

13. Первозванокий А.А. Финансовый рынок, расчет и риск. Инфпа-М, 1994.

14. Касимов 10,Ф, Основы теории оптимального портфеля ценных бумаг, М.5 фшшгь, 1998.

15. Тихонов AJI,, Арсенин .• . Методы решения некорректных задач. Наука, 1979.

16. Будет ли величина ¿(8) значения задачи (2.7.2) близка к числу с1 ?Л

17. Ограниченность целевой функции.В рамках факторного анализа очень трудно оценить ограниченность решения для задачи (2.9.1) и (2.9.2). Это можно сделать методами работы 15.

18. С.А. Ашманов Линейное программирование. М., Наука, 1981.

19. А.Г Сухарев, А.В. Тимохов, В.В. Фёдоров. Курс методов оптимизации. М., Наука, 1986.

20. Б.Т. Поляк. Введение в оптимизацию. М., Наука, 1983.

21. Д.В. Беклемишев. Дополнительные главы линейной алгебры. М., Наука, 1983.

22. Л.Г. Хачиян. Полиномиальный алгоритм в линейном программировании. ДАН СССР, 1979, 244, №5, с. 1093-1096.

23. Д Б. Юдин., А.С. Немировский. Информационная сложность и эффективные методы решения выпуклых экстремальных задач. Экономика и мат. методы, XII, № 2,1976.

24. Н.З. Шор. Метод отсечения с растяжением пространства для решения задач выпуклого программирования. Кибернетика, -1977,-№1.

25. Л.Г. Хачиян. Сложность задач линейного программирования. Новое в жизни, науке, технике. Серия математика, кибернетика, 10. М., Знание, 1987.

26. Karmarkar N.K. A new Polynomial Time Algorithm for Linear Programming, Combi-natorica 4, pp. 373-395, 1984.

27. Fiacco A.V. and McCormick. Nonlinear Programming: Sequential Unconstrained Minimization Techniques, John Wiley and Sons, New York, 1968.

28. B. Jansen, C. Roos, T. Terlaky, J-Ph. Vial. Interior Poin Methodology for Linear Programming: Duality, Sensivity Analysis and Computational Aspects. Report 93-28. Delft University of Technology. Delft 1993.

29. Ю.Г. Евтушенко, В.Г. Жадан. Барьерно-проективные и барьерно-ньютоновские численные методы оптимизации (случай нелинейного программирования). Сообщения по вычислительной математике. М., ВЦ РАН, 1991.

30. Ю.Г. Евтушенко, В.Г. Жадан. Барьерно-проективные и барьерно-ньютоновские численные методы оптимизации (случай линейного программирования). Сообщения по вычислительной математике. М., ВЦ РАН, 1992.

31. Василъев Ф.П., Иваницкий А.Ю. Линейное программирование. М., Факториал, 1998.