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

Переходим к шагу 4.3.6Если Fn− (ck ) < α < Fn+ (ck ) и Fn− (dk ) < α < Fn+ (dk ), то увеличиваем nна единицу и переходим к шагу 3.Зацикливание алгоритма ввиду бесконечного повторения шага 3.6 произойтине может в силу предположения о том, что xα − единственный корень уравнения11F (x) − α = 0. Поэтому за конечное число шагов мы перейдем в один из случаев3.1-3.5. В результате получаем новый отрезок меньшей длины.При этом в силу предложенного на каждом шаге алгоритма неравенство (4) остается выполненным, и xk+1 − yk+1 ≤ 32 (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 такая задача возникает приоценке кругового вероятностного отклонения точки падения космического аппарата.Здесь же рассматривается задача вычисления вероятности попадания двумерногогауссовского вектора в эллипс, которая с помощью линейной замены переменныхсводится к вычислению интеграла(6)F (R) =12πγZZ1y2− x2 +γ 2 dxdy.e 2x2 +y 2 ≤R2Заметим, что данный интеграл при γ 6= 1 не вычисляется аналитически. Привычислении данной величины на компьютере, используя стандартные методы, длянекоторых исходных данных можно получить F (R) > 1, что исключает возможностьоценки квантильного критерия.

Например, используя математический пакет Maple,при R = 5 и γ = 0, 0001 получаем F (R) = 1, 000000357.Исходя из этого предлагается другая процедура вычисления вероятности попадания в эллипс, основанная на вычислении вероятности попадания в круговые секторы.12Так как эллипс симметричен относительно осей координат, то будем рассматривать только часть эллипса, расположенную в первом квадранте.nn-1Рис. 1: Оценка вероятности попадания в эллипсДля оценки вероятности попадания в сектор эллипса предлагается рассмотретьдва круговых сектора с радиусами Rn и Rn+1 (см.

рис. 1), между которыми заключенадуга эллипса. Так как вероятность попадания в круговой сектор вычисляется какR2− 2n△ϕR(7)Fn (Rn ) = 1 − e, Rn = p, ϕn = n∆ϕ222πγ cos (ϕn ) + sin2 (ϕn )то легко найти все такие оценки для Rn и rn :(8)F−N N R2r2− 2n− 2n△ϕ X△ϕ X+1−e1−e=2иF =2,π n=1π n=1где Rn и rn — больший и меньший радиусы для каждого рассматриваемого эллиптического сектора, N — число разбиений эллипса на секторы.Таким образом F − ≤ F (R) ≤ F + . При увеличении N можно добиться нужнойF+ + F−.точности оценивания и получить вероятность попадания в эллипс F (R) =2С учетом специфического деления эллипса на секторы, становится возможнымвычисление гарантирующей границы погрешности оценок.Лемма 5.

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

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

Отметим, что в силу сделанных допущений ϕα ∈ (F (z0 ), +∞).Далее приводится алгоритм оценки вероятностной меры многоугольника. Рас-сматриваются множество уровня A(ϕ) = {z : Φ(z) 6 ϕ}. В силу (10) A(ϕ) = {z :aTi z + bi 6 ϕ}, а значит F (ϕ) = P (ξ ∈ A(ϕ)). Таким образом задача вычисления F (ϕ)сводится к нахождению вероятности попадания случайного вектора ξ в многоугольник, заданный системой линейных неравенств.Для удобства применения предлагаемых ниже алгоритмов нахождения вероятностных мер многоугольников полезно указать вершины многоугольника. Достаточно будет найти все ребра многоугольника и последовательно составлять треугольники из ребра и заданного центра. Под ребрами в данной процедуре будем пониматьнаборы из координат двух вершин.Далее рассматривается алгоритм вычисления оценок Fm+ (ϕ) и Fm+ (ϕ) для произвольного плоского многоугольника, который получается путем объединения алгоритма из доказательства теоремы 8 со специальным алгоритмом построения функцийFn+ и Fn− .

Алгоритм построения Fn+ и Fn− заключается в следующем:14Сначала определяются геометрические параметры многоугольника по заданнойсистеме линейных неравенств, после чего определяем где находится начало координат относительно найденной фигуры.1. Если начало координат находится внутри многоугольника, то переходим к шагу3, иначе к шагу 2.A maxA(φ)G1OnAminРис. 2: Иллюстрация к п.2 алгоритма2.

Вычисляем вероятности попадания в две фигуры G1 и G1 ∪ A(ϕ) , см. рис. 2.Для этого из центра проводим векторы через все вершины многоугольника и центр−−−→ −−−−→On A1 , ..., On Am . Вычисляем углы между всеми парами векторов как(14)x1 x2 + y1 y2parccos p 2x1 + y12 x22 + y22и находим два вектора, угол между которыми будет максимальным. Находим вершины, соответствующие этим векторам.

Обозначим их Amin и Amax . Проведем прямую(15)x − xAminy − yAmin=,yAmax − yAminxAmax − xAminразделяющую все ребра многоугольника на два множества. В первое войдут все ребра, вершины которых расположены от центра до прямой, т.е. если выполнено(16)yAk − yAminxAk − xAmin−6 0,yAmax − yAminxAmax − xAminдля каждой точки ребра. Во второе множество — все остальные. Первая фигура будетобразована ребрами из первого множества плюс ребра On Amax и On Amin , вторая —ребрами из второго множества, а так же On Amax и On Amin .

Применяя к данныммногоугольникам шаги 3-8 найдем оценки F + и F − для каждой фигуры. Вычитая15из оценки вероятности попадания в большую фигуру оценку вероятности попаданияв меньшую, получим искомое значение. Переходим к шагу 3.3. Нумеруем ребра многоугольника в порядке их нахождения g1 , ..., gm и переходим к шагу 4.4. Разделяем многоугольник на треугольники, образованные центром On и ребрами On A1 , On A2 , On Am−1 , ..., On Am , см.

рис. 3. Вероятность попадания в каждыйтреугольник будем искать, деля их на более мелкие. Если высота, проведенная източки On находится внутри треугольника 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 как!|On A1 |2 + |On A2 |2 − |A1 A2 |2∠A1 On A2 = arccos,2|On A1 |2 |On A2 |2и делим его на n углов, величины которых одинаковы и равны ∆γ =∠A1 On A2.nПере-ходим к шагу 6.6. Рассмотрим каждый треугольник On A1 B1 , On B1 B2 , .., On Bk A2 .