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

При этом данные табл. 3 показывают правильнуюработу предложенного алгоритма при тех же значениях входных параметров.47Таблица 4: Результаты вычисления оценок квантили для среднеквадратического отклонения γ = 0, 01Точность ε0,010,010,010,10,10,1Доверительная вероятность α0,950,990,60,950,990,6Оценка квантили снизу1,9552,5720,8381,9662,5240,796Оценка квантили сверху1,9642,5820,8451,9792,5970,8691.2.5Выводы по главе 1.Известные численные методы вероятностного анализа имеют ряд методологических недостатков, не позволяющих решать задачи оценивания значений вероятностных критериев с гарантированной, заданной наперед точностью.Предложен метод вычисления квантильного критерия с заданной точностью.

Метод основан на построении монотонно сходящихся детерминированных двустороннихграниц для квантильного критерия, определяемых по двусторонним монотонно сходящимся границам для функции вероятности. Метод успешно применен для решениязадачи оценки квантили нормы двумерного гауссовского вектора с произвольно коррелированными компонентами.482Построение двусторонних аппроксимаций для функции вероятности для кусочно-линейных функцийпотерь в гауссовском случае.2.1Оценка вероятностных мер для систем с кусочно-линейнойструктурой.2.1.1Постановка задачи .Пусть ξ — n-мерный случайный вектор, распределенный по нормальному закону N(On , In ), где On —n-мерный вектор из нулей, In — единичная n × n матрица.Рассмотрим кусочно-линейную функцию потерь видаΦ(ξ) = max aTi ξ + bi ,(99)i=1,mгде ai — детерминированный n-мерный вектор, bi — детерминированная константа.Будем предполагать, что параметры функции (100) таковы, что она достигает своегоминимума в точке z0 , и множество {z : Φ(z) 6 ϕ} является ограниченным выпуклыммногогранником в Rn для любого ϕ > Φ(z0 ).

Предположим также, что(100)mesn {z : Φ(z) = Φ(z0 )} = 0,где mesn - мера Лебега борелевских множеств в Rn .Если обозначить η = Φ(ξ), то вероятностный критерий, определенный согласно[43] выражением(101)F (ϕ) = P (Φ(ξ) 6 ϕ),является функцией распределения случайной величины η.Квантильный критерий для α ∈ (0, 1) определим выражением [43]:(102)ϕα = min{ϕ : F (ϕ) > α}.Величина ϕα является квантилью уровня α распределения случайной величиныη и подлежит оценке. Отметим, что в силу сделанных допущений ϕα ∈ (F (z0 ), +∞).2.1.2Алгоритм оценки вероятностной меры плоского многоугольника .Рассмотрим множество уровня A(ϕ) = {z : Φ(z) 6 ϕ}. В силу (1) A(ϕ) = {z :aTi z + bi 6 ϕ}, а значит F (ϕ) = P (ξ ∈ A(ϕ)).

Таким образом задача вычисления49F (ϕ) сводится к нахождению вероятности попадания случайного вектора ξ в многоугольник, заданный системой линейных неравенств. Для начала определим геометрические параметры многоугольника. Предлагается следующий алгоритм построения многоугольника из системы линейных неравенств:1. Полагаем i = 1, j = 2, l = 1.2. Составим из исходной системы, состоящей из L неравенств, подсистемы вида(aTi z + bi = ϕ, i = 1..L,aTj z + bj = ϕ, j = 1..L, i 6= j.Решая эти системы, будем иметь все пересечения прямых, входящих в исходные огра2ничения. Максимально имеем Cm=m!(m−2)!2!=m(m−1)2точек при l > 3. Для подсистем,одно из неравенств которой является линейной комбинацией второго, решений не будет, т.е. точку пересечения найти нельзя.Решаем систему и находим точку zl пересечения двух прямых, образованных изограничений.

Подставляем координаты найденной точки в исходную систему неравенств. Если все неравенства выполняются, то найденная точка является вершиноймногоугольника, увеличиваем l на единицу и переходим к шагу 3 иначе переходим кшагу 3 не меняя l.3. Если j < L то увеличиваем j на единицу и переходим к шагу 2. Иначе еслиi < L увеличиваем i на единицу и j = i + 1 и переходим к шагу 2. Когда i станетравной L переходим к шагу 4.Для удобства применения предлагаемых ниже алгоритмов нахождения вероятностных мер многоугольников полезно указать вершины ребер многоугольника. Достаточно будет найти все ребра многоугольника и последовательно составлять треугольники из ребра и заданного центра.

Под ребрами в данной процедуре будемпонимать наборы из координат двух вершин.4. Чтобы найти координаты вершин ребер будем искать пары вершин, удовлетворяющих уравнениям, составленным из из исходной системы, путем замены неравенства на равенства. Полагаем l = 1 и t = 1 переходим к шагу 5.5. Подставляем координаты zl в t уравнение. Если оно выполнено, то записываемэту точку как первый элемент ребра, присваиваем l = l + 1, переходим к шагу 6.Иначе увеличиваем l на единицу и переходим к шагу 5.6. Подставляем координаты zl в t уравнение. Если оно выполнено, то записываемэту точку как второй элемент ребра, переходим к шагу 7. Иначе увеличиваем t наединицу и переходим к шагу 5.7. Если t < L, то увеличиваем t на единицу, l = 1 и переходим к шагу 5, иначепереходим к шагу 8.508.

Окончательно получаем многоугольник, заданный набором ребер, состоящихиз двух точек.Предлагается следующий алгоритм оценки ϕα , который получается путем объединения алгоритма из доказательства теоремы 8 со специальным алгоритмом построения функций Fn+ и Fn− .1.Выбираем точность ε и полагаем n = 1, k = 1. На первом шаге определя-ются границы отрезка [a1 , b1 ], в котором находится искомая величина квантили ϕα :a1 = a, b1 = b. Границы могут быть выбраны путем использования оценок функцииквантили на доверительных множествах [43].2.Делим отрезок [ak , bk ] на три части и находим точки2bk + ak= dk .33.Построим функций Fn+ , Fn− в точках ck , dk .2ak + bk= ck и3В качестве аргументов для оценок Fn+ , Fn− выступают вычисленные на шаге 2 значения ck , dk , а так же границы рассматриваемого на шаге k отрезка ak , bk .

Используяалгоритм для определения геометрических параметров многоугольника, описанныйвыше, зададим многоугольник набором из вершин и ребер.3.1. Если начало координат находится внутри многоугольника, то переходим кшагу 3.3, иначе к шагу 3.2.A maxA(φ)G1OnAminРис. 10: Иллюстрация к п.3.2 алгоритма3.2. Вычисляем вероятности попадания в две фигуры G1 и G1 ∪ A(ϕ) , см. рис.

10.Для этого из центра проводим векторы через все вершины многоугольника и центр−−−→ −−−−→On A1 , ..., On Am . Вычисляем углы между всеми парами векторов как(103)x1 x2 + y1 y2parccos p 2x1 + y12 x22 + y2251и находим два вектора, угол между которыми будет максимальным. Находим вершины, соответствующие этим векторам. Обозначим их Amin и Amax . Проведем прямуюy − yAminx − xAmin=,yAmax − yAminxAmax − xAmin(104)разделяющую все ребра многоугольника на два множества. В первое войдут все ребра, вершины которых расположены от центра до прямой, т.е.

если выполненоxAk − xAminyAk − yAmin−6 0,yAmax − yAminxAmax − xAmin(105)для каждой точки ребра. Во второе множество — все остальные. Первая фигура будетобразована ребрами из первого множества плюс ребра On Amax и On Amin , вторая —ребрами из второго множества, а так же On Amax и On Amin . Применяя к данныммногоугольникам шаги 3.3-3.8 найдем оценки F + и F − для каждой фигуры. Вычитаяиз оценки вероятности попадания в большую фигуру оценку вероятности попаданияв меньшую, получим искомое значение.

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

В этом случае шаги 3.5-3.8 необходимоприменить к каждому треугольнику. Переходим к шагу 3.5.3.5. Лучами, выходящими из начала координат On , делим каждый треугольникна n более мелких. Для этого находим величину угла ∠A1 On A2 как!222|On A1 | + |On A2 | − |A1 A2 |∠A1 On A2 = arccos,2|On A1 |2 |On A2 |2и делим его на n углов, величины которых одинаковы и равны ∆γ =∠A1 On A2.nПере-ходим к шагу 3.6.3.6. Рассмотрим каждый треугольник On A1 B1 , On B1 B2 , .., On Bk A2 . Для треугольника On A1 Bl найдем величину угла ∠A1 On Bl = γl = l∆γ. Здесь же найдем большуюи меньшую стороны для каждого рассматриваемого треугольника(106)Rl = On A1sin∠On A1 A2, R0 = On A1 , rl = Rl−1 .sin(π − γl − ∠On A1 A2 )52A2B3A3B2B1A1Δγ ΔγA4OAmAm-1Рис.