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

Поскольку ⊂ , то есть лежит внутри , при этом некасаясь его границ, а целевая функция ¯(, ), определяемая согласно (2.12), линейна по ,то получаем неравенство( , ) < ( , ) = .Но стратегия — необязательно оптимальная для ( , ). Поэтому выполняется следующее неравенствоΔ = ( , ) = min ( , ) < .∈По доказанному выше для стратегии выполняется ( ) ≥ , то есть ( ) ≥ .

Но поопределению функции квантили ( ) = min{ : ( ) ≥ }.Поэтому ( ) ≤ .Поскольку стратегия не обязательно является оптимальной стратегией для критерия (), что означает выполнение неравенства ≤ ( ), поэтому окончательно имеем ≤ ( ) ≤ < .3. Пусть теперь 2 > 1 , где 1 , 2 ∈ [0 , ), (2 ) ≥ и (1 ) ≥ . Получим ≤ 1 < 2 .Для доверительных шаров с радиусами 1 и 2 выполняется 1 ⊂ 2 , поскольку2 > 1 .

В силу линейности по реализации функции из (2.12), получаем неравенство(1 , 2 ) < (2 , 2 ) = 2 .58Поскольку стратегия 2 не обязательно является оптимальной для (1 , ), то для(1 , 1 ) = 1 выполняется следующее неравенство1 < 2 .Введём функцию квантили, характеризующую значение минимального порога прикотором выполняется вероятностное ограничение (1 ) ≥ (1 ) = min{ : (1 ) ≥ }.Поскольку (1 ) ≥ , а, следовательно, 1 (1 ) ≥ , то (1 ) ≤ 1 .Для критерия () выполняется ≤ () ≤ (1 ). Учитывая все вышесказанное, получаем неравенство ≤ 1 < 2 .Таким образом, теорема 2.1 полностью доказана. 2Рассмотрим более общий случай, когда случайный вектор имеет нормальное распределение вида (, ), где — невырожденная ковариационная матрица. Введём новыйвектор = −1/2 ( − ),который имеет нормальное распределение (⃗0, ). При такой замене переменных на ограничения, задающие множество допустимых стратегий второго этапа (, ), преобразуются в множество (, ), ограничения которого будут иметь точно такую же структуру,как и ограничения, описывающие множество (, ).

Таким образом, случай ∼ (, )сводится к случаю стандартного нормального распределения ∼ (⃗0, ), рассмотренномуранее.592.3.2.Алгоритм решения задачи выпуклого программированияЗадача, рассмотренная в разделе 2.1, с помощью доказанных в разделе 2.2 утверждений сведена к задаче выпуклого программирования. Для решения данной задачи предлагается следующий алгоритм.Рассмотрим вначале способ поиска точки 0 , определяемой выражением (2.28). Дляэтого используем алгоритм дихотомии в следующей модификации. Выберем точки = и = , для которых ( ) ≤ и ( ) ≥ .

Рассмотрим точку = ( + )/2 и найдемзначение вероятностной меры ( ) (алгоритм вычисления вероятностной меры ( ) приводится далее). Если ( ) ≥ , то далее оставляем точки и . Если же ( ) < , тооставляем точки и . И так далее производим деление пополам текущих отрезков неопределенности. Алгоритм сходится, поскольку ( ) ≤ и ( ) ≥ . Скорость сходимостиэтого алгоритма равна 1/2 , где — количество делений отрезков неопределенности пополам.Предложим теперь алгоритм вычисления ( ) для произвольного ∈ [, ]. С этойцелью дискретизируем меру так, как предложено в разделе 1.2.

Пусть , = 1, , —точки, сгенерированные на основе плотности нормального распределения (⃗0, ). Пусть = 1/ — вероятностная мера, приписанная к точке , = 1, . Таким образом, полу˜ аппроксимирующую гауссову меру . Заменим меру на меру ˜ при вычисчаем меру ,лении ( ). Пусть для некоторого ∈ [, ] найдены и в результате решения задачивыпуклого программирования = min ( , ), = arg min ( , ),∈∈(2.29)где выпуклая функция ( , ) определяется согласно (2.19).

Для решения задачи (2.29)можно использовать какие-либо эффективные методы выпуклого программирования [14],например метод внутренней точки.˜ ) множества , определяеРассмотрим процедуру поиска вероятностной меры (мого выражением (2.27)T = { : TT ( , ) ] ≤ }.0 + 1 + max [¯=1,Поскольку ⊂ , то исключим из рассмотрения точки ∈ . Отметим, что вероятностная мера ( ) множества известна и вычисляется по формуле (2.24), в которой нужнозаменить на , а — на получаемую меру ( ). Тогда˜ ∖ ) + ( ).( ) = ( ∖ ) + ( ) ≈ (60˜ ∖ ) может быть найдена за счёт перебора лишь точек , лежащих внеПри этом мера ( .

Таким образом, вычисление вероятностной меры ( ) множества резко упрощается.По сути, описанная процедура вычисления ( ) является реализацией методаМонте-Карло, из которой исключены точки, принадлежащие шару .Алгоритм, подобный описанному выше, был предложен ранее в работе А.И. Кибзунаи А.В. Наумова [34], и применен впоследствии для задачи из другой работы А.И. Кибзунаи А.В. Наумова [35]. Но в указанной работе ограничения, описывающие множество (, ),были линейными одновременно по и , а алгоритм, предложенный в данной главе, применяется для ограничений в (, ), линейных отдельно по и (билинейных). Таким образом,алгоритм, описанный в работе А.И. Кибзуна и А.В.

Наумова [34], является частным случаемалгоритма данной главы.Алгоритм решения задачи выпуклого программирования основан на том факте, чтослучайный вектор имеет нормальное распределение (см. условия леммы 2.2). Следуетотметить, что класс распределений случайного вектора может быть расширен, в частности,вектор случайных факторов может иметь сферически симметричное распределение. В этомслучае почти все приведённые рассуждения остаются верными, изменяются только размерыдоверительного шара и ядра вероятностной меры.612.4.Результаты решения двухэтапной задачи квантильной оптимизациис билинейной функцией потерьВ данном разделе приводятся результаты применения алгоритма поиска решениядвухэтапной билинейной задачи стохастического программирования с квантильным критерием.Пример 2.1.Рассмотрим пример двухэтапной задачи, в которой функция потерь имеет вид:TΦ(, ) = T0 + + Φ̄(, ),гдеTTΦ̄(, ) = min{T1 | 2 + ≥ },∈ = = 1 = = 2, вектор случайных параметров T = (1 , 2 ); стратегии первого этапаT = (1 , 2 ).TПараметры задачи принимают следующие значения: T0 = (3, −4); 1 = (6, 3); = 0, 1,T = 2, 5; T1 = (2; −2, 5); 2 = (−2; 4);⎛21 = ⎝1 10 4⎞⎛⎠, 22 = ⎝−2 326⎞⎠.Пусть ∼ (⃗0, ), где — единичная ковариационная матрица.

Рассматриваемаяфункция потерь соответствует постановке (2.1) — (2.2).Найдемрешениеэтойзадачидлятрехзначенийуровнявероятности = 0, 9; 0, 99; 0, 999. В зависимости от уровня вероятности и количества точекдискретизации , = 1, , сгенерированных согласно плотности распределения, получимрешение задачи (2.2) — (2.6). Результаты численных расчётов приведены в таблице 2.1.В таблице 2.1 в крайнем правом столбце приведено время счёта алгоритма в секундах для разного количества реализаций и уровня вероятности . Вычисления производилисьна персональном компьютере с характеристиками: процессор — 2,5 GHz Intel Core i5; оперативная память — 4 ГБ 1600 МГц; операционная система — OS X 10.9.Следует отметить, что при увеличении числа точек дискретизации на несколькопорядков время счёта увеличивается незначительно, кроме того, время счёта для одного итого же значения при разных значениях вероятности различается несущественно.

Этосвязано прежде всего с тем, что оптимизационная минимаксная задача (2.16) слабо зависитот уровня вероятности (длина интервала неопределенности [ , ] практически не зависит62от при больших его значениях). Кроме того, за счёт описанной выше процедуры сокращения перебора точек при вычислении вероятности по методу Монте-Карло перебираютсялишь точки, лежащие вне шара , что также снижает влияние на время счёта. Такимобразом, быстродействие предложенного алгоритма слабо зависит от уровня доверительнойвероятности.Таблица 2.1. Результаты численного эксперимента ()1 ()0, 9107, 54720, 8750 0, 3667 11, 4591006, 72280, 8673 0, 3648 11, 73610006, 72280, 8673 0, 3648 12, 284100006, 72280, 8673 0, 3648 18, 8210, 990, 9992 ()10012, 8226 0, 9044 0, 3728 11, 492100011, 2475 0, 8989 0, 3718 12, 0231000011, 2475 0, 8989 0, 3718 13, 47510000011, 2475 0, 8989 0, 3718 26, 354100014, 6035 0, 9171 0, 3750 11, 8721000014, 5385 0, 9133 0, 3744 12, 61310000014, 5385 0, 9133 0, 3744 17, 2731000000 14, 5385 0, 9133 0, 3744 64, 469С другой стороны, время счёта и точность решения существенно зависят от числа точек дискретизации.

При небольших (относительно уровня вероятности) значениях алгоритм работает быстрее, но возникают погрешности вычисления. С увеличением количества точек разбиения значение критерия ¯ () быстро стабилизируется и от зависитслабо. Это связано с тем, что при большом количестве точек разбиения бо́льшая их часть˜ ∖ ) оказывается существенно меньше ( ),содержится в доверительном шаре, а мера (поэтому она оказывает незначительное влияние на значение меры ( ).Пример 2.2.В первой главе двухэтапная задача квантильной оптимизации сводится к смешанной задаче целочисленного линейного программирования большой размерности.

Применималгоритм, описанный в этой главе, для решения задачи, рассмотренной в первой главе, исравним результаты, получаемые в ходе применения обоих алгоритмов (алгоритмов первойи второй главы).63Рассмотрим двухэтапную задачу (1.16) в априорной постановке. Пусть параметрызадачи принимают следующие значения: = col(1 , 2 ); = = 1 = = 2; T =T(1 , 2 ); ⎛T1 () =0 = (0, 3; −0, 4); 1 =⎞ , 3 () = , где = 2, 5; = 1, 5;⎞(6; 3); ⎛1 + 32 1 − 222 3⎠.⎠, = ⎝2 () = ⎝2241 + 625 1Пусть случайный вектор имеет нормальное распределение (⃗0; ), где — единич-ная ковариационная матрица.Результаты применения двух алгоритмов приведены в таблице 2.2.