Содержание к диссертации
Введение 5
1 Оценки квантили 15
-
Введение 15
-
Выборочная оценка квантили 16
-
Определение выборочной оценки квантили 16
-
Свойства первых моментов выборочной оценки квантили . . 17
1.3. Ядерная оценка квантили 18
-
Определение и свойства ядерной оценки квантили 18
-
Структура оптимального ядра 19
1.4. Децентрализированная оценка квантили 23
-
Определение децентрализированной оценки квантили .... 23
-
Свойства децентрализированной оценки квантили 25
-
Сравнение децентрализированной оценки квантили с выборочной оценкой 29
2 Свойства выпуклости функции квантили 32
-
Введение 32
-
7-вогнУтные функции и их свойства 33
Д.З. .Квази^огнутрс^ть^ейоятнрстной.мер^...^. ,, . .,.^..,., ,„,. . . 36
-
Определение квазивогнутости вероятностной меры 36
-
Достаточные условия квазивогнутости вероятностной меры . 36
-
Достаточные условия выпуклости и квазивыпуклости функции квантили 44
-
Примеры 46
2.4. Логарифмическая вогнутость вероятностной меры 48
-
Определение логарифмической вогнутости вероятностной меры 48
-
Достаточные условия логарифмической вогнутости вероятностной меры 48
-
Пример 53
3 Стохастический квазиградиентный алгоритм оптимизации
функции квантили 55
-
Введение 55
-
Постановка задачи квантильной оптимизации 57
-
Определение стохастического квазиградиента функции квантили . . 58
-
Стохастический квазиградиентный алгоритм на основе выборочной
оценки квантили 58
3.4.1. Стохастический квазиградиентный алгоритм минимизации
функции квантили 58
,w, . ?*,: и Сходимость стохастического,, квазиградиентного алгоритма
на основе выборочной оценки квантили 63
3.4.3. Пример использования стохастического квазиградиентного
алгоритма на основе выборочной оценки квантили 74
3.5. Распараллеливание процесса оптимизации функции квантили ... 75
-
Распараллеливание процедуры вычисления верхней оценки функции квантили 75
-
Стохастический квазиградиентный алгоритм на основе децентрализованной оценки квантили 84
-
Пример использования стохастического квазиградиентного алгоритма на основе децентрализованной оценки квантили . 86
3.6. Оптимизация площади ВПП 88
-
Постановка задачи 88
-
Эквивалентная задача квантильной оптимизации 90
-
Обзор существующих методов решения задачи оптимизации площади ВПП 91
-
Применение стохастического квазиградиентного алгоритма
для оптимизации площади ВПП 92
Заключение 94
Список литературы 96
( ><,.
.ІЛ," ' і -Ч , .» і- )*»«#.' «пЛЧ * '' 'iWtffl. ( '.> -»- Ч . «VAJ»!.' <-"»~ ««н*»""-**^»'" Hu**W«*.. **' і «-' - .» '-'-'
ґі***і . ,'^гЛ* ri* Г. ', , J**., <, . ч , , - с -t j*\tV ч >.-' * w * rt'„ kSj,^'..^^*^'
Введение к работе
В данной диссертационной работе исследуются задачи анализа и оптимизации систем с квантильным критерием качества.
В настоящее время при синтезе и анализе алгоритмов управления широкое распространение получили задачи стохастического программирования. Их решению посвящены, например, работы [33], [37], [54], [55]. Поиск решения в практических задачах часто приходится вести в случае, когда некоторые исходные данные не являются детерминированными, а известны лишь их законы распределения вероятностей. Например, при управлении летательными аппаратами необходимо решать задачу минимизации промаха, характеризующего точность попадания объекта в заданную область. При детерминированном подходе к моделированию систем влияние неопределенных факторов не учитывается. Но с практической точки зрения в этом случае может быть потерян реализм присутствующих в задаче явлений. В силу того, что на движение летательного аппарата оказывают воздействие случайные составляющие, задача сводится к минимизации функции со случайными параметрами. Стохастические модели, как правило, более адекватны реальным явлениям и процессам, чем детерминированные. Поэтому стратегии (управления), полученные на основе решения задач стохастического управления, являются практически более значимыми, чем стратегии, полученные в детерминированных постановках. Одним из способов решения задач стохастического управления является сведение их к задачам стохастического программирования. Естественный, на первый -взгляд; путь-'анализа* стохастических-задач (замена"-случайных параметров их средними значениями и нахождение оптимальных управлений полученных таким образом детерминированных задач) не всегда оправдан и может нарушить адекватность модели изучаемого явления. Решение детерминированной задачи с усредненными параметрами может не удовлетворять условиям задачи при различных реализациях случайных факторов. Жесткая же постановка задачи в условиях неполной или неопределенной информации, когда ограничения задачи должны удовлетворяться при всех реализациях случайных параметров, либо приводит к чрезвычайно перетяжелённым решениям, неуместным в практическом применении, либо и вовсе, множество допустимых решений .оказывается пустым. Таким образом, простейшие пути учета случайного характера условий задачи -замена случайных переменных их средними значениями или переход к жесткой постановке - не всегда приводит к осмысленному решению задачи стохастического программирования. В качестве разумного критерия, по которому производится оптимизация, является функция квантили. Функция квантили характеризует гарантированный при заданном уровне вероятности результат принимаемого решения. Так как при таком подходе маловероятные, наихудшие сочетания параметров, исключаются из рассмотрения. Риск их появления ограничивается на некотором допустимом уровне. В силу актуальности и важности этих задач исследованием их занимались известные российские и зарубежные ученые в области теории управления [1,2,10,15,25,27,28,31,42-47,52,53,64,78,83-87,95,96]. Рассмотрим работы [18, 54, 72], в которых содержатся обобщения многих результатов по стохастическому программированию. В книге [54] рассмотрены три группы методов стохастического программирования: методы прогнозирования поведения сложных систем, методы управления в условиях риска и неопределенности и методы адаптации и обучения (стохастическая аппроксимация). Исследованы одноэтапные, двухэтапные и многоэтапные задачи стохастического программирования, проблемы сглаживания и экстраполяции случайной функции, обобщенные задачи фильтрации и прогноза, одномерная и многомерная стохастическая аппроксимация. В работе [72] описаны основные вопросы стохастического программирования, в том числе нахождение вероятностных мер, детерминированных эквивалентов, решение многоэтапных задач оптимизации. В книге рассмотрен раздел динамических систем, включая принцип Беллмана, детерминированные и стохастические деревья решений, а также прёпроцессин'г данных - уменьшение размерности задачи, проверка на разрешимость - и задачи, связанные с системами массового обслуживания.
В книге [18] рассмотрены задачи стохастического программирования с вероятностным и квантильным критериями. Исследованы прикладные модели в производстве и экономике с вероятностным и квантильным критериями, свойства функции вероятности и квантили, в том числе их непрерывность и дифференцируемость, выпуклость для некоторых классов задач. Также изложены методы нахождения функций вероятности и квантили, определения нижних и верхних границ для данных функций, условия эквивалентности вероятностной и квантильной постановок, соотношение задачи квантильной оптимизации с минимаксной, описаны методы численной оптимизации функций вероятности и квантили.
При анализе систем в присутствии случайных параметров по квантильному критерию качества возникает сложности следующего характера.
Во-первых, в большинстве постановках квантильного анализа найти аналитическое выражение для квантильного критерия при заданном уровне доверительной вероятности, как правило, невозможно. Это связано с неявным (через вероятность) определением функции квантили. Кроме того, анализ усложняется нелинейностью квантильного критерия.
Во-вторых, для статистического оценивания квантили не всегда понятно, сколько нужно провести испытаний, чтобы с заданной точностью оценить искомую величину.
В-третьих, если количество опытных данных фиксировано, не понятно как улучшить точность оценки квантили. В силу указанных причин при разработке численных методов для вычисления квантили приходится использовать различные аппроксимации. Обычно применяют аппроксимации двух типов: основывающиеся на статистических оценках и на построении детерминированных границ квантили.
Так как в большинстве случаев точное распределение неизвестно, то вместо значения квантили распределения используется её оценка, полученная по статистической выборке. Работы [5, 57, 68, 69, 79, 80, 88, 92-94, 97-100] посвящены различным способам статистического оценивания квантилей и свойствам этих оценок. Книга [68] посвящена порядковым статистикам, частным случаем которых является выборочная оценка квантили. Рассматриваются распределения порядковых статистик, нахождение точечных оценок, а также построение доверительных интервалов для различных функций от порядковых статистик. В [5] исследована асимптотическая теория порядковых статистик. Получено асимптотическое распределение квантилей, а также асимптотическое распределение экстремального (крайнего) значения для различных видов распределений. Альтернативный подход к получению оценок функции квантили был предложен в [94] который основывается на решении определённого функционалвного 'уравнения:" В'-работе [80|"впервые бьтла предложена ядерная оценка квантили. В [100] исследовано асимптотическое поведение первых моментов ядерной оценки квантили. В работе [69] сравнивается относительная эффективность выборочной и ядерной оценок квантили. В работе [93] устанавливается эффективность ядерных оценок в зависимости от типа ядерной функции, а также предлагается процедура выбора оптимальной "ширины окна" из условия минимума среднеквадратического отклонения. В работе [98] предложена ядерная оценка условной квантили, а также доказана асимптотическая нормальность ошибки оценки. В [79] предложена оценка квантили, полученная из ядерной оценки функции распределения. В работах [57], [88] получено выражение для среднеквадратической ошибки при таком представлении. Данный результат обобщается в работе [92]. В работе [99] .устанавдив^ется..,асимптотическая,v нормальность ядерной оценки квантили в , некоторых нестандартных случаях, а также устанавливается закон повторного логарифма для ядерной оценки квантили. В [97] рассматривается вероятность отклонения ядерной оценки квантили от истинного значения квантили. К сожалению, выражения для первых моментов ядерной оценки квантили зависят от выбора конкретного вида ядерной функции. Поэтому актуальной становится задача выбора класса функций для нахождения оптимальной оценки квантили с точки зрения минимума среднеквадратичного отклонения ядерной оценки квантили от истинного значения. В первой главе диссертации рассматривается класс функций с конечным носителем, обладающих условием несмещённости и нормировки. Данный класс плотностей использовался в [6], [60], [62] в связи с проблемой ядерного оценивания плотности вероятности. В рамках указанного класса ищется оптимальная с точки зрения минимума среднеквадратичного отклонения ядерная оценка квантили. Характерной особенностью современных быстродействующих вычислительных систем является параллельная обработка информации. Поэтому актуальной становятся проблема разработки специальных алгоритмов, учитывающих параллельный процесс вычислений. В первой главе диссертации рассматривается децентрализованный алгоритм оценивания квантили основанный на использовании многопроцессорной архитектуры. Рассматриваются свойства оценки, полученной с помощью данного алгоритма. Показывается, что дисперсия оценки квантили, полученной с помощью децентрализованного алгоритма, убывает с ростом числа процессоров, участвующих в обработки данных.
При исследовании сходимости вычислительных алгоритмов оптимизации желательно, чтобы исследуемая функция обладала достаточно "хорошей" структурой и можно было сделать качественные выводы относительно получившихся результатов. Одним из примеров такого рода свойств является строгая квазивогнутость (квазивыпуклость) исследуемой функции вероятности (квантили) в силу того, что каждый локальный минимум функции будет являться одновременно и глобальным. Основным требованием, обеспечивающим квазивогнутость функции вероятности, является квазивогнутость вероятностной меры и квазивыпуклость целевой функции [18]. Но проверить условие квазивогнутости вероятностной меры с помощью определения оказывается весьма затруднительно. Впервые достаточное условие квазивогнутости вероятностной меры приведено в [84] и основано оно на логарифмической вогнутости плотности вероятности. В обзорной статье [66] приведены многочисленные результаты, посвященные обобщению неравенства Брунна-Минковского-Люстерника. В [59], [63], [73], [81] приведены различные неравенства для логарифмически вогнутых функций. В [74] получены неравенства типа Берри-Эссеена для случайных величии с логарифмически вогнутой плотностью вероятности. Оценки для хвостов распределений в случае логарифмически вогнутой функции распределения получены в [82]. В [56] устанавливаются необходимые и достаточные условия для того, чтобы вероятностная мера была логарифмически вогнутой. В [64] приведено достаточное условие квазивогнутости вероятностной меры, основанное на так называемой а-выпуклости плотности [36]. Однако доказательство соответствующего утверждения в [64] оказалось чрезвычайно сложным. Поэтому в работах [65], [67], [86], [90] дано новое доказательство сформулированного в [64] утверждения, основанное на неравенстве Брунна-Минковского-Люстерника [32] для некоторых множеств Лебега. Во второй главе диссертации приведено приведено альтернативное доказательство данного утверждения, а также показано, что доказательства в работах [65], [67], [86], [90] содержатся неточности. Доказательство носит достаточно универсальный характер и позволяет использовать его с небольшими модификациями для нахождения достаточных условий логарифмической вогнутости вероятностной меры.
Применение стандартных численных методов решения оптимизационных задач затруднено тем, что терминальная функция имеет случайную структуру. Для преодоления данной проблемы может быть использован стохастический квазиградиентный алгоритм [8], [12], [13], [19], [39], [49], [75], [78]. Квазиградиент отличается от обычного градиента тем, что позволяет учитывать вероятностную природу оптимизируемой функции. Использование стохастических квазиградиентных алгоритмов позволяет определить точное значение оптимизируемой величины, а не верхнюю оценку как при доверительном подходе. В книге [8] на примере различных задач указаны способы построения стохастических квазиградиентов. Работа [49] является в некотором смысле обобщением и продолжением работы [8]. В ней развиваются идеи алгоритмов квазиградиентного типа решения задач выпуклого стохастического программирования с негладкими функционалами цели и ограничений. В этой книге с единой точки зрения рассматривается вопрос построения адаптивных процедур регулирования параметров для различных градиентных алгоритмов оптимизации и теории игр: формируются критерии, определяющие качество регулировок, затем для регулировки параметров применяется итерационный алгоритм, работающий в этом классе задач. В [49] предложен сходящийся в чезаровском смысле квазиградиентный алгоритм типа Эрроу-Гурвица. Однако применение этого алгоритма к решению игры, возникающей из квантильной постановки, наталкивается на определённые трудности. Эти трудности указаны в [29], где отмечено, что применение квази- [8] и псевдоградиентных [39] алгоритмов к решению задач квантильной оптимизации затруднено сложностью функции вероятности (с помощью которой определяется функция квантили), обусловленной разрывностью индикаторной функции множества. В [91] предложен квазиградиентный алгоритм для максимизации функции вероятности. Квазиградиентные алгоритмы на основе ядерных оценок предложены в [78] в связи с проблемой максимизации функции вероятности, однако, сходимость алгоритма доказана в предположении, что функция вероятности является дважды дифференцируемой. Однако, во многих случаях функция вероятности не является дифференцируемой. Тогда можно воспользоваться алгоритмом, предложенным Юби в [52, 53]. В [12] предложен, а в [13] доказана сходимость алгоритма, базирующегося на неантагонистической игре двух лиц, и сводящегося к минимизации функции -квантили с, помощью ^стохастического квазиградиентного- алгоритма типа Эрроу-Гурвица. Однако, данный алгоритм предназначен для поиска минимума функции квантили на всём пространстве. Для поиска минимума функции квантили на ограниченном множестве в [19] предложен квазиградиентный алгоритм на основе выборочной оценки функции квантили с использованием свойств экстремальных порядковых статистик. Однако не получено строгое доказательство сходимости указанного алгоритма. Поэтому представляется актуальной проблема обоснования сходимости квазиградиентного алгоритма поиска минимума функции квантили на ограниченном множестве. В третьей главе диссертации приведён алгоритм на основе выборочной оценки квантили и доказана сходимость данного алгоритма при достаточно общих предположениях. Как известно, рекуррентные алгоритмы нельзя в принципе распараллелить, т.е. ускорить процесс решения, используя современную вычислительную технику. Поэтому актуальным является вопрос о распараллеливании процесса оптимизации функции квантили. В [17] приведены алгоритмы получения верхних оценок для оптимального значения функции квантили, которые удается распараллелить. При этом исходно невыпуклая задача квантильной оптимизации сводится к решению набора задач выпуклого программирования, которые можно решать независимо друг от друга. Поэтому помимо алгоритма на основе выборочной оценки квантили в третьей главе диссертации приведён также стохастический квазиградиентный алгоритм минимизации функции квантили на основе децентрализованной оценки квантили, полученной при использовании многопроцессорной архитектуры.
Подводя итог вышесказанному, можно сделать вывод о том, что постановки задач анализа и стохастического программирования с квантильным критерием активно исследуются в настоящее время, что подтверждает актуальность диссертационной работы.
Целью работы является оптимизация квантильного критерия при выпуклой целевой функции с помощью стохастического квазиградиентного алгоритма. Для достижения данной цели предлагается: построение оптимального ядра для ядерной оценки квантили; построение децентрализованной оценки квантили и исследование её свойств; получение универсального доказательства достаточных условий квазивогнутости и логарифмической вогнутости вероятностной меры; обоснование стохастического квазиградиентного алгоритма минимизации функции квантили с использованием порядковых статистик; демонстрация работоспособности алгоритма на примере решения прикладной задачи.
Основные результаты диссертации опубликованы в 4 статьях [20-23] в журналах, входящих в Перечень ВАК. Кроме того, данные результаты были апробированы на научных семинарах Московского авиационного института на кафедре "Теория вероятностей" и в Институте проблем управления на кафедре "Теория автоматического управления". . Диссертация состоит, ла трёх ,глав, заключения и списка литературы (100 источников). Объем диссертации включает 103 машинописных страницы, включая 7 рисуноков.
Краткое содержание основных результатов работы по главам состоит в следующем.
В первой главе рассматриваются различные оценки квантили. Рассматриваются ядерная и децентрализованная оценка квантили.
Для минимизации среднеквадратической ошибки ядерной оценки сформирован класс Ет при т ^ 2 функций с конечным носителем, обладающих условиями несмещенности и^ нормировки.,
Доказано утверждение, которое указывает вид оптимального в Sm с точки зрения минимума среднеквадратического отклонения ядра и устанавливает значение асимптотического среднеквадратического отклонения и смещения данной оценки.
Кроме того, приводится децентрализированная оценка, которая позволяет распараллелить процесс нахождения квантили. Алгоритм базируется на использовании многопроцессорной архитектуры и позволяет находить значение квантили при достаточно общих ограничениях.
Доказана теорема, которая устанавливает асимптотические оценки первых моментов децентрализированной оценки квантили.
Также приводится сравнение данной оценки с выборочной оценкой квантили.
Во второй главе рассматриваются выпуклые свойства функции квантили. В основе результатов лежит понятие 7~в0ГНУтй функции, которое является обобщением понятия выпуклой функции.
Устанавливаются достаточные условия квазивогнутости вероятностной меры.
Также приведены условия, обеспечивающие квазивыпуклость функции квантили и квазивогнутость функции вероятности.
Кроме того, приводится пример, показывающий, что квазивогнутость плотности не гарантирует квазивогнутость меры.
Третья глава посвящена стохастическому квазиградиентному алгоритму минимизации функции квантили. Введено понятие стохастического квазиградиента функции квантили.
Рассмотрен стохастический квазиградиентный алгоритм минимизации функции квантили.
Пи[ик-Ркк(ик,$к)], ШЫ,5к)\\ < L,Uk+l = < (1) й, ||&(ufcA)|| > L, где L — некоторое достаточно большое число, р/. — длина шага алгоритма, к(ик,$к) — значение стохастического квазиградиента функции квантили в точке щ, П{/[-] — оператор рандомизированного проецирования, а й имеет равномерное распределение на множестве U.
Доказан результат, который устанавливает условия сходимости описанного выше алгоритма к оптимальному значению функции квантили.
Помимо алгоритма на основе выборочной оценки квантили приведён также стохастический квазиградиентный алгоритм минимизации функции квантили на основе децентрализованной оценки квантили, описанной в главе 1.
