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

2 о

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

Черный Александр Иванович

МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ И ЧИСЛЕННОЕ РЕШЕНИЕ ЗАДАЧ ОПТИМИЗАЦИИ РАСПРЕДЕЛЕНИЯ РЕСУРСОВ

05.13.16 - применение вычислительной техники, математического моделирования и математических методов в научных исследованиях

Автореферат !

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

Автор:

Москва - 1997

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

Научный руководитель: доктор физико-математических наук,

профессор А.В. Крянев

Официальные оппоненты: доктор физико-математических наук,

профессор

Кузьмин Анатолий Михайлович доктор физико-математических наук, сне

Хананьян Александр Ашотович

Ведущая организация: Лаборатория вычислительной

техники и автоматизации Объединенного института ядерных исследований (г. Дубна)

Защита состоится "-//" 1997 г. в "

часов на заседании диссертационного совета Д053.03.08 в Московском государственном инженерно-физическом институте (техническом университете) по адресу: 115409, Москва, Каширское ш., дом 31, тел. 423-84-98.

С диссертацией можно ознакомиться в библиотеке МИФИ.

Автореферат разослан & 1997 г.

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

Ученый секретарь диссертационного совета

д.ф.-м.н., профессор А.СЛеонов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы исследования

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

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

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

Методика исследований

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

Научная новизна

В рамках решения поставленных задач в диссертации получены следующие новые результаты: . , ;

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

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

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

4. Разработаны новые алгоритмы робастного сглаживания, основанные на ортогональных полиномах и линейных сглаживающих сплайнах.

Все перечисленные выше результаты являются новыми и ориентированы на их использование при решении конкретные практических задач оптимизации распределения ресурсов.

Теоретическая и практическая значимость

Разработанные в диссертации новые постановки задач оптимиза ции распределения ресурсов позволяют на их основе конструироват:

новые модели равновесия совокупности объектов вложения ресурсов. Разработанный в диссертации аппарат робастных сглаживающих ортогональных многочленов и линейных сглаживающих сплайнов может быть ^использован при решении различного рода задач обработки данных во многих прикладных областях науки и техники. На основе разработанных в диссертации моделей задач оптимизации распределения ресурсов и методов их численного решения и алгоритмов робасгного сглаживания создан комплекс программ "СФЕРА"; используемый различными организациями для решения задач обработки информации и принятия оптимальных решений по распределению ресурсов.

Личный вклад

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

2. Автор принял участие в разработке двухуровневой модели взаимодействия эффективностей.

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

4. Автор принял участие в разработке математической модели равновесия рынка ГКО.

5. Автор, принял участие в разработке математической модели и алгоритма численного решения оптимизации большого портфеля.

6. Автором предложено новое определение риска вложения средств.

7. Автором разработан алгоритм вычисления робастных линейных сглаживающих сплайнов.

Автор защищает;

1. Алгоритм численного решения обобщенной задачи оптимизации Марковица.

2. Двухуровневую модель взаимодействия эффективностей вложения средств, учитывающую влияние регионов.

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

4. Математическую модель оптимизации большого портфеля.

5. Алгоритм вычисления робастных линейных сглаживающих сплайнов.

Структура и объем диссертации

Диссертация состоит из введения, трех глав, разбитых на 8 пунктов, заключения, списка литературы из,. 124 наименований и четырех приложений. Общий объем диссертации 135 машинописных страниц.

Содержание работы

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

Рассматривается обобщенная задача Марковица с априорными ограничениями

S* = argmin Op(mp), (2)

.'• у»;.; ieG(mp), ;

где oJ(mp) = - риск портфеля, j? = (*,,..„.jcJ7 - вектор долей

ресурсов, составляющий портфель; W - ковариационная матрица случайного вектора эффективностей R; G(mp) - множество, определяемое совокупностью естественных ограничений*г б,

I равенством, (MR, f) = mp и ограничений, задаваемых в виде

групповых неравенств вида.

Osa.sx. +...+Х/ sB.sl, (2)

Osam¿x¡ +...+X, sfl.sl,

где от(и <h) ,—/'' количество априорных ^ групп, , Л/Л - вектор математических ожиданий случайного вектора эффективностей R. ; . Прогнозируемое значение эффективности портфеля тр фиксируется на промежутке тр elwipBtíB, m^l Для нахождения mpmin, mpmix й, соответствующих;им распределений долей f^.f^ получаем две задачи линейного программирования

но . •'.••.'.'•

x^aigmiiiiMR.x), (4>

' lee

где G с — множество, определяемое совокупностью естественных ограничений на вектор долей X и априорных ограничений, задаваемых в виде групповых неравенств (2).

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

Для численного решения совокупности экстремальных задач (1) на сетке значений шр из промежутка ]'"pmin»'npIMJ[[ для двойственной к (1) задачи использован метод последовательных приближений, аналогичный методу Некрасова. Показано, что используемый метод дает минимизируемую последовательность, сходящуюся к искомому решению задачи (1) (теорема 1. Г диссертации).

В результате решения семейства локальных обобщенных задач Марковица для всевозможных > фиксированных значений /ггр е]/лртЬ,/йр1ШХ[ получаем зависимость минимального значения

риска портфеля op(wp) от среднего значения эффективности портфеля тр. ' '

Известно, что выпуклость функции ор'=Ь (/ир) в классической постановке Марковица играет ключевую роль в построении модели равновесия САРМ (Capital Asset Pricing Model). Показано, что свойство выпуклости функций op(mp) остается справедливым и в рамках обобщенной постановки задачи Марковица.

Рассматривается некорректная обобщенная задача Марковица в условиях плохой обусловленности или вырожденности ковариационной матрицы W. . В последнем случае задача (1) может иметь множество решений X'cG{mp). В диссертации предлагается регуляризация некорректной обобщенной задачи Марковица, использующая информацию о прежнем составе портфеля.

Вместо обобщенной задачи Марковица (1) рассмотрим обобщенную локальную регуляризованную задачу

х' =аг§пип{ор(т ) + а(£)(х -х -х0)}, (5)

где х0 = (х10,...,хк0)г - вектор долей прежнего портфеля, О -

диагональная матрица, элементы которой (^>0, 1 = 1,« характеризуют значимость изменений при переходе от прежнего состава портфеля к новому, а > 0 - параметр регуляризации.

Для каждого фиксированного /лр еи а >0 регуляри-зованная задача (5) имеет единственное решение, которое может быть найдено с помощью, численной итерационной процедуры, примененной в диссертации для нахождения приближенного решения корректной обобщенной задачи Марковица.

Рассмотрим взаимодействия эффективностей. Предлагается двухуровневая модель взаимодействия эффективностей вида

^а^ьР-кп + ьУ-кп+ь^-Ии + с,,

+ + (6)

где Я1П - эффективности рынка в целом, / -го объекта

вложения средств, к-й отрасли и I -го региона, которым принадлежит I -й объект вложения средств соответственно.

Двухуровневая модель (6) позволяет естественным образом выделить составляющие альфа, бета-коэффициентов, коэффициента^2 и риска для рассматриваемого (/ -го) объекта вложения средств, отнесенные к отрасли, к региону и непосредственно к рынку. Тем самым математическая модель (6) дает возможность рассчитывать вклад отрасли, региона и непосредственно рынка в каждый из

показателей а, (3, Д2 и риск для каждого объекга вложения средств.

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

до текущей даты равна длине промежутка Д»,' на который решается задача оптимизации портфеля и определена эффективность. В качестве риска вложения средств в рассматриваемый объект.берется мера отклонения от прогнозируемого ; значения эффективности. ■ Например, в качестве расчётных значений эффективностей и рисков рассматриваемого объекта можно взять соответственно математическое ожидание и дисперсию случайной величины И^. Очевидно в предлагаемой схеме оценки расчетных значений эффективностей и рисков реализуется правило - тот, кто лучше прогнозирует, имеет лучший результат. -' ...'. : IV';- :, ^ ■■-•о.- _-•'.-,■■■•./.'г . '

Обозначим через /»^(Л, совместную штоттность вероятностей компонент вектора Обозначим через/^ вероятность события А( = (Л)рге>Л(/,¿' =1,п,|'*I), I = Т~пл Очевидно событйя Л,, < =Т~п

попарно несовместны и £р1 = 1. Оценки вероятностей р1 можно'

получить с помощью статистического эксперимента Монте-Карло, разыгрывая значение случайного вектора Определим риск

портфеля, определяемого вектором долей £ «■(*1,.:.>х(|)т/формулой °р= гДе _ ковариационная матрица случайного

Н ' И ' И т

нормированного вектора эффективностей вложений^, =(/?, ,.,.,/?,), с дисперсиями о2(Л,я) = + « '= М. « > О,

о^Ж1=шах|о^ге}, с корреляционной матрицей и вектором математических ожиданий Мй" равными соответственно корреляционной матрице и вектору математического ожидания вектора прогнозируемых эффективностей /■.•.•:'•'•• '•"'..--.

Из определения портфельного риска аг(Я") для i -го объекта следует:

Io. a2(Jt¡B)-0 при р, -1, в частности, а2(Я") = 0, если списочный состав портфеля состоит из одного объекта;

2°. o2(Ä*)-«» при р, -0 в том числе и для "безрисковых" объектов, например, для объектов с гарантированной эффективностью, для которых прогнозируемый собственный риск о^е=0. Поскольку при pt = 0 пор+фельный риск i-го объекта равен

; бесконечности, такой о&ъект автоматически исключается из списочного состава портфеля и оптимйзация состава портфеля будет производиться только относительно объектов, для которых pt> 0.

Далее рассматривается оптимизация "большого" поргфеля вложений.

Вместо риска портфеля, фигурирующего в задаче Марковица, в качестве минимизируемого функционала в задаче оптимизации большого портфеля берется функционал расстояния Jfo(.x,x0) нового портфеля от существующего V

4s,(*.*„) = ¿ «Ддг(5р-х1050)2, (7)

<-1 .

где '«,, Sp, S0> 0.

Глобальная задача оптимизации большого портфеля имеет вид

•'/' min J&(X,x0) (8)

tcGim,) ■

для всех mp eCmpiBia,mpnixJ,

Для каждого фиксированного тр е[гарпйп,тршах1 локальная задача

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

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

Математическая модель рассматриваемой . линейной задачи оптимизации портфеля имеет вид

х(Я ) = г1%тта , (9)

где ' У '.'Л. ■ Л ■ ." V \ ••' '-•■■'•^ •

= <10>

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

(9) получаем зависимость ар = ^ 6 . Функция ар(Др) возрастающая, выпукла вниз и кусочно-линейна. Следователь- . но, для линейной задачи оптимйзации глобальной минимум ар достигается при минимально возможном значении эффективности вложений. Отсутствие глобального минимума ар внутри промежутка [/?ршЬ, /?рю1Х] означает, что в линейной постановке задачи оптимизации распределения вложений невозможно за счет диверсификации вложений добиться меньшего значения минимизируемой линейной целевой функции, чем его минимальное значение в одной из крайних точек.

Предложен эффективный алгоритм численного решения экстремальных задач (3), (4).

Предлагается модель динамического управления распределением ресурсов, использующая робастные сглаживающие ортогональные полиномы. Задача оперативного управления состоит в максимизации роста стоимости портфеля Rp на задаваемый временной промежуток от текущего момента f0 до i, за счет перевложения средств из менее

эффективных в более эффективные.

Считается, что объекты вложения средств отличаются друг от друга только сроком полного возврата средств. Следовательно, вся информация о состоянии совокупности объектов вложения средств содержится в зависимости />(х.), где р(т.), - цена вложения средств

в /-й объект со сроком полного возврата средств tr

Будем считать текущим равновесным состоянием совокупности объектов вложения средств совокупность точек (т,-,/'Я1Ю(т|.)),/ = 1,п, полученную путем сглаживания исходной совокупности точек i=I7n. Если paB0(t,)<p(il), то 1-й объект считается переоцененным, если же то i -й объект считается

недооцененным.

В качестве функций, сглаживающих совокупность точек (т(,р(т()), i = l,п, взяты робастные ортогональные полиномы 2

к = 0,1,..., где х{ =-т,.-1,

тш»х

1 •

5и, - символ Кронекера, wf - заданные веса. Система ортогональных полиномов Ф4(х) может быть построена с помощью схемы Форсайта.

Сглаживающая робастная функция р^х) определяется равенством ' у ■ "" у V- У~-,,; у у J-' ' -У/'л •'...■ ■ "V '.у, ¡:-- ,

Pm»(X):EUt*i(X)' где коэффициенты ик определяются равенством у 7уд'.у.

й = argminè р( W^)-ptmo(xi))), OD

, у'.----.- "* i-1 y " . //ууу:4 "• ' У y У-

a p(s) - функция, определяющая М-оценкй вектора S. .'С/^-

Алгоритм численного: решения экстремальной задачи (11) : зависит от вида функции p(s). " "у'.':;у; "'у'•'.;••••' у уУ

Например, если р (s) - функция Хьюбера, т.е.

^»V; j 5'ЛГ; :лу'; V У^ %;:у-t л > : гад-*2, \s\>K, ;

где К - параметр ^Сьюбера, то решение й экстремальной задачи (11) может быть найдено как предел итерационной процедуры

«;'"> = £»?Ф/*Х\ 02)

где у,Ю-Р(х{), если / е/0(Ц(1)), у{1) - £ ^ если

i»0

я

iel,(«<'>), у/0 = £ «<'>Ф*(х,) - К! Wit если i 6 (и(0), а множества /0(и)> /.(и), /_(й) определены равенствами

./oWrji:\P(xt) - £ и4Ф4(х4) jу

/.(¿?) = |г:Р(х4) - £ и^Ц) >

/.(*) = |«:Р(х,) - £ и*Ф4(х() <

В качестве начальных значений uj0) рекомендуется брать i-0

Выбор в качестве p(s) функции Хьюбера обеспечивает робас-тность сглаженной оценки p^ix) в условиях симметрии расположения больших выбросов, что в свою очередь предполагает, чго число больших выбросов достаточно велико. В то же время при решении реальных задач наиболее типичны ситуации, когда число больших выбросов мало (обычно от одного до пяти). В таких условиях явного нарушения симметрии необходимо применять методы робастного оценивания, не предполагающие наличия симметрии, в частности, можно использовать оценку (11), где

¡я1, !■<!>*•.

В этом случае решение и экстремальной задачи (11) может быть найдено как предел итерационной процедуры (12), где

= если terato),

у1° = Ê «Г «**(*,). если ¿е/в(и<"), о

а множество /»(и) определено равенством

Ш) =

ЦР1х,)-i«t9t(xt)\>Klw\. к-О J

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

Введем класс непрерывных функций Дх)е1У1, заданных на

промежутке [*,,*„]:

1°. f(xi)=yt, i=T7n, где yi ^- заданные числа; .

2°. f(x) - непрерывно дифференцируема на каждом интервале

i = 1 ; я - 1 ; .

3°. в точках х = xlt i - 2,п - 1 f (x) может иметь разрывы первого рода.

Рассмотрим робастный сглаживающий функционал

лс/) = Е + (14)

¡-1 ■ , ' X, • ; • •

где а > 0 сглаживающий параметр, а функций р (s) определяет робастную М-оценку.

Ниже предполагается, что функция р (s) * 0, причемр (s) = О только при s = 0, p(s) - четная кусочно непрерывно дифференцируема. . ■' ,■■': ... у.,'.'■' , -. В классе Wl функция, доставляющая минимум функционалу

(14) — линейный сплайн Sa(x). ' - ."S'•/.;'

Значения РЛСС S^xJ - берутся в качестве сглаживающих

значений в точках хп i = 1 ,п. Обозначим St(xi)~ S^S = (5,,. .,S/I)T.

Возьмем в качестве p(s) функцию Хыобера. Введем три множества индексов

= {«'M I /

/л= {i : PCJC.) - > /Л*)

Тогда искомый вектор s является пределом последовательности S-(>, определяемой системой равенств

= P(Xj), если i € /0(S("), y^ = S^ + K/fVj, если i 6I,(Sa)),

y<° = sj-l) -Klесли ieIASa)),

A - симметричная положительно определенная трехдиагональная матрица с диагональным преобладанием

= И?+ «/*,, И?-.«(l/A,.,.!/*,)'.

A*.« = wî + alhn-1- ai.i.v=a,.i.ib i=27îi-

В качестве- начальных значений S/0) рекомендуется брать SÎ0)*P(x,), i-TTH. "

Если в качесгве p(s) взять функцию (16), то искомый вектор5 является пределом последовательности Sl'\ определяемой системой равенств (15), где yfl)=P(x:,), если /e/0(S(,)); = если ieIB{S(li), а множество IB(S) определяется равенством

/^«{«.■to-s^W}.

Основные результаты

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

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

ции распределения ресурсов, в том числе в условиях вырожденности или плохой обусловленности ковариационной матрицы вектора эффективностей объектов вложения средств.

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

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

4. Разработаны новые алгоритмы робастного • сглаживания экспериментальных данных с помощью ортогональных на множестве экспериментальных точек полиномов и робастных линейных сглаживающих сплайнов. . ;

Публикации и апробация диссертации

Результаты диссертации докладывались и обсуждались на научных конференциях и семинарах: Конференция "Обратные и некорректно поставленные задачи" (Москва, 1995); Международная конференция "Математическое моделирование и вычисления в физике" (Дубна, 1996); Международная конференция "Обратные и некорректно поставленные задачи" (Москва, 1996); на научных семинарах в Институте научной информации по общественным наукам РАН; в Центре информационного обеспечения банковской деятельности и

предпринимательства; в JIBTA ОИЯИ, в МИФИ и других организациях. Основные результаты диссертации опубликованы в следующих работах:

1. Крянев A.B., Черный А.И. Численные методы решения некорректно поставленных задач математической теории инвестиций. В сб. докл. конф. "Обратные и некорректно поставленные задачи". М.:

1995, с.30.

2. Крянев A.B., Черный А.И. Численные решения оптимизационных задач математической теории инвестиций. М.: Препринт МИФИ 022-95, 1995.

3. Крянев А.В„ Черный А.И. Математические модели и взаимодействие эффективностей инвестиций. М.: Препринт МИФИ 009-96,

1996.

4. Крянев A.B., Рубинский ДА, Черный А.И. Математические модели и компьютерные реализации решений задач, оптимизации портфелей инвестиций. Компьютерная .хроника. М.: Интерсоцинформ,

1996, с.24-32.

5. Крянев A.B., Черный А.И. Численное решение оптимизационных задач математической теории инвестиций// Математическое моделирование, 8 (8), 1996, с.97-103.

6. Крянев А, Черный А. Равновесие на рынке ГКО: теория и практика. Рынок ценных бумаг// Аналитический журнал, 14, 1996, с.30-32,

7. Chorny АЛ, Krianev A.V. and Rubinsky D.A. Ill-posed problems of mathematical investment theory. Abstr. of Intern. Conf. "Inverse and Ill-Posed Problems". M„ 1996, p.44.

8. Chorny A.I, Krianev A.V. and Vdovina O.P. Continuous analogy of iterative method for the solution of ill-posed problems. Abstr. of Intern. Conf. "Inverse and Ill-Posed Problems." M, 1996, p.45.

9. Крянев A.B„ Черный А.И. Робастные сглаживающие линейные сплайны и их применения. М.: Препринт МИФИ 005-97, 1997.

10. Крянев А.В, Черный А.И. Математические модели задач оптимизации портфелей инвестиций. М.: Препринт МИФИ 006-97,

1997.