На правах рукописи
Матвеев Евгений Леонидович
ОПТИМИЗАЦИЯ КВАНТИЛЬНОГО КРИТЕРИЯ
ПРИ ВЫПУКЛОЙ ЦЕЛЕВОЙ ФУНКЦИИ С ПОМОЩЬЮ
СТОХАСТИЧЕСКОГО КВАЗИГРАДИЕНТНОГО АЛГОРИТМА
Специальность 05.13.01
Системный анализ, управление и обработка информации
(авиационная и ракетно-космическая техника)
АВТОРЕФЕРАТ
диссертации на соискание ученой степени кандидата физико-математических наук
Москва, 2010
Работа выполнена на кафедре Теории вероятностей Московского авиационного института (государственного технического университета).
Научный руководитель: доктор физико-математических наук, профессор Кибзун Андрей Иванович
Официальные оппоненты: доктор физико-математических наук, профессор Матасов Александр Иванович кандидат физико-математических наук, доцент Руденко Евгений Александрович
Ведущая организация: Институт проблем управления им. В.А.
Трапезникова РАН
Защита состоится “11” июня 2010 г. в 12 ч. 00 мин. на заседании Диссертационного совета Д 212.125.04 Московского авиационного института по адресу: 125993, Москва, А-80, ГСП-3, Волоколамское ш., 4, Ученый совет МАИ.
С диссертацией можно ознакомиться в библиотеке Московского авиационного института (государственного технического университета).
Отзыв на автореферат, заверенный гербовой печатью организации, просьба направлять по указанному адресу в двух экземплярах.
Автореферат разослан “ ” 2010 г.
Ученый секретарь Диссертационного совета Д 212.125.04, кандидат физико-математических наук М.В. Ротанина
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Объект исследования. Диссертационная работа посвящена анализу и оптимизации конечномерных стохастических систем с квантильным критерием качества.
Актуальность темы. Поиск решения в практических задачах часто приходится вести в случае, когда некоторые исходные данные не являются детерминированными, а определяются случайными параметрами с известными законами распределения вероятностей.
При детерминированном подходе к моделированию систем влияние случайных факторов не учитывается. Но с практической точки зрения в этом случае может быть потерян реализм присутствующих в задаче явлений. Например, при управлении летательными аппаратами необходимо решать задачу минимизации промаха, характеризующего точность попадания объекта в заданную область фазового пространства.
В силу того, что на движение летательного аппарата оказывают воздействие случайные составляющие, задача сводится к минимизации функции со случайными параметрами. Одним из способов решения задач стохастического управления является сведение их к задачам стохастического программирования. Задачам стохастического программирования посвящены работы Дж. Бёржа, Р. Ветcа, С. Волласа, Ю. М. Ермольева, П. Калла, Ю. С. Кана, А. И. Кибзуна, В. Купера, Р. Леппа, К. Марти, А. В. Назина, Н. М. Новиковой, Б. Т. Поляка, А. Прекопы, Э. Райка, С. П. Урясьева, А. Чарнса, Д. Б. Юдина и многих других авторов.
Естественный, на первый взгляд, путь анализа стохастических систем (замена случайных параметров их средними значениями и нахождение оптимальных управлений полученных таким образом детерминированных задач) не всегда оправдан и может нарушить адекватность модели изучаемого явления. Решение детерминированной задачи с усредненными параметрами может не удовлетворять условиям задачи при различных реализациях случайных факторов. Учёт неопределённости в рамках детерминированного подхода зачастую приводит к чрезвычайно пессимистическим выводам, например, множество допустимых решений может быть пусто. Таким образом, простейшие пути учета случайного характера условий задачи - замена случайных переменных их средними значениями или переход к жесткой постановке - не всегда приводит к осмысленному решению задачи стохастического программирования. В качестве разумного критерия, по которому производится оптимизация, является функция квантили.
Функция квантили характеризует гарантированный при заданном уровне вероятности результат принимаемого решения. При таком подходе маловероятные, наихудшие сочетания параметров исключаются из рассмотрения за счёт того, что риск их появления ограничивается на некотором допустимом уровне. Таким образом, оптимизация стохастических систем с квантильным критерием качества является актуальной проблемой. Исследованием этой проблемы занимались известные российские и зарубежные ученые в области теории управления, такие как Бахшиян Б. Ц., Зубов В. И., Кац И. Я., Кибзун А. И., Колмановский В. Б., Красовский Н. Н., Кузьмин В. П., Лидов М. Л., Матасов А. И., Назиров Р. Р., Черноусько Ф. Л., Эльясберг П. Е., Юби Э., Ярошевский В. А. и др.
При анализе систем в присутствии случайных параметров по квантильному критерию качества возникают определённые сложности.
Во-первых, в большинстве постановок квантильной оптимизации найти аналитическое выражение для критерия при заданном уровне доверительной вероятности, как правило, невозможно. Это связано с неявным определением функции квантили. Кроме того, анализ усложняется нелинейностью квантильного критерия. Во-вторых, если количество опытных данных фиксировано, не понятно, как улучшить точность оценки квантили.
В силу указанных причин при разработке численных методов для вычисления квантили приходится использовать различные аппроксимации. Так как в большинстве случаев точное распределение неизвестно, то вместо значения квантили распределения используется её статистическая оценка. Проблемой статистического оценивания квантили в разное время занимались Галамбош Я., Azzalini А., David H. A., Falk M., Marron J. S., Nadaraya E. A., Nagaraja H. N., Parzen E., Reiss R. D., Shao Y., Sheather S. J., Tamm E., Xiang X., Yang S. и др.
Квантильный критерий относится к группе вероятностных критериев и впервые введен в рассмотрение С. Катаокой. Создание основ теории оптимизационных задач с таким критерием связано с именем эстонского математика Э. Райка и его учеников Р. Леппа, Э. Тамм и Э. Юби.
Существенный вклад в развитие этой теории внесли С. Бойд, К. Марти, Домбровский В. В., Ермольев Ю. М., Кан Ю. С., Келли Дж., Кибзун А. И., Красильщиков М. Н., Малышев В. В., Норкин В. И., Панков А. Р., Роенко Н. В., Урясьев С. П. и др.
Задачи стохастического программирования, особенно при оптимизации по квантильному критерию, являются достаточно сложными. Это объясняется в основном отсутствием аналитического вида квантильного критерия, а также сложностью построения конструктивных численных методов решения подобных задач.
Одним из наиболее эффективных путей решения задач стохастического программирования является использование стохастического квазиградиентного алгоритма. Построением и изучением свойств квазиградиентов занимались Гупал А. М., Ермольев Ю. М, Кан Ю. С., Кибзун А. И., Курбаковский В. Ю., Лепп Р., Михалевич В. С., Норкин В. И., Поляк Б. Т., Роенко Н. В., Третьяков Г., Урясьев С. П., Юби Э. и др.
Таким образом, проблема разработки эффективных методов поиска оптимальных стратегий в задачах стохастического программирования с использованием квантильного критерия качества является актуальной.
Цель работы. Целью работы является оптимизация квантильного критерия при выпуклой целевой функции с помощью стохастического квазиградиентного алгоритма. Для достижения данной цели предлагается обосновать стохастический квазиградиентный алгоритм минимизации функции квантили с использованием порядковых статистик, получить универсальное доказательство достаточных условий квазивогнутости вероятностной меры, построить децентрализованную оценку квантили и исследовать её свойства, построить оптимальную ядерную оценку квантили в классе финитных функций с моментными ограничениями, продемонстрировать работоспособность алгоритмов на примере решения задачи оптимизации площади взлётно-посадочной полосы.
исследования. Для исследования теоретических проблем использовались современные методы стохастического программирования, теории вероятностей, математической статистики, нелинейного программирования, выпуклого анализа. Для исследования прикладных задач использовались методы компьютерного статистического моделирования.
Достоверность результатов. Достоверность результатов обеспечивается:
1) строгостью постановок и доказательств утверждений;
2) приведением численных расчетов, подтверждающих справедливость результатов;
3) рассмотрением конструктивных примеров, которые демонстрируют достоверность приведенных результатов.
Научная новизна. В работе получены новые результаты эффективного решения задач квантильной оптимизации, среди которых можно выделить следующие:
1) построена оптимальная ядерная оценка квантили в классе финитных функций с моментными ограничениями;
2) разработан алгоритм получения децентрализованной оценки квантили и найдено её асимптотическое распределение;
3) получено универсальное доказательство достаточных условий квазивогнутости и логарифмической вогнутости вероятностной меры;
4) разработан стохастический квазиградиентный алгоритм минимизации функции квантили и доказана его сходимость с вероятностью единица;
5) продемонстрирована работоспособность алгоритма на примере решения задачи оптимизации площади взлётно-посадочной полосы.
Практическая значимость. Диссертация обладает практической значимостью, поскольку полученные результаты позволяют быстро и эффективно решить прикладные задачи квантильной оптимизации.
Апробация работы. Результаты работы докладывались на следующих научных конференциях и симпозиумах: международные конференции “Системный анализ, управление и навигация” (Евпатория, 2007, 2008, 2009гг.), а также на научных семинарах в МАИ и ИПУ РАН.
Работа была поддержана грантами РФФИ №05-08-17963, №04-01Публикации. Основные результаты диссертации опубликованы в четырёх статьях [1-4] в журналах из Перечня ВАК, а также в трудах научных конференций [5-6].
Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения и списка литературы ( источников). Объем диссертации включает 103 машинописных страниц, включая 7 рисунков.
СОДЕРЖАНИЕ РАБОТЫ
Во введении обоснована актуальность исследуемой проблемы, сформулированы цель и задачи диссертационной работы, описана структура диссертации, перечислены полученные в ней результаты.
В первой главе рассматриваются различные оценки квантили.
Пусть имеется априорная выборка Xi, i = 1, n из независимых, одинаково распределенных случайных величин с плотностью вероятности fX (x). Тогда ядерная оценка квантили, соответствующая ядру k(x), определяется выражением где hn 0 при n, а X(i) i-й элемент вариационного ряда.
Для минимизации среднеквадратической ошибки ядерной оценки квантили сформирован следующий класс m при m 2 финитных функций с моментными ограничениями.
Введено понятие оптимального ядра в классе m с точки зрения минимума среднеквадратичного отклонения.
О п р е д е л е н и е 1.1. Назовем оптимальным в классе m ядро k (·) m, если Установлен вид оптимального в смысле определения 1.1 ядра для ядерной оценки квантили.
Т е о р е м а 1.1. Пусть плотность вероятности fX (x) дифференцируема в окрестности точки (0, 1) и fX (x ) > 0.
Тогда a) оптимальное в классе m ядро k (·) будет иметь вид где R2 (x) полином Лежандра 2-й степени;
б) смещение оценки определяется соотношением в) среднеквадратичная погрешность определяется соотношением M[|X (hn, k (·))x |2 ] = (1)(x )2 hn (x )2 +o(n1 hn ), (4) где X (hn, k (·)) ядерная оценка типа (1), x fX (x ).
Кроме того, приводится децентрализированная оценка, которая позволяет децентрализировать процесс нахождения квантили. Алгоритм базируется на использовании многопроцессорной архитектуры и позволяет находить значение квантили при достаточно общих ограничениях.
Предположим, что в нашем распоряжении имеется вычислительная сеть (см. рис. 1), состоящая из блока генерации данных, генерирующего независимые наблюдения и передающего их для обработки процессорам, процессоров, которые накапливают информацию о выборке и вычислительного блока, обрабатывающего данные, поступающие от процессоров.
Тогда децентрализованный алгоритм оценивания квантили уровня (0, 1) выглядит следующим образом:
1. n = 0. Сформировать выборку x1, x2,... случайной величины X с плотностью вероятности fX (x) > 0. Выбрать числовую последовательность n, n = 1, 2,..., удовлетворяющую следующим условиям Выбрать константу r > 0 и начальное значение квантили z0, одинаковое для всех r процессоров.
2. Вычислить значения индикаторных функций ai (zn ), i = 1,..., r 3. Вычислить усреднённую величину 4. Вычислить новую оценку квантили zn+1 следующим образом 5. Положить n = n + 1 и перейти к пункту 2.
Другими словами, предположим, что блок генерации данных содержит независимые наблюдения случайной величины X с плотностью вероятностей fX (x) > 0. На каждом шаге n = 0, 1,..., блок генерации данных передаёт (r · n + i)-е наблюдение случайной величины X в каждый i-й процессор i {1,..., r}. Далее каждый процессор i = 1, 2,..., r передаёт 1 бит ai (zn ), вычисленный по определённому алгоритму, описанному ниже, в вычислительный блок. Вычислительный блок обрабатывает полученную информацию и передает 1 бит bn+1 (zn ), вычисляемый определённым образом, назад каждому процессору в которых уточняется текущая оценка квантили zn.
1. Каждый i–й процессор вычисляет значение индикаторной функции используя реализацию xn+1 (i) случайной величины Xn+1, которую он получил из блока генерации данных, а затем передаёт её в вычислительный блок.
2. Вычислительный блок рассчитывает значение индикаторной функции по усреднённой величине, характеризующей полученную информацию от всех процессоров.
и передаёт её обратно каждому процессору.
3. Каждый процессор вычисляет новую оценку квантили zn+1 по формуле где определена в (8).
Т е о р е м а 1.2. Рассмотрим последовательность Zn, полученную с помощью описанного выше алгоритма. Тогда 1) для произвольного начального состояния z0 :
2) если константа r выбрана таким образом, что где определена в (8).
Во второй главе изучаются свойства выпуклости функции квантили. В основе результатов лежит понятие -вогнутой функции, которое является обобщением понятия выпуклой функции.
Пусть дана функция (u, x) : Rm Rs R1, измеримая по X и имеющая смысл функции потерь, которую необходимо минимизировать.
Вектор u размерности m имеет смысл управления, X случайный вектор с реализациями в Rs и плотностью вероятности fX (x).
Функции вероятности и квантили имеют вид где R1, (0, 1), а P(·) – вероятностная мера на Rs, определённая с помощью плотности fX (x).
Функция вероятности равна вероятность того, что потери при выбранной стратегии u не превысят заданный порог. Функция квантили показывает, что потери при выбранной стратегии u с вероятностью, не меньшей, не превысят значения (u).
Основным требованием, обеспечивающим вогнутость функции вероятности, является квазивогнутость вероятностной меры и выпуклость целевой функции. В диссертации используются следующие понятия.
О п р е д е л е н и е 1.2. (Prekopa) Вероятностная мера P называется квазивогнутой на Rs, если для любых двух выпуклых непустых множеств A, B Rs и для любого (0, 1) выполняется неравенство где A B обозначает сумму множеств A и B по Минковскому, т.е.
О п р е д е л е н и е 1.3. (Prekopa) Вероятностная мера P называется логарифмически вогнутой на Rs, если для любых двух выпуклых непустых множеств A, B Rs и для любого (0, 1) выполняется неравенство Т е о р е м а 1.3. (Кан, Кибзун) Если функция (u, x) выпукла на выпуклом множестве U X Rm Rs и вероятностная мера P квазивогнута, то функция квантили (u) является выпуклой на U.
квазивогнутости вероятностной меры используется понятие -вогнутой функции.
О п р е д е л е н и е 1.4. (Норкин, Роенко) Неотрицательная функция f (·) : Rs R1 называется -вогнутой на выпуклом множестве A Rs если для любого [0, 1] и для любых x, y A выполняются неравенства 1. если > 0, то 2. если < 0, то 3. если = 0, то Приведено достаточное условие, обеспечивающее квазивогнутость вероятностной меры.
что плотность вероятности fX (x) с выпуклым носителем X Rs оказывается -вогнутой на X. Тогда вероятностная мера P, порождённая плотностью fX (x), квазивогнута.
Доказательство этого утверждения было приведено у нескольких специалистов: Borell, Brascamp, Das Gupta, Prkopa, Rinott. Однако доказательства содержат ряд неточностей, о которых указано в диссертации. В диссертации приведено новое доказательство данного утверждения, лишенного этих недостатков. Доказательство носит достаточно универсальный характер и позволяет использовать его с небольшими модификациями для нахождения достаточных условий логарифмической вогнутости вероятностной меры.
логарифмически вогнута на R. Тогда вероятностная мера P, порождённая плотностью fX (x), является логарифмически вогнутой.
На основе теорем 1.3,1.4 и 1.5 получены достаточные условия для выпуклости функции квантили.
Т е о р е м а 1.6. Если функция (u, x) выпукла на выпуклом множестве U X Rm Rs и существует 1, такое, что плотность вероятности fX (x) с выпуклым носителем X Rs оказывается -вогнутой на X, то функция квантили (u) является выпуклой на U.
Третья глава посвящена стохастическому квазиградиентному алгоритму минимизации функции квантили.
Рассматривается задача стохастического программирования с использованием квантильного критерия где U Rm выпуклый компакт. Предположим, что точка минимума функции (u) на множестве U единственна.
Пусть для любого u U Rm есть возможность моделировать серию независимых выборок {(u, Xi )}nk функции (u, X). Обозначим через {(i) (u)}nk вариационный ряд выборки, т.е. расположенные в порядке возрастания значения На основе данного вариационного ряда сконструируем выборочную оценку квантили функции квантили случайный вектор где ui независимые равномерно распределенные случайные величины на отрезке [ui k, ui + k ].
Рассмотрен стохастический квазиградиентный алгоритм минимизации функции квантили.
1. k = 0. Положить начальное значение u(0) R(U ). Выбрать > 0, константу L таким образом, что почти наверное выполняется соотношение u {u : ||k (u, k )|| L} и числовую последовательность k.
2. Вычислить новое значение алгоритма следующим образом где u имеет равномерное распределение на множестве U, а U оператор рандомизированного проецирования на область U1, т.е.
отображение U : Rm U1, задаваемое соотношением где случайная величина u имеет равномерное распределение на 3. Положить k = k + 1 и перейти к шагу 2.
Доказана сходимость данного алгоритма к минимальному значению функции квантили на выпуклом компакте U.
Т е о р е м а 1.7. Пусть последовательность получена в результате описанного выше алгоритма и выполнены следующие условия:
(i) функция квантили (u) выпукла, удовлетворяет условию Липшица на выпуклом компакте U1 и почти наверное выполняется условие u {u : ||k (u, k )|| L};
(ii) для каждого u int(U1 ) функция вероятности P (u) непрерывно дифференцируема по и P (u) > 0 для всех R1 ;
(iii) последовательность k удовлетворяет условиям (iv) последовательность k удовлетворяет условиям max nk [nk ], [nk ]+1, такое, что (vi) mes {(u, x) U1 Rs : (u, x) = } = 0 для всех R1.
Тогда u(k) u, где последовательность u(k) образована алгоритмом (24), а u удовлетворяет (16).
Также приведён стохастический квазиградиентный алгоритм минимизации функции квантили на основе децентрализованного алгоритма оценивания квантили, который приведён в первой главе диссертации.
Предположим, что в нашем распоряжении имеется вычислительная сеть (см. рис. 2) состоящая из двух основных блоков: блока обработки результатов и блока вычисления квантили, состоящего из r процессоров, блока генерации данных и вычислительного блока. В блоке обработки результатов происходит уточнение текущей оценки минимума функции квантили, а в блоке вычисления квантили по текущему значению u(k) происходит вычисление новой оценки квантили, согласно алгоритму, описанному в первой главе диссертации.
Стохастический квазиградиентный алгоритм минимизации функции квантили при помощи децентрализованной оценки квантили выглядит следующим образом.
1. k = 0. Положить начальное значение u(0) R(U ). Выбрать > 0, константу L таким образом, что почти наверное выполняется соотношение u {u : ||k (u, k )|| L} и числовые последовательности k > 0, nk > 0, k > 0 таким образом, чтобы выполнялись соотношения ul независимые равномерно распределенные величины на отрезке 3. Сформировать выборку x1, x2,... случайной величины X с плотностью вероятности fX (x) > 0. Выбрать константу r > и начальное значение квантили i (u(k) ), одинаковое для всех r процессоров.
«