Использование свойств VaR-критерия для построения алгоритмов решения задач стохастического программирования с CVaR-критерием

• Автор: Чернобровов, Алексей Игоревич
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 2012
• Место защиты: Москва
• Количество страниц: 105 с.

Оглавление
Введение

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

1.1. Введение.

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

1.3. Свойства V и V

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

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

1.4.2. Задача с Vкритерием

1.4.3. Задача с Vкригерием.

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

1.5.1. Задача Марковица
2 Сравнение постановок с критериями в форме V и V
2.1. Введение.
2.2. Связь критериев V и V в терминах дохода и потерь
2.3. Эквивалентность задач с критериями V и V
2.3.1. Функция потерь, линейная относительно случайной величины
2.3.2. Функция потерь со скалярной билинейной структурой
2.3.3. Функция потерь с билинейной структурой
3 Стохастический квазиградиентный алгоритм решения задач с
Vкритерием
3.1. Введение.
3.2. Постановка задачи минимизации Vкритерия
3.3. Вспомогательные утверждения.
3.4. Стохастический квазиградиентный алгоритм минимизации Vкритерия.
3.5. Практические особенности реализации стохастического квазиградиентного алгоритма минимизации Vкритерия
3.6. Примеры.
4 Комбинированная задача с критериями V и V
4.1. Введение .
4.2. Задача с Vкритерием и ограничением на V.
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. Использование Vкритерия, как верхней оценки Vкритерия .
5.2. Задача оптимизации инвестиционных вложений в наземнокосмический комплекс.
5.2.1. Постановка задачи
5.2.2. Решение задачи с помощью стохастического квазиградиентного алгоритма
Заключение
Список литературы


Квантильная постановка задачи (или постановка с УаИ-критерием) [8] заключается в поиске стратегии, которая гарантирует максимальный доход с заданной вероятностью. Такая постановка гораздо лучше учитывает интересы инвестора, чем описанные выше. В качестве критики УаЯ-критерия можно привести следующий пример. Можно получить стратегию, которая с заданной вероятностью гарантирует доход в 1 рубль, но при этом во всех остальных случаях сулит миллионные убытки. Такую стратегию можно легко получить с помощью УаЯ. В частности, чтобы избежать получения таких стратегий, был предложен СУаЯ-критерий (интегральная квантиль), который характеризует усредненное значение в неблагоприятных случаях [,,,]. Хотя Уа-критерий хорошо изучен [6,,,,,] и имеет тесную связь с СУа (как будет показано позже), первые работы по СУаВ. ХХ-века [, , ]. Они тесно связаны с понятием когерентной меры риска []. Х + і) = р(Х) 4- ? Х) = Ьр(Х) верно для любой константы ? В работе [] показано, что VaR не является когерентной мерой риска, так как не выполняется свойство субаддитивности. А в работах [,,,] показано, что CVaR является когерентной, а следовательно выпуклой мерой риска. Во многом благодаря исследованиям в области когерентных и выпуклых мер риска CVaR-критерию стало уделяться значительное внимание [,,]. В работе [] показано, что если целевая функция является выпуклой на некотором множестве, то и CVaR-критерий также является выпуклой функцией на этом множестве. Благодаря этому свойству можно проверять выпуклость CVaR, не получая его аналитический вид. Для VaR-критерия проверка выпуклости часто является затруднительной задачей ||. Не сложно построить примеры, где CVaR является выпуклой функцией, a VaR - нет. Как упоминалось ранее, CVaR разные авторы называют по-разному - это в основном связано с тем, что определения для CVaR вводились по-разному. Х]р - VaR (квантиль) уровня /3, т. Х]р = min{<^ : V{ X < ip} ^ /? Аа ‘= a Fx(x) - функция распределения случайной величины X. Эквивалентность этих определений доказана в работах [,,,]. У CVaR есть также и ряд недостатков. CVaR нельзя определить для случайных величин с “тяжелыми” хвостами, что является существенным недостатком по сравнению с VaR. На практике задачи часто формулируются в виде требований по надежности (ограничение на вероятности). Такие задачи можно свести к задаче с VaR критерием, но не с CVaR. Помимо этого CVaR и VaR критерии обладают тесной связью между собой. В (1) и (3) они связаны непосредственно через определение, причем разными способами. Как видно из определений, VaR всегда не превосходит CVaR, поэтому CVaR можно использовать как оценку сверху для VaR. Также видно, что при больших значениях уровня вероятности значения критериев CVaR и VaR близки друг к другу. Решения задач на основе VaR и CVaR, как правило, получаются различными, в силу разной природы данных критериев. Однако часто есть информация о решении задачи с помощью VaR-критерия, например, полученная методом детерминированного эквивалента [б], поэтому актуальна проблема поиска условий, при которых множества решений данных задач пересекаются или совпадают. В [) был предложен алгоритм, который сводил задачу минимизации CVaR-критерия для билинейной целевой функции к задаче линейного программирования большой размерности. Современная вычислительная техника позволяет достаточно быстро решать подобные задачи. Однако существенным недостатком данного алгоритма является то, что его сходимость можно доказать только при условии, что случайные величины имеют дискретные распределения. Если же считать, что случайные величины имеют непрерывные распределения, то сходимость данного алгоритма доказать затруднительно. Поэтому возникает необходимость построения алгоритмов, для которых можно доказать сходимость. Применение стандартных численных методов решения задач стохастического программирования затруднено тем, что целевая функция имеет случайную структуру. Для преодоления данной трудности был разработай в [,] стохастический квазиградиентный алгоритм (СКА). Квазиградиент отличается от обычного градиента тем, что позволяет учитывать вероятностную природу оптимизируемой функции.