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

В работеВ.В. Подиновского и В.Д. Ногина [56, C. 205] показано, что для выполнения данного условиятребуется, как уже отмечалось выше, чтобы конус рецессивных направлений множества состоял только из нулевого вектора:Δ0+ = { ∈ IR : ≤ 0} = ⃗0,где ⃗0 ∈ IR — нулевой вектор, матрица имеет размерность (1 × ).Введём функцию потерь, зависящую от стратегии первого этапа ∈ ⊂ IR и отреализаций случайного вектора и учитывающую оптимальную стратегию второгоэтапаTΦ(, ) = T0 + 1 +inf∈(,)T1 ,(2.1)где множество допустимых стратегий второго этапаΔTT(, ) = { ∈ : T 2 + T2 + ≥ 3 + , = 1, },(2.2)Δ = { ∈ IR1 : ≥ 0, = 1, 1 },где 0 и 1 — заданные детерминированные вектор-столбцы размерности ( × 1) и (1 × 1)соответственно;матрицы 1 и 2 имеют размерность ( × );2 , и 3 — вектор-столбцы размерности ( × 1), (1 × 1) и ( × 1) соответственно; — константа.Следует отметить, что часть матриц 2 и векторов 3 , = 1, , определяющих множество (, ) допустимых стратегий второго этапа, могут быть нулевыми.

Тогда частьограничений с теми же номерами , соответствующими этим матрицам и векторам в множестве (, ), будут детерминированными.45Рассмотрим функцию вероятности, то есть вероятность такого события, что целеваяфункция потерь не превосходит некоторый уровень ∈ IR1ΔT () = { : T0 + 1 + Φ(, ) ≤ },где – вероятностная мера, порождённая распределением (⃗0, ),⎧⎪⎨ inf T1 , (, ) ̸= ∅,Φ(, ) = ∈ (,)⎪⎩+∞, (, ) = ∅.(2.3)(2.4)Введём в рассмотрение также функцию квантили, которая характеризует минимальный уровень оптимального значения критериальной функции второго этапа, который неможет быть превышен с заранее заданной вероятностью :Δ () = min{ : () ≥ }, ∈ (0, * ),(2.5)гдеΔ * = sup { : (, ) ̸= ∅}.∈В задачах экономических и технических приложений, как правило, рассматриваетсяуровень доверительной вероятности, превышающий 1/2, поэтому далее будем рассматриватьуровень , принимающий значения из диапазона (1/2, * ).Поиск значения * из выражения (2.5) представляет собой сложную математическуюзадачу.

Исследования, касающиеся данного вопроса отражены в монографиях А.И. Кибзунаи Ю.С. Кана [25, 117], а также в работах Р. Леппа [47, 122].Если для всех и ∈ верно неравенство () < , будем считать, что выполняетсяΦ(, ) = +∞.Сформулируем задачу первого этапа = inf (), = arg min ().∈∈(2.6)Задача (2.2) — (2.6) — двухэтапная билинейная задача квантильной оптимизации.Подобная постановка рассматривалась в работе А.И.

Кибзуна и А.В. Наумова [35]. Но вуказанной работе ограничения, описывающие множество (, ) допустимых стратегий второго этапа, были линейными одновременно по стратегии первого этапа и реализации случайного параметра. В рассматриваемой постановке (2.6) задачи стохастического программирования с квантильным критерием ограничения являются линейными отдельно по и по (билинейными).462.2.Свойства верхней оценки функции квантили двухэтапнойбилинейной задачи стохастического программированияФункция квантили в прикладных задачах служит мерой риска. Особенности этогокритерия подробно изучены в монографии А.И. Кибзуна и Ю.С.

Кана [25], в частности,в этой работе предложены различные методы и алгоритмы решения задач вероятностнойоптимизации. Например, для решения задач минимизации функции квантили в монографии А.И. Кибзуна и Ю.С. Кана [25], как и в работах Ю.С. Кана [19, 20], А.И. Кибзуна иЕ.Л. Матвеева [30, 31], применялись квазиградиентные алгоритмы. К недостаткам данногометода следует отнести отсутствие возможности получения в явном виде оптимального значения критерия задачи второго этапа. Это приводит к тому, что возникает необходимостьчисленного решения задачи второго этапа на каждом шаге квазиградиентного алгоритма.Поскольку размерность экономических и технических задач, имеющих структуру двухэтапных задач, как правило, достаточно большая, это существенно замедляет сходимость квазиградиентных алгоритмов, следовательно, затрудняет получение асимптотически точногорешения.В монографии А.И.

Кибзуна и Ю.С. Кана [25] также рассмотрен доверительныйметод, являющийся основным аналитическим инструментом решения задач минимизациифункции квантили. Как уже отмечалось в первой главе, доверительный метод позволяетоценить сверху оптимальное значение критерия путём рассмотрения произвольного доверительного множества. Суть данного метода заключается в аппроксимации исходной задачи минимизации функции квантили детерминированной минимаксной задачей, в которойвнутренний максимум целевой функции берётся по всем реализациям случайных параметров на некотором доверительном множестве, а внешниий минимум берётся по стратегииоптимизации. Естественно, что качество такой оценки зависит от структуры выбранногодоверительного множества. Если в качестве доверительного множества выбрано оптимальное доверительное множество, то данный подход позволяет найти точное решение задачи.Согласно доверительному методу, изложенному в монографии А.И.

Кибзуна иЮ.С. Кана [25], рассмотренная в разделе 2.1 задача (2.6) первого этапа двухэтапной задачистохастического программирования эквивалентна следующей задаче: =inf∈,∈ℱ(, ), ( , ) = argmin∈,∈ℱ(, ),(2.7)где введена функция максимумаΔT(, ) = T0 + sup[ 1 + Φ(, )],∈(2.8)47 — доверительное множество, то есть () ≥ , ∈ ℱ , где ℱ — семейство доверительныхмножеств уровня .Эквивалентность понимается здесь в смысле определения 1.1, введенного в главе 1.В соответствии с определением 1.1 выполняется = , = , причем под допустимым решением задачи (2.6) понимается пара (, ()), для которой ≤ (), ∈ ,а для задачи (2.7) — тройка (, , (, )), для которой ≤ (, ), ∈ ℱ , ∈ .Зафиксируем множество ∈ ℱ и рассмотрим подзадачу из (2.7): = inf (, ), = arg min (, ).∈∈(2.9)Справедливо следующее утверждение, устанавливающее связь между , и критерием ( ).Лемма 2.1.

Если существует стратегия , где ∈ ℱ — доверительное множество, то выполняются следующие неравенства ≤ ( ) ≤ .Доказательство леммы 2.1.Для стратегии пара ( , ( )) является допустимым решением для задачи (2.6),то есть ≤ ( ), ∈ .Поскольку для всех ∈ выполняется неравенство () ≤ (),при = получаем ( ) = , поэтому выполняется ( ) ≤ .Лемма 2.1 доказана. 2Далее будем рассматривать процедуру сведения двухэтапной билинейной задачи стохастического программирования к задаче выпуклого программирования с последующим еёрешением.482.3.2.3.1.Поиск решения задачи выпуклого программирования в случаедискретизированного распределения случайных параметровСведение двухэтапной билинейной задачи стохастическогопрограммирования с квантильным критерием к задаче выпуклогопрограммированияПусть векторы 1 и , = 1, , введённые в разделе 2.1, таковы, что множествоΔ = { ∈ IR : T ≤ 1 , ≥ 0, = 1, }(2.10)компактно, гдеT1⎞⎜Δ ⎜ = ⎜ ...⎝T⎟⎟⎟.⎠⎛Рассмотрим подзадачу задачи второго этапа (2.4), для которой запишем согласно монографии Е.Г.

Гольштейна [13] эквивалентную двойственную задачу с вектором двойственных переменных ∈ IR :Φ(, ) = sup T (, ),(2.11)∈где⎛T31 ⎜⎜¯(, ) = () + () = ⎜⎝ΔΔ¯T⎛⎜Δ ⎜T¯ () = ⎜⎝T−T21 + 1 −T21 ...T TTT3 − 2 + − 2 ⎞TT T31 − 21⎟⎟⎟,...⎠TT T3 − 2¯T () = (1 − T , ..., − T ),212⎞⎟⎟⎟,⎠(2.12)(2.13)(2.14) — выпуклый ограниченный многогранник, представляющий собой допустимое множестводля двойственных переменных.Пусть , = 1, , — вершины многогранника , являющегося выпуклым компактом.Поскольку функция в (2.11) линейна по , то ее максимум на компакте будет достигатьсяв его вершинах :Φ(, ) = max T (, ) ,∈1,где — количество вершин многогранника .(2.15)49Заметим, что задача поиска вершин множества , определяемого выражением (2.10),может быть решена априорно, поскольку множество не зависит от реализаций случайноговектора ∈ и стратегий ∈ .Ранее доверительное множество было зафиксировано.

Исследования, касающиесявыбора структуры доверительного множества, приведены в работе А.И. Кибзуна и А.В. Наумова [35] и монографии В.В. Малышева и А.И. Кибзуна [49]. Наиболее часто рассматривается оптимальное доверительное множество в виде эллипсоида или шара некоторогорадиуса ∈ [0, +∞). Следует отметить, что, как правило, в качестве центра шара выбирается вектор, равный математическому ожиданию вектора случайных параметров задачи,хотя вместо этого при наличии априорной информации в качестве центра шара может бытьвыбрана любая другая точка.В монографии А.И. Кибзуна и Ю.С. Кана [25] приведены следующие результаты.Лемма 2.2.

Если случайный вектор имеет нормальное распределение (0, ), тоядром уровня является шар с центром в нуле и радиусом , равным квантилиуровня стандартного нормального распределения (0, 1).Для множества вида = { : Φ( , ) ≤ } выполняется следующая лемма.Лемма 2.3. Если Φ(, ) выпукла по ∈ IR для всех ∈ , то для оптимальногомножества в задаче (2.7) выполняется включение ⊂ .Рассмотрим подзадачу (2.9) задачи (2.7) для фиксированного множества , в качествекоторого выбирается доверительный шар с радиусом и центром в нуле, ( ) = .Для простоты обозначений далее будем использовать ≡ , ≡ .

Рассмотрим болееобщую задачу вида (2.9) для шара с центром в нуле и переменным радиусом ∈ [, ]: = inf ( , ), = arg min ( , ),∈∈(2.16)где функция ( , ) определяется согласно (2.8) для множества , то естьΔT( , ) = T0 + sup [ 1 + Φ(, )].(2.17)∈Поскольку функция [T 1 + Φ(, )], стоящая под знаком sup в (2.17), являетсякусочно-линейной и выпуклой по для каждого ∈ , согласно (2.12) и (2.15), а шар —компактное множество, то знак sup можно заменить на знак max. Таким образом, функция( , ) в задаче (2.16) будет иметь вид:T( , ) = T0 + max[ 1 + Φ(, )].∈(2.18)50Исследуем задачу (2.16) с функцией ( , ), определяемой выражением (2.18).

Оказывается верным следующее утверждение.Лемма 2.4. Задача (2.16) является задачей выпуклого программирования, и существует для всех ∈ [, ].Доказательство леммы 2.4.Сначала найдем явное выражение для функции ( , ) из (2.18). Согласно (2.15)функция Φ(, ) имеет видΦ(, ) = max T (, ) ,∈1,где вектор-функция (, ), определяемая выражением (2.12), линейна по реализации случайного вектора для каждого значения стратегии ∈ . Поэтому максимум на шаре срадиусом в выражении (2.18) достигается.

Более того, этот максимум линейной по функции может быть найден аналитически. Он достигается в одной из точек касания шара с гиперплоскостями Γ , = 1, , которые характеризуются векторами нормали к ним:Δ¯¯ = (1 + ())/||1 + ()||,¯Γ = {T (1 + ()) = }, = 1, ,где — некоторые константы, подбираемые из условия касания гиперплоскости Γ и шара . Поэтому задача (2.18) может быть представлена в виде:¯T¯( , ) = T0 + max [||1 + () || + () ].(2.19)=1,¯Заметим, что элементы матрицы ()и вектора ¯(), определяемых выражениями (2.13) и (2.14) соответственно, линейны по .

Следовательно, ( , ) непрерывна по ∈ . Но, как было отмечено выше, — компакт, поэтому по теореме Вейерштрасса оптимальная стратегия в задаче (2.16) существует.Далее проанализируем вид функции Φ(, ). Согласно (2.12) вектор-функция (, ),стоящая под знаком max в выражении (2.15), линейна по стратегии для всех реализаций ∈ IR случайного вектора и вершин , = 1, , множества допустимых значений переменных в задаче, двойственной к задаче второго этапа. Поэтому функция Φ(, ) являетсякусочно-линейной и выпуклой по ∈ для каждого .