автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Использование свойств VaR-критерия для построения алгоритмов решения задач стохастического программирования с CVaR-критерием

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

ир,1 s-fj—' —

Чернобровов Алексей Игоревич

ИСПОЛЬЗОВАНИЕ СВОЙСТВ УаЛ-КРИТЕРИЯ ДЛЯ ПОСТРОЕНИЯ АЛГОРИТМОВ РЕШЕНИЯ ЗАДАЧ СТОХАСТИЧЕСКОГО ПРОГРАММИРОВАНИЯ С СУаЕ-КРИТЕРИЕМ

Специальность 05.13.01 Системный анализ, управление и обработка информации (авиационная и ракетно-космическая техника)

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

1 и ЯНВ 2013

Москва, 2012

005048155

005048155

Работа выполнена на кафедре «Теория вероятностей» Московского авиационного института (национального исследовательского университета, МАП).

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

доктор физико-математических наук, профессор Кибзун Андрей Иванович

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

кандидат физико-математических наук, доцент Рыбаков Константин Александрович

доктор физико-математических наук, профессор Щербаков Павел Сергеевич

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

Институт проблем информатики РАН

Защита состоится "21" декабря 2012 г. в 10 ч. 30 мин. на заседании Диссертационного совета Д 212.125.04 Московского авиационного института по адресу: 125993, Москва, А-80, ГСП-3, Волоколамское ш., 4, аудитория 301 ГАК.

С диссертацией можно ознакомиться в библиотеке Московского авиационного института (национального исследовательского университета).

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

Автореферат разослан " fe' " HüUiV Л 2012 г. Ученый секретарь Диссертационного совета Л919 1"):) П.1

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

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

Объект исследования. В диссертационной работе изучаются задачи стохастического программирования с критерием в форме интегральной квантили. Интегральную квантиль также называют Conditional-Value-at-Risk (CVaR), Average-Value-at-Risk (AVaR), Expected Shortfall, Tail Value-at-Risk (TVaR), Tail Conditional Expectation (TCE).

Актуальность темы. В технике, экономике, биологии часто приходится иметь дело с математическими моделями, где часть исходных данных является случайными. Такие модели удобно описывать с помощью задач стохастического программирования. Такие задачи, как правило, более адекватно описывают реальные явления и процессы, чем детерминированные. Поэтому результаты, полученные на основе этих моделей, являются более практически значимыми, чем для детерминированных моделей. Задачам стохастического программирования посвящены работы Дж. Бёржа, Р. Ветса, С. Волласа, Ю.М. Ермольева, П. Калла, Ю.С. Кама, А.И. Кибзуна, В. Купера, Р. Леппа, К. Марта, A.B. Назина, Н.М. Новиковой, Б.Т. Поляка, А. Прекопы, Э. Райка, С.П. Урясьева, А. Чарнса, Д.Б. Юдина и многих других авторов.

Так, к прикладным задачам стохастического линейного программирования относятся, например, задача управления воздушным движением и планирования полетов с учетом погодных условий, задача планирования добычи угля, различные логистические задачи в стохастической постановке и многие другие. Наиболее распространенными на практике являются задачи нелинейного стохастического программирования. К этому классу принадлежат экономические задачи, связанные с распределением инвестиционных капиталов, изучавшиеся В.В. Домбровским, Ю.С. Капом, Дж. Келли, А.И. Кибзуном, Е.А. Кузнецовым, Г. Марковичем, А.Р. Панковым, К.В. Семенихиным, Дж. Тобиным, С.П. Урясьевым; организационно-технические задачи планирования добычи, обработки и хранения нефти, оптимизации деятельности железнодорожного узла, прогноза скорости ветра и многие другие задачи. В настоящее время при синтезе и анализе алгоритмов управления беспилотными летательными аппаратами, в том числе управляемыми ракетами различных классов, широкое распространение получили задачи стохастического управления, которые иногда удается свести к задачам стохастического программирования. Задачам стохастического управления посвящены, например, работы Б.И. Ананьева, Б.Ц. Бахшияна, Р. Беллмана, А. Брайсона, Р. Калмана, И.Я. Каца, В.Б. Колмановского, М.Н. Красилыцикова, H.H. Красовского, А.П. Крищенко, В В. Малышева, А.И. Матасова,

Б.M. Миллера, A.B. Наумова, П.В. Пакшина, A.B. Пантелеева, Ю.П. Пы-тьева, Г.А. Тимофеевой, В.М. Хаметова, Ф.Л. Черноусько.

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

Можно привести пример из современной теории инвестирования. В классической постановке Марковица средний доход фиксируется, и минимизируется дисперсия дохода как мера риска получить доход, отличный от среднего. Во многих случаях такая постановка не оправдана, так как слабо учитывает субъективные желания игрока. Более того, при тяжелых "хвостах" распределения постановка Марковица может быть и вовсе лишена смысла. Если в качестве критерия выбрать максимизацию среднего дохода, возникает эффект, называемый эффектом "биржевого парадокса". Данный эффект заключается в том, что доход лица, принимающего решения, может стремиться к бесконечности, но вероятность разориться при этом стремится к единице. Квантильная постановка задачи (или постановка с VaR-критерием) заключается в поиске стратегии, которая гарантирует максимальный доход с заданной вероятностью. Такая постановка гораздо лучше учитывает интересы инвестора, чем описанные выше, однако и ее легко раскритиковать. Например, можно получить стратегию, которая с заданной вероятностью гарантирует доход в 1 рубль, но при этом во всех остальных случаях сулит миллионные убытки. Такую стратегию можно легко получить с помощью VaR-критерия, поскольку он не учитывает все неблагоприятные случаи за уровнем заданной вероятности (на "хвосте" распределения). В частности, чтобы избежать получения таких стратегий, был предложен CVaR-критерий (интегральная квантиль), который характерезует усредненное значение в неблагоприятных случаях.

Задачам с VaR-критерием посвящены работы Б.В. Вишнякова, Р. Леппа, А.В Наумова, В.И. Норкина, Ю.С. Кана, А.И. Кибзуна, В.В. Малышева, Е.Л. Матвеева, К. Марти и других. Задачи с CVaR-критерием рассматриваются например, в работах Ф. Арцнера, Д. Дент-чевой, Е.А. Кузнецова, А.И. Кибзуна, Е.А. Нурминского, Дж. Пфлюга, Р. Рокафеллара, А. Ручинского, C.B. Стоянова, С. Урясьева, А. Шапиро.

Первые работы по CVaR-критерию были сделаны в самом конце XX-века. Они тесно связаны с понятием когерентной меры риска. VaR, в отличие от CVaR-критерия, не является когерентной мерой риска.

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

У CVaR критерия также есть недостатки. CVaR нельзя определить для случайных величин с "тяжелыми" хвостами, что является существенным недостатком по сравнению с Va.R. На практике задачи часто формулируются в виде требований по надежности (ограничение на вероятности). Такие задачи можно свести к задаче с VaR критерием, но не с CVaR.

Помимо этого CVaR и VaR критерии обладают тесной связью между собой. Они могут быть связаны непосредственно через определение, причем разными способами. Поэтому некоторые результаты, справедливые для VaR, также можно использовать при решении задач с CVaR-критерием. Хотя сами критерии разные, представляют интерес случаи, когда множества решений задач VaR и CVaR будут совпадать.

Стоит отметить, что применение стандартных численных методов к решению задач стохастического программирования затруднено тем, что целевая функция имеет случайную структуру. Для преодоления данной трудности были разработаны алгоритмы, использующие стохастический квазиградиент. Ему посвящены работы Ю.М. Ермольева, A.M. Гупала, B.C. Михалевича, В.И. Норкина, С. Урясьева и других. Применение таких алгоритмов достаточно полно исследованно для задач с VaR-критерием, некоторые эти результаты можно использовать для CVaR-критерия. Поэтому представляет интерес построение стохастического квазиградиентного алгоритма для решения задач с CVaR-критерием.

Таким образом, проблема разработки эффективных методов поиска оптимальных стратегий в задачах стохастического программирования с CVaR-критерием, ипользующих свойства VaR-критерия, является актуальной.

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

Для достижения поставленной цели предполагается:

1) построение детерминированных эквивалентов для задач с CVaR-критерием;

2) описание условий эквивалентности задач с критериями VaR и CVaR;

3) разработка стохастического квазиградиентного алгоритма миними-

зации СУаЯ-критерия;

4) разработка, алгоритма, для решения комбинированной задачи с УаИ-критерием и ограничением на СУа11.

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

Достоверность результатов. Достоверность результатов обеспечивается:

1) строгостью постановок и доказательств утверждений;

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

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

1) Получены детерминированные эквиваленты для широкого круга задач с СУаН-критерием;

2) Получено аналитическое решение для задач с УаГ1 и СУаН. критериями для билинейной целевой функции при симметричном распределении случайного вектора;

3) Сформулированы условия, при которых задачи с критериями Уа11 и СУа11 эквиваленты для разных классов функции потерь;

. 4) Разработан стохастический квазиградиентный алгоритм минимизации СУаИ-критерия, использующий выборочные оценки, сходящийся почти наверное;

5) Предложены алгоритмы решения задач с УаЛ-критсрнем и ограничением на СУаЯ для кусочно-линейной и билинейной функций потерь.

Практическая значимость. Диссертация обладает практической значимостью, поскольку полученные результаты позволяют эффективно решать прикладные задачи с С УАК-критерием, в частности:

в области экономики при построении рациональной стратегии распределения ресурсов;

в области техники - рассмотрена задача об оптимизации взлетно-посадочной полосы: найдена её верхняя оценка с использованием СУай.-критерия.

Апробация работы. Результаты работы докладывались на следу-

ющих научных конференциях п симпозиумах: Международная конференция "Авиация и космонавтика" (Москва, 2011, 2012гг.), Международная студенческая олимпиада по автоматическому управлению "ВОАС" (Санкт-Петербург, 2011г.), Международная (43-я Всероссийская) молодежная школа-конференция «Современные проблемы математики», (Екатеринбург, 2012г.), молодежная школа "Информация, управление, оптимизация" (Ярополец, 2011г., Звенигород, 2012г.) а также на научном семинаре в МАИ.

Публикации. Основные результаты диссертации опубликованы в трех статьях [1-3] в журналах, входящих в Перечень ВАК, в научном журнале [4] и в трудах и тезисах международных научных конференций [5-12].

Структура и объем диссертации. Диссертация состоит из введения, пяти глав, заключения и списка литературы (99 источников). Объем диссертации включает 105 машинописных страниц, включая 2 рисунка, 1 таблицу.

СОДЕРЖАНИЕ РАБОТЫ Во введении обоснована актуальность исследуемой проблемы, сформулированы цель и задачи диссертации, описана структура работы, перечислены полученные в диссертации новые результаты.

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

Рассмотрим Ф{и, X) - функцию потерь, которую необходимо минимизировать. Вектор и размерности т имеет смысл управления, и € U С С R771, U - область допустимых управлений, а X - вектор случайных параметров размерности п.

Определим для Ф(м, X) функцию вероятности, VaR-критерий (функцию квантили) и CVaR-критерий (функцию интегральной квантили):

(i)

где (р - некоторый допустимый уровень потерь,

<ра{и) "=' [Ф(и, Х)]а =' min{v : Pv(u) 2 а}, (2)

фа{и) 'Ш {Ф(и, Х)}а -J_ [1 w(u)dj3. (3)

1 (У- Ja

VaR-критерий показывает, что потери при выбранной стратегии и с вероятностью не меньше а не превысят значения CVaR-критерий

- усредненное значение функции квантили на отрезке [а, 1}. Физический смысл данной функции есть усредненные потери на "хвосте" распределения.

В технических задачах VaR может характеризовать гарантированную с заданной вероятностью точность попадания объекта в заданную область. Тогда CVaR характеризует среднее значение точности за уровнем VaR.

Как видно из (3) VaR и CVaR связаны между собой через определение. Между ними также установлена другая связь.

Теорем а 1.1. [Кибзун А.И., Кузнецов Е.А.] Если для некоторого и £ U выполнено условие |тДа(и)| < оо, то функция фа{и) представима в виде

фа{и) = Лa(u)Va(u) + (1 - Ла(и))ф+(и), (4)

где

ф+(и)"^М[Ф(и,Х)\Ф(и,Х)>^)}- (5)

CVaR-критерий также можно представить как решение задачи оптимизации.

Теорема1.2. [Rockafellar R.T., Uryasev S.] Если для некоторого и € £ U выполнено условие М[Ф(и, X)] < оо, то функция представима в виде

фа (и) = min Fa (u, iр), (6)

где

Fa(u, <р) + —^—M[max{0, Ф(и, X) - у,}]. (7)

1 — а

В первой главе приведены основные свойства VaR и CVaR критериев, которые используются в работе. Рассматриваются задачи стохастического программирования с критерием в форме математического ожидания, VaR-критерием, CVaR-критерием. Данные постановки рассмотрены как в терминах потерь, так и в терминах точности (доходов).

Задача стохастического программирования с VaR-критерем

<Ра{и) min. (8)

Задачи с VaR-критерием возникают в случае, когда, необходимо найти такую стратегию и, которая бы минимизировала потери с заданной вероятностью а.

Задача стохастического программирования с CVaR-критерием

фа{и)min. (9)

usLT

Задачи с CVaR-критерием возникают в случае, когда необходимо минимизировать усредненные потери, наступающие в неблагоприятных случаях (вероятность наступления таких случаев 1 — а).

Во второй главе рассматриваются задачи с VaR и CVaR-критериями, найдены условия, при которых данные задачи эквиваленты. Установлена эквивалентность между формулировками задач в терминах точности (дохода) и терминах потерь, приведенными в первой главе работы.

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

= Arg minvpQ (ы), uft = arg min ipa(u), (10)

u€U ueu

для множества решений задачи оптимизации интегральной квантили

= Arg ттфа (и), = aigmmi[>a(u). (11)

ueU U€U

Множество решений задачи с критерием в виде математического ожидания обозначено как

UM = ArgminM№(u,A')], uM = argminM[<S(u, X)]. (12)

ибU neu

В работе Б.В. Вишнякова и А.И. Кибзуна получены детерминированные эквиваленты для задачи оптимизации VaR-критерия (10) для различных функций потерь. Во второй главе диссертации получены детерминированные эквиваленты задачи (11) для разных целевых функций.

Для различных видов целевых функций приведены условия, когда задачи с CVaR-критерием и VaR-критерием имеют общий детерминированный эквивалент.

Определение 2.1. Будем говорить, что решение одной из задач (10),(11),(12) частично эквивалентно решению другой задачи, если множество решений первой не пусто и оно является подмножеством решений второй.

О пр еде леи ч е 2.2. Будем говорить, что одна из задач (10), (11), (12) эквивалентна другой тогда, когда множества их решений совпадают.

1. Функция потерь, линейная относительно случайной величины. Лемма 2.5. Пусть Ф(и, X) = si(u) + S2(u)/i(X), где

/i(.t) : К" ->■ R — измеримая функция, M[/j(X)] < оо, Si(u) : Km —> R, S2(w) '■ Rm —> R+ — неотрицательная функция, def

U, = Argminsi(u) П Argmins2(w) ф 0.

ueU ueu

Тогда

(i) если M[/i(X)] > 0, то для всех а e (0,1) = UM = [/,;

(ii) если [/i(X)];3 > 0 для некоторого ß € (0,1), то для всех a е [ß, 1)

щ = и$ = и,.

2. Функция потерь со скалярной билинейной структурой. Билинейной функцией будем называть функцию вида Ф(гл, X) = иТХ.

В работе доказана следующая теорема. Теорем а 2.1. Пусть Ф(и, X) =

г(Я1(и) + в2(иШХ) + /а(Х)),

r(-) : R —> К — строго возрастающая непрерывная слева функция, sj(u) : Rm —>■ R, s2(w) : Km —> R+ — неотрицательная на U функция, fi(x) : R" —> R и f2(x) : Rn R — измеримые функции, fi(x) > 0 для всех x e Rm, М[Ф(и, X)] < оо для всех и е {/, dtf

Ut = Argminsi(it) П Argmins2(w) Ф (13)

u£jj uüU

Тогда для всех а 6 (0,1) задача (13) будет частично эквивалентна задачам (10), (11) и эквивалентна задаче (12).

3. Функция потерь обладает билинейной структурой при сферически симметричном распределении случайного вектора.

Будем говорить, что распределение случайного вектора X сферически симметрично, если его плотность можно представить в виде

Рх(х) <й /(||х|[2) = f{xTx), (14)

где функция f(t) определена для t 6 [0, оо) и является неотрицательной. В работе доказана следующая теорема об эквивалентности. Теор ем а 2.3. Пусть функция потерь имеет вид Ф(и, X) = г(иГАХ), где ||Аги|| > 0, а распределение X имеет вид (14), [Х\)р > 0 для некоторого ß € (0,1), причем М[Ф(и, X)] < оо для всех и е U. Тогда для всех а 6 [ß, 1) задачи (10), (И) эквивалентны, т.е.

US = U* = Uf Argmin||AT«||.

4- Функция потерь обладает билинейной структурой при симлгет-ричном распределении ыучайного вектора.

Определение 2.3. Будем говорить, что распределение п-мерного случайного вектора X = (А'], Х<1,..., ХП)Т симметрично, если его функция распределения Рх{х\,х2, • ••,£„) не изменяется при всех перестановках входящих в нее переменных 11,хг, ••■, х„.

В работе доказана следующая теорема об эквивалентности. Теорема 2.4. Пусть Ф(и, X) = — Х^^гцХ,-, X обладает симметричным распределением таким, что а-ядро является регулярным и [—АТ,-]а < О, М[АГ,-] = ц < оо для всех г = 1 ,тп, множество допустимых стратегий и — {и : и,- = 1, и; ^ О, I = 1, тп}. Тогда задачи (10), (11) частично эквивалентны задаче (12) и их решением является

< = < = (1 /тп,.... 1 /™)т,

Третья глава посвящена стохастическому квазиградиентному алгоритму (СКА) минимизации СУаЫ-критерия (11).

Для построения алгоритма используются выборочные оценки СУа11. Пусть для любого и е и есть возможность получить выборку {Ф(и, объёма щ функции Ф(и,Л'). Обозначим через {Ф(1)(и)}"^1

вариационный ряд выборки, т.е. расположенные в порядке возрастания порядковые статистики

Ф(1)(") < Ф(2)М < - <

На основе данного вариационного ряда сконструируем оценку

^ - гЬ £-а) фыМ+<15>

где

(1е/ Г апк, апк £ к _ \ [апк] + 1, апк £

Пусть ¿к > 0 — числовая последовательность 5к —> 0 при к —>■ ос. Назовем стохастическим квазиградиентом СУаГ1 случайный вектор

^ т

Ыи, ¿к) щ • ■ ■' • • '' йт)~Фк(й 1, ■ • • > щ-бк, • • •, йт)]е,-,

(16)

где й( имеют равномерные распределения на отрезках [щ — ¿к, «>+<У, г = 1,?п, и независимы. А л г о р и т м 1.

1) к = 0. Выбрать стартовую точку и'0' ~ 7?.(Г/). Выбрать е > 0, константу Ь таким образом, что почти наверное выполняется соотношение

2) Вычислим следующую точку последовательности

1 й«, \Ыи1к)Л)\\>ь,

где г1(к) имеет равномерное распределение на множестве II, и все й^ независимы, Ь > 0 — достаточно большое число, рк — длина шага алгоритма. Пц - оператор рандомизированного проецирования на область II1 на к-ом шаге, т.е. отображение П£> : Мт —>■ (Уь задаваемое соотношением

II* (и) ( ^ 6 и' (18)

где случайная величина и^ имеет равномерное распределение на шаре

зЛ1 {

as {щ 6 Щ :

и 1 — argmin||u —

veU

все u^ независимы.

3) Если не выполены условия остановки, то к = к + 1 и переходим к шагу 2.

В главе сформулирована теорема о сходимости данного алгоритма почти наверное при к —> оо.

Теорема 3.6. Пусть выполнены следующие условия:

(i) Функция Ф(и,х) является выпуклой по и на компакте U\ для всех х S К5;

(и) фа(и) имеет ограниченные непрерывные вторые производные для всех и б U\\

(iii) для каждого и G int(t/i) функция вероятности Р9(и) дважды дифференцируема по ip и эти производные ограничены, j~Plf{v) > 0 для всех ip € Vc(u) для каждого и 6 Е^;

(iv) для всех и € int(i/i) функция квантили <рр{и) непрерывна по в Е 6 [а, 1) и ММи)) = - Л ПРИ $

(у) последовательность удовлетворяет условиям

оо со

Рк> о, = °°<

1 1

(VI) последовательности и щ удовлетворяют условиям

ОО 00 ^ оо ^ оо

У^Йсоо, У^ —— < оо, —< с», V Рк- < оо; существует 7 > 1, удовлетворяющее условию

Т > рда}-такое' что

М[[Ф(и, Х)Р] < оо для всех и е С/и

(лгн!) шее {(и, х) € 1/1 х К" : Ф(и, х) — ¡р) = 0 для всех <р 6 К.

Тогда «№) и0, где последовательность и* образована алгоритмом (17), а иа - решение задачи (11).

Примерами последовательностей, удовлетворяющих условиям (у]-(уг) теоремы, являются, например, последовательности

РО г г , 2+3-1

К &2+£:

В четвертой главе рассмотрена задача с Уа11-критерием и ограничением на СУаН. Данная постановка модифицирует известную задачу Марковица: необходимо найти стратегии, дающие максимальный доход, гарантированный с заданной вероятностью а £ (0,1), при этом доход в среднем в 1 — а неблагоприятных случаях должен быть не меньше наперед заданного значения С.

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

иа = а^тт<^а(и) (19)

иес/

при условии

Ми) < С. (20)

Такая постановка, в отличие от обычной задачи квантилыюй оптимизации, учитывает возможный эффект в неблагоприятных случаях (вероятность которых 1 — а), когда ограничение (20) активно.

Рассмотрен пример для скалярного билинейного случая, где удается построить аналитическое решение. Приводится сравнение данного решения с решением задачи (10). Однако поиск аналитических решений в многомерном случае представляется затруднительным, поскольку не удается получить явный вид ограничения (20).

В работе предложен алгоритм приближенного решения задачи (19)-(20) для кусочно-линейной функции потерь.

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

def

N = N(a) =J [1/(1 — а)]. Рассмотрим выборку Xik объема К А', где Ч = {к — i)N, (к — 1 )N + 1,..., kN, к — 1, К. Данная выборка состоит из К подвыборок, каждая из которых имеет объем N. Сформируем К экстремальных порядковых статистик и К предпоследних порядковых статистик

Флдь(и)= тах Ф(и,Х{к), k=ÏJC. (21)

i),fc(u) = тах ФК^), к=1,К. (22)

В качестве оценки VaR-критерия используется

ФаМ =f ^ Е *А'Л(«) + £ Е

it=l it=l

(23)

где /1» 0,5772 - константа Эйлера. Введем обозначение для множества

где Рп(и, ф) - выборочная оценка функции Р„(и, </?), определенной в (7).

^ КИ

Ра{и, <р)=<р + {1_а)км Е [тах(°' ф(и' *«) - V)]. (24)

где Х1, I — 1, КМ, — это элементы выборки {Хь Х>,..., Хкы}-Алгоритм 2.

1) к = 0. Решается задача (19) без учета ограничения (20) любым известным методом. Например, можно (19) заменить оценкой (23) и использовать стандартные методы выпуклой оптимизации, поскольку если функция потерь кусочно-линейная, то (23) является выпуклой кусочно-линейной функцией, которую можно записать в явном виде.

Если найденное решение и* удовлетворяет ограничению (20), то счет окончен. Иначе решение исходной задачи находится на границе множества ограничений и в (20) должно выполняться равенство. Полагаем w(u) = |ра(и*) и переходим к шагу 2.

2) Решается задача линейного программирования

фа(ут) = min t, (25)

teK^üstt^xR^nK

решение которой зависит ог параметра v^ 6 R1.

Ut, {и 6 U : фа{и) sS i/*>}

является выпуклым многогранным множеством, так как функция фа{и) кусочно-линейна и имеет явное выражение. Так как UV2QUxll при г»2 < i>i, то функция фа{у) монотонно возрастает по у. Кроме того, по свойствам задач линейного программирования решение, в данном случае фа(у), непрерывно зависит от начального параметра v. Переходим к шагу 3.

3) Если выполнены условия остановки алгоритма или условие

Фа(У(к)) = С, (26)

где константа С взята из ограничения (20) модифицированной задачи Марковица, то переходим к шагу 4.

Иначе к = к + 1. Так как функция фа(у) является монотонной и непрерывной по параметру v, то корень v, уравнения (26) можно найти, например, методом дихотомии. Выбираем следующую точку wC=+i) методом дихотомии и переходим к шагу 2.

4) В качестве приближенного решения модифицированной задачи Марковича выбираются üa(v,) и <ßa(vt), которые являются решениями задачи (25) для параметра у,. Если уравнение (26) не имеет решения, то в качестве приближенного решения модифицированной задачи Марковича принимается задача

üa = arg min v

которая также является задачей линейного программирования.

В четвертой главе также предложен алгоритм решения задачи для (19)-(20) в случае, когда функция потерь имеет билинейный вид

п

Ф(и, X) = -Ьщ - Хтй — —Ьщ -

¡=1

а X имеет многомерное нормальное распределение X = со1(Х(1),...,Х(п)) ~ ЛГ(тп,К), где m = col{ти ...,тп„) - вектор

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

АлгоритиЗ.

1) Вычислим 7 л/(т — Ъе)ТК~1(т — бе), где е = со1(1,1,..., 1) -вектор, составленный из единиц соответствующей размерности. Если 7а ^ 7, то задача имеет тривиальное решение иао = 1, иа = со1(0,0, ...,0).

2) Если 7а < 7, то зафиксируем средний доход, т.е (и) = V, и добавим это ограничение в (19)-(20). Получим задачу

= argmin(7acr$(u) — v) (27)

usU

при условии

^/7^/3 -^С, (28)

а

РФ (и) = V. (29)

3) Можно воспользоваться аналитическим способом нахождения и«, при котором в ограничении (28) будет выполняться равенство

1 г 1 u,=b J fßdß 7 + У 7/

"ifldß

-1

Таким образом, разрешено ограничение (28).

В случае, если решение находится не на границе ф0(и) = С, то модифицированная задача Марковица эквивалентна задаче максимизации VaR-критерия без ограничений.

4) Решение задачи (27)-(29) будет совпадать с решением следующей задачи квадратичного программирования.

ua(v,) = arg min (йТКй) (30)

при условии

цф (и) = v„ (31)

Данная задача может быть легко решена одним из методов квадратичного программирования. Минимум в (30) обусловлен тем, что 7а > 0. Следовательно, минимизируя йтКй, будем максимизировать VaR-критерий.

В пятой главе рассматриваются две задачи из авиационной отрасли.

Первой задачей является оптимизация площади взлётно-посадочной полосы (ВПП), необходимой для гарантированной посадки самолета.

В работе Ю.С. Кана показано, что задачу оптимизации ВПП можно свести к задаче с Va.R-критерием:

1,1*2)-* min, (32)

Ul,U2>0

где (ра(щ,и2) — функция квантили уровня а для функции потерь Ф(й1, и2, X, Z). Значением <ра(и 1,^2) является корнень из минимальной площади ВПП, которая гарантирует посадку самолета с вероятность а.

Ф(иии2,Х,г)^ тах{Ф1(щ,иьХ),Ф(и1:и2,Х),Ф3(и2,г)}, (33) Ф + + (34)

V«2

Ф2(«ь «2, X) Ы + Ф3(„2, Z) t/ 2\Z\Vui. (35)

V«2

X = auWx + a12\Wz\, Z = aaW» (36)

где о.п,в12,0-22, /о ~~ известные коэффициенты. Такая модель влияния ветра используется в случае, когда посадка JIA управляется лишь путем изменения угла крена. Предположим, что Wx, Wz — независимые нормально распределенные случайные величины с параметрами

M[WX] = тх, M[WJ = mtID[Wy = а2х, D[WJ = ff*.

Для решения данной задачи используется CVaR как оценка сверху для VaR-критерия.

ipa(ui,u2) ->■ min , (37)

где 4>c,{u\, и2) — CVaR-критерий уровня а для Ф(г*1, и2, X, Z).

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

К сожалению, Ф(ы1, и2, X, Z) не является выпуклой функцией по переменным щ,и2, поэтому проверить выпуклость функции фа(и1,и2) представляется затруднительным.

Вычисления были проведены для следующих значений параметров: тх — тг = 0, ах — crz = 5, ац = aj2 = —20, <122 = 3, Iq — 1500.

Результаты решения для разных уровней а приведены в таблице ниже. Первая строчка - это решения задачи (32), они взяты из работы E.JI. Матвеева, вторая строчка - это решения задачи (37) СКА, предложенным в третьей главе диссертации.

а Метод Ul U2 Площадь, км

0.99 VaR 1,9189 27,014 0,173

CVaR 1,9210 27,108 0,189

0.999 VaR 1,424 22,043 0,2348

CVaR 1,426 22,142 0,2461

Как видно из таблицы, оценка CVaR-критерия оказывается между VaR-оценкой и аналитической оценкой. Таким образом, CVaR-критерий можно применять как верхнюю оценку для данной задачи.

Второй пример относится к области инвестирования в высокорисковые активы авиационной промышленности.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ, ВЫНОСИМЫЕ НА ЗАЩИТУ

1) Получены детерминированные эквиваленты для задач с CVaR-критерием [3, 10].

2) Найдено аналитическое решение для задач с VaR и CVaR критериями для билинейной целевой функции при симметричном распределении случайной величины [9].

3) Найдены условия, при которых задачи с критериями VaR и CVaR эквиваленты для разных классов функции потерь [3, 11].

4) Разработан стохастический квазиградиентный алгоритм минимизации CVaR-критерия, сходящийся почти наверное [2, 6, 8, 12].

5) Предложен вычислительный алгоритм решения задачи с VaR-критерием и ограничением на CVaR для кусочно-линейной функции потерь и для билинейной функции потерь при многомерном нормальном распределении случайного вектора [1,5].

6) Решены две задачи из авиационной области. Задача оптимизации распределения инвестиций в развитие отраслей наземно-космического комплекса [4] и задача оптимизации площади взлетно-посадочной полосы [6, 7].

Публикации в журналах из перечня ВАК

1) Кибзун А.И., Чернобровое А.И. Алгоритм решения обобщенной задачи Марковица // Автоматика и Телемеханика, 2011, № 2, С. 41-60.

2) Кибзун А.И., Чернобровое Л.И. Стохастический квазиградиентпый алгоритм минимизации функции интегральной квантили // Автоматика

и Телемеханика, 2012, № 2, С. 77 — 92.

3) Кибзун А.И., Чернобровое А.И. Эквивалентность задач с критериями в форме квантили и интегральной квантили // Автоматика и Телемеханика, 2013, А1-2 2, (в печати).

Публикации в других изданиях

4) Кибзун А. И., Чернобровое А.И. Задача оптимизации производства для наземных космических комплексов с критериями в форме квантили и интегральной квантили // Труды МАИ, 2012, №52.

5) Кибзун А.И., Чернобровое А.И. Алгоритмы решения задач стохастического программирования с критериями VaR и CVaR // XIV-я Всероссийская конференция «Математическое программирование и приложения», Екатеринбург, 2011, С. 254 — 256.

6) Кибзун А.И., Чернобровое А.И. Применение стохастического квазиградиентного алгоритма минимизации интегральной квантили для оценки сверху квантилыюго критерия // 10-я Международная конференция «Авиация и космонавтика - 2011», Москва, С. 285 — 286.

7) Кибзун А.И., Чернобровое А.И. Оптимизация площади взлетно-посадочной полосы с помощью CVaR-критерия // 11-я Международная конференция «Авиация и космонавтика - 2012», Москва, С. 399 — 400.

8) Чернобровое А.И. Доказательство сходимости алгоритма минимизации функции интегральной квантили с вероятностью единица. //16-я международная научная конференция «Системный анализ, управление и навигация», 2011, С. 134 - 135.

9) Чернобровое А.И. Об эквивалентности задач с критериями в форме квантили и интегральной квантили с билинейной целевой функцией // Сборник тезисов докладов «Инновации в авиации и космонавтике -2012», 2012, С. 259.

10) Чернобровое А.И. Об эквивалентности некоторого класса задач с критериями в форме квантили и интегральной квантили // Научные труды Международной молодежной научной конференции «XXXVIII Гагаринские чтения». М: МАТИ, 2012, Т. 5., С. 129 - 130.

11) Чернобровое А.И. Параллельный и рекуррентный способ решения семейства задач минимизации CVaR-критерия // Тезисы Международной (43-й Всероссийской) молодежной школы-конференции «Современные проблемы математики», 2012, С. 299 - 301.

12) Chernobrovov A.I. Optimization of the CVaR by a Stochastic Quasigradient Algorithm // 14th International Student Olympiad on Automatic Control, Russia, 21-23 September, 2011. P. 100 - 104.

Подписано в печать 16 ноября 2012 г. Объем 1 п.л. Тираж 90 экз. Отпечатано с готовых оригинал-макетов. Типография «11-й ФОРМАТ», 115230, Москва, Варшавское ш., 36.

Введение

1 Задачи стохастической оптимизации

1.1. Введение

1.2. Основные понятия и определения.

1.3. Свойства УаЯ и СУаИ.

1.4. Постановки задач стохастической оптимизации в терминах потерь

1.4.1. Задача с критерием в форме математического ожидания

1.4.2. Задача с УаЯ-критерием.

1.4.3. Задача с СУаЯ-критерием.

1.5. Постановки задач стохастической оптимизации в терминах дохода . 24 1.5.1. Задача Марковица.

2 Сравнение постановок с критериями в форме УаГ1 и С\^аК

2.1. Введение

2.2. Связь критериев УаЯ и СУаИ в терминах дохода и потерь.

2.3. Эквивалентность задач с критериями УаЯ и СУаИ,.

2.3.1. Функция потерь, линейная относительно случайной величины

2.3.2. Функция потерь со скалярной билинейной структурой

2.3.3. Функция потерь с билинейной структурой.

3 Стохастический квазиградиентный алгоритм решения задач с СУаК-критерием

3.1. Введение

3.2. Постановка задачи минимизации СУаИ,-критерия.

3.3. Вспомогательные утверждения.

3.4. Стохастический квазиградиентный алгоритм минимизации СУаЫ-критерия

3.5. Практические особенности реализации стохастического квазиградиентного алгоритма минимизации СУаР1-критерия.

3.6. Примеры

4 Комбинированная задача с критериями УаЛ и СУаИ

4.1. Введение

4.2. Задача с УаЯ-критерием и ограничением на СУаИ,.

4.3. Алгоритм решения модифицированной задачи Марковица.

4.3.1. Кусочно-линейная функция потерь.<

4.3.2. Билинейная функция потерь.

4.3.3. Случай скалярной билинейной функции дохода.

4.3.4. Случай многомерной билинейной функции дохода.

5 Примеры

5.1. Задача оптимизации площади взлетно-посадочной полосы (ВПП)

5.1.1. Постановка задачи.

5.1.2. Эквивалентная задача квантильной оптимизации.

5.1.3. Обзор существующих методов решения задачи оптимизации площади ВПП.

5.1.4. Использование СУаЫ-критерия, как верхней оценки УаИ-критерия.

5.2. Задача оптимизации инвестиционных вложений в наземно-космический комплекс.

5.2.1. Постановка задачи.

5.2.2. Решение задачи с помощью стохастического квазиградиентного алгоритма.

Объектом исследования в диссертационной работе являются задачи стохастического программирования с критерием в форме интегральной квантили. В англоязычной литературе принято использовать обозначение Conditional-Value-at-Risk (что можно перевести как "условное значение на уровне риска"), или сокращенно CVaR-критерий. CVaR также называют Average-Value-at-Risk (AVaR) [76,95], expected shortfall [64,84], Tail Value-at-Risk (TVaR) [74], tail conditional expectation (TCE) [67] и др. Рассмотрение данных задач ведется в тесной связи с рассмотрением задач с критерием в форме квантили. Функцию квантили часто (особенно в англоязычной литературе) [67,74,93-95] называют Value-at-Risk (что можно перевести как "значение на уровне риска" или "плата за риск"), или сокращенно VaR-критерием. Исследуются как свойства явного вида (аналитической формы) CVaR-критерия, так и численные оценки.

В экономике, биологии и технике часто приходится иметь дело с математическими моделями, где часть исходных данных является случайными факторами. Такие модели удобно описывать с помощью задач стохастического программирования [12,35,52,54,61,62,72,82,83,88,90]. Модели, описанные с помощью случайных факторов, как правило, более адекватно описывают реальные явления и процессы, чем детерминированные. Поэтому результаты, полученные на основе этих моделей, являются более практически значимыми, чем для детерминированных моделей.

Поскольку задачи стохастического программирования, построенные для реальных моделей, бывают крайне сложны [20], на практике часто строятся более простые модели. Так, первые оптимизационные задачи по стохастическому программированию были построены на основе задач линейного программирования, где коэффициенты целевой функции или элементы матрицы ограничений были не детерминированы, а случайны [77]. В плане приложения, данные модели можно использовать, например, в задаче планирования перевозок [77], при планировании добычи угля [62], в различных транспортных задачах в стохастической постановке [61], где спрос в пунктах потребления принимается случайной величиной, и многих других.

Наиболее распространенными на практике являются задачи, описанные в терминах нелинейного стохастического программирования. К этому классу принадлежат экономические задачи в области распределения инвестиций при управлении капиталом компании [8,21,45,87,95,97], организационно-технические задачи планирования добычи, обработки и хранения нефти [62], прогнозирование скорости ветра [83], задачи оптимизации деятельности железнодорожного узла [24] и многие другие прикладные задачи. В авиационной сфере аппарат стохастического программирования применяется при синтезе и анализе алгоритмов управления летательными аппаратами, управляемыми ракетами различных классов, при оптимизации деятельности наземных космических комплексов. Исследованиям в этой области посвящены, например, работы [2,13,34,36,60].

Задачи стохастического управления рассматриваются, например, в работах [1,3,4,10,18,36,39,46]. Также нельзя не упомянуть, что стохастические модели используются и в других областях, например в задачах, связанных с устойчивостью [44,49], оцениванием [11,37] и других [33].

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

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

Наряду с классическими примерами типа "Санкт-Петербургского парадокса", который иллюстрирует расхождение математического ожидания выигрыша с его реальным эффектом, можно привести пример из современной теории инвестирования. На финансовые показатели, наряду со стратегией поведения на рынке ценных бумаг, влияют также факторы, не контролируемые лицом, принимающим решение. Эти факторы можно рассматривать как случайные величины с известным распределением или с распределением из некоторого оговоренного класса. В этом случае финансовые показатели операции также являются случайными величинами. Для их сравнения, а также для выбора оптимальной стратегии поведения, применяются различные статистические характеристики этих показателей [48,95]. Например, в классической постановке Марковица [87] средний доход фиксируется, и минимизируется дисперсия дохода как мера риска получить доход, отличный от среднего. Во многих случаях такая постановка не оправдана, так как слабо учитывает субъективные желания игрока. Более того, при тяжелых "хвостах" распределения постановка Марковица может быть и вовсе лишена смысла. В частности, такой случай возникает, когда доходность имеет распределение Коши. Если в качестве критерия выбрать максимизацию среднего дохода, возникает эффект, называемый эффектом "биржевого парадокса" [96]. Данный эффект заключается в том, что ожидаемый доход лица, принимающего решения, может стремиться к бесконечности, но вероятность разориться при этом стремится к единице. Квантильная постановка задачи (или постановка с УаК-критерием) [8] заключается в поиске стратегии, которая гарантирует максимальный доход с заданной вероятностью. Такая постановка гораздо лучше учитывает интересы инвестора, чем описанные выше.

В качестве критики УаЫ-критерия можно привести следующий пример. Можно получить стратегию, которая с заданной вероятностью гарантирует доход в 1 рубль, но при этом во всех остальных случаях сулит миллионные убытки. Такую стратегию можно легко получить с помощью УаИ-критерия, поскольку он не учитывает все неблагоприятные случаи за уровнем заданной вероятности (на "хвосте" распределения). В частности, чтобы избежать получения таких стратегий, был предложен СУаЯ-критерий (интегральная квантиль), который характеризует усредненное значение в неблагоприятных случаях [64,66,93,94].

Хотя УаИ-критерий хорошо изучен [6,16, 20, 22, 35, 53] и имеет тесную связь с СУаЯ (как будет показано позже), первые работы по СУаИ-критерию были сделаны в самом конце XX-века [89, 93, 98]. Они тесно связаны с понятием когерентной меры риска [67]. Когерентной мерой риска является мера риска р(-) '■ О —> К, для любых случайных величин X и У из Г2, обладающая следующими свойствами:

1) р(Х + £) = р{Х) + £ верно для любого Ь е К (инвариантность);

2) р(Х + У) ^ р{Х) + р(У) (субаддитивность);

3) Если X ^ У то р(Х) ^ р(У) (монотонность);

4) р^Х) = Ьр{Х) верно для любой константы t > 0 (положительная однородность).

В работе [67] показано, что УаИ. не является когерентной мерой риска, так как не выполняется свойство субаддитивности. А в работах [65, 89, 93, 94] показано, что СУа11 является когерентной, а следовательно выпуклой мерой риска. Во многом благодаря исследованиям в области когерентных и выпуклых мер риска СУаЛ-критерию стало уделяться значительное внимание [71,80,81]. В работе [94] показано, что если целевая функция является выпуклой на некотором множестве, то и СУаЯ-критерий также является выпуклой функцией на этом множестве. Благодаря этому свойству можно проверять выпуклость СУа11, не получая его аналитический вид. Для УаЯ-критерия проверка выпуклости часто является затруднительной задачей [20]. Не сложно построить примеры, где СУаЯ является выпуклой функцией, а УаИ, - нет.

Как упоминалось ранее, СУаИ, разные авторы называют по-разному - это в основном связано с тем, что определения для СУаЫ вводились по-разному. СУаЯ уровня а для случайной величины X можно определить, как минимум, тремя эквивалентными способами: x\pdfi, (1)

1 ~ а Ja е/ где [Х]р - УаЫ (квантиль) уровня /3, т.е. [Х]р = тт{<^ : Т{ X ^ ^ /3},

2)

Х}а =' Ла[Х]а + (1 - Аа)М№ > рщ (3) а= тга ек р +-М[тах{0, X - </?}]

1 - а где Ла й= а Рх(х) - функция распределения случайной величины X.

Эквивалентность этих определений доказана в работах [21,64,89,93].

У СУаЯ есть также и ряд недостатков. СУаЯ нельзя определить для случайных величин с "тяжелыми" хвостами, что является существенным недостатком по сравнению с УаИ. На практике задачи часто формулируются в виде требований по надежности (ограничение на вероятности). Такие задачи можно свести к задаче с УаИ, критерием, но не с СУаЫ. Помимо этого СУа11 и УаЯ критерии обладают тесной связью между собой. В (1) и (3) они связаны непосредственно через определение, причем разными способами. Как видно из определений, УаИ. всегда не превосходит СУаЯ, поэтому СУа11 можно использовать как оценку сверху для УаЯ. Также видно, что при больших значениях уровня вероятности значения критериев СУаЯ и УаИ, близки друг к другу.

Решения задач на основе УаЯ и СУаИ,, как правило, получаются различными, в силу разной природы данных критериев. Однако часто есть информация о решении задачи с помощью УаЯ-критерия, например, полученная методом детерминированного эквивалента [6], поэтому актуальна проблема поиска условий, при которых множества решений данных задач пересекаются или совпадают.

В [94] был предложен алгоритм, который сводил задачу минимизации СУа11-критерия для билинейной целевой функции к задаче линейного программирования большой размерности. Современная вычислительная техника позволяет достаточно быстро решать подобные задачи. Однако существенным недостатком данного алгоритма является то, что его сходимость можно доказать только при условии, что случайные величины имеют дискретные распределения. Если же считать, что случайные величины имеют непрерывные распределения, то сходимость данного алгоритма доказать затруднительно. Поэтому возникает необходимость построения алгоритмов, для которых можно доказать сходимость.

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

СКА использовался и для решения задач УаК-оптимизации [14,15,22,32]. В работе [22] использовались выборочные оценки для построения данного алгоритма. К недостаткам данного алгоритма можно отнести скорость сходимости. Она не превышает 1 /у/к, где к является номером шага итерационного алгоритма. Это свойственно всем алгоритмам, построенным по схеме стохастической аппроксимации [92]. В работе [51] был предложен новый способ стохастической аппроксимации, а в работах [41, 42] обобщен и развит данный метод. Однако, как отмечено в [38], применение данных методов затруднительно для задачи квантильной оптимизации с выборочными оценками.

В ряде работ применялся СКА для оптимизации задач с СУаЫ-критерием. В [68] был предложен алгоритм вычисления СУаИ, использующий стохастический квазиградиент и метод Монте-Карло для вычисления оценок. Была доказана слабая сходимость данного алгоритма при выполнении ряда труднопроверяемых условий. В [69] данный алгоритм был усилен и применен для совместного вычисления Уа11 и СУаЯ, для улучшения сходимости оценок использовалась выборка по значимости.

В [89] были предложены, а в [73,95] исследованы свойства выборочных оценок СУаЯ-критерия. Поэтому представляет интерес построение СКА для СУаЯ на основе выборочных оценок.

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

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

Для достижения поставленной цели предполагается решить следующие задачи:

1) построение детерминированных эквивалентов для задач с СУаИ-критерием;

2) описание условий эквивалентности задач с критериями УаЯ и СУаИ;

3) разработка стохастического квазиградиентного алгоритма минимизации СУаБ,критерия;

4) разработка алгоритма для решения комбинированной задачи с УаЛ-критерием и ограничением на СУаЯ.

Основные результаты диссертации опубликованы в трех статьях [25-27] в журналах, входящих в Перечень ВАК, а также в научном журнале [28], в трудах и тезисах международных научных конференций [24, 29-31, 56-59, 75]. Кроме того, данные результаты были апробированы на научных семинарах Московского авиационного института на кафедре "Теория вероятностей", на Ш-ей и 1У-ой традиционной молодежной школе "Информация, управление, оптимизация", на 14-ой международной студенческой олимпиаде по автоматическому управлению (Балтийской олимпиаде - ВОАС'2011), и на международной конференции "Авиация и космонавтика" в 2011 и 2012 годах.

Работа выполнена при поддержке государственного финансирования целевых программ «Научные и научно-педагогические кадры инновационной России» (Мероприятие 1.2.2, Госконтракт № 14.740.11.1128).

Диссертация состоит из пяти глав, заключения и списка литературы (99 источников).

Объем диссертации включает 105 машинописных страниц, включая 2 рисунка, 1 таблицу.

Краткое содержание основных результатов работы по главам состоит в следующем.

В первой главе приводятся основные понятия и определения, относящиеся к стохастическому программированию, а также к математическому и выпуклому анализу. Приведены основные свойства квантили и интегральной квантили, которые используются в работе. Рассматривается целевая функция Ф(и, X) -функция потерь, которую необходимо минимизировать. Вектор и размерности т имеет смысл управления, и € [/ С К", а X - вектор случайных параметров размерности п.

Для функции Ф(и,Х) определены функция вероятности, УаЯ и СУаЯ: ад ^7>{ф(и> (4) где ip - некоторый допустимый уровень потерь, ра{и) =f [Ф(и, Х)]а =f min{(^ : Pv(u) ^ а}, (5) фа(и) ^ {Ф(и, X)}Q f1 <pp{u)dß. (6)

Je

Также рассматриваются различные задачи стохастического программирования с критерием в форме математического ожидания, VaR-критерием, CVaR-критерием. Данные постановки рассмотрены как в терминах доходов, так и в терминах потерь.

Задача стохастического программирования с использованием VaR-критерия примет вид ipa(u) —> min. (7) ее/

Задачи с VaR-критерием возникают в случае, когда необходимо найти такую стратегию и, которая бы минимизировала потери с заданной вероятностью а.

Задача стохастического программирования с CVaR-критерием фа(и) —» min. (8) u&U

Задачи с CVaR-критерием возникают в случае, когда необходимо минимизировать усредненные потери, наступающие в неблагоприятных случаях (вероятность наступления таких случаев 1 — а).

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

Получены детерминированные эквиваленты для CVaR-критерия для различных видов функции потерь. Детерминированные эквиваленты - это детерминированные (не зависящие от случайных величин) задачи математического программирования, множество решений которых является подмножеством решений соответствующих задач стохастического программирования с вероятностными критериями. Получение детерминированных эквивалентов значительно упрощает решение вероятностных задач, поскольку для решения детерминированных задач, эквивалентных исходным стохастическим, можно использовать стандартные методы математического программирования [47,50]. Также для этих видов целевых функций приведены условия, когда задачи с CVaR-критерием и VaR-критерием имеют общий детерминированный эквивалент.

Функции потерь Ф(гх, X), которые были рассмотрены:

1. Функция потерь, линейная относительно случайной величины b(u,X) = sl(u) + s2(u)f1(X), где fi(x) : Мп —> R — некоторая измеримая функция, si(u) : Еш М, s2(u) : К7" —> неотрицательная функция.

2. Функция потерь со скалярной билинейной структурой

Ф(и, X) = r(si(u) + s2(u)h(X) + f2(X)), r(-) : М —v М — строго возрастающая непрерывная слева функция, Si(u) : Rm —> R — некоторая функция, S2(u) : IR"1 —> М+ — неотрицательная на U функция, Д(х) : Г ч Е и f2{x) : Мп Ш — измеримые функции, /г(х) > 0 для всех х £ Ет, М[Ф(и, X)] < оо для всех и £ U.

3. Функция потерь с билинейной структурой при сферически симметричной плотности и при симметричной функции распределения

Ф (и,Х) = г(ит(АХ)), (9) где А - некоторая матрица m х n, r(í) : R1 —>• К1 - строго возрастающая по t, непрерывная слева функция, определенная на всей числовой оси. А распределение случайного вектора X сферически симметрично, то есть его плотность можно представить в виде

Рх(®) ='/(\\х\\2) = 1(хтх), где функция /(¿) определена для £ € [0, сю), неотрицательна и интегрируема по Лебегу. Или же распределение вектора X - симметрично, то есть его функция распределения Рх{х\, Х2,., хп) не изменяется при всех перестановках входящих в нее переменных х\, Х2,., хп.

Третья глава посвящена задаче минимизации СУаЫ-критерия. Предложен стохастический квазиградиентный алгоритм минимизации функции СУаП-критерия.

Для построения алгоритма используются выборочные оценки СУаИ.

1 / / \ 1 Пк где йе/ ) апк, апк £ М+, и = апк} + 1, ап^М*, - ^'-ый элемент вариационного ряда функции Ф(и, X), пк - объем выборки. Стохастический квазиградиент СУаЯ - это случайный вектор

1 т ~ ^ Ь(и,6к) = — ^[фк(щ,.,иг + 5к,.,йт) - фк(щ,.7иг-5к,.,йт)]ег, (11) к г=1 где йг имеют равномерные распределения на отрезках [иг — 5к, иг + г = 1, т, и независимы.

В главе доказаны некоторые свойства выборочной оценки СУаИ и стохастического квазиградиента СУаЯ.

Рассмотрен стохастический квазиградиентный алгоритм минимизации функции интегральной квантили. и№+1) I п* , й, \Ыи{к))\\>Ь, где Ь — некоторое достаточно большое число, рк — длина шага алгоритма, ПМ-] оператор рандомизированного проецирования, а й имеет равномерное распределение на множестве С/.

Пу - оператор рандомизированного проецирования на область 11\ на /с-ом шаге, т.е. отображение Пу : —» задаваемое соотношением еГ и,иеи,

ПЬЫ) = (13) и(к\и<?и, где случайная величина и^ имеет равномерное распределение на шаре

В£ ^ е С/1 : щ — ащтт \ \и — ь\ уеи £ все и^ независимы.

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

В четвертой главе рассмотрена задача с УаЫ-критерием и ограничением на СУаЫ, обобщающая в некотором смысле известную постановку Марковица [87].

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

Благодаря утверждениям из главы 2, данную задачу можно сформулировать в терминах потерь в следующем виде иа = а^гшп 1ра(и) (14) при условии

Фа(и) ^ С. (15)

Такая постановка, в отличие от обычной задачи квантильной оптимизации, учитывает возможный эффект в неблагоприятных случаях (вероятность которых 1 — а), когда ограничение (15) активно. Но добавление такого ограничения делает задачу достаточно сложной для поиска аналитических решений.

В работе предложен алгоритм приближенного решения данной задачи для кусочно-линейной Ф(и, X) = шах(а^-и. + Ь^Х + с,) и билинейной функций потерь, который сводит исходную задачу к последовательности задач линейного программирования. Найдено аналитическое решение в случае скалярной билинейной функции потерь при равномерном распределении доходности, проводится его анализ и сравнение решения с другими постановками задач. Рассмотрен численный алгоритм решения задачи для случая многомерной билинейной функции потерь при нормальном распределении доходностей.

В пятой главе рассматриваются два примера из авиационной отрасли.

Первым примером является оптимизация площади взлётно-посадочной полосы, необходимой для гарантированной посадки самолета. Для решения данной задачи используется СУаЫ как оценка сверху для УаК-критерия. Задача решается с помощью стохастического квазиградиентного алгоритма, рассмотренного в третьей главе данной работы. Полученный результат сравнивается с уже известными решениями данной задачи. Второй пример относится к области инвестирования в высокорисковые активы авиационной промышленности.

Основные результаты, выносимые на защиту:

1. Получены детерминированные эквиваленты для задач с СУаЛ-критерием.

2. Найдено аналитическое решение для задач с УаР1 и СУаИ, критериями для билинейной целевой функции при симметричном распределении случайного вектора.

3. Найдены условия, при которых задачи с критериями УаЫ и СУаЫ эквиваленты для разных классов функции потерь.

4. Разработан стохастический квазиградиентный алгоритм минимизации СУаЯ-критерия, сходящийся почти наверное.

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

6. Решены две задачи из авиационной области. Задача оптимизации распределения инвестиций в развитие отраслей наземно-космического комплекса и задача оптимизации площади взлетно-посадочной полосы.

Заключение

В диссертации исследуются задачи оптимизации систем с СУаИ-критерием, основанные на Уа11-критерии. В первой главе приведены известные свойства СУаЛ и УаИ-критериев, основные постановки задач. Во второй главе построены детерминированные эквиваленты для задач с СУаИ-критерием для разных видов целевых функций. Проведено сравнение постановок задач с СУаЯ и УаЫ-критериями, найдены условия, при которых они являются эквивалентными. В третьей главе предложен стохастический квазиградиентный алгоритм (СКА) минимизации СУаЯ-критерия на основе выборочных оценок. В четвертой главе сформулирована новая задача с УаЯ-критерием и ограничением на СУаЯ. Предложен вычислительный алгоритм решения задачи для кусочно-линейного случая и для билинейного многомерного случая при нормальном распределении случайного вектора. В последней главе рассмотрены примеры из авиационной сферы. Рассмотрена задача об инвестировании в наземно-космический косплекс с СУаИ-критерием, использован СКА для ее решения. Рассмотрена возможность применения СУаЯ, как верхней оценки для УаИ-критерия, на примере задачи оптимизации площади взлётно-посадочной полосы. Приведены результаты сравнения с уже известными задачами.

Основным итогом диссертации является построение СКА минимизации СУаИ-критерия, основанного на выборочных оценках.

1. Ананьев Б. И. Оптимальные каналы связи с шумом в задачах оценивания и коррекции движения // Труды Ин-та математики и механики УрО РАН. Т. 16, № 1. 2010. С. 15-29.

2. Бахшиян Б.Ц., Назиров H.H., Эльясберг П.Е. Определение и коррекция движения. М.: Наука, 1980.

3. Беллман Р. Динамическое программирование. М.: Ин.Лит., 1960.

4. Брайсон А., Хо Ю-Ши Прикладная теория оптимального управления. М.: Мир, 1972.

5. Величко A.C., Нурминский Е.А. Прямо-двойственная декомпозиция задачи о репликации портфеля рыночных активов // Автоматика и Телемеханика, 2004, № 2, С. 170 178.

6. Вишняков Б.В., Кибзун А.И. Детерминированные эквиваленты для задач стохастического программирования с вероятностными критериями // Автоматика и Телемеханика, 2006, Я2 6, С. 126 143.

7. Галамбош Я. Асимптотическая теория экстремальных порядковых статистик. М.: Наука, 1984.

8. Григорьев П.В., Кан Ю.С. Оптимальное управление по квантильному критерию портфелем ценных бумаг // Автоматика и Телемеханика, 2004, № 2, С. 179 197.

9. Дзотцоев А. А., Кан Ю. С., Шахлевич П. К. Оптимизации площади взлётно-посадочной полосы //Изв. РАН, Теория и системы управления, 2007, № 6, С. 44 49.

10. Домбровский В. В. Синтез оптимальных динамических регуляторов пониженного порядка для нестационарных линейных дискретных стохастических систем // Автоматика и Телемеханика, 1996, № 4, С. 79 86

11. Евдокименков В.Н., Красильщиков М.Н. Алгоритм стохастического оценивания в приложении к автоматизации диагностики наследственных заболеваний // Автоматика и Телемеханика, 1998, № 11, С. 213 220.

12. Ермольев Ю.М. Методы стохастического программирования. М.: Наука, 1976.

13. Калман Р., Фалб П., Арбиб М. Очерки по математической теории систем. М.: Мир, 1971.

14. Кан Ю.С. Квазиградиентный алгоритм минимизации функции квантили // Известия РАН. Теория и системы управления, 1996, № 2, С. 81 86.

15. Кан Ю.С. О сходимости одного стохастического квазиградиентного алгоритма квантильной оптимизации // Автоматика и Телемеханика, 2003, № 2, С. 100 — 116.

16. Кан Ю.С., Кибзун А.И. Свойства выпуклости функций вероятности и квантили в задачах оптимизации // Автоматика и Телемеханика, 1996, Я2 3, С. 82 102.

17. Кан Ю.С., Тузов Н.В. Минимизация квантили нормального распределения билинейной функции потерь // Автоматика и Телемеханика, 1998. № 11, С. 82 -92.

18. Кац И.Я., Тимофеева Г.А. Бикритериальная задача стохастической оптимизации // Автоматика и Телемеханика, 1998. № 11, С. 82 92.

19. Кибзун А.И. О наихудшем распределении в задачах стохастической оптимизации с функцией вероятности // Автоматика и Телемеханика, 1998, № 11, С. 104 116.

20. Кибзун А.И., Кан Ю.С. Задачи стохастического программирования с вероятностными критериями. М.: Физматлит, 2009.

21. Кибзун А.И., Кузнецов Е.А. Сравнение критериев VaR и CVaR // Автоматика и Телемеханика, 2003, № 7, С. 153 165.

22. Кибзун А.И., Матвеев E.JI. Стохастический квазиградиентный алгоритм минимизации функции квантили // Автоматика и Телемеханика, 2010, № 6, С. 64 78.

23. Кибзун А.И., Наумов A.B., Уланов C.B. Стохастический алгоритм управления летным парком авиакомпании // Автоматика и Телемеханика, 2000, № 8, С. 126 136.

24. Кибзун А.И., Чернобровое А.И. Алгоритм решения обобщенной задачи Марковича // Автоматика и Телемеханика, 2011, № 2, С. 41 — 60.

25. Кибзун А.И., Чернобровое А.И. Стохастический квазиградиентный алгоритм минимизации функции интегральной квантили // Автоматика и Телемеханика, 2012, № 2, С. 77 92.

26. Кибзун А.И., Чернобровое А.И. Эквивалентность задач с критериями в форме квантили и интегральной квантили // Автоматика и Телемеханика, 2013, № 2, С. 75 93.

27. Кибзун А. И., Чернобровое А.И. Задача оптимизации производства для наземных космических комплексов с критериями в форме квантили и интегральной квантили / / Труды МАИ, 2012, № 52, http: / / www.mai.ru / science/trudy / published.php?ID=29589

28. Кибзун А.И., Чернобровое А.И. Алгоритмы решения задач стохастического программирования с критериями VaR и CVaR // XIV-я Всероссийская конференция «Математическое программирование и приложения», Екатеринбург, 2011, С. 254 256.

29. Кибзун А.И., Чернобровое А. И. Применение стохастического квазиградиентного алгоритма минимизации интегральной квантили для оценки сверху квантильного критерия // 10-я Международная конференция «Авиация и космонавтика 2011», Москва, С. 285 — 286

30. Кибзун А.И., Чернобровое А. И. Оптимизация площади взлетно-посадочной полосы с помощью CVaR-критерия // 11-я Международная конференция «Авиация и космонавтика 2012», Москва, С. 399 — 400.

31. Кибзун А.И., Курбаковский В.Ю. Численные алгоритмы квантильной оптимизации и их применение к решению задач с вероятностными ограничениями. // Изв. АН СССР, техническая кибернетика, 1991, № 1, С. 75 81.

32. Красовский H.H., Куржанский А.Б., Кибзун А.И. Современные проблемы оптимизации и устойчивости неопределенных и стохастических систем // Автоматика и Телемеханика, 2007, № 10, С. 3 4.

33. Красильщиков М.Н., Серебряков Г. Г. Управление и наведение беспилотных маневренных летательных аппаратов на основе современных информационных технологий. М.: Физматлит, 2003.

34. Лепп Р. Исследования эстонских ученых по стохастическому программированию // Изв. АН ЭССР. Физ.-мат., 1982, № 8, С. 57 64.

35. Малышев В.В., Кибзун А.И. Анализ и синтез высокоточного управления летательными аппаратами. М.: Машиностроение, 1987.

36. Матасов А.И. Введение в теорию гарантирующего оценивания. — М.: МАИ, 1999.

37. Матвеев Е.Л. Оценивание и оптимизация квантильного критерия при выпуклой целевой функции с помощью стохастического квазиградиентного алгоритма: дис. . канд. ф.-м. наук: 05.13.01: защищена 11.06.10: утв. 24.09.10. — М., 2010 . 104 с.

38. Миллер В.М., Авраченков К.Е., Степанян К.В., Миллер Г.Б. Задача оптимального стохастического управления потоком данных по неполной информации // Пробл. передачи информ., 41:2 (2005), С. 89 110.

39. Михалевич B.C., Гупал A.M., Норкин В.И. Методы невыпуклой оптимизации. М.: Наука, 1987.

40. Назин A.B., Щербаков С.В. Пассивная стохастическая аппроксимация с усреднением вдоль траектории // Автоматика и Телемеханика, 1994, № 5, С. 48 58.

41. Назин A.B., Щербаков С.В. Реализуемый оптимальный алгоритм пассивной стохастической аппроксимации с усреднением вдоль траектории // Пробл. передачи информ., 1994. 30:3, С. 68 78.

42. Наумов A.B., Иванов С.В. Задача распределения инвестиций в развитие отраслей наземного космического комплекса // Труды МАИ, 2012, № 50, http://www.mai.ru/content/files/index.php?ID=28928

43. Пакшин П.В., Угриновский В.А. Стохастические задачи абсолютной устойчивости // Автоматика и Телемеханика, 2006, № 11, С. 122 158.

44. Панков А.Р., Платонов E.H., Семенихин К.В. Минимаксная оптимизация инвестиционного портфеля по квантильному критерию // Автоматика и Телемеханика, 2003, № 7, С. 117 133.

45. Пантелеев A.B. Оптимальные нелинейные системы управления: синтез при неполной информации. М.: Вузовская книга, 2008.

46. Пантелеев A.B., Летова Т. А. Методы оптимизации в примерах и задачах. М., Высшая школа, 2002.

47. Первозванский A.A., Первозванская Т.М. Финансовый рынок: расчет и риск. М.: Инфра-М, 1994.

48. Пиуновский A.B., Хаметов В.М. Оптимальное управление случайными последовательностями при ограничениях // Матем. заметки, 49:6 (1991), С. 143 145.

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

50. Поляк Б. Т. Новый метод типа стохастической аппроксимации // Автоматика и Телемеханика, 1990, № 3. С. 98 107.

51. Райк Э. О функции квантили в задачах стохастического нелинейного программирования // Изв. АН ЭССР. Физ.-мат., 1971, № 1 (24), С. 3 8.

52. Тамм Э. О квазивыпуклости функций вероятности и квантиля. // Изв. АН ЭССР Физ.-мат., 1976, № 2(25), С. 141 143.

53. Урясъев С.П. Адаптивные алгоритмы стохастической оптимизации и теории игр. М.: Наука, 1990.

54. Фихтенголъц Г.М. Курс дифференциального и интегрального исчисления. Том И. М.: Наука, 1962.

55. Чернобровое А.И. Доказательство сходимости алгоритма минимизации функции интегральной квантили с вероятностью единица. //16-я международная научная конференция «Системный анализ, управление и навигация», 2011, С. 134 135.

56. Чернобровое А.И. Об эквивалентности задач с критериями в форме квантили и интегральной квантили с билинейной целевой функцией // Сборник тезисов докладов «Инновации в авиации и космонавтике 2012», 2012, С. 259.

57. Чернобровое А.И. Об эквивалентности некоторого класса задач с критериями в форме квантили и интегральной квантили // Научные труды Международной молодежной научной конференции «XXXVIII Гагаринские чтения». М: МАТИ, 2012, Т. 5., С. 129 130.

58. Чернобровое А.И. Параллельный и рекуррентный способ решения семейства задач минимизации СУаЯ-критерия // Тезисы Международной (43-й Всероссийской) молодежной школы-конференции «Современные проблемы математики», 2012, С. 299 301.

59. Черноусъко Ф.Л., Колмановский В. Б. Оптимальное управление при случайных возмущениях. М.: Физматлит, 1978. — 352 с.

60. Юдин Д.Б. Задачи и методы стохастического программирования. М.: Советское радио, 1979.

61. Юдин Д. Б. Математические методы управления в условиях неполной информации. М.: Советское радио, 1974.

62. Ширяев А.Н. Вероятность 1. М.: МЦНМО, 2004.

63. Acerbi С. Spectral Measures of Risk: a coherent representation of subjective risk aversion // Journal of Banking & Finance, 2002, № 26, P. 1505 — 1518.

64. Acerbi C., Tasche D. On the coherence of expected shortfall //J. Banking & Finance, 2002, № 26:7, R 1487 1503.

65. Andersson F., Mausser H., Rosen D., Uryasev S. Credit risk optimization with conditional value-at-risk criterion // Math. Program., 2001, № 89(2), P. 273 — 291.

66. Artzner P., Delbaen F., Eber J.M., Heath D. Coherent measures of risk // Mathematical Finance, 1999, № 9(3), P. 203 228.

67. Bardou O., Frikha N., Pages G. Recursive Computation of Value-at-Risk and Conditional Value-at-Risk using MC and QMC // Monte Carlo and Quasi-Monte Carlo Methods, 2008, Part 3, P. 193 208.

68. Bardou O., Frikha N., Pages G. Computing VaR and CVaR using Stochastic Approximation and Adaptive Unconstrained Importance Sampling // Monte Carlo Methods and Applications, 2009, № 15(3): P. 173 210.

69. Benbachir S., Gaboune В., El Alaoui M. Comparing Portfolio Selection using CVaR and Mean-Variance Approach // International Research Journal of Finance and Economics Issue 88 April, 2012, P. 6 15.

70. Ben-Tal A., Teboulle M. An old-new concept of convex risk measures: the optimized certainty equivalent // Math. Finance, 2007, 17, 3, P. 449 476.

71. Birge J., Louveaux F. Introduction to Stochastic Programming. Springer Verlag, New York, 1997.

72. Brazauskas V., Jones B.L., Puri M.L., Zitikis R. Estimating conditional tail expectation with actuarial applications in view //J. Statist. Planning Inference, 2008, Vol. 138. № 11, P. 3590 3604.

73. Campana A. On Tail Value-at-Risk for sums of non-independent random variables with a generalized Pareto distribution // The Geneva Risk and Insurance Review, 2007, Vol. 32, P. 169 180.

74. Chernobrovov A.I. Optimization of the CVaR by a Stochastic Quasigradient Algorithm // 14th International Student Olympiad on Automatic Control, Russia, 21-23 September, 2011, P. 100 104.

75. Chun S.Y., Shapiro A., Uryasev S. Conditional Value-at-Risk and Average Value-at-Risk: Estimation and Asymptotics // Operations Research, 2012, 60(4), P. 739 756.

76. Dantzig G.B. Linear Programming under Uncertainty // Management Science, 1951, Vol. 1, P. 197 206.

77. David H.A., Nagaraja H.N. Order Statistics. Third Edition. John Willey, New Jersey, 2003.

78. Dentcheva D., Ruszczynski A. Portfolio optimization with stochastic dominance constraints // J. Banking and Finance, 2006, V. 30, № 2, P. 433 451.

79. Detlefsen K., Scandolo G. Conditional and dynamic convex risk measures. // Finance Stoch., 2005, 9, № 4, P. 539 561.

80. Follmer H., Schied A. Convex and Coherent Risk Measures // Encyclopedia of Quantitative Finance, Cont, R. (Ed.). John Wiley &; Sons, 2010, P. 1200 1204

81. Kali P., Wallace S. W. Stochastic Programming. Chichester: John Wiley & Sons, 1994.

82. Kibzun A.I., Kan Yu.S. Stochastic Programming Problems with Probability and Quantile Functions. Chichester: John Wiley & Sons, 1996.

83. Landsman Z., Valdez E. Tail conditional expectation for exponential dispersion models // ASTIN Bulletin, 2005, Vol. 35, № 1, P. 189 209.

84. Lim C., Sherali H., Uryasev S. Portfolio Optimization by Minimizing Conditional Value-at-Risk via Nondifferentiable Optimization // Computational Optimization and Applications,2010 Vol. 46, № 3, P. 391 415

85. Lu G., Wen F., Chung C.Y., Wong K.P. Conditional value-atrisk based mid-term generation operation planning in electricity market environment //IEEE/PES/Asia and Pacific: Conf. and Exhibition Trans, and Dist., 2005.

86. Markowitz H.M. Portfolio Selection // J. Finance, 1952, №7(1), P. 77 91.

87. Marti K. Stochastic Optimization Methods. 2nd ed. Springer, 2008.

88. Pflug G.C. Some Remarks on the Value-at-Risk and on the Conditional Value-at-Risk // Probabilistic Constrained Optimization: Methodology and Applications, (Uryasev ed), Kluwer, 2000

89. Prekopa A. Stochastic Programming. Dordrecht: Kluwer Academic Publishers, 1995.

90. Reiss R.D. Approximate Distributions of Order Statistics. Springer, New York, 1989

91. Robbins H., Monro S. A Stohastic Approximation Method // Ann. Math. Statist, 1951, P. 400 407.

92. Rockafellar R.T., Uryasev S. Optimization of conditional value-at-risk. // The Journal of Risk, 2000. Vol. 2, № 3, P. 21-41.

93. Rockafellar R. T., Uryasev S. Conditional value-at-risk for general loss distribution //J. Banking & Finance, 2002. № 26. P. 1443 1471.

94. Stoyanov S.V., Rachev S.T., Fabozzi F.J. Advanced Stochastic Models, Risk Assessment, and Portfolio Optimization: The Ideal Risk, Uncertainty, and Performance Measures. John Wiley & Sons, Finance, 2007.

95. Szekey, G.J. Paradoxes in Probability Theory and Mathematical Statistics // Budapest: Akademiai Kiado, 1986.

96. Tobin D. Liquidity Preference as Behavior Towards Risk //Review of Economic Studies, 1958, 25, № 1, P. 65 86.

97. Uryasev S. Conditional Value-at-Risk: Optimization Algorithms and Applications // Financial Engineering News, 2000, № 14.99. http://www.tsenki.com/ сайт Центра эксплуатации объектов наземной космической инфраструктуры.