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

Дискретизируем вероятностную меру следующим образом.Пусть , = 1, , — точки, сгенерированные случайным образом согласно плотности ().Δ ˜Определим меры этих точек как = {= } = 1/, = 1, .Δ˜=˜ 1 , ..., ˜ −1 ) — случайный вектор, соответствующий этим мерам,Пусть col(˜ ˜ = } = , где случайные подвекторы ˜ имеют ту же размерность, что ито есть {˜ Рассмотрим , = 1, − 1. Пусть () — функция распределения случайного вектора .выборочную функцию распределения ˆ (). В соответствии с теоремой Гливенко и Кантелп.н.ли, приведённой в работе А.Н.

Ширяева [71, С. 482], имеет место сходимость ˆ ()−−−→ ()при → ∞ для всех (п.н. – почти наверное), где () — функция распределения случайного вектора .Далее под дискретным распределением () специального вида будем понимать дискретное распределение, полученное путём дискретизации непрерывного распределения с помощью описанной выше схемы дискретизации.Рассмотрим следующее утверждение.˜ = col(˜ 1 , ..., ˜ −1 ) имеет дискретноеЛемма 1.1.

Пусть случайный вектор распределение () специального вида. Тогда существуют детерминированные функции˜ 1 ) такие, что (˜ ˜ = (˜ 1 )} = 1, = 2, − 1,{где ˜ – вероятностная мера, аппроксимирующая меру .Доказательство леммы 1.1.Пусть , = 1, , — апостериорная выборка, соответствующая плотности ().˜ = col(˜ 1 , ..., ˜ −1 ) имеет распределение () c мерамиПусть случайный вектор ˜ ˜ = } = 1/, = 1, . Найдем распределение подвектора ˜ 1 . Поскольку у исход{ного вектора существует плотность (), то вероятность { =˜ } = 0 для любого .Пусть , = 1, , — априорная выборка, соответствующая плотности ().

Поскольку˜˜ = } = 0 для всех ̸= , то есть ̸= почти навер{= } = 0 для всех , то {ное для всех ̸= . Но компоненты , = 1, − 1, вектора также имеют плотности˜ = } = 0 для всех ̸= , = 1, − 1. Это означает, что ̸= ( ), поэтому {почти наверное для всех ̸= , = 1, − 1.22˜ 1 , соответствующая введёнПусть 1 (˜1 ) — функция распределения подвектора ˜ а ˜1 — реализация слуным выше мерам.

Пусть ˜ — реализация случайного вектора ,чайного подвектора ˜1 . В соответствии с построением ˜1 = 1 для некоторого = 1, .Но так как среди подвекторов , = 1, , = 1, − 1, нет хотя бы двух одинаковых,то все остальные подвекторы ˜ , = 2, − 1, реализации ˜ совпадают с , = 2, − 1,где является тем же номером, что и у первого подвектора. Таким образом, устанавливается взаимно-однозначное соответствие ˜ = (˜1 ), = 2, − 1, между подвектором ˜1˜ Поэтомуи подвекторами ˜ , = 2, − 1.

Это верно для любой реализации ˜ вектора .˜ ˜ = (˜ 1 )} = 1, = 2, − 1.{Лемма 1.1 доказана.2Сформулируем утверждение, в соответствии с которым -этапная задача квантильной оптимизации сводится к эквивалентной двухэтапной задаче стохастического программирования. С этой целью будем пользоваться определением, введённым в работе А.И.

Кибзуна,А.В. Наумова и В.И. Норкина [36].Определение 1.1. Две задачи оптимизации будем считать эквивалентными, если:1) либо обе эти задачи имеют допустимые решения (с конечными значениями целевыхфункций), либо обе не имеют таких решений;2) если эти задачи имеют допустимые решения, то оптимальные значения их целевыхфункций (конечные или бесконечные) совпадают;3) если оптимальные значения их целевых функций конечны, то эти значения в обеихзадачах либо достигаются, либо не достигаются;4) если оптимальные значения целевых функций достигаются, то по оптимальномурешению одной задачи с помощью явно описанного алгоритма указывается оптимальноерешение другой задачи;5) если оптимальные значения целевых функций конечны, но не достигаются, то пооптимизирующей последовательности стратегий одной задачи по явно описанному алгоритму указывается оптимизирующая последовательность стратегий для другой задачи.Следует отметить, что в указанной работе отсутствует 5-й пункт определения.

Данноеупущение было выявлено и дополнено Ю.С. Каном.Далее везде будем понимать эквивалентность в смысле определения 1.1. Отметим, чтоприведённое отношение эквивалентности оптимизационных задач является транзитивным.Верна следующая теорема об эквивалентности многоэтапной линейной относительностратегий задачи стохастического программирования и двухэтапной задачи в априорных23постановках.Теорема 1.1.

-этапная задача в априорной постановке (1.6) с дискретным рас˜ эквивалентна в смысле определения 1.1 двухпределением () случайного вектора этапной задаче стохастического программирования специального вида.Доказательство теоремы 1.1.Рассмотрим вначале трёхэтапную задачу стохастического программирования в априорной постановке с учётом дискретизации меры. Запишем функцию потерь (1.8) исследуе˜ имеющиймой задачи, где вместо случайного вектора рассмотрим случайный вектор ,дискретное распределение специального вида:T ˜TT ˜T˜ ˜˜˜˜ = TΦ3 (, (·), )0 + 11 (1 ) + 1 1 (, 1 ) + 12 (1 , 2 ) + 2 2 (, 1 , 2 ).Согласно лемме 1.1 функция потерь трёхэтапной задачи стохастического программированияв априорной постановке будет иметь вид:T ˜TT ˜T˜ = T˜˜˜˜Φ3 (, (·), )0 + 11 (1 ) + 1 1 (, 1 ) + 12 (1 , 2 (1 )) + 2 2 (, 1 , 2 (1 )) =T ˜T ˜TT˜˜˜˜= T0 + (11 (1 ) + 12 (1 , 2 (1 ))) + 1 1 (, 1 ) + 2 2 (, 1 , 2 (1 )).Введём следующие обозначения:Δ˜ 1 ) = col(1 (, ˜ 1 ), 2 (, ˜ 1 , 2 (˜ 1 ))),¯1 (, Δ˜1) =˜ 1 ) + 12 (˜ 1 , 2 (˜ 1 )),¯11 (11 (T T¯T1 = (1 , 2 ).С учётом введённых обозначений функция потерь трёхэтапной задачи имеет структуруфункции потерь двухэтапной задачи:Δ˜ = Φ̄2 (, ¯1 (·), ˜1) =˜˜ 1 ).¯TΦ3 (, (·), )T¯T¯1 (, 0+11 (1 ) + 1(1.10)˜ имеющий дискретное распределение специальногоПодставим случайный вектор ,вида, в ограничения (1.9) исследуемой трёхэтапной задачи, тогда получим:˜ 2 ) = 22 (˜1, ˜ 2 ) + 2 2 (, ˜1, ˜ 2 ) ≥ 32 (˜1, ˜ 2 ),Φ2 (, 2 (·), ˜ 1 ) = 21 (˜ 1 ) + 1 1 (, ˜ 1 ) ≥ 31 (˜ 1 ).Φ1 (, 1 (·), Согласно лемме 1.1 данные ограничения можно записать в виде:˜ 2 ) = 22 (˜ 1 , 2 (˜ 1 )) + 2 2 (, ˜ 1 , 2 (˜ 1 )) ≥ 32 (˜ 1 , 2 (˜ 1 )),Φ2 (, 2 (·), ˜ 1 ) = 21 (˜ 1 ) + 1 1 (, ˜ 1 ) ≥ 31 (˜ 1 ).Φ1 (, (·), 1(1.11)24Введём следующие векторыΔ˜1) =˜ 1 ), Φ2 (, 2 (·), ˜ 2 )),Φ̄1 (, ¯1 (·), col(Φ1 (, 1 (·), Δ˜ 1 ) = col(31 (˜ 1 ), 32 (˜ 1 , 2 (˜ 1 ))),¯31 (Δ˜ 1 ) = col( 1 (, ˜ 1 ), 2 (, ˜ 1 , 2 (˜ 1 ))) = ¯1 (, ˜1)¯1 (, и матрицы⎛Δ˜1) =⎝¯21 (˜1)21 (˜ 1 , 2 (˜ 1 ))22 (⎞⎠,¯1 = (1 , 2 ),тогда ограничения (1.11) можно записать в видеΔ ¯˜1) =˜ 1 ) + ¯1 ¯1 (, ˜1) ≥ ˜ 1 ).Φ̄1 (, ¯1 (·), 21 (¯31 ((1.12)При этом с учётом введённых обозначений ограничения (1.12) имеют структуру ограниченийдвухэтапной задачи.После рассмотренных преобразований получена новая форма записи для функциипотерь и ограничений многоэтапной задачи, рассмотренной на примере трёхэтапной задачи (1.7) — (1.9).Рассмотрим двухэтапную задачу (1.6) с функцией вероятности˜ 1 ) ≤ , Φ̄1 (, ¯1 (·), ˜1) ≥ ˜ 1 )}.

(, ¯1 (·)) = {Φ̄2 (, 1 (·), ¯31 ((1.13)Поскольку значения функции потерь и ограничения в задаче (1.6), (1.13) совпадаютс функцией потерь и ограничениями в задаче (1.6), (1.7), то эти задачи эквивалентны всмысле определения 1.1.Таким образом, трёхэтапная задача (1.7)–(1.9) стохастического программированиясведена к двухэтапной задаче (1.6) с функцией потерь вида (1.10) и ограничениями вида (1.12).Сведение -этапной задачи к двухэтапной доказывается по индукции.Теорема 1.1 доказана.

2Получение решения поставленной многоэтапной задачи стохастического программирования в пространстве функций оказывается достаточно сложным из-за использованияв качестве критерия квантиль функции потерь. В частности, как уже отмечалось, метод25динамического программирования, сводящий задачу оптимизации в функциональном пространстве к последовательному решению задач математического программирования в конечномерном пространстве, для квантильного критерия неприменим.

Благодаря описаннойв данном разделе схеме дискретизации меры удаётся свести многоэтапную задачу стохастического программирования к двухэтапной задаче квантильной оптимизации. Структураограничений (1.12) полученной двухэтапной задачи повторяет структуру ограничений (1.3)исходной задачи (1.6), кроме того, совпадают значения функций потерь (1.10) и (1.1) обеих задач. Это доказывает эквивалентность многоэтапной задачи (1.6) стохастического программирования в априорной постановке и полученной двухэтапной задачи (1.13) в смыслеопределения 1.1.Следует отметить, что частный случай рассмотренной в данном разделе задачи, изучен в работе А.И.

Кибзуна и А.В. Наумова [35]. В указанной работе рассматривалась двухэтапная задача квантильного линейного программирования с функционалом вероятностиΔT (, (·)) = {T1 + 2 () ≤ , + () ≥ }.В правой части ограничений данной задачи рассматривался случайных вектор , а детерминированная матрица от случайного вектора не зависела.261.3.Сведение двухэтапной задачи стохастического программированияв априорной постановке к двухэтапной задаче в апостериорнойпостановкеВ данном разделе предлагается процедура сведения рассмотренной в предыдущемразделе двухэтапной задачи (1.6) стохастического программирования в априорной постановке с функцией потерь вида (1.10) и ограничениями (1.12) к двухэтапной задаче в апостериорной постановке.Следует отметить, что впервые на связь двухэтапных задач в априорной и апостериорной постановках было обращено внимание в работе А.И.

Кибзуна и А.В Наумова [35].Но в указанной работе, как уже отмечалось выше, рассматривался частный случай задачи,исследуемой в данной главе.Перепишем двухэтапную задачу (1.6) стохастического программирования в априорΔΔ˜1 =ной постановке в более простом виде, полагая, что 1 (·) = (·), . Рассмотрим функ-цию потерьTTΦ(, (·), ) = T0 + 1 () + 1 (, )(1.14)с ограничением для второго этапаΔΦ1 (, (·), ) = 2 () + (, ) ≥ 3 (),(1.15)где 0 , 1 — детерминированные вектор-столбцы размерностей ( × 1) и (1 × 1) соответственно; ∈ IR — допустимые стратегии первого этапа; ∈ IR1 — стратегии второго этапа; ∈ IR — случайный вектор;3 () — вектор-функция размерности ( × 1), выбираемая в классе измеримых функций;матрицы 1 (), 2 (), выбираемые в классе измеримых функций, и матрица имеютразмерности ( × 1), ( × ) и ( × 1 ) соответственно.Рассмотрим задачу квантильной оптимизации вида =min∈, (·)∈ (, (·)), = arg min[ min (, (·))]∈ (·)∈(1.16)с функцией квантили, определяемой согласно (1.5) на основе функции вероятности (, (·)) = {Φ(, (·), ) ≤ , Φ1 (, (·), ) ≥ 3 ()}.(1.17)Рассмотрим также двухэтапную задачу стохастического программирования в апостериорной постановке следующего вида.27Пусть известна реализация ∈ IR случайного вектора и множество допустимыхΔпланов второго этапа задается как = { : ∈ IR1 , ≥ 0}.

Рассмотрим задачу второгоэтапа, считая, что стратегии ∈ ⊂ IR первого этапа и реализации ∈ IR вектораслучайных параметров известны:ΔΦ̄(, ) = min{T1 | 2 () + () ≥ 3 ()},∈(1.18)где 1 – вектор размерности 1 .Если для некоторой стратегии ∈ первого этапа и из множества допустимыхреализаций не существует стратегии второго этапа ∈ , удовлетворяющей ограничениямзадачи (1.18), будем полагать, что критериальная функция второго этапа Φ̄(, ) = +∞.Определим функцию вероятности, характеризующую непревышение целевым функционалом некоторого заранее заданного уровня при использовании стратегии , то естьΔ¯ () = {T1 () + Φ̄(, ) ≤ },и функцию квантили, характеризующую некоторое минимальное значение уровня , прикотором функционал вероятности будет не ниже заданного значения Δ¯ () = min{ : ¯ () ≥ }.Сформулируем задачу первого этапа¯ = min[T¯ ()], ¯ = arg min[T¯ ()].0+0+∈∈(1.19)В рассмотренных предположениях верно следующее утверждение, устанавливающее эквивалентность двухэтапных задач стохастического программирования в априорной и апостериорной постановках.Теорема 1.2.