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

Кана [27], А.И. Кибзуна, В.Ю. Курбаковского [44],В.В. Малышева, А.И. Кибзуна [65].Для нахождения явного вида функции вероятности, как правило, аналитическихпреобразований сделать не удается. Это существенно сдерживает ее применение.Несмотря на это вероятность, в отличие от математического ожидания и дисперсии, является исчерпывающей статистической характеристикой первичной целевойфункции с произвольным распределением.6Для подсчета вероятности в инженерной практике используется метод статистических испытаний (Монте-Карло), обладающий простотой, универсальностью и позволяющий исследовать широкий класс моделей. Однако для проведения расчетовс использованием этого метода требуются большие вычислительные затраты, поскольку метод Монте-Карло основан на проведении многократных статистическихиспытаний исследуемой модели и оценке вероятности как частоты успешных испытаний.

Поэтому, к сожалению, существует большой разрыв между достижениямитеории и практическим применением этих достижений, во всяком случае – в оченьважной области, относящейся к исследованию задач динамики полета. Численныеметоды для решения задач анализа точности, возникающих при исследовании движения авиационных и космических ЛА, в которых в качестве критерия непосредственно использовались вероятность и квантиль рассматривались Малышевым В.В.,К.А Карпом [61,62], Ермаковым С.М., Жиглявским А.А. [20], Вентцель Е.С. [11], Володиным В.Д., Евдокименковым В.Н., Карловым В.И., Красильщиковым М.Н. [12],Кибзуном А.И., Каном Ю.С.

[43].Функция вероятности в задачах анализа систем управления техническими объектами, как правило, имеет вид кратного интегралаZPϕ = P (Φ(ξ) ≤ ϕ) =f (x)dx,Φ(x)≤ϕгде Φ(x) – исходная целевая функция, а f (x) – плотность вероятности вектора ξ случайных параметров. В прикладных задачах параметр ϕ обычно моделирует допустимую точность системы управления. Таким образом, функцию вероятности можно интерпритировать как характеристику "алгоритмической надежности"системыуправления.Сложность задач анализа систем управления с использованием функций вероятности и квантили обусловлена главным образом необходимостью точного вычисленияуказанного кратного интеграла.

Если размерность случайного вектора ξ достаточновелика, то для решения этой задачи обычно используются известные статистические методы, описанные ниже в главе 1. Для случая невысокой размерности (до 3-хвключительно) обычно стараются разработать детерминированные численные схемы. Ниже такие схемы предлагаются для двух практически важных случаев, когдаисходная целевая функция является квадратичной, либо кусочно-линейной по случайным параметрам. Предполагается, что последние распределены по нормальномузакону.В последнее десятилетие внимание исследователей задач оптимизации функционала квантили было сосредоточено главным образом на разработке численных методов решения конечномерных задач, в которых U ∈ Rm .

Все эти методы основаны7на доверительном подходе к решению квантильных задач оптимизации [65] и носятрекуррентный характер:uk+1 = fk (uk ),где k – номер шага (итерации). При этом на каждом шаге приходится для некотороготочностного функционала Φk (u, ξ) подбирать параметр ϕk таким образом, чтобыP (Φk (uk , ξ) ≤ ϕk ) ≥ α,см. например [68]. Это необходимо для того, чтобы множество {x ∈ Rn : Φk (uk , x) ≤ϕk } было доверительным. В [68] эта задача обозначена, но не решена ввиду ее сложности.

На решение этой проблемы и направлена настоящая диссертация. Рассматри-ваемая задача является по сути задачей анализа систем управления и в дальнейшемзависимость от u (или uk ) в тексте опускается.В диссертации предложен подход к синтезу новых алгоритмов оценки вероятностного и квантильного критериев.

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

Во-вторых, такие алгоритмы допускают естественное распараллеливание вычислений, что позволяет им успешно конкурироватьс существующими алгоритмами.Цель работы. Целью работы является построение алгоритмов для решения задач вероятностного анализа, в частности алгоритмов численного вычисления функций вероятности и квантили.Для достижения цели предполагается:1. Разработка численного метода вычисления квантильного критерия с заданнойточностью. Метод заключается в решении уравнения для функции распределения методом дихотомии с использованием специальным образом сконструированных ее верхних и нижних аппроксимаций.2. Разработка алгоритма вычисления квантильного критерия с заданной точностью для квадратичной функции потерь.3. Разработка алгоритма вычисления квантильного критерия с заданной точностью для кусочно-линейной функции потерь в двумерном и трехмерном пространствах.4.

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

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

Алгоритм генерирует не одну, а две последовательности, сходящиеся к искомому значению оцениваемого критерия.2. Разработан алгоритм вычисления квантильного критерия с заданной точностью для квадратичной функции потерь. Получены гарантирующие априорные оценки точности вычислений функции вероятности для сконструированнойквадратичной функции потерь.3. Разработан алгоритм вычисления квантильного критерия с заданной точностью для кусочно-линейной функции потерь в двумерном и трехмерном пространствах.

Получены гарантирующие априорные оценки точности вычисленийфункции вероятности для сконструированной кусочно-линейной функции потерь в двумерном пространстве.Практическая значимость. Диссертация обладает практической значимостью,поскольку полученные результаты позволяют эффективно решать прикладные задачи, связанные с вычислением вероятностных и квантильных критериев, в частности:в области техники — рассмотрена задача вероятностного анализа рассеиванияточек падения фрагментов летательного аппарата для оценки района поиска фрагментов.Структура и объем диссертации.Диссертация состоит из введения, трех глав, заключения и списка литературы(103 источника).

Объем диссертации включает 99 машинописные страницы, включая23 рисунка, 26 таблиц и 2 приложения.9СОДЕРЖАНИЕ РАБОТЫВо введении обоснована актуальность исследуемой проблемы, сформулированацель и задачи диссертации, описана структура работы, перечислены полученные вдиссертации новые результаты.В первой главе приводится обзор результатов в области вероятностного анализа. Приводится описание нового метода построения двусторонних оценок для квантильного критерия. Суть его в следующем.Пусть ξ- случайный вектор размерности m, Φ(x) : Rm → R1 - измеримаяпо Борелю функция. Тогда η = Φ(ξ) является случайной величиной с функциейраспределения(1)F (x) = P (η ≤ x) = P (Φ(ξ) ≤ x).Квантильный критерий (функция квантили) определяется выражением [43](2)xα = min{x : F (x) ≥ α},где α ∈ (0, 1) — доверительная вероятность.В приложениях функция Φ(·) обычно моделирует качество исследуемой системы.В этом смысле поставленную задачу можно интерпретировать как задачу вероятностного анализа системы при случайных возмущениях [65].Рассмотрим ηn− и ηn+ — последовательности случайных величин с функциями распределения Fn− (x) и Fn+ (x) соответственно, сходящиеся по распределению к η , причем Fn− (x) ≤ F (x) ≤ Fn+ (x) ∀x.Требуется оценить функцию квантили xα с заданной точностью ε, используя по-следовательности Fn+ (x) , Fn− (x).

Предполагается, что значения функций Fn+ (x) иFn− (x) вычислить намного проще, чем F (x).Т е о р е м а 8. Пусть для некоторых xk , yk ∈ R1 справедливы неравенстваFn− (xk ) > α,(3)Fn+ (yk ) < α.Тогда функция квантили xα , определенная выражением (2), удовлетворяет неравенству(4)yk < xα ≤ xk .Более того, если функция F (x) непрерывна на некотором отрезке [a, b] и xα ∈ (a, b)- единственный корень уравнения F (x) = α, то для каждого k можно подобратьxk , yk , удовлетворяющие (4) и такие, что(5)xk − yk → 0 при k → ∞.10Под индексом k в нижеописанных процедурах будем понимать шаг алгоритма,т.е. число шагов, за которые достигается конкретная точность оценивания квантилиε = |xk − yk |.

Индекс n далее характеризует точность оценивания функций Fn+ (x),Fn− (x). Например для описанной ниже процедуры нахождения вероятности попадания двумерного гауссовского вектора в эллипс, n есть число разбиений эллипса насекторы. Чем больше n, тем лучше точность оценки. В этом конкретном примеренайдена априорная зависимость точности оценивания |Fn+ (x) − Fn− (x)| от числа разбиений.Предлагается следующий алгоритм, порождающий последовательности xk , yk .1.Выбираем точность ε и полагаем n = 1, k = 1, где n — счетчик, отвечающийза точность Fn+ − Fn− оценки функции распределения F , а k – шаг алгоритма. Напервом шаге полагаем a1 = a, b1 = b, т.е. определяем границы отрезка, в которомпредположительно находится искомая величина.2ak + bk2.Делим отрезок [ak , bk ] на три части и находим точки= ck и32bk + ak= dk . Вычисляем значение функций Fn+ , Fn− в точках ck , dk и переходим3к шагу 3.3.Проверяем, где находятся вычисленные на шаге 2 значения и уменьша-ем отрезок путем присвоения старых границ новым.

Здесь возможны 6 вариантоврасположения значений:3.1Если Fn+ (ck ) < α ≤ Fn− (dk ), то значению ak присваиваем значение ck , азначению bk значение dk и увеличиваем k на единицу. Переходим к шагу 4.3.2Если Fn− (ck ) > α, то значение ak не меняем, а значению bk присваиваемзначение ck и увеличиваем k на единицу. Переходим к шагу 4.3.3Если Fn+ (ck ) < α и Fn− (dk ) < α < Fn+ (dk ), то значение bk не меняем,а значению ak присваиваем значение ck и увеличиваем k на единицу. Переходим кшагу 4.3.4Если Fn− (dk ) > α и Fn− (ck ) < α < Fn+ (ck ), то значение ak не меняем,а значению bk присваиваем значение dk и увеличиваем k на единицу. Переходим кшагу 4.3.5Если Fn+ (dk ) < α, то значение bk не меняем, а значению ak присваиваемзначение dk и увеличиваем k на единицу.