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

Поэтому за конечное число шагов мы перейдем в один из случаев 3.1-3.5.В результате получаем новый отрезок меньшей длины.При этом в силу предложенной процедуры на каждом шаге алгоритма неравенство(4) остается выполненным, и xk+1 − yk+1 ≤ 23 (xk − yk ), откуда и следует (5).4.Проверяем условие окончания алгоритма: |ak − bk | ≤ ε. Если условие выполнено, то переходим к шагу 5, иначе повторяем шаги 2-4.ak + bk5.Окончательно, для оценки xα , вычисляем xα =.2Из описания алгоритма видно, что ключевым моментом в успешной реализацииметода является конструирование последовательностей ηn− и ηn+ . Далее по тексту диссертации эти последовательности строятся для кусочно-линейной и квадратичной функциипотерь, зависящей от двумерного гауссовского вектора, а также для кусочно-линейнойфункции потерь, зависящей от трехмерного гауссовского вектора.

Во всех перечисленных случаях приводятся алгоритмы вычисления значений функций Fn+ (x) и Fn− (x),которые используются в изложенном выше алгоритме. Случай квадратичной функциипотерь, исследуется в первой главе, кусочно-линейные функции рассматриваются вовторой.Приводится описание процедуры вычисления квантилей нормы двумерного гауссовского вектора, в основе которой вышеописанный алгоритм.Двумерный случайный вектор ξ = (ξ1 , ξ2 )⊤ распределён по нормальному закону снулевым математическим ожиданием и невырожденной ковариационной матрицей K.Для заданного α ∈ (0, 1) определяется квантиль xα уровня α распределения нормы kξk.В частном случае α = 1/2 такая задача возникает при оценке кругового вероятностногоотклонения точки падения космического аппарата и рассмотрена в главе 3.Здесь же рассматривается задача вычисления вероятности попадания двумерногогауссовского вектора в эллипс, которая с помощью линейной замены переменных сво-9дится к вычислению интеграла1F (R) =2πγ(6)ZZ1y2− x2 +22γedxdy.x2 +y 2 ≤R2Заметим, что данный интеграл при γ 6= 1 не вычисляется аналитически.

При вычислении данной величины на компьютере, используя стандартные методы, для некоторыхисходных данных можно получить F (R) > 1, что исключает возможность оценкиквантильного критерия. Например, используя математический пакет Maple, при R = 5и γ = 0, 0001 получаем F (R) = 1, 000000357.Исходя из этого предлагается другая процедура вычисления вероятности попаданияв эллипс, основанная на вычислении вероятности попадания в круговые секторы.n+1nРис. 1: Оценка вероятности попадания в эллипсВ качестве аргументов для оценок Fn+ , Fn− выступают вычисленные с помощью п.2вышеописанного алгоритма значения ck , dk , а так же границы рассматриваемого на шагеk отрезка ak , bk . Так как эллипс симметричен относительно осей координат, то будемрассматривать только часть эллипса, расположенную в положительном квадранте.1.Часть эллипса, расположенная в рассматриваемом квадранте, делится на nπсекторов с одинаковыми углами ∆ϕ = 2n, как показано на рис. 1.

Переходим к шагу 2.2.Для оценки вероятности попадания в сектор эллипса рассматриваются двакруговых сектора со сторонами Rn и rn = Rn−1 (см. рис. 1), между которыми расположен эллиптический сектор, r1 = R0 = R. Вычисляем угол ϕn , а так же большую именьшую стороны круговых секторов.Rϕn = n∆ϕ Rn = p.γ 2 cos2 (ϕn ) + sin2 (ϕn )Переходим к шагу 3.103.какТак как вероятность попадания в круговой сектор с углом ∆ϕ вычисляется(7)∆F (R) =2− R21−e△ϕ,2πто вероятность попадания в эллиптический сектор может быть оценена сверху и снизувеличинамиR2r2− 2n− 2n△ϕ△ϕ+−Fn (Rn ) = 1 − e, Fn (rn ) = 1 − e.2π2πПереходим к шагу 4.4.Суммируем оценки,полученные на шаге 3.3. по всем эллиптическим секторам,тем самым находим оценки Fn+ , Fn− для ak , bk , ck , dk .!!nnR2r2XX− 2i− 2i(8)F− = 41−eи F+ = 41−e,i=1i=1где Ri и ri – больший и меньший радиусы для каждого рассматриваемого эллиптического сектора, n — число разбиений эллипса на секторы.Таким образом F − ≤ F (R) ≤ F + .

При увеличении n можно добиться нужнойF+ + F−точности оценивания и оценить вероятность попадания в эллипс F (R) =.2С учетом специфического деления эллипса на секторы, становится возможным вычисление гарантирующей границы погрешности оценок.Л е м м а 5. Справедливо соотношение2△ϕ − R2− R2+−2γe 2 −e.F −F =2πПервая глава заканчивается примерами расчетов оценок квантили для различныхзначений среднеквадратического отклонения и доверительной вероятности.Во второй главе описываются методы оценки квантильного критерия для системс кусочно-линейной структурой.Пусть ξ – n-мерный случайный вектор, распределенный по нормальному законуN(On , In ), где On – n-мерный вектор из нулей, In – единичная n × n матрица. Рассматривается кусочно-линейная функция потерь вида(9)Φ(ξ) = max aTi ξ + bi ,i=1,mгде ai — детерминированный n-мерный вектор, bi — детерминированная константа.Предполагается, что параметры функции (9) таковы, что она достигает своего минимума в некоторой точке z0 , и множество {z : Φ(z) 6 ϕ} является ограниченным выпуклыммногогранником в Rn для любого ϕ > Φ(z0 ).

Предполагается также, чтоmesn {z : Φ(z) = Φ(z0 )} = 0,где mesn – мера Лебега борелевских множеств в Rn .11Если обозначить η = Φ(ξ), то вероятностный критерий, выражениемF (ϕ) = P (Φ(ξ) 6 ϕ),является функцией распределения случайной величины η.Квантильный критерий для α ∈ (0, 1) определим выражением:ϕα = min{ϕ : F (ϕ) > α}.Величина ϕα является квантилью уровня α распределения случайной величины η иподлежит оценке.

Отметим, что в силу сделанных допущений ϕα ∈ (F (z0 ), +∞).Далее приводится алгоритм оценки вероятностной меры многоугольника. Рассматривается множество уровня A(ϕ) = {z : Φ(z) 6 ϕ}. В силу (9) A(ϕ) = {z : aTi z + bi 6 ϕ},а значит F (ϕ) = P (ξ ∈ A(ϕ)). Таким образом задача вычисления F (ϕ) сводится кнахождению вероятности попадания случайного вектора ξ в многоугольник, заданныйсистемой линейных неравенств. Предварительно определяются геометрические параметры многоугольника A(ϕ), находятся все вершины и ребра (наборы из двух соседнихвершин).1. Если начало координат находится внутри многоугольника, то переходим к шагу3, иначе к шагу 2.A maxA(φ)G1OnAminРис.

2: Иллюстрация к п.2 алгоритма2. Вычисляем вероятности попадания в две фигуры G1 и G1 ∪ A(ϕ) , см. рис. 2.Применяя к данным многоугольникам шаги 3-8 найдем оценки F + и F − для каждойфигуры. Вычитая из оценки вероятности попадания в большую фигуру оценку вероятности попадания в меньшую, получим искомое значение. Переходим к шагу 3.3.

Нумеруем ребра многоугольника в порядке их нахождения g1 , ..., gm и переходимк шагу 4.4. Разделяем многоугольник на треугольники, образованные центром On и ребрамиOn A1 , On A2 , On Am−1 , ..., On Am , см. рис. 3. Вероятность попадания в каждый треугольник будем искать, деля их на более мелкие. Если высота, проведенная из точки On ,12находится внутри треугольника A1 On A2 , будем разбивать этот треугольник на 2 найденной высотой h. Соответственно необходимо переобозначить вершины и увеличитьих количество на единицу Ak+2 = Ak+1 ,. . . , Am+1 = Am , Ak+1 = Ah ,где Ah — вершина, найденная при высоте.

Шаги 5-8 необходимо применить к каждому треугольнику.Переходим к шагу 5.A2B3A3B2B1A1Δγ ΔγA4OAmAm-1Рис. 3: Оценка вероятности попадания в многоугольник5. Лучами, выходящими из начала координат On , делим каждый треугольник на nболее мелких. Для этого находим величину угла ∠A1 On A2 как!222|On A1 | + |On A2 | − |A1 A2 |∠A1 On A2 = arccos,2|On A1 |2 |On A2 |2n A2. Переходими делим его на n углов, величины которых одинаковы и равны ∆γ = ∠A1 Onк шагу 6.6. Рассмотрим каждый треугольник On A1 B1 , On B1 B2 , .., On Bk A2 .

Для треугольникаOn A1 Bl найдем величину угла ∠A1 On Bl = γl = l∆γ. Здесь же найдем большую именьшую стороны для каждого рассматриваемого треугольника(10)Rl = On A1sin∠On A1 A2, R0 = On A1 , rl = Rl−1 .sin(π − γl − ∠On A1 A2 )Если Rl < rl то необходимо переобозначить эти величины. Переходим к шагу 7.7. Оценка вероятности попадания в каждый треугольник есть вероятность попадания в круговой сектор соответствующего радиуса. Найдем оценки снизу и сверху длявсех треугольников, используя Rl и rl :−rl2−R2∆γ −∆γl+(11)Fn = 1 − e 2, Fn = 1 − e 2.2π2πПереходим к шагу 8.138.

Суммируя все Fn+ и Fn− , получаем оценки вероятности попадания в каждыйтреугольник On A1 A2 , On A2 A3 ...On Am−1 Am :XX(12)Fm+ =Fn+ , Fm− =Fn− .kkПереходим к шагу 9.9. Суммируя все Fm+ (ϕ) и Fm− (ϕ) по m, получим оценки вероятности попадания вмногоугольник сверху и снизу.Здесь же приводятся формулы гарантированной границы погрешности вычислений,которые позволяют оценить количество разбиений каждого треугольника перед запуском алгоритма.Л е м м а 6. Справедливо соотношение−|On A1 |2−|On Am |2∆γ+−2F −F = e−e 2.2πДалее следует описание процедуры оценки вероятностной меры многогранника втрехмерном случае.Для решения вспомогательной задачи вычисления F (ϕ) = P (ξ ∈ A(ϕ)) , гдеA(ϕ) = {z : aTi z + bi 6 ϕ}, предварительно определяем геометрические параметрымногогранника A(ϕ) . С этой целью все грани A(ϕ) нумеруются и для каждой граниищутся координаты всех прилегающих к ней вершин.Для оценки искомой вероятности предлагается разделить каждую грань на треугольники, составить пирамиды, построенные из центра многогранника к этим треугольникам и рассматривать вероятности попадания в некоторые сферические секторы.Способ разделения грани на треугольники.Пусть имеется некоторая грань, у которой N вершин z1 , ..., zN .NPzi .1.