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

сходится по распределению к случайной величине U, имеющей стандартное нормальное распределение N(0, 1).Т е о р е м а 3 [85]. Если выполнены условия леммы 3, тоbb n (α) − ϕα = Pn (ϕα ) − α + oP n−1/2 ,Φp(ϕα )(61)где Pbn (ϕα ) — значение выборочной оценки вероятности в точке ϕα , а n−1/2 oP n−1/2 →0 по вероятности при n → ∞.Практическое вычисление выборочной квантили требует построения вариацион-ного ряда для всей выборки Φ1 , ..., Φn , что практически эквивалентно построениювыборочной функции распределения Pbn (ϕ) для всех ϕ. При этом увеличение n при-водит к тому, что номер [αn], определяющий выборочную квантиль, оказывается су-щественно меньше n. Возникает естественный вопрос о возможности использованиямалых выборок, таких что [αn] = n − 1, например выборки объема n = [1/(1 − α)].b n (α), известны и другие статистические оценкиПомимо выборочной квантили Φквантилей, основанные на порядковых статистиках. В [99] предложена следующаяоценка:(62)а в [94] – оценка(63)Φn (α) = Φn[αn−1] + Φn[αn+1] /2,e n (α) = (j − αn)Φnj−1 + (αn − j + 1)Φnj ,Φj − 1 ≤ αn ≤ j.e n (α) кусочноОценки Pbn (ϕα ) и Φn (α) кусочно постоянны по α, в то время как оценка Φлинейна.Экстремальная порядковая оценка квантили.Рассмотрим задачу статистической оценки квантили, поставленную выше дляслучая малой выборки объема n = n(α) = [1/(1 − α)].

В этом случае выборочная33квантиль совпадает с порядковой статистикой Φnn−1 . Точность этой оценки можетоказаться неудовлетворительной, поскольку в данном случае объем выборки фиксирован и однозначно определен заданным значением величины α. Величины Φnn и Φnn−1называются экстремальными порядковыми статистиками.

Их свойства исследованыв [13, 17].Рассмотрим статистикуe n (α) = Φn − µ(Φn − Φn ),Φnnn−1(64)которая называется экстремальной порядковой оценкой функции квантили, где n =[1/(1 − α)], а µ ≈ 0.5772 — константа Эйлера.Введем в рассмотрение случайную величину Φ = Φ(ξ). Тогда функция вероятно-сти Pϕ совпадает с функцией распределения FΦ (ϕ) этой величины, а (FΦ (ϕ))n является функцией распределения экстремальной порядковой статистики Φnn .Будем говорить, что функция FΦ (ϕ) принадлежит области притяжения третьего предельного закона, что обозначается посредством FΦ (·) ∈ Λ3 , если существуютпоследовательности an и bn > 0, для которых справедливо соотношение [13]lim (FΦ (an + bn ϕ))n = Λ3 (ϕ) = exp(− exp(−ϕ))(65)n→∞для всех ϕ ∈ R1 .Пусть(66)ϕmin = inf{ϕ : FΦ (ϕ) > 0}, ϕmax = sup{ϕ : FΦ (ϕ) < 1}.Т е о р е м а 4. Необходимые и достаточные условия для FΦ (ϕ) ∈ Λ3 [13].FΦ (ϕ) ∈ Λ3 тогда и только тогда, когда выполнены следующие условия:(а) при некотором конечном a справедливо соотношение(67)ϕZmaxa(1 − FΦ (y))dy < ∞;(б) для любого x ∈ R1 существует предел(68)limϕ→ϕmax1 − FΦ (ϕ + xR(ϕ)),1 − FΦ (ϕ)где для ϕ ∈ (ϕmin , ϕmax ) функция R(ϕ) определена следующим образом:34(69)R(ϕ) =ϕRmaxϕ(1 − FΦ (y))dy1 − FΦ (ϕ).При этом последовательности an и bn могут быть выбраны следующим образом:(70)an = inf{ϕ : 1 − FΦ (ϕ) ≤ 1/n},(71)bn = R(an ).В частном случае, когда случайная величина Φ имеет плотность вероятности p(ϕ),непрерывную и отличную от нуля на интервале N(ε) = (ε, ϕmax), где ε ∈ (ϕmin, ϕmax )очевидно, что последовательность an не убывает и стремится к ϕmax .

Поэтому длядостаточно больших n выполняется an ∈ N(ε) и справедливо соотношение(72)1 − FΦ (an ) =1.nОтсюда, в частности, следует, что an = ϕ(n−1)/n начиная с некоторого конечногономера.Т е о р е м а 5 [13]. Пусть случайная величина Φ удовлетворяет следующимусловиям:(а) функция распределения FΦ (·) ∈ Λ3 ;(б) случайная величина Φ имеет плотность вероятности, непрерывную и отличнуюот нуля на интервале N(ε), где ε < ϕmax ;(в) M[|Φ|] < ∞Тогда(73)limn→∞e n (α)] − ϕ(n−1)/n = 0.M[ΦЯдерная оценка функции квантили.cn (α), как отмечено выше, является кусочно-постоянной функВыборочная оценка Φцией параметра α, т.е.

имеет точки разрыва. Проблема сглаживания этой функцииможет быть решена путем введения в рассмотрение ядерной оценки функции квантили:35(74)b ∗ (α) = 1ΦnhnZ10b n (y)qΦy−αhndy =1hnnXi=1Zn/tq(i−1)/ny−αhndy  Φni ,где q(y) – плотность вероятности некоторой случайной величины Y , аΦn1 ≤ Φn2 ≤ ...Φnn ≤ — порядковые статистики для случайной величины Φ.Ядерная оценка функции квантили предложена впервые в [94]. Свойства ее рас-смотрены в [87, 103].Т е о р е м а 6 [103]. Пусть выполнены следующие условия:(а) случайная величина Φ = Φ(ξ) имеет плотность вероятности p(ϕ), причемp(ϕα ) > 0;(б) p(ϕ) непрерывно дифференцируема в точке ϕ = ϕα ;(в) плотность вероятности q(y) ограничена, равна нулю вне [−1, 1] иR1yq(y)dy = 0;−1(г) n1/4 hn → 0 при n → ∞.Тогдаb ∗ (α) − ϕα = (α − Pbn (ϕα ))/p(ϕα ) + oP (n−1/2 ),Φn(75)где Pbn (ϕ) — выборочная оценка вероятности, а n−1/2 oP (n−1/2 ) → 0 по вероятностипри n → ∞.Выборочная и ядерная оценки функции квантили асимптотически эквивалентны,т.е.

их точности при больших n примерно одинаковы.1.1.5Алгоритм стохастической аппроксимации.Статистические оценки квантили, описанные выше, не являются рекуррентными,так как подразумевают процедуру сортировки выборки для определения порядковыхстатистик. В этом пункте рассматривается принципиально иной метод, основанныйна рекуррентном уточнении статистической оценки квантили по мере увеличенияобъема выборки, который позволяет избежать сортировки. Этот метод, известныйкак метод стохастической аппроксимации, впервые предложен в [100] для определения квантили как корня уравнения Pϕ = α. Метод стохастической аппроксимацииразвит и приспособлен для решения широкого круга оптимизационных задач в большом числе публикаций [7, 14, 20, 21, 51].Алгоритм стохастической аппроксимации для оценки α-квантили распределенияслучайной величины Φ = Φ(ξ), где Φ(x) : R1 → R1 — борелевская функция случайного вектора ξ, определяется следующим рекуррентным соотношением:36(76)Φk+1 = Φk + ρk (α − Yk+1),k = 0, 1, ...,где ρk — неотрицательная детерминированная последовательность,(77)Yk+1 =1,0,Φ(ξk+1) ≤ Φk ,Φ(ξk+1) > Φk ,а ξ1 , ξ2 , ...— последовательность независимых реализаций случайного вектора ξ, Φ0 =ϕ0 — константа.

Эта процедура порождает случайную последовательность Φk , k =1, 2, ....Т е о р е м а 7 [43]. Если α ∈ (0, 1) и квантиль ϕα является единственным обоб-щенным корнем уравнения Pϕ = α, а последовательность ρk удовлетворяет условиям(78)ρk ≥ 0,∞Xk=0ρk = ∞,∞Xk=0ρ2k < ∞,то последовательность Φk , генерируемая процедурой (77), с вероятностью 1 сходитсяк ϕα для любого Φ0 ∈ R1 .1.1.6Чебышевские оценки вероятностей и квантилей.Неравенство Чебышева.В данном пункте приводится описание оценок функции вероятности, основанныхна детерминированных неравенствах для вероятностей. Таких неравенств известнодовольно много.

Подробнее с ними можно ознакомиться в [40, 97]. Здесь будет приводиться лишь наиболее известное вероятностное неравенство — неравенство Чебышева.Л е м м а 4 [43]. Пусть случайная величина Φ неотрицательна и существует M[Φ].Тогда для любого ϕ > 0 справедливо неравенство Чебышева(79)P {Φ ≥ ϕ} ≤M[Φ].ϕС некоторыми следствиями леммы 4 можно подробнее познакомиться в [43].Оценки функции вероятности и квантили.

Применяя изложенные в [43] результаты следствий неравенства Чебышева, строятся границы функции вероятностии квантили. Для удобства полагается Φ = Φ(ξ). Пусть g(x) — строго возрастающаяфункция скалярного аргумента. Под функцией g −1(y) в следующей теореме будем37понимать единственный обобщенный корень уравнения g(x) = y относительно x.

Отметим, что g −1(g(x)) = x, а если функция g(x) непрерывна справа, то справедливонеравенство g(g −1(y)) ≥ y.Т е о р е м а 7 [43]. Пусть g(·) : (−∞, ∞) → [0, ∞) — строго возрастающаянепрерывная справа функция, а Φ — случайная величина, для которой существуетM[g(Φ)]. Тогда для любого ϕ, такого что g(ϕ) > 0, справедливо неравенство(80)Pϕ ≥ 1 −M[g(Φ)]= PbCh (ϕ),g(ϕ)а для любого α ∈ (0, 1) — неравенство(81)1.2ϕα ≤ g−1M[g(Φ)]1−α=ϕbCh (α).Двусторонние оценки квантильного критерия на основеаппроксимаций функции распределения.1.2.1Постановка задачи.Пусть ξ- случайный вектор размерности m, Φ(x) : Rm → R1 - измеримая поБорелю функция. Тогда η = Φ(ξ) является случайной величиной с функцией распределения(82)F (x) = P (η ≤ x) = P (Φ(ξ) ≤ x).Квантильный критерий (функция квантили) определяется выражением [43](83)xα = min{x : F (x) ≥ α},где α ∈ (0, 1) — доверительная вероятность.Свойства функций (82) и (83) подробно изучены в [43], где в частности установлено, что минимум в (83) достигается.Пусть ηn− и ηn+ - последовательности случайных величин с функциями распределения Fn− (x) и Fn+ (x) соответственно, сходящиеся по распределению к η , причемFn− (x) ≤ F (x) ≤ Fn+ (x) ∀x, см.

рис. 6.Требуется оценить функцию квантили xα с заданной точностью ε, используя по-следовательности Fn+ (x) , Fn− (x). Предполагается, что Fn+ (x) и Fn− (x) известны, аF (x) нет.38Рис. 6: Иллюстрация к постановке задачиВ приложениях функция Φ(·) обычно моделирует качество исследуемой системы [65].

В этом смысле поставленную задачу можно интерпретировать как задачувероятностного анализа системы при случайных возмущениях.1.2.2Алгоритм построения двусторонних оценок квантильного критерия.Т е о р е м а 8. Пусть для некоторых xk , yk ∈ R1 справедливы неравенстваFn− (xk ) > α,(84)Fn+ (yk ) < α.Тогда функция квантили xα , определенная выражением (83), удовлетворяет неравенству(85)yk < xα ≤ xk .Более того, если фунуция F (x) непрерывна на некотором отрезке [a, b] и xα ∈ (a, b)- единственный корень уравнения F (x) − α = 0, то для каждого k можно подобратьxk , yk , удовлетворяющие (85) и такие, что(86)xk − yk → 0 при k → ∞.Д о к а з а т е л ь с т в о: Докажем первое утверждение. Из определения кватилиxα следует:(87)F (xα ) ≥ α и F (xα − ε) < α ∀ε > 0.Тогда с учетом предположений Fn− ≤ F ≤ Fn+ , Fn+ (yk ) < α < Fn− (xk ) получаем(88)Fn+ (yk ) < α ≤ F (xα ) ≤ Fn+ (xα ) и Fn− (xα − ε) ≤ F (xα − ε) < α < Fn− (xk ),39т.е.

Fn+ (yk ) < Fn+ (xα ) и Fn− (xα − ε) < Fn− (xk ), что в силу монотонности этих функцийозначает yk < xα и xα − ε < xk , отсюда и следует справедливость неравенства (85).Для доказательства второго утверждения рассмотрим следующий алгоритм, по-рождающий последовательности 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 вариантоврасположения значений см.рис. 7: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 на единицу. Переходим к шагу 4.3.6Если Fn− (ck ) < α < Fn+ (ck ) и Fn− (dk ) < α < Fn+ (dk ), то увеличиваем nна единицу и переходим к шагу 3.Зацикливание алгоритма ввиду бесконечного повторения шага 3.6 произойтине может в силу предположения о том, что xα − единственный корень уравненияF (x) − α = 0.