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

На прав^,руко|^с

I

004693846

Матвеев Евгений Леонидович

ОПТИМИЗАЦИЯ КВАНТИЛЬНОГО КРИТЕРИЯ ПРИ ВЫПУКЛОЙ ЦЕЛЕВОЙ ФУНКЦИИ С ПОМОЩЬЮ СТОХАСТИЧЕСКОГО КВАЗИГРАДИЕНТНОГО АЛГОРИТМА

Специальность 05.13.01 Системный анализ, управление и обработка информации (авиационная и ракетно-космическая техника)

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических: наук

Москва, 2010

1 о июн 2010

004603846

Работа выполнена на кафедре Теории вероятностей Московского авиационного института (государственного технического университета).

доктор физико-математических наук, профессор Кибзун Андрей Иванович

доктор физико-математических наук, профессор Матасов Александр Иванович

кандидат физико-математических наук, доцент Руденко Евгений Александрович

Институт проблем управления им. В.А. Трапезникова РАН

Защита состоится "11" июня 2010 г. в 12 ч. 00 мин. на заседании Диссертационного совета Д 212.125.04 Московского авиационного института по адресу: 125993, Москва, А-80, ГСП-3, Волоколамское ш., 4, Ученый совет МАИ.

С диссертацией можно ознакомиться в библиотеке Московского авиационного института (государственного технического университета).

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

Автореферат разослан (^//¿tf1 2010 г.

Ученый секретарь Диссертационного совета Д212.125 кандидат физико-математических наук

Научный руководитель:

Официальные оппоненты:

Ведущая организация:

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Объект исследования. Диссертационная работа посвящена анализу и оптимизации конечномерных стохастических систем с квантильным критерием качества.

Актуальность темы. Поиск решения в практических задачах часто приходится вести в случае, когда некоторые исходные данные не являются детерминированными, а определяются случайными параметрами с известными законами распределения вероятностей. При детерминированном подходе к моделированию систем влияние случайных факторов не учитывается. Но с практической точки зрения в этом случае может быть потерян реализм присутствующих в задаче явлений. Например, при управлении летательными аппаратами необходимо решать задачу минимизации промаха, характеризующего точность попадания объекта в заданную область фазового пространства. В силу того, что на движение летательного аппарата оказывают воздействие случайные составляющие, задача сводится к минимизации функции со случайными параметрами. Одним из способов решения задач стохастического управления является сведение их к задачам стохастического программирования. Задачам стохастического программирования посвящены работы Дж. Бёржа, Р. Ветса, С. Волласа, Ю. М. Ермольева, П. Калла, Ю. С. Кана, А. И. Кибзуна, В. Купера, Р. Леппа, К. Марта, А. В. Назина, Н. М. Новиковой, Б. Т. Поляка, А. Прекопы, Э. Райка, С. П. Урясьева, А. Чарнса, Д. Б. Юдина и многих других авторов.

Естественный, на первый взгляд, путь анализа стохастических систем (замена случайных параметров их средними значениями и нахождение оптимальных управлений полученных таким образом детерминированных задач) не всегда оправдан и может нарушить адекватность модели изучаемого явления. Решение детерминированко!} задачи с усредненными параметрами может не удовлетворять условиям задачи при различных реализациях случайных факторов. Учёт неопределённости в рамках детерминированного подхода зачастую приводит к чрезвычайно пессимистическим выводам, например, множество допустимых решений может быть пусто. Та.ким образом, простейшие пути учета случайного характера условий задачи - замена случайных переменных их средними значениями или переход к жесткой постановке - не всегда приводит к осмысленному решению задачи стохастического программирования. В качестве разумного критерия, по которому производится оптимизация, является функция квантили.

Функция квантили характеризует гарантированный при заданном уровне вероятности результат принимаемого решения. При таком подходе маловероятные, наихудшие сочетания параметров исключаются из рассмотрения за счёт того., что риск их появления ограничивается на некотором допустимом уровне. Таким образом, оптимизация стохастических систем с квантильным критерием качества является актуальной проблемой. Исследованием этой проблемы занимались известные российские и зарубежные ученые в области теории управления, такие как Бахшиян Б. Ц., Зубов В. И., Кац И. Я., Кибзуи А. И., Колмановский В. Б., Красовский H. Н., Кузьмин В. П., Лидов М. Л., Матасов А. И., Назиров Р. Р., Черноусько Ф. Л., Эльясберг П. Е., Юби Э., Ярошевский В. А. и др.

При анализе систем в присутствии случайных параметров по квантильному критерию качества возникают определённые сложности.

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

В силу указанных причин при разработке численных методов для вычисления квантили приходится использовать различные аппроксимации. Так как в большинстве случаев точное распределение неизвестно, то вместо значения квантили распределения используется её статистическая оценка. Проблемой статистического оценивания квантили в разное время занимались Галамбош Я., Azzalini A., 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. и др.

Квартальный критерий относится к группе вероятностных критериев и впервые введен в рассмотрение С. Катаокой. Создание основ теории оптимизационных задач с таким критерием связано с именем эстонского математика Э. Райка и его учеников Р. Леппа, Э. Тамм и Э. Юби. Существенный вклад в развитие этой теории внесли С. Бойд, К. Марти, Домбровский В. В., Ермольев Ю. М., Кан Ю. С., Келли Дж., Кибзун А. И., Красильщиков M. Н., Малышев В. В., Норкип В. И., Панков А. Р., Роенко Н. В., Урясьев С. П. и др.

Задачи стохастического программирования, особенно при оптимизации по квантильному критерию, являются достаточно

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

Одним из наиболее эффективных путей решения задач стохастического программирования является использование стохастического квазиграднентпого алгоритма. Построением и изучением свойств квазиградиептов занимались Гун ал А. М., Ермольев Ю. М, Кан Ю. С, Кибзун А. И., Курбаковский В. Ю, Лепп Р., Михалевич В. С., Норкнн В. И., Поляк Б. Т., Роенко Н. В., Третьяков Г., Урясьев С. П., Юби Э. и др.

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

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

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

Достоверность результатов. Достоверность результатов обеспечивается:

1) строгостью постановок и доказательств утверждений;

2) приведением численных расчетов, подтверждающих справедливость результатов;

3) рассмотрением конструктивных примеров, которые демонстрируют достоверность приведенных результатов.

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

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

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

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

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

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

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

Апробация работы. Результаты работы докладывались на следующих научных конференциях и симпозиумах: международные конференции "Системный анализ, управление и навигация" (Евпатория, 2007, 2008, 2009гг.), а также на научных семинарах в МАИ и ИПУ РАН.

Работа была поддержана грантами РФФИ №05-08-17963, №04-0100758, №09-08-00369.

Публикации. Основные результаты диссертации опубликованы в четырёх статьях [1-4] в журналах из Перечня ВАК, а также в трудах научных конференций [5-6].

Структура и объем диссертации. Диссертация состоит из введения, трёх глав, заключения и списка литературы (100 источников). Объем диссертации включает 103 машинописных страниц, включая 7 рисунков.

СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе рассматриваются различные оценки квантили. Пусть имеется априорная выборка X¿, г = 1,п из независимых, одинаково распределенных случайных величин с плотностью

вероятности ¡х{х)- Тогда ядерная оценка квантили, соответствующая ядру к(х), определяется выражением

Ха(ЬП1к(-)) = ¿*(0

где 1гп —> 0 при п —» оо, а — г-й элемент вариационного ряда.

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

Ет = (ф) : зирр[£(з:)] = [-1,1], J к{х)йх = 1, ^ х1к{х)йх = О

J-l

для г = 1,т — 1,

г/а; < оо}.

Введено понятие оптимального ядра в классе Бт с точки зрения минимума среднеквадратичного отклонения.

Определение 1.1. Назовелг оптимальным в классе Ет ядро к*(-) & Ет, если

а) М[|Аа(Л„, &*(•)) - 1а|] -+ 0, п -»оо,

б) М[|Л'0(АП) *:*(•)) - ха\2] < М[|Х0(Л„,А(-)) - ха\2\ дм всех к{-) € Ет,п -* оо.

Установлен вид оптимального в смысле определения 1.1 ядра для ядерной оценки квантили.

Теорема 1.1. Пусть плотность вероятности /х{х) дифференцируема в окрестности точки а € (0,1) и /х(ха) > 0. Тогда

а) оптимальное в классе Ет ядро к'(-) будет иметь вид

**(*) = ^= з*2-1), (2)

где /?2(г) - полином Лежандра 2-й степени;

б) смещение оценки определяется соотношением

М[Ха(К, Г (•)) - ха] = о(Н1) + о(п-1); (3)

в) среднеквадратичная погрешность определяется соотношением

М[1А'а(Лп,Г(-))-а;а|21 = -а^а^-^ф'^+о^К), (4)

где Ха(кп,к'(-)) — ядерная оценка типа (1), х'а =

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

Блок генерации данных

Процессор

Процессор

// //ь„м

, х ;

Вычислительный Блок

Блок вычисления квантили

Рис. 1

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

Тогда децентрализованный алгоритм оценивания квантили уровня а £ (0,1) выглядит следующим образом:

А л г о р и т м 1.

1 .п — 0. Сформировать выборку 2:1,2:2,... случайной величины X с плотностью вероятности /х(х) > 0. Выбрать числовую последовательность рп, п = 1,2,..., удовлетворяющую следующим условиям

Рп

>0, = оо,

00.

п=0

п=О

Выбрать константу ц,- > 0 и начальное значение квантили z0, одинаковое для всех г процессоров.

2. Вычислить значения индикаторных функций а'(1+1(г„),г = 1,..., г

; / \ д I 1) если Хг п+1 ^ ¿П) ап+1\гп) = ^ „ 5)

10, иначе,

3. Вычислить усреднённую величину

Г1, если ¿¿0;1+1(2п) 0»+1(2п) = < ¡=1 (6) (О, иначе,

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

гп+1 = г„ + рпт)г (6,г+1 (г„) -13), (7)

где

М

0^СГга'(1~аГ\ (8)

¿=о

5. Положить п = п + 1 и перейти к пункту 2.

Другими словами, предположим, что блок генерации данных содержит независимые наблюдения случайной величины X с плотностью вероятностей /х{х) > 0. На каждом шаге п = 0,1,..., блок генерации данных передаёт (г • п + г)-е наблюдение, случайной величины X в каждый г-й процессор г € {1,...,г}. Далее каждый процессор г = 1,2,...,г передаёт 1 бит агп+1(гп), вычисленный по определённому алгоритму, описанному ниже, в вычислительный блок. Вычислительный блок обрабатывает полученную информацию и передает 1 бит Ьп+1(г„), вычисляемый определённым образом, назад каждому процессору в которых уточняется текущая оценка квантили гп.

1. Каждый г-й процессор вычисляет значение индикаторной функции < / , Л^ если 1п+1(г) ^ гп;

ап+1\2п) = < п (9)

10, иначе,

используя реализацию х^+^г) случайной величины Хп+1, которую он получил из блока генерации данных, а затем передаёт её в вычислительный блок.

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

если±2Х+1Ы<а; оп+1{гп) = < ¿=1 (10)

(0, иначе, и передаёт её обратно каждому процессору.

3. Каждый процессор вычисляет новую оценку квантили гп+1 по формуле

1 = гп + РпТ}г {Ьп+\{гп) ~ Р), (И)

где /3 определена в (8).

Теорема 1.2. Рассмотрим последовательность полученную с помощью описанного выше алгоритплш. Тогда

1) для произвольного начального состоянья г®:

ха при п —► со;

2) если константа т]г выбрана таким образом, что

2/х(х0)ОН(1 - ау-М-1

Пг > , , -ГП-ГТ' (12)

Г17 л л \Г (п

у/п (¿п-ха) —> N О,

2г1г/х{ха)т&ДаЩ1 - а)г-Н"1 - 1)

(13)

где 0 определена в (8).

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

Пусть дана функция Ф(м, х) : Нт х И8 —» Е1, измеримая по X и имеющая смысл функции потерь, которую необходимо минимизировать. Вектор и размерности ш имеет смысл управления, X — случайный вектор с реализациями в и плотностью вероятности /х(х)-

Функции вероятности и квантили имеют вид

рАи) ~ Г{Х ф(и>Х) < V}. ¥><»(«) = тт{р : Р9{и) > а},

где ip 6 R1, Q' e (0,1), a V(-) - вероятностная мера на Rs, определённая с помощью плотности fx(x)-

Функция вероятности равна вероятность того, что потери при выбранной стратегии и не превысят заданный порог /р. Функция квантили показывает, что потери при выбранной стратегии и с вероятностью, не меньшей а, не превысят значения <ра{и).

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

Определение 1.2. (Prtkopa, А.) Вероятностная мера V называется квазивогнутой на Л3,, если для любых двух ' выпуклых непустых множеств А, В е Е! и для любого Л б (0,1) выполняется неравенство

где А® В — обозначает сумму множеств А и В по Минковскому, т.е. А® В = {х + у : х е А.у £ В}.

Определение 1.3. (Ргекора, А.) Вероятностная мера V называется логарифмически вогнутой на если для любых двух выпуклых непустых множеств ДВ 6 1! « для любого X 6 (0,1) выполняется неравенство

Теорема 1.3. (Кан Ю., Кибзун А.) Если функция Ф(и,х) выпукла на выпуклом множестве V х X С И"1 х и вероятностная мера V квазивогнута, то функция квантили </>а(м) является выпуклой на и.

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

Определение 1.4. (Норкин В., Роенко Н.) Неотрицательная функция /(■) : К8 —> называется 7-вогнутой на выпуклом множестве А С если для любого X € [0,1] и для любых х. у 6 А выполняются неравенства

1. если 7 > 0, то

V (АЛ © (1 - А)В) > min {V{A),V(B)),

(14)

V {XA © (1 - Л)В) > Р*(А)Р1-\В).

(15)

Г(Хх + (1 - \)у) > Xр(х) + (1 - Л)Г(Уу,

2. если 7 < 0, то

Р(Хх + (1 - А)у) < ХГ(х) + (1 - Л)/7(у);

3. если 7 = 0, то

/(Лх + (1-Л)у)>/А(х)/1-А(1/).

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

Теорем a 1.4. Пусть существует 7 S [— ^,оо)\{0} такое, что плотность вероятности fx{%) с выпуклым носителем X С С В8 оказывается 7-вогнутой на X. Тогда вероятностная мера V, порождённая плотностью fx(x), квазивогнута.

Доказательство этого утверждения было приведено у нескольких специалистов: Borell, Brascamp, Das Gupta, Prekopa, Rinott. Однако доказательства содержат ряд неточностей, о которых указано в диссертации. В диссертации приведено новое доказательство данного утверждения, лишенного этих недостатков. Доказательство носит достаточно универсальный характер и позволяет использовать его с небольшими модификациями для нахождения достаточных условий логарифмической вогнутости вероятностной меры.

Теорема 1.5. Пусть плотность вероятности fx(x) логарифмически вогнута на Rs. Тогда вероятностная мера V, порождённая плотностью fx(x), является логарифлшчески вогнутой.

На основе теорем 1.3,1.4 и 1.5 получены достаточные условия для выпуклости функции квантили.

Теорема 1.6. Если функция Ф(и,х) выпукла на выпуклом множестве U х X С Rm х R' к существует 7 6 [—-¡,оо) такое, что плотность вероятности fxix) с выпуклым носителем X С ft* оказывается "у-вогпутой на X, то функция квантили tpa(u) является выпуклой na, U.

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

Рассматривается задача стохастического программирования с использованием квантильного критерия

иа = arg minpo (и), (16)

u£U

где U С Rm — выпуклый компакт. Предположим, что точка минимума функции tpa(u) на множестве U единственна.

Пусть для любого и 6 V С Шт есть возможность моделировать серию независимых выборок {Ф(и, функции Ф(и,Х). Обозначим через

{Ф(1)(и)}.^1 вариационный ряд выборки, т.е. расположенные в порядке возрастания значения

Ф<1)(") < Ф(2)(и) < - < $(«*)(")■

На основе данного вариационного ряда сконструируем выборочную оценку квантили

ФкЫ 4 Ф(Ка]+1)(«). (17)

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

1 ш ¿=1

(18)

где щ независимые равномерно распределенные случайные величины на отрезке [и; — IX; + <у.

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

1. к = 0. Положить начальное значение и^ ~ Выбрать е > 0, константу Ь таким образом, что почти наверное выполняется соотношение иа € {и: ||&(и,<5^)|| < Ь} и числовую последовательность рк-

2. Вычислить новое значение алгоритма следующим образом

и(Ш) Г М«<*)А)], А)1К (19х

где й имеет равномерное распределение на множестве V, а Пу оператор рандомизированного проецирования на область и^ т.е. отображение Пу : К."1 —>задаваемое соотношением

(20)

где случайная величина и имеет равномерное распределение на шаре

■ г

«1 - а^т.т||и -

v£U

В€ й |И1 6 и, : а = {и 6 Кт : Зг? € V такое, что ||и — < г}.

3. Положить к — к + 1 и перейти к шагу 2.

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

Теорема 1.7. Пусть последовательность получена в

результате описанного выше алгоритма и выполнены следующие условия:

(i) функция квантили <ра{и) выпукла, удовлетворяет условию Липшица на выпуклом компакте U\ и почти наверное выполняется условие иа € {и : ^ L};

(гг) для каждого и € int(£/i) функция вероятности Pv(u) непрерывно дифференцируема по <р и VvPv(u) > 0 для всех убЕ1;

(iii) последовательность Pk удовлетворяет условиям

ОО 00

Pk> 0, 5> = оо, ]Гр|<оо;

Ь=1 fc=l

(iv) последовательность 5k удовлетворяет условиям

ОО 00

О, У"—Г2<оо, У]т^7=<оо;

(v) существует 7 > О, удовлетворяюш,ее условию 7 >

такое> что

М[|Ф(и,Х)|7] < оо для всех ueUù

(vi) mes {(и, x) e U\ x Rs : Ф(и, x) = <p] = 0 для всех ip € R1.

Тогда u^ ua, где последовательность и'*' образована алгоритмом (24), а иа удовлетворяет (16).

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

Блок

обработки результатов

и / * У \ •

Блок генерации данных

\\

Ч \

Процессор I'.........Процессор:

\\

ч.\

\\ а,', |(Ф',('<!,)) ^ /У

\\ ' ' / '' Ч\ //

КЛФЛщ.,))

А..:(?.«'.-,)) \ ,................................................... //

ЧИСЛИ1

Блок

\ 1 I».-

\1 Вычислительный '

Блок вычисления квантили Рис. 2

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

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

А л г о р и т м 3.

1 .к — 0. Положить начальное значение и^ ~ 71(11). Выбрать г > 0, константу Ь таким образом, что почти наверное выполняется соотношение иа € {и: < Ь} и числовые

последовательности рь > 0,П£ > 0,(5^ > 0 таким образом, чтобы

выполнялись соотношения

= 00,^p? < 00,4 - < < Jfe=l fc=l fc=l ^ Jt=l v

2. Положить ы"1' = üjj, где ujj = col ..., u^p + ■ ■ ■, ür*^ , a ií¡ независимые равномерно распределенные величины на отрезке [u^-SbU^+Skil^üü, 1ф].

3. Сформировать выборку xi,xo,... случайной величины X с плотностью вероятности fx(x) > 0- Выбрать константу r¡T > О и начальное значение квантили иW), одинаковое для всех г процессоров.

4. Вычислить значения индикаторных функций ah+ii^phiu^)), i =

(21)

10, иначе,

5. Вычислить усреднённую величину

[О, иначе,

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

= + PnVr (ь„+Ш^)) - Р), (23)

где ¡3 определена в (8).

7. Если п < щ, то положить п = п + 1 и перейти к пункту 4. В противном случае перейти к пункту 8.

8. Вычислить

1=1

9. Вычислить

где и] независимые равномерно распределенные случайные величины на отрезке [и^ — и+ 4], I = 1, тп, I ф ]. После этого шаги 3-8 повторить для й^ = и^.

10. Вычислить

.. т

4) = 2Г Е [^(«й) -к ^

11. Вычислить новое значение алгоритма следующим образом

\ ü, ||fc(u<*>A)ll >

(24)

где ы имеет равномерное распределение на множестве £/, а Т1ц оператор рандомизированного проецирования на область /Ух, т.е. отображение Пу : И"1 —> задаваемое соотношением

пмл{ щиеи,

Пу(и) = < л (25)

I и,и$.и,

где случайная величина и имеет равномерное распределение на шаре

B^iureUr-

щ — arg mm и — г>

vtU

а Ui = {и 6 В"1: Зи 6 U такое, что ||ы — г>|| < е}.

12. Положить к — к +1 и перейти к шагу 2.

Глава завершается рассмотрением примера оптимизации площади взлётно-посадочной полосы. Данная задача рассматривалась ранее в работах Кана, Кибзуна, Курбаковского, Малышева.

Как показано у Кана, задача оптимизации площади эквивалентна следующей задаче квантильной оптимизации.

Va(ui>«2)—> min, (26)

Uj,U2>0

где ¡ра(и 1,112) — функция квантили уровня а для функции потерь Ф(щ,и2,Х,2), где

Ф(«ь «2, X, Z) ± тах {Ф^иь «г, X), X), Ф3(и2, Z)} , (27)

а функции Ф1(и1,и2,Х),Ф2(«1,И2,Х),Фз(ы2,£) определяются следующим образом.

Ф1(щ,щ,Х) =-—-, (28)

\/и2

Ф2(«1, «2, А) = —:--, (29)

у/Щ

= (30)

Оптимизация функции квантили проводилась двумя различными способами - квазиградиентным алгоритмом на основе выборочной оценки квантили (выборочный) и квазиградиентным алгоритмом на основе децентрализованной оценки квантили (параллельный). Значения стратегий н соответствующих им критериев сравниваются с аналитически гарантированным значением, полученным в работе Кана (аналитический).

а Метод «1 Щ Площадь, км2

0.99 выборочный 1,9189 27,014 0,173

параллельный 1,9210 27,098 0,169

аналитический 1 23.15 0.192

0.999 выборочный 1,424 22,043 0,2348

параллельный 1,416 22,132 0,2361

аналитический 1. 20.12 0.25

0.9999 выборочный 2,132 21,35 0,308

параллельный 2,150 21,236 0,310

аналитический 1 18.32 0.304

На. основании полученных данных можно сделать вывод, что оценка, полученная при использовании стохастического квазиградиентного алгоритма на основе децентрализованной оценки квантили, при малых объемах выборки ведет себя более устойчиво чем на основе выборочной, а при возрастании объема выборки они сближаются. Также можно сказать, что при достаточно высоком уровне вероятности а (больше 0,9999) оценка, полученная с помощью аналитического метода не сильно отличается от точного решения (первые два алгоритма).

ОСНОВНЫЕ РЕЗУЛЬТАТЫ, ВЫНОСИМЫЕ НА ЗАЩИТУ

1) Построена оптимальная ядерная оценка квантили в классе финитных функций с момептными ограничениями [1,5].

2) Разработан алгоритм получения децентрализованной оценки квантили и найдено её асимптотическое распределение |2].

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

4) Разработан стохастический квазиградиентпый алгоритм минимизации функции квантили и доказана его сходимость с вероятностью единица [6].

5) Продемонстрирована работоспособность алгоритма на примере решения задачи оптимизации площади взлётно-посадочной полосы. Публикации в журналах из перечня ВАК

1) Кпбзун А. И., Матвеев Е. Л. Оптимизация функции квантили на основе ядерных оценок // Автоматика и Телемеханика, 2007, № 1, С. 187

- 189.

2) Кибзуи А. И., Матвеев Е. Л. Алгоритм распараллеливания процесса оптимизации функции квантили // Вестник МАИ, 2008, Т.15, №2, С. 51 - 59.

3) Кпбзун А. И., Матвеев Е. Л. Достаточные условия квазивогнутости функции вероятности // Автоматика и Телемеханика, 2010, № 3, С. 54 -71.

4) Кибзуи А. И., Матвеев Е. Л. Стохастический квазиградиентный алгоритм минимизации функции квантили / / Автоматика и Телемеханика, 2010, № 6, С. 64 - 78.

Публикации в других изданиях

5) Кпбзун А. И., Матвеев Е. Л. Квантильная оптимизация на основе ядерных оценок // Проектирование и изготовление аэрокосмических аппаратов М.: Изд-во МАИ, 2006, С. 276 - 283.

6) Кибзуи А. И., Матвеев Е. Л. Квазиградиентный алгоритм минимизации функции квантили /'/ Тезисы межд. конф. "Системный анализ, управление и навигация", Евпатория, 2009, С. 96 - 97.

Подписано в печать:

29.04.2010

Заказ № 3672 Тираж - 100 экз. Печать трафаретная. Типография «11-й ФОРМАТ» ИНН 7726330900 П5230, Москва, Варшавское ш., 36 (499) 788-78-56 www.autoreferat.ru

Введение

1 Оценки квантили

1.1. Введение.

1.2. Выборочная оценка квантили

1.2.1. Определение выборочной оценки квантили.

1.2.2. Свойства первых моментов выборочной оценки квантили

1.3. Ядерная оценка квантили.

1.3.1. Определение и свойства ядерной оценки квантили.

1.3.2. Структура оптимального ядра.

1.4. Децентрализированная оценка квантили.

1.4.1. Определение децентрализированной оценки квантили

1.4.2. Свойства децентрализированной оценки квантили.

1.4.3. Сравнение децентрализированной оценки квантили с выборочной оценкой.

2 Свойства выпуклости функции квантили

2.1. Введение.

2.2. 7-вогнутные функции и их свойства.

Д.З. .Кваздаогнутррт^ .^ероятностцор, меры, . ;. ., . . ,>1;.л.,„,.

2.3.1. Определение квазивогнутости вероятностной меры.

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

2.3.3. Достаточные условия выпуклости и квазивыпуклости функции квантили.

2.3.4. Примеры.

2.4. Логарифмическая вогнутость вероятностной меры.

2.4.1. Определение логарифмической вогнутости вероятностной меры

2.4.2. Достаточные условия логарифмической вогнутости вероятностной меры.

2.4.3. Пример.

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

3.1. Введение.

3.2. Постановка задачи квантильной оптимизации.

3.3. Определение стохастического квазиградиента функции квантили

3.4. Стохастический квазиградиентный алгоритм на основе выборочной оценки квантили.

3.4.1. Стохастический квазиградиентный алгоритм минимизации функции квантили. , 3.4^2. ь Сходимость стохастического,- квазшрадиентного алгоритма на основе выборочной оценки квантили.

3.4.3. Пример использования стохастического квазиградиентного алгоритма на основе выборочной оценки квантили.

3.5. Распараллеливание процесса оптимизации функции квантили

3.5.1. Распараллеливание процедуры вычисления верхней оценки функции квантили.

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

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

3.6. Оптимизация площади ВПП.

3.6.1. Постановка задачи.

3.6.2. Эквивалентная задача квантильной оптимизации.

3.6.3. Обзор существующих методов решения задачи оптимизации площади ВПП.

3.6.4. Применение стохастического квазиградиентного алгоритма для оптимизации площади ВПП.

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

В настоящее время при синтезе и анализе алгоритмов управления широкое распространение получили задачи стохастического программирования. Их решению посвящены, например, работы [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. Завершается глава рассмотрением примера применения описанных квазиградиентных алгоритмов для оптимизации площади взлётно-посадочной полосы. Показано преимущество использования стохастических квазиградиентных алгоритмов перед использованием гарантирующего решения при малых уровнях доверительной вероятности а.

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

1. Афанасьев В. Н'.','Ко'лмаНовский В. Б., Носов В. Р. Математическая теория конструирования систем управления. - М.: Высш. шк., 1998.

2. Вахшиян Б. Ц., Назиров Р. Р., Элъясберг П. Е. Определение и коррекция движения. М.: Наука, 1980.

3. Богачев В. И. Гауссовские меры М.: Наука, 1997.

4. Вишняков Б. В., Кибзун А. И. Применение метода бутстрепа для оценивания функции квантили // Автоматика и Телемеханика, 2007, N0. 11. С. 46 60.

5. Галамбош Я. Асимптотическая теория экстремальных поряковых статистик // М.: Наука, 1984.

6. Деврой Л. Дьёрфи Л. Непараметрическое оценивание плотности. Ьг подход.• // М.: Мир, 1985. • ' .

7. Дзотцоев А. А., Кан Ю. С., Шахлевич П. К. Оптимизации прощади взлётно-посадочной полосы //Изв. РАН, Теория и системы управления, 2007, №6, С. 4449.

8. Ермольев Ю. М. Методы стохастического программирования М.: Наука, 1976.

9. Зорич В. А. Математический анализ. М.: Наука. 1984.

10. Зубов В. И. Лекции по теории управления. М.: Наука, 1975.

11. Иоффе А. Д., Тихомиров В. М. Теория экстремальных задач. М.: Наука, 1974.

12. Кан Ю. С. Квазиградиентый алгоритм минимизации функции квантили // Изв. РАН. Теория и системы управления, 1996, №2, С. 81-86.

13. Кан Ю. С. О сходимости одного стохастического квазиградиентного алгоритма квантильной оптимизации // АиТ, 2003, №2, С. 100-116.

14. Кан Ю. С., Кибзун А. И. Свойства выпуклости функции вероятности и квантили в задачах оптимизации // АиТ, 1996, №3, С. 82-102.

15. Кац И. Я. Метод функций Ляпунова в задачах устойчивости и стабилизации систем случайной структуры. Екатеринбург: изд-во Уральской, . государственной.академии путей, сообщения, 1998, . ,

16. Кенуй М. Г. Быстрые статические вычисления. М.: Статистика, 1979.

17. Кибзун А. И. Распараллеливание алгоритмов оптимизации функции квантили // АиТ, 2007. N0.5. С 59 70.

18. Кибзун А. И., Кан Ю. С. Задачи стохастического программирования с вероятностными критериями. М.: Физматлит, 2009.

19. Кибзун А. И., Курбаковский В. Ю. Численные алгоритмы квантильной оптимизации и их применение к решению задач с вероятностными ограничениями // Изв. АН СССР. Техн. кибернетика 1991. N0. 1. С. 75-81.

20. Кибзун А. И., Матвеев Е. Л.Оптимизация функции квантили на основе2007;4о,1,С,187 -,189; --------- .„ ,

21. Кибзун А. И., Матвеев Е. Л. Алгоритм распараллеливания процесса оптимизации функции квантили // Вестнк МАИ, 2008, Т.15, №2, С. 51 59.

22. Кибзун А. И., Матвеев Е. Л. Достаточные условия квазивогнутости функции вероятности // АиТ, 2010, N0 3, С. 54 71.

23. Кибзун А. И., Матвеев Е. Л. Стохастический квазиградиентный алгоритм минимизации функции квантили // АиТ, 2010, N0 6, С. 64 78.

24. Кибзун А. И., Наумов А. В. Гарантирующий алгоритм решения задачи квантильной оптимизации // Космические исследования, 1995, т. 33, № 2. С. 160-165.

25. Колмановский В. Б. Об управлении по вероятности некоторыми системами // Прикладная математика и механика, 1976, т.40, вып.5, сс.782-789.

26. Коростелёв А. П. Стохастические рекуррентные процедуры. Локальные свойства М.: Наука. 1984.

27. Красовский Н. Н. Об оптимальном регулировании при случайных возмущениях // Прикладная математика и механика, 1960, т.24, вып.1, сс.64-79.

28. Кузьмин В. П., Ярошевский В. А. Оценка предельных отклонений фазовых координат динамической системы при случайных возмущениях. М.: Наука, 1995.

29. Лепп Р. Минимизация гладкой функции при вероятностных ограничениях // Изв. АН ЭССР. Физ.-мат., 1980. Т.29 N0.2. Р. 140 144.

30. Лепп Р. Детерминистические эквиваленты задач стохастического программирования с эллиптически симметричными распределениями // Изв. АН ЭССР. Физ.-мат., 1979. Т.28 N0.2. Р. 158 160.

31. Лидов М. Л., Лукьянов С. С. Задача о времени движения точки в области при случайных ошибках управления // Космические исследования, 1971, т.9, вып. 5, сс.707-722.

32. Люстерник Л. Неравенство Брунна-Минковского для измеримых по Лебегу множеств // Докл. АН СССР. 1935. Т. 3. №2. С. 55-58.

33. Малышев В. В., Кибзун А. И. Анализ и синтез высокоточного управления летательными аппаратами // М.: Машиностроение, 1987.

34. Мирошкин В. Л. Алгоритм квантильного оценивания неизвестного параметра // Теория и системы управления. 1996. Т.2. №2. С. 56-80.

35. Михалевич В. С., Гупал А. М., Норкин В. И. Методы невыпуклой оптимизации М.: Наука, 1987.

36. Норкин В. И., Роенко Н. В. а-вогнутые функции и меры и их применения //Кибернетика и системный анализ. 1991. №6. С. 77-88.

37. Пантелеев А. В. Оптимальные нелинейные системы управления: синтез при неполной информацииМ.: Вузовская книга, 2008.

38. Поляк Б. Т. Введение в оптимизацию М.: Наука, 1983.

39. Поляк Б. Т., Цыпкин Я. 3. Псевдоградиентные алгоритмы адаптации и обучения // Автоматика и Телемеханика, 1973, №3, С. 45-68.

40. Пугачев В. С. Лекции по функциональному анализу М.: Изд-во. МАИ, 1996.

41. Райк Э. О функции квантили в задачах стохастического нелинейного. программирования //.,Изв,,.АН„ЭССР, Физг-маяу1971. 24. N0. Д. С.- З 8.

42. Райк Э. Качественные исследования в задачах стохастического нелинейного программирования // Изв. АН ЭССР, физ.-мат., 1971, 20, № 1, сс. 8-14.

43. Райк Э. О функции квантиля в стохастическом нелинейном программировании // Изв. АН ЭССР, физ.-мат., 1971, 20, № 2, сс. 229231.

44. Райк Э. О задачах стохастического программирования с функционалами вероятности и квантиля // Изв. АН ЭССР, физ.-мат., 1972, 21, № 2, сс. 142-148.

45. Райк Э. Дифференцируемость по параметру функции вероятности и стохастический псевдоградиентный метод для ее оптимизации // Изв. АН ЭССР, физ.-мат., 1975, 24, № 1, сс. 3-9.

46. Тамм Э. О квазивыпуклости функций вероятности и квантили // Изв. АН ЭССР Физ.-мат., 1976. Т.25. N0.2. С.141 143.

47. Тамм Э. О минимизации функции вероятности // Изв. АН ЭССР. Физика. Математика. 1979, 28, № 1, сс.17-24.

48. Ширяев А. Н. Вероятность 1 М.: МЦНМО, 2004.

49. Урясъев С. П. Адаптивные алгоритмы стохастической оптимизации и теории игр. М.: Наука, 1990.

50. Эфрон Б. Нетрадиционные методы многомерного статистического анализа. М.: Финансы и статистика, 1988.

51. Элъстер К. X. Введение в нелинейное программирование М.: Наука, 1985.

52. Юби Э. Статистическое исследование задач стохастического программирования и метод их решения // Изв. АН ЭССР. Физика. Математика. 1977, 26, № 4, сс.369-375.

53. Юби Э. Минимизация функции вероятности методом статистического моделирования // Труды Таллинского политехнического института, 1976, 411, сс.57-76.

54. Юдин Д. Б. Математические методы управления в условиях неполной информации // М.: Советское радио, 1974.

55. Юдин Д. Б. Задачи и методы стохастического программирования // М.: Советское радио, 1979.

56. Ambrosio L., Giuseppe S., Zambotti L. Existence and stability for Fokker-Planck equations with log-concave reference measure // Probab. Theory Relat. Fields, 2009, 145, P. 517-564.

57. Azzalini A. A note on the estimation of a distribution function and quantiles by a kernel method // Biometrica, 68, С. 326-328.

58. Bahadur R. R. A note on quantiles in large samples // Ann. Math. Statist., 1966, No. 37. P. 577 580.

59. Barihe F. Log-concave and spherical models in isoperimetry // GAFA, Geom. funct. anal., 2002, V. 12. P. 32-55

60. Bartlett M. S. Statistical estimation of density functions // Sankhya Series A, 1963, V. 25. P. 245-254

61. Benveniste A., Metivier M., Priouret P. Adaptive Algorithms and Stochastic Approximations Springer-Verlag, New York, NY, 1990.

62. Bretagnolle J., Huber C. Estimation de densites: risque minimax // Zeitschrift für Wahrscheinlich keitstheorie und verwandte Gebiete, 1979, V. 47, P. 119-137

63. Bobkov S. G., Ledoux M. Weighted Poincare-type inequalities for Cauchy and other convex measures // The Annals of Probability, 2009, V. 37, No. 2, P. 403-427

64. Borell G. Convex set functions in d-spaces // Periodica Mathematica Hungari-ca. 1975. V. 6. No. 2. P. 111-136.

65. Brascamp H.J., Lieb E.H. On extensions of the Brunn-Minkowski and Prekopa-Liendler theorems, including inequalities for log-concave functions, and with application to the diffusion equations //J. Functional Analysis. 1976. V. 22. P. 366389.

66. Gardner R. J. The Brunn-Minkowski Inequality // Bulletin (New Series) of the American Mathematical Society, V. 39, No. 3, P. 355-405.

67. Das Gupta S. Brunn-Minkowski inequlity and its aftermath //J. Multivariate Analysis. 1980. V. 10. P. 296-318.

68. David H.A., Nagaraja H.N. Order Statistics. Third Edition John Willey, New Jersey, 2003.

69. Falk M. Relative deficienty of kernel type estimators of quantiles // Universitat-Gesamthochschule Siegen, 1983, Vol. 12, No. 1, C. 261-267.

70. Gaivoronski A. A., Pfug G. Finding optimal portfolios with constraints on value at risk //In Proceedings of III Stockholm Seminar on Risk Behavior and Risk Management, 1999.

71. Gaivoronski A. A., Pfug G. Value at Risk in Portfolio Optimization: Properties and Computational Approach // Working Paper 00/2, Norwegian University of Science and 28 Technology, 2000.

72. Kail P., Wallace S. W. Stochastic Programming // Chichester: John Wiley & Sons, 1994.

73. Kahn J., Yang Yu. Log-concave functions and poset probabilities // Combinatoria, 1998, V. 18, P. 85-99

74. Klartag B. A Berry-Esseen type inequality for convex bodies with an unconditional basis // Probab. Theory Relat. Fields, 2009, V. 145 P. 1-33

75. Kibzun A. I., Kurbakovkiy V. Yu. Guaranteeing approach to solving quantile otimization problems // Ann. Oper. Research. 1991, V. 30, P. 81-93.

76. Kibzun A. I., Kuznetsov E. A. Analysis of criteria VaR and CVaR //J. of Banking and Finance, 2006, V. 30, P. 779-796.

77. Kushner H. J., Yin G. G. Stochastic Approximation and Recursive Algoritms and Applications Springer-Verlag, New York, NY, 2003.

78. Lepp R. Stochastic approximation type algorithm for the maximization of the probability function // Eesti NSV Teaduste Akademia Toimetised, Fiiusika * Matemaatika, 32, No. 2, C. 150-156.

79. Nadaraya E. A. Some new estimates for distribution functions // Theory Probab.'Appl., 9^C. 497-500. ' ' *'' '

80. Parzen E. Nonparametric Statistical Data Modeling //J. Amer. Statist. Association, 1979, Vol. 74, No. 365, C. 105-131.

81. Pecaric J. On Hadamard Inequality for Log-Concave Functions // Southeast Asian Bulletin of Mathematics, 2002, V. 26, P. 307-312.

82. Pinelis I. Exact inequalities for sums of asymmetric random variables, with applications // Probab. Theory Relat. Fields, 2007, V. 139, P. 605-635.

83. Prekopa A. Logarithmic Concave Measures with Application to Stochastic Programming 11 Acta Sci. Math. (Szeged), 1971, 32, pp.301-316.

84. Prekopa A. On logarithmic concave measures and functions // Acta Scientiarum

85. Mathematicarum. 1973. V. 34. P." 335-343.

86. Prekopa A. Logarithmic Concave Measures and Related Topics. In: Stochastic Programming, ed. M.A.H.Dempster. London: Academic Press, 1980, pp.63-82.

87. Prekopa A. Stochastic programming Kluwer, Dordrecht, Netherlands, 1995.

88. Raik E. On the Stochastic Programming with the Probability and quantile Function // Eesti NSV Teaduste Akademia Toimetised, Fiiiisika -Matemaatika, 1972, 21, No.2, C. 142-148.

89. Reiss R. D. Nonparametric estimation of smooth distribution function // Scand. J. Statist. 8, C. 116-119.

90. Reiss R.D. Approximate Distributions of Order StatisticsSpringer, New York, pp. 207-212.

91. Rinott Y. On convexity of measures // Ann. Probability. 1976. No. 6, P. 1020-1026.

92. Shao Y., Xiang X. Some extensions of the asymptotics of a kernel estimator of a1.• , . V" t ' >distribution function // Statistics and Probability Letters, 34, C. 301-308.

93. Sheather S. J., Marron J. S. Kernel Quantile Estimators // Journal of the American Statistical Associations, 1990, Vol. 85, No. 410.

94. Tamm, E. Estimation of quantiles avoding order statistics // Research Report Math. 55/92. Inst. Cybernetics, Estonian Academy Sei., 1992.

95. Tamm E. On g-concave Functions and Probability Measures // Изв. АН ЭССР, физ.-мат., 1977, 26, № 4, cc.376-379.

96. Tamm E. On Minimization of a Function under an Equality Chance Constraint // Math. Operationsforsch. Statist., Ser. Optimization, 1981, 12, No.2, pp.253-262.

97. Xiang X. A Berry-Essen theorem for the kernel quantile estimator with application to studying the deficiency of quantile estimators // Ann. Inst. Statist. Math., 1995, Vol. 47, No. 2.

98. Xiang X. A Kernel Estimator of a Conditional Quantile // Journal of multivariate analysis, 59, C. 206-216.

99. Xiang X. Estimation of a quantile in some nonstandard cases // Ann. Inst. Statist. Math., 1995, Vol. 47, No. 1.

100. Yang S. A Smooth nonparametric Estimator of a quantile function // Journal of the. American Statistical Associations,. 1985, Vol.80, No. 392.