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

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

В настоящее время при синтезе и анализе алгоритмов управления широкое распространение получили задачи стохастического программирования. Их решению посвящены, например, работы [33], [37], [54], [55]. Поиск решения в практических задачах часто приходится вести в случае, когда некоторые исходные данные не являются детерминированными, а известны лишь их законы распределения вероятностей. Например, при управлении летательными аппаратами необходимо решать задачу минимизации промаха, характеризующего точность попадания объекта в заданную область. При детерминированном подходе к моделированию систем влияние неопределенных факторов не учитывается. Но с практической точки зрения в этом случае может быть потерян реализм присутствующих в задаче явлений. В силу того, что на движение летательного аппарата оказывают воздействие случайные составляющие, задача сводится к минимизации функции со случайными параметрами. Стохастические модели, как правило, более адекватны реальным явлениям и процессам, чем детерминированные. Поэтому стратегии (управления), полученные на основе решения задач стохастического управления, являются практически более значимыми, чем стратегии, полученные в детерминированных постановках. Одним из способов решения задач стохастического управления является сведение их к задачам стохастического программирования. Естественный, на первый — взглядпуть-анализа* стохастических-задач (замена" -случайных параметров их средними значениями и нахождение оптимальных управлений полученных таким образом детерминированных задач) не всегда оправдан и может нарушить адекватность модели изучаемого явления. Решение детерминированной задачи.

В книге [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] .устанавдив§ ед-ся., асшУ1птотинеска^^нормальиость ядерной оценки квантили в, некоторых нестандартных случаях, а также устанавливается закон повторного логарифма для ядерной оценки квантили. В [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] приведены алгоритмы получения верхних оценок для оптимального значения функции квантили, которые удается распараллелить. При этом исходно невыпуклая задача квантильной оптимизации сводится к решению набора задач выпуклого программирования, которые можно решать независимо друг от друга. Поэтому помимо алгоритма на основе выборочной оценки квантили в третьей главе диссертации приведён также стохастический квазиградиентный алгоритм минимизации функции квантили на основе децентрализованной оценки квантили, полученной при использовании многопроцессорной архитектуры.

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

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

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

2) построение децентрализованной оценки квантили и исследование её свойств;

3) получение универсального доказательства достаточных условий квазивогнутости и логарифмической вогнутости вероятностной меры;

4) обоснование стохастического квазиградиентного алгоритма минимизации функции квантили с использованием порядковых статистик;

5) демонстрация работоспособности алгоритма на примере решения прикладной задачи.

Основные результаты диссертации опубликованы в 4 статьях [20−23] в журналах, входящих в Перечень ВАК. Кроме того, данные результаты были апробированы на научных семинарах Московского авиационного института на кафедре «Теория вероятностей» и в Институте проблем управления на кафедре «Теория автоматического управления». Диссертация состоите ла трёх, глав, заключения и списка литературы (100 источников). Объем диссертации включает 103 машинописных страницы, включая 7 рисуноков.

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

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

Для минимизации среднеквадратической ошибки ядерной оценки сформирован класс Ет при т ^ 2 функций с конечным носителем, обладающих условиями несмещенности и^ нормировки.,.

Доказано утверждение, которое указывает вид оптимального в Нт с точки зрения минимума среднеквадратического отклонения ядра и устанавливает значение асимптотического среднеквадратического отклонения и смещения данной оценки.

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

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

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

Во второй главе рассматриваются выпуклые свойства функции квантили. В основе результатов лежит понятие 7-вогнутой функции, которое является обобщением понятия выпуклой функции.

Устанавливаются достаточные условия квазивогнутости вероятностной меры.

Также приведены условия, обеспечивающие квазивыпуклость функции квантили и квазивогнутость функции вероятности.

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

Третья глава посвящена стохастическому квазиградиентному алгоритму минимизации функции квантили. Введено понятие стохастического квазиградиента функции квантили.

Рассмотрен стохастический квазиградиентный алгоритм минимизации функции квантили. г.

П.и[ик-рк?к (ик,$к)], ШЫ, 5к)\ ^ Ь, ик+1 = (1) V где Ь — некоторое достаточно большое число, — длина шага алгоритма, -(ик,$к) — значение стохастического квазиградиента функции квантили в точке.

П[/[-] — оператор рандомизированного проецирования, а й имеет равномерное распределение на множестве и.

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

Помимо алгоритма на основе выборочной оценки квантили приведён также стохастический квазиградиентный алгоритм минимизации функции квантили на основе децентрализованной оценки квантили, описанной в главе 1.

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

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

1. построена оптимальная ядерная оценка квантили в классе функций с конечным носителем, обладающих условиями несмещённости и нормировки и исследованы её свойства;

2. предложен алгоритм получения децентрализованнрй оценки квантили и получены асимптотические оценки первых её моментов;

3. получено универсальное доказательство достаточных условий квазивогнутости и логарифмической вогнутости вероятностной меры;

4. предложен стохастический квазиградиентный алгоритм минимизации функции квантили и доказана его сходимость с вероятностью единица;

5. продемонстрирована работоспособность алгоритма на примере решения задачи оптимизации площади взлётно-посадочной полосы.

Заключение

.

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

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