Software & Systems

В моделях принятия решений зачастую приходится решать задачи оптимизации. В некоторых из них условия на допустимое множество задаются в лингвистической форме. Например, инвестор желает получить прибыль  с вероятностью не ниже некоторого заранее оговоренного уровня. Это приводит к формулировке оптимизационной задачи с вероятностными ограничениями [1]. Однако при решении подобных задач зачастую мы не знаем априори распределения вероятностей в тех или иных ситуациях и вынуждены вместо них использовать некоторые приближения или оценки. Для оценивания подобных приближений пользуются методами теории устойчивости или анализа возмущений, приложение которых и рассмотрено в настоящей статье для класса задач, определенного соотношением (1).

Рассмотрим следующую задачу оптимизации с вероятностными ограничениями

.                       (1)

Здесь  – s-мерный случайный вектор, определенный на вероятностном пространстве ;  – целевая функция;  – некоторое множество;  система ограничений неравенств;  – некоторый заданный уровень вероятности. Заданные ограничения по вероятности означают, что неравенство  должно быть выполнено с вероятностью не ниже p. Наиболее очевидным представляется задать ограничения в виде системы линейных неравенств, то есть , где A – некоторая матрица. Обозначим через  (борелево пространство вероятностных мер, определенных на ) распределение вероятностей случайного вектора . Сделаем некоторые предположения о выпуклости рассматриваемой проблемы: g выпукла, X замкнуто и выпукло, компоненты h вогнуты и вероятностная мера  является -вогнутой для некоторого .

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

           (2)

верно для всех  и всех измеримых по Борелю и выпуклых множеств , таких что  также измеримо по Борелю. Заметим, что большинство многомерных распределений являются r-вогнутыми для некоторого  [1].

Функцию распределения, соответствующую вероятностной мере , представим в виде , таким образом задачу (1) можно переписать следующим образом:

.

Однако в большинстве случаев известна лишь частичная информация о , и проблема (1) решается в предположениях некоторой меры , являющейся оценкой для . Обычно v выбирается как параметрическая или непараметрическая оценка . Таким образом, вместо задачи (1) решается некоторая задача

.                       (3)

И если получена достаточно хорошая аппроксимация v меры , очевидно, что решения задачи (3) будут стремиться к решениям задачи (1) при условии, что v стремится к .

Хотя предполагается, что исходная задача выпукла, однако не следует делать предположений о возмущенной задаче (3). Это позволяет рассмотреть класс эмпирических аппроксимаций, которые не обладают свойствами выпуклости или гладкости. И поскольку в общем случае задача (3) предполагает не единственное решение в условиях предположений (2), рассмотрим множества решений. Зависимость решений и оптимальных значений от параметра v описывается точечно множественным отображением  и расширенно-значной функцией  как

,

.

Рассмотрим условия, наложенные на исходную задачу (1), при которых  и  локально устойчивы относительно фиксированной меры . Для того чтобы измерить расстояние между параметрами и между решениями, воспользуемся метрикой Колмогорова, заданной на множестве вероятностных мер,

, () и мет­рикой Колмогорова, определенной на множестве замкнутых подмножеств ,

, ().

Качественная устойчивость задачи (1) предполагает, что  при . При определенных условиях это означает, что предельные точки аппроксимирующих решений будут решениями исходной задачи и любое решение исходной задачи будет пределом для последовательности аппроксимирующих решений.

Помимо качественной устойчивости огромный интерес представляет вопрос количественной устойчивости. Напомним, что  непрерывно в смысле Хаусдорфа-Гельдера с показателем  в , если существуют  такие, что

                             (4)

для всех , .

Существует прямая связь между непрерывностью по Хаусдорфу-Гельдеру с показателем k отображения множества решений и экспоненциальными границами эмпирических приближений решения [2]. И отклонения эмпирических аппроксимаций от множества решений исходной задачи может быть оценено при помощи экспоненциальных границ [2,3].

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

Теорема 1. В дополнение к условиям (2) пусть выполнены следующие положения для фиксированной вероятностной меры :

1.  не пусто и ограничено.

2. Существует , такой что .

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

Заметим, что в теореме 1 липшицева оценка для  имеет ограничения: одна из мер () должна быть фиксирована. Более сильный результат, когда обе меры варьируются около некоторой меры , не является верным при сделанных предположениях.

Для формулировки условий устойчивости множества решений введем следующие объекты, где  – открытый шар,

,

, (),

, ().

Заметим, что  и  обозначают соответственно множества решений и оптимальное значение параметрической задачи, ограничивающей решения исходной задачи снизу, а параметр y соответствует правосторонним возмущениям в неравенствах, заданных отображением h. В противоположность многозначная функция Y определяет множество решений параметрической задачи, ограничивающей решения исходной задачи сверху, в которой явные ограничения неравенства заменены условием, наложенным на значения функции распределения . Это позволяет отдельно рассматривать влияние  и h на выполнение условий неравенства, определенного для задачи (3).

Сформулируем результат, позволяющий определить устойчивость множества оптимальных решений задачи (3).

Теорема 2. В дополнение к условиям (2) пусть выполнены следующие предположения для некоторой фиксированной меры .

1.  не пусто и ограничено.

2. Существует , такой что .

3.  является строго выпуклой в  некоторой выпуклой окрестности U отображения , где  выбран в соответствии с условиями (2), так что  является r-вогнутой.

4.  непрерывна в смысле Хаусдорфа-Гельдера с показателем  на .

Тогда  непрерывна по Хаусдорфу-Гельдеру с показателем  в , то есть существуют константы , такие что

,, .

Первое предположение теоремы 2 носит чисто технический характер и может быть усилено, например, компактностью множества X. Второе может быть интерпретировано как условие Слейтера. В некоторых случаях его можно проверить, не зная в явном виде меры . Третье предположение теоремы 2 выполнено для r-вогнутых мер (), для которых  является строго выпуклой на ограниченных выпуклых множествах. И последнее предположение теоремы 2 требует Гельдеревой непрерывности  при условии, что определена метрика Хаусдорфа. Оно выполняется, например, в случае линейных отображений h, полиэдральных множеств X и выпуклых квадратичных функций g.

Список литературы

1.   Prekopa, A. Stochastic Programming. Kluwer, Dordrecht, 1995.

2.   Henrion, R., Romisch, W. Metric regularity and quantitative stability in stochastic programs with probability constraints. Math. Program. 84, 55-88 (1999).

3.   Henrion, R., Romisch, W. Stability of solutions to chance constrained stochastic programs. In: (J. Guddat, R. Hirabayashi, H.Th. Jongen and F. Twilt eds.) Parametric optimization and Related Topics V, Peter Lang, Frankfurt a.M. 2000, pp. 95-114.