Автоматика и телемеханика, № 11, 2019

Стохастические системы

Ю.С. КАН, д-р физ.-мат. наук (yu_kan@mail.ru)

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

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

АППРОКСИМАЦИЯ ВЕРОЯТНОСТНЫХ ОГРАНИЧЕНИЙ

В ЗАДАЧАХ СТОХАСТИЧЕСКОГО ПРОГРАММИРОВАНИЯ

С ИСПОЛЬЗОВАНИЕМ ЯДРА ВЕРОЯТНОСТНОЙ МЕРЫ¹

Рассматривается задача линейного стохастического программирования

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

ными ограничениями. Каждое вероятностное ограничение представля-

ет собой ограничение снизу на функцию вероятности, равную вероятно-

сти выполнения некоторого линейного неравенства. Предлагается снача-

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

венств для функций квантили. После этого каждая функция квантили

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

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

многомерного вероятностного распределения. Для случая когда функции

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

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

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

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

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

ничения, ядро вероятностной меры.

DOI: 10.1134/S0005231019110059

1. Введение

Введем основные понятия и обозначения. Пусть η - случайная величи-

на с функцией распределения F_η(y) = P{η ≤ y}, где P обозначает вероят-

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

p ∈ (0,1) определяется стандартным соотношением

[η]_p = min{y : F_η(y) ≥ p}.

Пусть f(u, ξ) - вещественная функция потерь, зависящая от вектора стра-

тегии u и случайного вектора ξ. Если функция потерь является борелев-

ской по ξ, то η_u = f(u, ξ) является случайной величиной. Ее функция рас-

пределения называется функцией вероятности для функции потерь f(u, ξ),

и p-квантиль [η_u]_p , как функция u, называется функцией квантили для той

¹ Результаты работы получены в рамках выполнения Государственного задания Мин-

обрнауки № 2.2461.2017/4.6.

же функции потерь. Роль функций вероятности и квантили в стохастическом

программировании описана в [1]. Современное состояние теории оптимизаци-

онных задач с такими функциями достаточно полно отражено в [2]. Наиболее

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

роятностными ограничениями. Их можно определить двумя способами. Пер-

вый способ связан с совместными вероятностными ограничениями. Стра-

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

когда

(1)

P{g(u, ξ) ≤ 0} ≥ p,

где g(u, x) - вектор-функция, p ∈ (0, 1) - заданная вероятность и неравенство

g(u, ξ) ≤ 0 понимается покомпонентно. Таким образом, совместные вероят-

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

системы неравенств, зависящих от случайных параметров. Второй способ свя-

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

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

(2)

P{g_i(u, ξ) ≤ 0} ≥ p_i

∀i = 1,k,

где вещественные функции g_i(u, ξ) можно интерпретировать как компоненты

вектор-функции g(u, ξ). Заметим, что с формальной точки зрения совмест-

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

индивидуальное вероятностное ограничение

{

}

(3)

P max g_i(u,ξ) ≤ 0

≥ p.

i=1,k

Однако на этом пути можно потерять “хорошие” свойства функций g_i, напри-

мер их линейность.

Впервые вероятностные ограничения в форме совместных вероятностных

ограничений были введены и рассмотрены в [3], где функция g(u, ξ) = T u - ξ

имеет линейную структуру, T - технологическая матрица. Ранее исследо-

вания вероятностных ограничений были сконцентрированы в основном на

построении детерминированных эквивалентов. Их суть - преобразование ве-

роятности в левой части (1) в детерминированную функцию вектора страте-

гии [4]. К сожалению, класс задач, в которых могут быть построены такие

эквиваленты, является достаточно узким. Наиболее сложный случай возни-

кает, если случайные параметры - компоненты вектора ξ - являются взаимно

зависимыми. Это препятствие было преодолено в [5, 6] путем использова-

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

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

гда g(u, ξ) = T u - ξ имеет детерминированную технологическую матрицу T.

Этот результат был позже распространен на случай со случайной технологи-

ческой матрицей [7], см. также [8].

Большой прорыв в этой области связан с именем венгерского математика

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

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

ми. Эти условия основаны на том, что многие многомерные распределения

обладают свойством логарифмической вогнутости. Этот факт позволил при-

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

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

вероятностными ограничениями. Основные результаты по данному вопросу

собраны в [9]. Хотелось бы также отметить другие результаты, достигну-

тые в конце XX в., а именно эффективные алгоритмы проверки выполнения

вероятностных ограничений. Хороший обзор этих алгоритмов можно найти

в [10].

Среди недавних результатов, определяющих современное состояние тео-

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

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

Монте-Карло (SAA - Sample Average Approximation), см., например, [11-18],

также отметим метод стохастической аппроксимации [19, 20] и математиче-

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

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

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

ры имеют дискретное распределение. Отметим, что понятие p-эффективных

точек фактически является расширением понятия p-квантили в многомерном

случае.

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

также сыграли публикации [24-27], где развит метод решения задачи кван-

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

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

ности. В отличие от этих работ, в настоящей статье рассматриваются зада-

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

случайных параметров модели. В [28] исследована задача квантильной опти-

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

параметрами. Предложен алгоритм нахождения некоторого решения, назы-

ваемого “гарантирующим” и дана оценка его точности по значению критерия.

На примерах показано, что гарантирующее решение может быть удовлетво-

рительно. Вместе с тем следует отметить, что сходимость гарантирующего

решения к точному не обоснована.

Мотивация авторов настоящей статьи связана с двумя обстоятельствами.

Во-первых, большинство публикаций, посвященных вероятностным ограни-

чениям, рассматривают случаи, когда функции g(u, ξ) и g_i(u, ξ) линейны по

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

в области стохастического программирования с вероятностными критериями

нацелены именно на такой класс задач. Основными публикациями авторов по

данной тематике являются [29, 30]. В них предлагаются алгоритмы решения

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

вероятностного распределения. Его определение и свойства описаны в разде-

ле 2. В разделе 3 показано, что совместные и индивидуальные вероятностные

ограничения могут быть записаны как неравенства для функции(й) кванти-

ли и представлены в детерминированной форме с помощью p-ядра. В раз-

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

минированной линейной функцией потерь и несколькими индивидуальными

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

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

помощью подхода, предложенного в [29] для решения задачи квантильной оп-

тимизации с билинейной функцией потерь. Основу подхода составляет внеш-

няя, сколь угодно точная полиэдральная аппроксимация p-ядра [29].

2. p-Ядро многомерного распределения

Введем понятие p-ядра [1] для n-мерного случайного вектора ξ. Это поня-

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

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

функции g_i(u, ξ), i = 1, k, линейны по ξ. Здесь и далее вероятностная мера P

ассоциируется с распределением вектора ξ, т.е. она определена на всех изме-

римых по Борелю подмножествах Rⁿ. Также будем полагать, что векторы

из Rⁿ являются вектор-столбцами.

Измеримое по Борелю множество S является p-доверительным, если спра-

ведливо P(S) ≥ p. p-Ядро K(p) определяется как пересечение всех замкнутых

выпуклых p-доверительных множеств [2]. С другой стороны, для него спра-

ведливо следующее представление [2]:

⋂

{

}

(4)

K(p) =

x ∈ Rⁿ : c^Tx ≤ b_p(c)

∥c∥=1

где ∥·∥ - евклидова норма вектора, а b_p(c) = [c^Tξ]_p - квантиль уровня p. Таким

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

полупространств, соответствующих единичным векторам внешней нормали c.

Как показано в [29], множество K(p) всегда (т.е. для любого распределения P)

не пусто, если p > n/(n + 1). Очевидно, что непустое p-ядро является выпук-

лым компактным множеством. Также в [29] предложен алгоритм аппрокси-

мации p-ядра выпуклым многогранником

⋂

{

}

(5)

K_N(p) =

x ∈ Rⁿ : c^Tx ≤ b_p(c)

c∈C_N

где C_N - конечное множество из N единичных векторов. Этот алгоритм осно-

ван на построении сгущающейся сети точек на поверхности единичной сфе-

ры, задающих множество векторов нормали c ∈ Rⁿ. Алгоритм построения

векторов нормали заключается в нанесении равномерной сети точек на по-

верхность n-мерного куба. Проекция этих точек на единичную сферу и бу-

дет задавать множество C_N векторов нормали c. Такое множество векторов

нормали сгущается с увеличением числа N. Соседними векторами из множе-

ства C_N на единичной сфере назовем векторы, прообразы которых на кубе

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

В некоторых случаях в [29] для функции b_p(c) удается получить анали-

тическое выражение. В общем случае это сделать проблематично. В таких

ситуациях вместо b_p(c) можно попытаться использовать ее выборочную оцен-

куbp(c) [2] и аппроксимировать p-ядро множеством

⋂

{

}

(6)

K_N (p) =

x ∈ Rⁿ : c^Tx ≤ bp(c)

c∈C_N

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

K_N (p) вместо

K_N(p) выходит за рамки данной статьи.

Алгоритм построения густого множества векторов C_N , предложенный

в [29], реализован в программном модуле ProKer (Probabilistic Kernel) [31]

для пакета MATLAB в случае n = 2, где компоненты вектора ξ независимы

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

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

p-ядра для различных p.

Схожая идея аппроксимации выпуклых p-доверительных множеств с по-

мощью многогранников использовалась ранее в [25]. Отметим, что p-ядро не

является p-доверительным множеством.

Очевидно, что K(p) ⊆ K(q) для всех p < q, так как каждое p-довери-

тельное полупространство с вектором нормали c является подмножеством

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

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

мации вероятностных ограничений свойством p-ядра непрерывных распреде-

лений является регулярность [2]. p-Ядро является регулярным тогда и только

тогда, когда каждое замкнутое полупространство, содержащее его, является

p-доверительным. Пример нерегулярного p-ядра можно найти в [2]. Там же

сформулированы следующие достаточные условия регулярности p-ядра.

Теорема 1. Пусть выполнены следующие условия:

(i) случайный вектор ξ имеет плотность вероятности,

(ii) граница p-ядра K(p) для распределения вектора ξ является гладкой

поверхностью в Rⁿ.

Тогда K(p) является регулярным.

Для обобщения теоремы 1 определим множество S_p всех точек x^∗ на гра-

нице p-ядра, для которых выполнено условие x^∗ ∈ Arg maxx∈K(p) c^T x для раз-

личных c. Другими словами, вектор внешней нормали к K(p) в точках из S_p

не является единственным.

Теорема 2. Пусть выполнены следующие условия:

(i) случайный вектор ξ имеет плотность вероятности,

(ii) P{c^Tξ ≤ c^Tx^∗} ≥ p для любого x ∈ S_p и любого единичного нормального

вектора c.

Тогда K(p) является регулярным.

Доказательство теоремы 2 приведено в Приложении.

Следующий, не менее важный результат, также доказан в [2, след-

ствие 3.13].

Теорема 3. Пусть случайный вектор ξ имеет регулярное p-ядро для

некоторого p ∈ (0,1). Тогда

[

]

a^T(u)ξ + b(u)_p = b(u) + max a^T(u)x.

x∈K(p)

Именно эта теорема является основополагающей при построении детерми-

нированных эквивалентов или аппроксимаций вероятностных ограничений,

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

треугольника для квантилей, т.е.

[ξ₁ + ξ₂]_p ≤ [ξ₁]_p + [ξ₂]_p,

если p-ядро распределения случайного вектора ξ = (ξ₁, ξ₂)^T является регу-

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

[ξ₁ + ξ₂]_p =

max

(x₁ + x₂) ≤ max

x₁ + max x₂ = [ξ₁]_p +[ξ₂]_p.

(x₁,x₂)∈K(p)

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

p-ядер, которые имеют самостоятельный интерес. Обозначим координа-

ты векторной медианы μ случайного вектора ξ с помощью соотношения

μ_k = [ξ_k]1/2 для всех k = 1,... ,n.

Теорема 4. Пусть выполнены следующие условия:

(i) случайный вектор ξ имеет плотность вероятности;

(ii) P{μ_k < ξ_k < μ_k + ε} > 0 и P{μ_k - ε < ξ_k < μ_k} > 0 для любого ε > 0,

k = 1,...,n;

(iii) p-ядро K(p) не пусто для любого p ∈ (1/2, 1).

Тогда при p = 1/2 p-ядро K(p) является регулярным и содержит един-

ственную точку μ.

Доказательство теоремы 4 приведено в Приложении.

Свойство регулярности ядра, состоящего из единственной точки - медиа-

ны μ - приводит к ее устойчивости по отношению к ортогональным преобра-

зованиям. Рассмотрим новый случайный вектор ξ^∗ = Sξ, где S - ортогональ-

ная (n × n)-матрица, т.е. S^T = S-1. Обозначим через μ медиану вектора ξ, а

через μ^∗ - медиану вектора ξ^∗. Регулярность μ означает μ^∗ = Sμ точно так

же, как для математического ожидания E всегда справедливо Eξ^∗ = S · Eξ.

Следует подчеркнуть, что наиболее ограничительным условием теоремы 4

является (iii). Оно может быть проверено численно, например, с помощью

программного модуля ProKer, а также при построении p-ядер с p, близкими

к 1/2, или при прямом построении K_N (1/2). Успешные в этом смысле ре-

зультаты получены для нормального распределения, распределения Коши и

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

случае. Однако аппроксимации p-ядер для экспоненциального и логнормаль-

ного распределений оказались пустыми уже при p = 0,53, что свидетельству-

ет о невыполнении условия (iii) теоремы 4 и, как следствие, о пустоте p-ядра

для p = 0,5.

Лемма 1. Для любой точки x₀, принадлежащей границе p-ядра K_p, су-

ществует p-доверительное полупространство, для которого эта точка то-

же является граничной.

Доказательство леммы 1 приведено в Приложении.

Для доказательства теоремы 5 понадобится следующая лемма [29].

Лемма 2. Для любых соседних точек c_j и c_k на единичной сфере, сгене-

рированных алгоритмом из [29], справедливо ||c_j - c_k|| → 0 при N → ∞.

Теорема 5. Пусть функция квантили b_p(c) непрерывна, тогда множе-

ство K_N(p), построенное с помощью алгоритма, предложенного в [29], схо-

дится в метрике Хаусдорфа к множеству K(p) с ростом N.

Доказательство теоремы 5 приведено в Приложении.

Из теоремы 5 следует, что полиэдральная модель, построенная с помощью

алгоритма, предложенного в [29], сколь угодно точно аппроксимирует p-ядро

как в случае регулярного, так и в случае нерегулярного ядра.

Условие непрерывности функции квантили b_p(c) может быть проверено с

помощью известных результатов из [2]. Например, если случайная величи-

на ξ имеет ограниченный носитель, то функция квантили b_p(c) непрерывна

согласно [2, теорема 2.5].

3. Задача стохастического программирования

с вероятностными ограничениями

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

ми вероятностными ограничениями

(7)

h(u) → max

u∈U

при ограничениях (2), где h(u) - детерминированная вещественная целевая

функция. Как было отмечено в [32], индивидуальные вероятностные ограни-

чения (2) легко сводятся к системе детерминированных неравенств в случае,

когда функции g_i(u, ξ) являются сепарабельными по u и ξ. Обобщим этот

результат для случая, когда эти функции линейны по ξ.

Для начала рассмотрим индивидуальные вероятностные ограничения об-

щего вида (2). Они связаны с неравенствами для функций вероятности, со-

ответствующих функциям потерь g_i(u, ξ). Пусть η - случайная величина c

функцией распределения F_η(y). В [33] установлено, что неравенство F_η(y) ≥ p

выполнено тогда и только тогда, когда [η]_p ≤ y. Поэтому каждое вероятност-

ное ограничение в (2) может быть представлено в эквивалентной квантильной

форме:

(8)

[g_i(u, ξ)]

≤ 0.

p_i

Рассмотрим случай, когда функции g_i(u, ξ) линейны по ξ, т.е. g_i(u, ξ) =

= aTi (u)ξ + b_i(u) и p_i-ядра распределения вектора ξ являются регулярными.

Тогда, применяя теорему 3, выражение (8) можно представить в форме

(9)

b_i(u) + max

aTi

(u)x ≤ 0.

x∈K(p_i)

Отметим, что если функция b_i(u) выпукла, а функция aTi(u)x выпукла по

u для любого вектора x ∈ K(p_i), то левая часть неравенства (9) является

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

является выпуклым.

Далее, заменим p_i-ядро в выражении (9) его полиэдральной аппроксимаци-

ей K_N (p_i), где v^ji ∈ J_i - j-я вершина многогранной аппроксимации p-ядра для

значения p = p_i, j = 1, N , и J_i - множество вершин полиэдральной аппрокси-

мации p-ядра для значения p = p_i. Учитывая линейность максимизируемой

функции в (9), имеем

max

aTi(u)x = maxaTi(u)v^ji.

x∈K_N (p_i)

j∈J_i

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

ное ограничение из (2) может быть аппроксимировано системой неравенств

(10)

b_i(u) + aTi(u)v^ji ≤ 0, j ∈ J_i.

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

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

b_i(u) и a_i(u) линейны по u, это условие выполнено. Рассмотрим это подробнее

в разделе 4.

4. Аппроксимация задачи стохастического программирования

с билинейными вероятностными ограничениями

Рассмотрим специальный случай задачи линейного стохастического про-

граммирования

(11)

d^Tu → max

u∈U

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

(12)

U = {u : Au ≤ B}

и индивидуальных вероятностных ограничениях вида

{

}

(13)

αTiu + βTiξ + u^TΘ_iξ + γ_i ≤ 0

≥p_i

∀i = 1,k,

где u - вектор оптимизируемой стратегии из R^m, d - детерминированный

вектор размерности m, p_i ∈ (0, 1) - заданная доверительная вероятность, A -

детерминированная матрица размеров k × m, B - заданный вектор размерно-

сти k, ξ - n-мерный случайный вектор, α_i - детерминированный m-мерный

вектор, β_i - детерминированный n-мерный вектор, Θ_i - заданная матрица

размеров m × n и γ_i - действительное число. С учетом результатов раздела 3

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

вания. Следуя результатам раздела 3, функции a_i(u) и b_i(u) можно предста-

вить в линейной форме:

a_i(u) = β_i + ΘTiu, b_i(u) = αTiu + γ_i.

Учитывая факт, что ограничения (10) могут быть записаны в виде линейных

неравенств

(

)

(14)

αTiu + γ_i +

βTi + u^TΘ_i

v^ji ≤ 0, j ∈ J_i,

исходная задача стохастического программирования (11), (12) и (13) аппрок-

симируется задачей линейного программирования (11), (12) и (14).

Теорема 6. Пусть U - компактное множество, функции bpi(c) непре-

рывны по c, p_i-ядра регулярны и β_i + Θ_iu = 0 ∀i = 1,k,∀u ∈ U. Тогда решение

100

задачи (11), (12) и (14) сходится по значению критерия к решению задачи

(11), (12) и (13).

Доказательство теоремы 6 приведено в Приложении.

5. Пример

Рассматривается оптимизационная задача

(15)

u₁ - 2u₂ → max

u₁,u₂

при детерминированных ограничениях:

(16)

u₁ ≥ 0, u₂ ≥ 0, u₁ + u₂

≤1

и двух вероятностных ограничениях вида:

(17)

P(u₁ξ₁ - u₂ξ₂

≤ 1) ≥ 0,9,

(18)

P(3u₁ξ₁ - u₂ξ₂

≤ 2) ≥ 0,7,

где ξ₁, ξ₂ — независимые, одинаково равномерно распределенные на [0, 1] слу-

чайные величины.

В соответствии с результатами раздела 3 вероятностные ограничения (25),

(26) можно переписать в эквивалентной квантильной форме:

(19)

[u₁ξ₁ - u₂ξ₂]0,9 ≤ 1,

[3u₁ξ₁ - u₂ξ₂]0,7

≤ 2.

С использованием теоремы 2 эти неравенства равносильны следующим:

(20)

max

(u₁x₁ - u₂x₂) ≤ 1,

max

(3u₁x₁ - u₂x₂

) ≤ 2,

(x₁,x₂)∈K(0,9)

(x₁,x₂)∈K(0,7)

где K(p) — p-ядро равномерного распределения на квадрате [0, 1] × [0, 1].

В [29] установлена регулярность p-ядра равномерного распределения. Так-

же в [29] были получены соотношения для нахождения координат точек на

границе p-ядра K(p) в случае двумерного случайного вектора, имеющего рав-

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

осям координат и симметричными относительно них:



(1 - p)



(21)

|x₂| =

-^



ри |x₁| ≤ p -

 п

1 - 2|x₁|

С целью иллюстрации предложенного в статье подхода заменим p-ядра

в (20) их аппроксимациями с помощью многогранников, как описано в раз-

деле 4. В расчетах множества J₁ и J₂ содержат одинаковое число точек, т.е.

ядра K(0,9) и K(0,7) аппроксимированы полиэдрами, содержащими одина-

ковое число вершин N. В результате ограничения (20) аппроксимируются

системами линейных неравенств:

(22)

u₁vj1 - u₂vj2 ≤ 1 ∀j ∈ J₁,

3u₁vj1 - u₂vj2 ≤ 1 ∀j ∈ J₂,

а исходная задача - задачей линейного программирования (23), (24), (22).

Для N = 128 получено следующее решение аппроксимирующей задачи

линейного программирования: u = (0,9522; 0), оптимальное значение целе-

вой функции 0,9522. Время работы программы составляет около 3 секунд.

101

Для N = 16 результаты схожие: u = (0,9524; 0), оптимальное значение целе-

вой функции 0,9524, время счета составляет примерно 0,8 с. В этих расче-

тах функция квантили b_p(c) вычислялась точно с использованием указанно-

го выше результата [29]. При замене точного выражения для функции b_p(c)

ее выборочной оценкой для объема выборки n = 10⁶ результаты следующие.

Для N = 16 получено решение u = (0,9530; 0), оптимальное значение крите-

рия 0,9530. Для N = 128 : u = (0,9527; 0), значение критерия 0,9527.

В силу того что первое вероятностное ограничение выполнено для всех

допустимых u₁ и u₂, получается решить поставленную задачу аналитиче-

ски с помощью метода детерминированных эквивалентов [2]. Таким образом,

может быть получено точное решение исходной задачи: u = (20/21, 0), значе-

ние критерия 20/21. Это свидетельствует о работоспособности предложенно-

го подхода.

Заменим значения параметров в ограничениях предыдущей задачи

(23)

u₁ - 2u₂ → max

u₁,u₂

при детерминированных ограничениях:

(24)

u₁ ≥ 0, u₂ ≥ 0, u₁ + u₂

≤1

и двух вероятностных ограничениях вида:

(25)

P(u₁ξ₁ - u₂ξ₂

≤ 0,5) ≥ 0,9,

(26)

P(3u₁ξ₁ - u₂ξ₂

≤ 2) ≥ 0,7,

где ξ₁, ξ₂ — независимые, одинаково распределенные по равномерному закону

на отрезке [0, 1] случайные величины.

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

это было сделано в предыдущем примере. При N = 128 получено решение

u = (0,5556;0), значение критерия равно соответственно 0,5556. При N = 16

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

знака.

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

Рассмотрена задача стохастического программирования с детерминиро-

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

ниями, задаваемыми неравенствами с билинейной структурой. С использова-

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

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

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

с большим числом ограничений типа неравенств. Работоспособность предло-

женного метода проиллюстрированна на численном примере.

ПРИЛОЖЕНИЕ

Доказательство теоремы 2. Случай, когда множество S_p пусто,

рассматривается по аналогии с доказательством теоремы 1 из [2]. Если же

S_p не пусто, то указанное доказательство сохраняет силу, так как условие (ii)

102

гарантирует, что каждое замкнутое полупространство, содержащее K(p) и

имеющее граничную гиперплоскость, которая проходит через точку x^∗ ∈ S_p,

автоматически является p-доверительным.

Теорема 2 доказана.

Доказательство теоремы

Из (i) следует P {ξ_k = μ_k} = 0,

P{ξ_k < μ_k} = 1/2 и P{ξ_k > μ_k} = 1/2, k = 1,n. Используя (ii), получа-

ем, что для некоторого ε > 0 существует 2n замкнутых полупространств

{x : x_k ≤ μ_k + ε} и {x : x_k ≥ μ_k - ε}, k = 1, n, которые являются p-довери-

тельными для некоторого p = p(ε) > 1/2. Их пересечение образует куб C_ε со

стороной 2ε, для которого справедливо включение μ ∈ C_ε.

Из выполнения условия (iii) следует, что K(p) = ∅ и выполнено K(p) ⊂ C_ε.

Пусть при этом μ ∈ K(p). Тогда по аналогии с C_ε можно построить множе-

ство Cε1 , для ε₁ < ε такое, что μ ∈ Cε1 и Cε1 ∩ K(p) = ∅. Тогда найдется такое

p₁ = p₁(ε), для которого справедливо 1/2 < p₁ < p, для которого выполне-

но K(p₁) ⊂ Cε1 . Но поскольку p₁ < p, то должно выполняться K(p₁) ⊂ K(p),

но по построению имеем Cε1 ∩ K(p) = ∅. Получаем противоречие. Следова-

тельно, медиана μ является внутренней точкой p-ядра K(p) для любого p ∈

∈ (1/2, 1).

Пусть p-ядро K(p) при p = 1/2 не является регулярным. Тогда существует

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

ше 1/2. Тогда его замкнутое дополнение имеет меру p₁ > 1/2. По определению

p-ядра это дополнение содержит в себе ядро K(p₁). Выше было доказано, что

для любого p ∈ (1/2, 1) μ ∈ K(p). Таким образом, получаем противоречие.

Согласно условиям P {ξ_k = μ_k} = 0, P {ξ_k < μ_k} = 1/2 и P {ξ_k > μ_k} = 1/2

p-ядро при p = 1/2 содержит единственную точку μ.

Теорема 4 доказана.

Доказательство леммы 1. Предположим, что точка x₀ принадле-

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

ства, для которого она является граничной. В случае когда p-доверительное

полупространство не содержит точку x₀, она также не принадлежит и p-ядру.

Пусть точка x₀ принадлежит некоторому p-доверительному полупростран-

ству вместе со своей окрестностью, тогда выполнено c^Tx₀ < b_p(c) для любого

c : ∥c∥ = 1. Преобразуем данное выражение:

0 < b_p(c) - c^Tx₀.

Поскольку настоящее выражение справедливо для любого c : ∥c∥ = 1, то вве-

дем обозначение

h = min (b_p(c) - c^Tx₀).

c:∥c∥=1

Минимум достигается, поскольку функция b_p(c) - полунепрерывна снизу

согласно [2, лемма 2.11], а функция c^Tx₀ - непрерывна.

Тогда справедливо неравенство

0 < h ≤ b_p(c) - c^Tx₀.

103

Рассмотрим любую точку x^∗, принадлежащую малой окрестности точки x₀.

Из полунепрерывности снизу функции квантили вытекает, что для всех c :

∥c∥ = 1 справедливо неравенство

0 < b_p(c) - c^Tx^∗.

Это можно представить как

(Π.1)

c^Tx^∗ < b_p

(c)

∀c : ∥c∥ = 1.

Согласно определению p-ядра (4) и (Π.1) точка x^∗ является внутренней точ-

кой p-ядра. Это противоречит тому, что точка x₀ выбрана на границе p-ядра.

Лемма 1 доказана.

Доказательство теоремы 5. С учетом того что полиэдральная ап-

проксимация K_N (p) является внешней, т.е. K(p) ⊂ K_N (p), достаточно прове-

рить, что расстояние от любой граничной точки множества K(p) до границы

множества K_N (p) стремится к нулю при N → ∞.

Согласно лемме 1 для любой точки x₀, принадлежащей границе ядра K(p),

существует полупространство, заданное неравенством c∗Tx ≤ b_p(c^∗), для ко-

торого точка x₀ является граничной. Тогда в силу непрерывности функции

квантили b_p(c) и леммы 2 для любого ε > 0 существуют δ = δ(ε) > 0 и N =

= N(ε) такие, что для любого вектора c^∗ : ∥c^∗∥ = 1 существует вектор c^′, по-

рожденный алгоритмом из [29] и такой, что ∥c^∗ - c^′∥ < ε и |b_p(c^∗) - b_p(c^′)| < δ

начиная с номера N.

Расстояние от x₀ до гиперплоскости {x : c′Tx = b_p(c^′)} равно b_p(c^′) - c′Tx₀.

Из неравенств ∥c^∗ - c^′∥ < ε и |b_p(c^∗) - b_p(c^′)| < δ вытекает, что это расстояние

стремится к нулю при N → ∞.

Теорема 5 доказана.

Доказательство теоремы 6. Для доказательства необходимо опре-

делить дилатацию множества K_N (p) радиуса δ:

⋃

(Π.2)

K^δ(p_i) =

B_δ(x), где B_δ

(x) = {y : ∥y - x∥ ≤ δ}.

x∈K(p_i)

Обозначим g_i(u, ξ) = αTiu + βTiξ + u^TΘ_iξ + γ_i. Поскольку, как отмечалось

выше, ограничение (13) равносильно неравенству

(Π.3)

[g_i(u, ξ)]pi

≤ 0,

то с учетом условия регулярности p_i-ядра K(p_i) и (9) неравенство (Π.3) может

быть представлено в эквивалентной форме

(Π.4)

max g_i

(u, x) ≤ 0.

x∈K(p_i)

Поскольку функции bpi (c) непрерывны по условию теоремы, то, используя

лемму 5, заключаем, что K_N (p_i) ----→

K(p_i) в метрике Хаусдорфа и ∀δ > 0

N→∞

∃N₀ : ∀N ≥ N₀ K(p_i) ⊆ K_N (p_i) ⊂ K^δ(p_i) ∀i = 1,k. При этом K^δ(p_i)

−-→

K(p_i)

δ→0

в метрике Хаусдорфа. Обозначим U_i(δ) = {u ∈ U : h_i(u, δ) ≤ 0}, где h_i(u, δ) =

= max_x∈Kδ(pi) ^gi(u,x). Отметим, что множество Ui(δ) имеет вспомогательный

104

характер и введено оно для применения результата из [34]. Так как функ-

ция h_i(u, δ) непрерывна по u ∈ U и по δ в точке δ = 0 согласно [34, лемма 1.1

(II)], то для завершения доказательства теоремы достаточно показать [34,

лемма 1.1 (II)], что многозначное отображение U_i(δ) непрерывно в метрике

Хаусдорфа по δ в точке δ = 0. Для этого достаточно проверить, что функ-

ция h_i(u, δ) строго монотонна по δ. Для этого покажем, что функция g_i(u, x)

достигает по x на множестве K^δ(p_i)\K(p_i) значения, которое превышает ве-

личину maxx∈K(pi) gi(u, x), при фиксированном u. Градиент функции gi(u, x)

по x не зависит от x и равен

∇_x (g_i(u,x)) = β_i + Θ_iu.

По условию теоремы градиент отличен от нуля, что и обеспечивает выполне-

ние доказываемого условия. Таким образом, решение задачи линейного про-

граммирования (11), (12) и (14) сходится по значению критерия к решению

задачи (11), (12) и (13).

Теорема 6 доказана.

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

Kibzun A., Kan Yu. Stochastic Programming Problems with Probability and

Quantile Functions. Wiley: Chichester, 1996.

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

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

Charnes A., Cooper W.W. Chance-constrained Programming // Manag. Sci. 1959.

No. 6. P. 73-79.

Miller B.L., Wagner H.M. Chance Constrained Programming with Joint

Constraints // Oper. Res. 1965. No. 13. P. 930-945.

Lejeune M.A. Pattern-based Modeling and Solution of Probabilistically Constrained

Optimization Problems // Oper. Res. 2012. No. 60. P. 1356-1372.

Lejeune M.A. Pattern Definition of the p-Efficiency Concept // Ann. Oper. Res.

2012. No. 200 P. 23-36.

Kogan A., Lejeune M.A. Threshold Boolean Form for Joint Probabilistic Constraints

with Random Technology Matrix // Math. Program. 2014. No. 147. P. 391-427.

Henrion R. Structural Properties of Linear Probabilistic Constraints

Optimization. 2007. V. 56. No. 4. P. 425-440.

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

10.

Genz A., Bretz F. Computation of Multivariate Normal and t-Probabilities.

Heidelberg: Springer, 2009.

11.

Barrera J., Homem-de-Mello T., Moreno E., Pagnoncelli B.K., Canessa G. Chance-

Constrained Problems and Rare Events: an Importance Sampling Approach // Math.

Program. Ser. B. 2016. No. 157. P. 153-189.

12.

Guigues V., Juditsky A., Nemirovski A. Non-asymptotic Confidence Bounds for the

Optimal Value of a Stochastic Program // Optim. Methods Softw. 2017. V. 32. No. 5.

P. 1033-1058.

13.

Kleywegt A.J., Shapiro A., Mello-de-Homem T. The Sample Average Approximation

Method for Stochastic Discrete Optimization // SIAM J. Optim. 2002. No. 12.

P. 479-502.

105

14.

Linderoth J., Shapiro A., Wright S. The Empirical Behavior of Sampling Methods

for Stochastic Programming // Ann. Oper. Res. 2006. No. 142. P. 215-241.

15.

Mak W.-K., Morton D.P., Wood R.K. Monte Carlo Bounding Techniques for

Determining Solution Quality in Stochastic Programs // Oper. Res. Lett. 1999.

No. 24. P. 47-56.

16.

Shapiro A. Monte Carlo sampling methods / Handbooks in Operations Research

and Management Science. Ruszczynski A., Shapiro A., eds. V. 10. Elsevier, 2003.

P. 353-425.

17.

Shapiro A., Nemirovski A. On Complexity of Stochastic Programming Problems

/ Continuous Optimization: Current Trends and Applications. Jeyakumar V.,

Rubinov A. Eds. Springer, 2005. P. 111-146.

18.

Verweij B., Ahmed S., Kleywegt A.J., Nemhauser G., Shapiro A. The Sample

Average Approximation Method Applied to Stochastic Routing Problems: A

computational study // Comput. Optim. Appl. 2003. No. 24. P. 289-333.

19.

Bottou L. Large-Scale Machine Learning with Stochastic Gradient Descent // Proc.

COMPSTAT’2010. Springer, 2010. P. 177-186.

20.

Nemirovski A., Juditsky A., Lan G., Shapiro A. Robust Stochastic Approximation

Approach to Stochastic Programming // SIAM J. Optim. 2009. No. 19. P. 1574-1609.

21.

Beraldi P., Ruszczynski A. A Branch and Bound Method for Stochastic Integer

Problems Under Probabilistic Constraints // Optim. Methods Softw. 2002. V. 17.

No. 3. P. 359-382.

22.

Prékopa A., Vizvári D., Badics T. Programming Under Probabilistic Constraint

with Discrete Random Variable / Giannesi F. (Ed.) New Trends in Mathematical

Programming. P. 235-255. Netherlands: Kluwer Acad. Publishers, 1998.

23.

Dentcheva D., Prékopa A., Ruszczynski A. Concavity and Efficient Points of Discrete

Distributions in Probabilistic Programming // Math. Program. 2000. No.

89.

P. 55-77.

24.

Иванов С.В., Кибзун А.И. О сходимости выборочных аппроксимаций задач сто-

хастического программирования с вероятностными критериями // АиТ. 2018.

№ 2. С. 19-35.

Ivanov S.V., Kibzun A.I. On the Convergence of Sample Approximations for

Stochastic Programming Problems with Probabilistic Criteria // Autom. Remote

Control. 2018. V. 79. No. 2. P. 216-228.

25.

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

полиэдральной функции потерь и дискретного распределения случайных пара-

метров // АиТ. 2012. № 1. С. 116-129.

Ivanov S.V., Naumov A.V. Algorithm to Optimize the Quantile Criterion for the

Polyhedral Function and Discrete Distribution for Random Parameters // Autom.

Remote Control. 2012. V. 73. No. 1. P. 105-117.

26.

Кибзун А.И., Наумов А.В., Норкин В.И. О сведении задачи квантильной оп-

тимизации с дискретным распределением к задаче смешанного целочисленного

программирования // АиТ. 2013. № 6. С. 66-86.

Kibzun A.I., Naumov A.V., Norkin V.I. On Reducing a Quantile Optimization

Problem with Discrete Distribution to a Mixed Integer Programming Problem //

Autom. Remote Control. 2013. V. 74. No. 6. P. 951-967.

27.

Норкин В.И., Кибзун А.И., Наумов А.В. Сведение задачи двухэтапной вероят-

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

чам частично целочисленного программирования // Кибернетика и системный

анализ. 2014. Т. 50. № 5. С. 34-48.

106

28. Наумов А.В., Иванов С.В. Исследование задачи стохастического программиро-

вания с квантильным критерием // АиТ. 2011. № 2. С. 142-158.

Naumov A.V., Ivanov S.V. On Stochastic Linear Programming Problems with the

Quantile Criterion // Autom. Remote Control. 2011. V. 72. No. 2. P. 353-369.

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

билинейной функцией потерь // АиТ. 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.

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

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

параметров // АиТ. 2017. № 7. С. 95-109.

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

Problems with Loss Function Depending on a Vector of Small Random Parameters //

Autom. Remote Control. 2017. V. 78. No. 7. P. 1251-1263.

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

ной меры // Информатика и ее применения. 2018. № 12. Вып. 2. С. 60-68.

32. Guigues V., Henrion R. Joint Dynamic Probabilistic Constraints with Projected

Linear Decision Rules // Optim. Methods Softw. 2017. V. 32. No. 5. P. 1006-1032.

33. Rosenblatt-Roth M. Quantiles and Medians // Ann. Math. Stat. 1965. No. 36.

P. 921-925.

34. Федоров В.В. Численные методы максимина. М.: Наука, 1979.

Статья представлена к публикации членом редколлегии А.И. Кибзуном.

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

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

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

107