Использование свойств 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 можно определить, как минимум, тремя эквивалентными способами: xpdfi, (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.

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

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