Использование свойств VaR-критерия для построения алгоритмов решения задач стохастического программирования с CVaR-критерием тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат физико-математических наук Чернобровов, Алексей Игоревич

• Чернобровов, Алексей Игоревич
• кандидат физико-математических наук
• 2012

Оглавление диссертации кандидат физико-математических наук Чернобровов, Алексей Игоревич

Введение

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. Решение задачи с помощью стохастического квазиградиентного алгоритма.

Введение диссертации (часть автореферата) на тему «Использование свойств VaR-критерия для построения алгоритмов решения задач стохастического программирования с CVaR-критерием»

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Чернобровов, Алексей Игоревич, 2012 год

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/ сайт Центра эксплуатации объектов наземной космической инфраструктуры.