Автоматика и телемеханика, № 4, 2020

С.В. ИВАНОВ, канд. физ.-мат. наук (sergeyivanov89@mail.ru),

А.С. СТЕПАНОВА (nas778810@yandex.ru)

(Московский авиационный институт

(Национальный исследовательский университет))

ПОСТРОЕНИЕ ДОВЕРИТЕЛЬНОГО МНОЖЕСТВА

ПОГЛОЩЕНИЯ В ЗАДАЧАХ АНАЛИЗА

СТАТИЧЕСКИХ СТОХАСТИЧЕСКИХ СИСТЕМ¹

Рассматривается задача о построении доверительного множества по-

глощения при анализе статических стохастических систем. Под довери-

тельным множеством поглощения понимается множество начальных по-

зиций системы, для которых система в терминальный момент не выйдет

за пределы допустимых значений с заданной вероятностью. Устанавли-

ваются свойства доверительного множества поглощения, в частности его

выпуклость. На основе доверительного метода предлагается алгоритм по-

строения внутренней аппроксимации доверительного множества погло-

щения. Устанавливаются свойства этой аппроксимации. На основе полу-

ченных результатов решается задача о прогнозе скорости ветра в районе

аэродрома посадки самолетов. Приводятся численные расчеты.

Ключевые слова: стохастическое программирование, доверительное мно-

жество поглощения, прогноз скорости ветра.

DOI: 10.31857/S0005231020040029

1. Введение

Многие реальные технические системы описываются в терминах стохасти-

ческих динамических систем, критерием качества функционирования кото-

рых является некоторый статистический критерий [1]. В большинстве случа-

ев в качестве критерия рассматривается математическое ожидание функции

потерь. Но во многих прикладных задачах анализа стохастических систем

встречаются критерии в виде функции квантили [2, 3]. Функция квантили

(или VaR-критерий) характеризует гарантированный по вероятности резуль-

тат решения задачи. Функция квантили по смыслу — это значение функ-

ции потерь, которое не будет превышено с заданной вероятностью. Функция

квантили является в некотором смысле обратной к функции вероятности, ко-

торая характеризует вероятность достижения системой заданной цели. Этим

задачам посвящено много публикаций. Можно привести монографии [2, 3],

в которых подробно изучаются свойства функции квантили и предлагаются

¹ Работа выполнена при финансовой поддержке Российского фонда фундаментальных

исследований (проект № 19-07-00436 А).

методы ее минимизации. В [4] исследуются свойства функции вероятности и

предлагаются методы ее максимизации.

Особое место в задачах анализа стохастических систем по квантильному

критерию занимает задача о построении доверительного множества погло-

щения начальных позиций системы. Речь идет о начальных позициях систе-

мы, обеспечивающих в конечный момент времени выполнение ограничений

с заданной вероятностью. Такое множество называется [3] доверительным

множеством поглощения.

Доверительное множество поглощения в статических стохастических си-

стемах можно рассматривать как множество уровня функции вероятности.

Свойства множества уровня тесно связаны со свойствами функции вероят-

ности. В частности, при квазивыпуклости функции вероятности множества

уровня являются выпуклыми. Свойства квазивыпуклости функции вероятно-

сти обсуждаются в [4-7]. Условия выпуклости множеств уровня для досточно

больших значений вероятности исследуются в [8]. Утверждения о свойствах

квазивыпуклости функции вероятности, как правило, опираются на поня-

тия квазивогнутых и логарифмически вогнутых вероятностных мер [9-12].

Условия связности множества уровня функции вероятности получены в [13],

достоинством которой является отсутствие каких-либо ограничений на рас-

пределение случайных параметров.

Множество уровня функции вероятности нетрудно построить в тех случа-

ях, когда вероятностные ограничения могут быть заменены на детерминиро-

ванные. Данный подход известен как метод детерминированного эквивален-

та [3]. Класс систем, к которым этот метод применим, является достаточно

узким. Как правило, для его применения необходима монотонность функции

потерь.

В другом частном случае, когда функция потерь представима в виде мак-

симума функций, в которые случайные параметры входят аддитивно, для по-

строения множества уровня функции вероятности может быть применен ап-

парат p-эффективных точек, введенный в [14]. По сути, p-эффективная точка

является многомерным аналогом квантили распределения. Алгоритм, позво-

ляющий получить множество p-эффективных точек дискретного случайно-

го вектора, предложен в [15]. Нетрудно проверить, что в случае дискретно-

го распределения с конечным числом реализаций множество p-эффективных

точек конечно, что позволяет получить детерминированное описание множе-

ства уровня функции вероятности. С помощью p-эффективных точек также

можно получить верхние и нижние оценки целевой функции в задаче оптими-

зации детерминированной функции при ограничениях на значение функции

вероятности [16]. Алгоритм решения данной задачи, основанный на исполь-

зовании p-эффективных точек, в случае непрерывного распределения пред-

ложен в [17]. Обзор методов решения задач с вероятностными ограничениями

указанного выше типа, основанных на построении внутренних и внешних ап-

проксимаций множества уровня функции вероятности, приведен в [18].

Следует отметить способ построения внешней аппроксимации множества

уровня функции вероятности, основанный на использовании понятия α-ядра

вероятностной меры [3]. При выполнении некоторых условий регулярности

с помощью ядра можно получить нижнюю оценку функции квантили, ко-

торую можно использовать для построения внешней аппроксимации довери-

тельного множества поглощения. Методы аппроксимации α-ядра предложе-

ны в [19, 20].

Таким образом, известные методы позволяют построить доверительное

множество поглощения только для весьма узкого класса стохастических си-

стем. Поэтому актуальной является задача построения доверительного мно-

жества поглощения для стохастических систем общего вида. В настоящей

статье более детально исследовано свойство доверительного множества по-

глощения для статической стохастической системы. В частности, приводятся

условия, когда это множество выпукло. При этом функция потерь имеет до-

статочно общую структуру. Для построения доверительного множества по-

глощения предлагается использовать доверительный метод, который впервые

был описан в [21] и более детально исследован в [3]. В данном случае дове-

рительный метод позволяет построить внутреннюю аппроксимацию довери-

тельного множества поглощения. Приводятся условия, когда граница довери-

тельного множества поглощения переходит в границу терминального множе-

ства. Эффективность полученных результатов демонстрируется на примере,

состоящем в построении множества значений скорости ветра в районе аэро-

дрома, при которых скорость ветра по происшествии фиксированного време-

ни не выйдет с заданной вероятностью за пределы допустимых значений, что

позволяет осуществить безопасную посадку самолета.

2. Постановка задачи

Предположим, что известна зависимость z(y, X) вектора z ∈ R^l терми-

нального состояния системы от вектора начальных позиций y ∈ R^s системы

и от случайного вектора X ∈ Rⁿ, влияющего на положение системы. Пред-

полагается, что случайный вектор X имеет известную функцию распределе-

ния F_X (x). Пусть вектор терминального состояния z должен удовлетворять

заданным ограничениям

(2.1)

Φ(y, X) ≜Φ(z(y, X)) ≤ ϕ, ϕ ∈ R¹,

где функцияΦ(z) описывает эти ограничения. Установим вероятность вы-

полнения терминальных ограничений

(2.2)

P_ϕ

(y) ≜ P{Φ(y, X) ≤ ϕ} ≥ α, α ∈ (0, 1).

Требуется построить множество значений y, для которых будет выполнено

это неравенство

(2.3)

Y_ϕ,α ≜ {y: P_ϕ

(y) ≥ α}.

Множество (2.3) назовем доверительным множеством поглощения.

3. Свойства доверительного множества поглощения

В [2, 3] рассматривается аналогичная задача, в которой роль функции

Φ(u, X) играет функция потерь, а вместо начальных позиций y рассматрива-

ются стратегии управления u ∈ U. Для этой функции потерь вводятся функ-

ция вероятности

(3.1)

P_ϕ

(u) ≜ P{Φ(u, X) ≤ ϕ}

и функция квантили

(3.2)

ϕα(u) ≜ min{ϕ: Pϕ(u) ≥ α}.

Согласно лемме Розенблатта [2, 3]

(3.3)

Y_ϕ,α ≜ {y: P_ϕ(y) ≥ α} = {y: ϕ_α

(y) ≤ ϕ}.

Таким образом, для построения доверительного множества поглощения мож-

но использовать не только свойства функции вероятности, но и свойства

функции квантили.

В упомянутых публикациях приводятся условия, когда функция кванти-

ли ϕ_α(u) квазивыпукла, а функция вероятности P_ϕ(u) квазивогнута. Приве-

дем этот результат из [3].

Определение 1

[4]. Вероятностная мера P на борелевских подмноже-

ствах Rⁿ называется квазивыпуклой, если для любой пары непустых выпук-

лых множеств A, B ⊂ Rⁿ и любого λ ∈ (0, 1) выполняется неравенство

P(λA + (1 - λ)B) ≥ min{P(A), P(B)}.

Здесь сумма множеств и умножение множества на число понимаются в

смысле Минковского:

(A + B) = {z : z = x + y, x ∈ A, y ∈ B},

λA = {z : z = λx, x ∈ A}.

Приведем достаточное условие для квазивогнутости вероятностной меры.

Лемма 1

[4]. Если случайный вектор имеет плотность вероятно-

сти p(x) такую, что функция p-n (x) выпукла на Rⁿ, то соответствующая

ей вероятностная мера P квазивогнута.

На основании этой леммы легко установить, что многие известные распре-

деления имеют квазивогнутую вероятностную меру: нормальное распределе-

ние, экспоненциальное распределение, распределение Коши и т.д.

Напомним и другие определения.

Определение 2

[4]. Функция f(u), определенная на выпуклом множе-

стве U ⊂ R^m, называется квазивыпуклой на U, если для любых u₁,u₂ ∈ U и

любого λ ∈ (0, 1) выполняется неравенство

f (λu₁ + (1 - λ)u₂) ≤ max{f(u₁), f(u₂)}.

Определение 3

[4]. Функция f(u), определенная на выпуклом множе-

стве U ⊂ R^m, называется квазивогнутой на U, если для любых u₁,u₂ ∈ U и

любого λ ∈ (0, 1) выполняется неравенство

f (λu₁ + (1 - λ)u₂) ≥ min{f(u₁), f(u₂)}.

Приведем основной результат из [3], касающийся свойств выпуклости

функции квантили ϕ_α(u) и функции вероятности P_ϕ(u).

Теорема 1

[3]. Пусть функция потерь Φ(u, x) квазивыпукла по сово-

купности аргументов на U × X, где U ⊂ R^m — выпуклое подмножество,

а X — выпуклый носитель квазивогнутой вероятностной меры P. Тогда

функция вероятности P_ϕ(u) квазивогнута на U для любого ϕ ∈ R¹, а функ-

ция квантили ϕ_α(u) квазивыпукла на U для любого α ∈ (0, 1).

Из этой теоремы получаем тривиальное следствие для исследования дове-

рительного множества поглощения.

Следствие 1. Пусть функция Φ(y,x), определяющая множество по-

глощения, квазивыпукла по совокупности аргументов на R^s × X , где X —

выпуклый носитель квазивогнутой вероятностной меры P. Тогда довери-

тельное множество поглощения Y_ϕ,α выпукло для любых ϕ ∈ R¹, α ∈ (0, 1).

Доказательство этого следствия основано на факте, что множество Y_ϕ,α

играет роль множества уровня для квазивогнутой функции вероятно-

сти P_ϕ(y), а множество уровня квазивогнутой функции выпукло.

Но остается вопрос: как строить доверительное множество поглощения.

Это можно сделать, например, используя прямые методы, т.е. поступить

следующим образом. Пусть зафиксировано некоторое конечное множество

Y ⊂R^s.

Алгоритм 1.

1. Фиксируется точка y ∈ Y .

2. С помощью метода статистических испытаний оценивается вероятность

P_ϕ(y):

M (S_ϕ(y))

P_ϕ(y) =

где M(S_ϕ(y)) — число успешных испытаний в серии из n испытаний, когда

точки x из выборки принадлежат множеству

S_ϕ(y) ≜ {x : Φ(y,x) ≤ ϕ}.

3. Проверяется услови

P_ϕ(y) ≥ α. Если оно выполнено, то точка y вклю-

чается в множеств

Y_ϕ,α, являющееся статистической аппроксимацией дове-

рительного множества поглощения Y_ϕ,α.

4. Процедура повторяется с шага 2 для новой точки y ∈ Y .

Можно отметить, что реализация данного алгоритма очень трудоемкая,

так как при вероятностях α, близких к 1, объем выборки n должен быть

очень большим, а перебрать нужно максимально большее число точек y из R^s,

чтобы хорошо оценить множество Y_ϕ,α.

В следующем разделе рассматривается другой способ построения множе-

ства Y_ϕ,α, основанный на доверительном методе.

4. Построение внутренней аппроксимации

доверительного множества поглощения

Рассмотрим доверительный метод, подробно изложенный в [2, 3] и впервые

опубликованный в [21].

Пусть S — доверительное множество, т.е. множество в пространстве Rⁿ

реализаций случайного вектора X с вероятностной мерой не менее α. Рас-

смотрим функцию максимума

(4.1)

ψ(y, S) ≜ sup

Φ(y, x).

x∈S

Из [3] вытекает следующее утверждение.

Лемма 2. Для любого доверительного множества S с вероятностной

мерой не менее α выполняется неравенство

(4.2)

ϕα

(y) ≤ ψ(y, S)

при всех y ∈ R^s.

Данное утверждение вытекает из леммы 3.4 из [3]. Аналогично, перефор-

мулируя теорему 3.9 из [3], получаем следующий результат.

Теорема 2. Для любого α ∈ (0,1) справедливы соотношения

(4.3)

ϕα(y) = min

ψ(y, S), S_α(y) = arg min

ψ(y, S),

S∈Fα

где F_α — семейство доверительных множеств с вероятностной мерой не

менее α.

Применим доверительный метод для построения доверительного множе-

ства поглощения. Зафиксируем множество S ∈ F_α и рассмотрим множества

(4.4)

Y_ϕ

(x) ≜ {y : Φ(y, x) ≤ ϕ},

⋂

(4.5)

Y_ϕ(S) ≜ Y_ϕ(x) = {y : ψ(y, S) ≤ ϕ}.

x∈S

В соответствии с доверительным методом получается внутренняя аппрок-

симация доверительного множества поглощения

(4.6)

Y_ϕ,α ⊃ Y_ϕ

(S).

При этом если перебрать все доверительные множества S ∈ F_α, то полу-

чится точное множество поглощения

⋃

(4.7)

Y_ϕ,α =

Y_ϕ

(S).

S∈Fα

Исследуем свойства множества Y_ϕ(S).

Пусть x ∈ S — некоторая точка из S, a N_i(x) — прямая, содержащая точ-

ку x и являющаяся параллельной i-й координатной оси. Введем обозначения:

a_i(x) ≜

min

x_i, b_i(x) ≜

max x_i.

x∈N_i(x)∩∂S

Определим часть ∂_iS границы множества S следующим образом:

⋃

(4.8)

∂_iS ≜

[{x ∈ N_i(x) ∩ ∂S : x_i = a_i(x)} ∪ {x ∈ N_i(x) ∩ ∂S : x_i = b_i

(x)}].

x∈S

Теорема 3. Пусть множество S компактно. Пусть функция Φ(y,x)

непрерывна и квазивыпукла по координате x_i вектора x ∈ S ⊂ Rⁿ для каж-

дого y ∈ R^s. Тогда

(4.9)

ψ(y, S) = max

Φ(y, x),

x∈∂_iS

(4.10)

Y_ϕ(S) = Y_ϕ(∂_i

S),

где ∂_iS — часть границы множества S, определяемая выражением (4.8).

Доказательство. Равенство (4.9) следует из определения части гра-

ницы ∂_iS и квазивыпуклости функции потерь по x_i:

ψ(y, S) = maxΦ(y, x) = max

max Φ(y, x) =

x∈S

x∈N_i(x)

= max

max

{Φ(y, x): x_i = a_i(x) или x_i = b_i(x)} = max Φ(y, x).

x∈S

x∈N_i(x)∩∂S

x∈∂_iS

По построению Y_ϕ(S) ⊂ Y_ϕ(∂_iS). Таким образом, для доказательства (4.10)

нужно показать, что Y_ϕ(S) ⊃ Y_ϕ(∂_iS). Пусть y ∈ Y_ϕ(∂_iS). Это означает, что

Φ(y, x) ≤ ϕ для всех x ∈ ∂_iS, или, что то же самое,

max Φ(y, x) ≤ ϕ.

x∈∂_iS

Но по доказанному выше

max Φ(y, x) = ψ(y, S),

x∈∂_iS

что эквивалентно выполнению неравенства Φ(y, x) ≤ ϕ для всех x ∈ S. Таким

образом, y ∈ Y_ϕ(S), т.е. равенство (4.10) выполнено. Теорема 3 доказана.

Таким образом, для вычисления функции ψ(y, S) и построения множе-

ства Y_ϕ(S) достаточно перебрать только точки, лежащие на части ∂_iS гра-

ницы ∂S доверительного множества S ∈ F_α.

Рассмотрим множество

{

}

(4.11)

Z_ϕ ≜ z ∈ R^l :Φ(z) ≤ ϕ

и часть ∂_rZ_ϕ границы ∂Z_ϕ множества Z_ϕ, которое соответствует координа-

те z_r вектора z ∈ R^l и построено аналогично множеству ∂_iS (4.8).

Теперь рассмотрим вопрос построения множества Y_ϕ(x).

Теорема 4. Пусть отображение y → z(x,y) при заданном x ∈ X явля-

ется гомеоморфизмом, а множество Z_ϕ компактно. Тогда прообразом мно-

жества Z_ϕ при данном отображении является множество Y_ϕ(x). При

этом

(4.12)

∂Y_ϕ(x) = {y: z(x,y) ∈ ∂Z_ϕ

Доказательство. Согласно свойствам гомеоморфных отображений

прообразом компакта является компакт, при этом граничные точки множе-

ства Z_ϕ переходят под действием отображения y → z(x, y) в граничные точки

множества Y_ϕ(x), и наоборот. Теорема 4 доказана.

Таким образом получаем, следующий алгоритм построения множества

Y_ϕ(S) при выполнении условий теорем 3 и 4.

Алгоритм 2.

1. Для различных x ∈ ∂_iS построить множества ∂Y_ϕ(x) по формуле (4.12).

2. По границе ∂Y_ϕ(x) восстановить множество Y_ϕ(x) для всех x ∈ ∂_iS.

3. Найти пересечение множеств Y_ϕ(x) по всем x ∈ ∂_iS.

Замечание 1. Если семейство доверительных множеств S(a) зависит от

некоторого вектора параметров a ∈ A, то описанный алгоритм 2 можно до-

полнить еще одним шагом, чтобы получить лучшую интерпретацию довери-

тельного множества поглощения:

⋃

(4.13)

Y_ϕ,α ⊃

Y_ϕ(S(a)).

a∈A

Рассмотрим вектор y в многомерной сферической системе координат

(y, β), где y ≜ ∥y∥, а β — вектор углов.

Введем определение 4.

Определение 4. Множество Y ⊂ R^s является звездчатым, если от-

резок, соединяющий начало координат с произвольной точкой y ∈ Y, полно-

стью принадлежит множеству Y ⊂ R^s.

Теорема 5. Пусть функцияΦ(y,β,x) = Φ(y,x) квазивыпукла по y для

каждого β. Если 0 ∈ Y_ϕ(x), то множество Y_ϕ(x) является односвязным и

звездчатым.

Доказательство. Из квазивыпуклости функции Φ(·) следует, что при

выполнении условий 0 ∈ Y_ϕ(x) и y ∈ Y_ϕ(x) справедливо, что

Φ(y,x) ≤ max{Φ(0,x), Φ(y,x)} ≤ ϕ,

для всех y, принадлежащих отрезку, соединяющему точки 0 и y. Таким об-

разом, доказана звездчатость множества Y_ϕ(x). А звездчатое множество яв-

ляется односвязным. Теорема 5 доказана.

Следствие 2. Пусть выполнены условия теоремы 5. Тогда множество

Y_ϕ(S) является звездчатым и односвязным.

Доказательство. Доказательство следует из факта, что пересечение

звездчатых множеств оказывается также звездчатым, а следовательно и од-

носвязным. Следствие 2 доказано.

5. Построение множества допустимых значений

скорости ветра в районе аэродрома

5.1. Постановка задачи

Сформулируем задачу. Пусть некоторый самолет вылетает из города N в

город M, до которого время полета равно t. Посадка самолета в аэропорту

города M возможна, если скорость ветра в продольном и боковом направле-

ниях не выходит за допустимые пределы

{

}

(5.1)

W_t =

(w^tx, w^tz ): |w^tz| ≤ wmaxz, wminx ≤ w^tx ≤ wmaxx

где w^tx, w^tz — скорости ветра в точке посадки в момент посадки самолета в

продольном и боковом направлениях.

В нулевой момент, т.е. в момент вылета самолета из города N, в аэропор-

ту города M скорость ветра была (w0x, w0z). Но по истечении времени t ветер

может значительно измениться и его скорости не будут удовлетворять допу-

стимым значениям, т.е. посадка самолета станет невозможной. Пусть значе-

ние скорости ветра w^t в момент t связано со скоростью ветра w⁰ в нулевой

момент соотношениями:

(5.2)

w^tx = (v⁰ + ξ)cos(β⁰

+ η),

(5.3)

w^tz = (v⁰ + ξ)sin(β⁰

+ η),

где v⁰, β⁰ — полярные координаты вектора w⁰, а ξ и η — независимые слу-

чайные величины, имеющие усеченное нормальное распределение

ξ ∼ N(0,σ2ξ), η ∼ N(0,σ2η),

причем ξ ∈ [v_∗, v^∗], η ∈ [β_∗, β^∗].

Найдем вероятность такого события, что самолету разрешат посадку в

городе M, когда в момент его вылета из города N вектор скорости ветра был

равен w⁰:

{

}

(5.4)

P (w⁰) = P

w^t(w⁰,ξ,η) ∈ W_t

Необходимо построить множество W₀ допустимых скоростей ветра w⁰ в

начальным момент, при которых по происшествии времени t скорость вет-

ра w^t не выйдет за допустимые пределы с вероятностью α:

(5.5)

W₀ = {w⁰ : P(w⁰

) ≥ α}.

Другими словами, нужно построить доверительное множество поглоще-

ния.

5.2. Алгоритм построения доверительного множества поглощения

Для построения множества W₀ воспользуемся результатами из предыду-

щих разделов. Заметим, что множество W_t можно записать через функцию

потерь:

{

}

(5.6)

W_t = (w^tx,w^tz) :Φ(w^t) ≤ 1 ,

где

{

}

Φ(w^t) = max

Φ₁(w^tx),Φ2(w^tz) ,

Φ₁(w^tx) =|2wx -wxin -wzax|,

wmaxx - wminx

|w^tz|

Φ₂(w^tz) =

wmaxz

Далее заметим, что скорости ветра в начальный и конечный моменты свя-

заны между собой соотношениями в полярной системе координат:

β⁰ = β^t - η,

v⁰ = v^t - ξ.

Приведем связь между декартовой и полярной системами координат:

w^tx = v^t cos(β^t), w^tz = v^t sin(β^t),

√

v^t =

(w^tx)² + (w^tz)²,

⎧

⎪

w^tz

⎪arctg

w^tx > 0,

⎨

w^tx

w^tz

β^t =

π + arctg

w^tx < 0,

⎪

w^tx

⎪

⎩π

w^tx = 0.

Рассмотрим в нормированной системе координат случайные векторы

ξ=

η=

σ_ξ

σ_η

и доверительное множество в форме квадрата

(5.7)

S_Δ

= {|ξ| ≤ Δ, |η| ≤ Δ},

где параметр Δ выбирается из условия P(S_Δ) = α. Предположим, что для

случайной величины U со стандартным нормальным распределением N (0, 1)

соответствующие вероятности удовлетворяют неравенствам:

P{U < v_∗/σ_ξ, U > v^∗/σ_ξ} ≪ 1 - α,

P{U < β_∗/σ_η, U > β^∗/σ_η} ≪ 1 - α.

Тогда поскольку случайные величины ξ и η независимы, то параметр Δ может

быть найден из условий

F₀(Δ) =

√α,

где

∫

F₀(Δ) =

√

e-2 dx.

2π

Рассмотрим также семейство квадратов S_Δ(γ), подобных S_Δ, но поверну-

тых относительно S_Δ на угол γ ∈ [-π/2, 0].

В данном случае w^tx и w^tz линейно зависят от ξ и v⁰, поэтому согласно

теореме 5 множество

{

}

(5.8)

W₀(ξ,η) = (w0x,w0z):Φ(w^t(w0x,w0z,ξ,η)) ≤ 1

является звездчатым и односвязным. Поэтому для построения множества

W₀(ξ,η) достаточно рассмотреть границу доверительного множества S_Δ(γ).

Отображение (w0x, w0z) → (w^tx, w^tz ) области {(w0x, w0z): v⁰ > max{0, -ξ}} в

область {(w^tx, w^tz): v^t > max{0, ξ}} является гомеоморфизмом. Поэтому в си-

лу теоремы 4 при выполнении условия v^t > |ξ| для всех (ξ, η) ∈ ∂S_Δ(γ) и

(w^tx, w^tz) ∈ ∂W_t для построения множества W₀(ξ, η) достаточно найти для всех

точек (ξ, η) ∈ ∂S_Δ(γ) прообраз в пространстве (w0x, w0z) границы ∂W_t множе-

ства W_t.

Построим аппроксимацию доверительного множества поглощения W₀ с

помощью следующего алгоритма.

Алгоритм 3.

1. Перебираются (ξ, η) на границе ∂S_Δ(γ) множества S_Δ(γ).

2. Для каждой точки (ξ, η) ∈ ∂S_Δ(γ) находится прообраз W₀(ξ, η) в про-

странстве переменных (w0x, w0z) границы множества W_t.

3. Находится пересечение множеств

⋂

W₀(S_Δ(γ)) =

W₀(ξ,η).

(ξ,η)∈S_Δ(γ)

4. Пп. 1-3 алгоритма 3 повторяются для разных значений γ ∈ [-π/2, 0] и

строится множество

⋃

W₀ =

W₀(S_Δ(γ)).

γ∈[-π,0]

5. Множество W₀ принимается за аппроксимацию доверительного множе-

ства поглощения W₀.

Заметим, что для корректной работы алгоритма 3 необходимо выполнение

условия v^t > |ξ| для всех (ξ, η) ∈ ∂S_Δ(γ) и (w^tx, w^tz) ∈ ∂W_t.

Уточним полученную оценку.

Рассмотрим теперь доверительные множества S_r в форме круга

S_r ≜ {(ξ,η) : ξ² + η² ≤ r²},

где радиус круга r определяется из условия, что P(S_r) = α. В данном случае

в связи с независимостью ξ и η радиус круга находится аналитически

√

-2ln(1 - α).

Для доверительного круга S_r шаги 1-3 алгоритма 3 повторяются и стро-

ится множество W₀(B_r), которое является внутренней аппроксимацией дове-

рительного множества поглощения W₀.

Полученную аппроксимацию можно еще уточнить, если рассмотреть се-

мейство доверительных множеств S_Δ(γ), где параметр γ выбирается из ин-

тервала [-π, 0], и построить множество W₀ так, как это описано в алгорит-

ме 3.

Поскольку

⋃

(5.9)

W₀ =

W₀

(S),

S∈Fα

то, взяв объединение множеств W₀(B_r) и W₀, получаем более точную аппрок-

симацию доверительного множества поглощения

(5.10)

W₀ ⊃ W₀(S_r) ∪ W₀.

Можно также сдвинуть одну из границ множества S_Δ(γ) ближе к началу

координат, сохраняя при этом вероятностную меру множества. Объединение

всех таких множеств W₀(S_Δ(γ)) будет образовывать внутреннюю аппрокси-

мацию множества поглощения W₀.

5.3. Вычислительный эксперимент

Пусть для примера

α = 0,99; σ_ξ = 1,9 [м/с]; σ_η = 27⁰;

wmaxz = 15 [м/с]; wminx = -25 [м/с]; wmaxx = 10 [м/с].

На рис. 1 сплошной линией изображена граница множества W₀(S_r), а

шрих-пунктирной линией — W₀(S_Δ).

Сдвигом границ доверительного множества S_Δ(γ) влево и последующим

вращением внутреннюю аппроксимацию множества W₀ можно существенно

улучшить. Граница полученного множестваW0 изображена на рис. 2 штрих-

пунктирной линией. МножествоW0 оказывается выпуклым, хотя, как извест-

но, объединение выпуклых множеств оказывается, как правило, невыпуклым.

Для сравнения граница множества W₀(S_r) изображена сплошной линией.

Заметим, что множествоW0 содержит в себе множество W₀(S_r). Это свя-

зано с тем, что доверительное множество S_r — одно и то же для всех на-

чальных позиций системы w₀, а для каждой начальной точки имеется свое

оптимальное доверительное множество, которое неизвестно. Варьируя мно-

жество S_Δ(γ), подбираем для каждой точки w₀ доверительное множество

лучше, чем S_r, поэтому множествоW0 оказывается шире множества W₀(S_r).

Рис. 3. Множество W₀ при σ_η = 0.

Границу множестваW0 можно уточнить с помощью метода статистиче-

ских испытаний, используя алгоритм 1. Статистическая аппроксимация мно-

жества W₀ изображена на рис. 2 точечной линией. Из рис. 2 видно, что полу-

чаемая статистическая аппроксимация доверительного множества поглоще-

ния W₀ незначительно отличается от аппроксимирующего множестваW0, но

для ее построения пришлось провести огромный объем вычислений.

Представляет интерес множество W₀ при σ_η = 0. Как видно из рис. 3, это

множество оказывается невыпуклым. При σ_η → ∞ прогнозируемое значение

скорости ветра оказывается распределенным в некотором кольце. Поэтому

при возрастании v⁰ радиус кольца увеличивается, а вероятность попадания

прогнозируемой скорости ветра в множество W_t монотонно убывает. Это зна-

чит, что предельная функция вероятности является квазивогнутой, что га-

рантирует выпуклость ее множеств уровня. Таким образом, множество W₀

становится выпуклым при достаточно большом значении σ_η.

6. Заключение

Исследована задача по построению доверительного множества поглоще-

ния при анализе стохастической системы. Устанавливаются свойства это-

го множества. На основе доверительного метода предлагается алгоритм по-

строения доверительного множества поглощения. Предлагается также алго-

ритм построения этого множества на основе метода статистических испыта-

ний. На основе полученных результатов решается задача о прогнозе скоро-

сти ветра в районе аэродрома посадки самолета. Рассматриваются несколько

вариантов доверительного множества случайных параметров: круг и квад-

рат в нормированном пространстве. Кроме того, рассматривается семейство

доверительных квадратов, повернутых на некоторый угол вокруг начала си-

стемы координат. Приводятся результаты численных расчетов, из которых

следует, что лучшей внутренней аппроксимацией доверительного множества

поглощения является объединение множеств поглощения, построенных для

разных повернутых доверительных квадратов.

СПИСОК ЛИТЕРАТУРЫ

Липцер Р.Ш., Ширяев А.Н. Статистика случайных процессов. М.: Наука, 1974.

Kibzun A.I., Kan Y.S. Stochastic Programming Problems with Probability and

Quantile Functions. Chichester-N.Y.-Brisbane-Toronto-Singapore: John Wiley &

Sons, 1996.

Кибзун А.И., Кан Ю.С. Задачи стохастического программирования с вероят-

ностными критериями. М.: Физматлит, 2009.

Prékopa A. Stochastic Programming. Dordrecht-Boston: Kluwer, 1995.

Shapiro A., Dentcheva D., Ruszczynski A. Lectures on Stochastic Programming.

Modeling and Theory. Philadelphia: Society for Industrial and Applied Mathematics

(SIAM), 2009.

Тамм Э. О квазивыпуклости функций вероятности и квантили // Изв. АН

ЭССР, физ.-мат. 1976. Т. 25. № 2. С. 141-144.

Кан Ю.С., Кибзун А.И. Свойства выпуклости функций вероятности и квантили

в задачах оптимизации // АиТ. 1996. № 3. С. 82-102.

Kan Yu.S., Kibzun A.I. Convexity Properties of Probability Functions and Quantiles

in Optimization Problems // Autom. Remote Control. 1996. V. 57. No. 3. P. 368-383.

Van Ackooij W. Eventual Convexity of Chance Constrained Feasible Sets //

Optimization (J. Math. Programm. Oper. Res.). 2015. V. 64. No. 5. P. 1263-1284.

Prékopa A. Logarithmic Concave Measures with Application to Stochastic

Programming // Acta Sci. Math. (Szeged). 1971. V. 32. P. 301-316.

10.

Prékopa A. On Logarithmic Concave Measures and Functions // Acta Sci. Math.

(Szeged). 1973. V. 34. P. 335-343.

11.

Borell C. Convex Set Functions in d-Space // Period. Math. Hung. 1975. V. 6. No. 2.

P. 111-136.

12.

Норкин В.И., Роенко Н.В. α-Вогнутые функции и меры и их приложения //

Кибернетика и системный анализ. 1991. № 6. С. 77-88.

Norkin V.I., Roenko N.V. α-Concave Functions and Measures and Their

Applications // Cybern. Syst. Anal. 1991. V. 27. No. 6. P. 860-869.

13.

Henrion R. On the Connectedness of Probabilistic Constraint Sets // J. Optim.

Theory Appl. 2002. V. 112. No. 3. P. 657-663.

14.

Prékopa A. Dual Method for the Solution of a One-Stage Stochastic Programming

Problem with Random RHS Obeying a Discrete Probability Distribution // ZOR —

Methods and Models of Oper. Res. 1990. V. 34. P. 441-461.

15.

Lejeune M., Noyan N. Mathematical Programming Approaches for Generating

p-Efficient Points // Eur. J. Oper. Res. 2010. V. 207 P. 590-600.

16.

Dentcheva D., Prékopa A., Ruszczynski A. On Convex Probabilistic Programming

with Discrete Distribution // Nonlinear Analysis. 2001. V. 47. P. 1997-2009.

17. Van Ackooij W., Berge V, de Oliveira W., Sagastizábal C. Probabilistic Optimization

via Approximate p-Efficient Points and Bundle Methods // Comput. Oper. Res. 2017.

V. 77. P. 177-193.

18. Lejeune M.A., Prékopa A. Relaxations for Probabilistically Constrained Stochastic

Programming Problems: Review and Extensions // Ann. Oper. Res. 2018 (online

first). DOI: 10.1007/s10479-018-2934-8

19. Васильева С.Н., Кан Ю.С. Метод решения задачи квантильной оптимизации с

билинейной функцией потерь // АиТ. 2015. № 9. С. 83-101.

Vasil’eva S.N., Kan Yu.S. A Method for Solving Quantile Optimization Problems

with a Bilinear Loss Function // Autom. Remote Control. 2015. V. 76. No. 9.

P. 1582-1597.

20. Васильева С.Н., Кан Ю.С. Алгоритм визуализации плоского ядра вероятност-

ной меры // Информ. и её примен. 2018. Т. 12. № 2. С. 60-68.

21. Кибзун А.И., Малышев В.В. Обобщенный минимаксный подход к решению за-

дач с вероятностными ограничениями // Изв. АН СССР. Техническая киберне-

тика. 1984. № 1. С. 20-29.

Статья представлена к публикации членом редколлегии Е.Я. Рубиновичем.

Поступила в редакцию 20.06.2019

После доработки 10.09.2019

Принята к публикации 26.09.2019