Автоматика и телемеханика, № 5, 2014
Стохастические системы, системы массового обслуживания
© 2014 г. А.И. КИБЗУН, д-р физ.-мат. наук (kibzun@mail.ru), О.М. ХРОМОВА (khromova-om@mail.ru) (Московский авиационный институт)
О СВЕДЕНИИ ДВУХЭТАПНОЙ ЗАДАЧИ КВАНТИЛЬНОЙ ОПТИМИЗАЦИИ К ЗАДАЧЕ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ1
Работа посвящена решению двухэтапной задачи стохастического программирования с квантильным критерием. Рассматривается случай функции потерь, линейной отдельно по случайным факторам и стратегиям (билинейной), когда случайные факторы имеют нормальное распределение. Предложен алгоритм, основанный на решении параметрической задачи выпуклого программирования, скалярный параметр которой выбирается с помощью метода дихотомии. Решение оказывается гарантирующим для исходной задачи. Рассматривается пример.
1. Введение
Двухэтапные задачи стохастического программирования встречаются в многих прикладных задачах [1], в частности при управлении финансами [2] и при управлении летательными аппаратами [3]. В этих задачах вначале задается стратегия первого этапа, при реализации которой возникают разные случайные факторы (возмущения). На втором этапе за счет выбора новой стратегии (стратегии второго этапа) можно частично компенсировать воздействие этих случайных помех. Традиционно в двухэтапных задачах стохастического программирования в качестве критерия рассматривается математическое ожидание (средние потери) [1]. Тем не менее в многих приложениях этот критерий оказывается неудовлетворительным. Например, в финансовой математике часто используется [4] УЕИ-критерий, характеризующий порог, который потери не превысят с заданной вероятностью. В задачах управления летательными аппаратами более адекватным критерием является гарантированная с заданной вероятностью точность управления [3]. Математически эти критерии описываются функцией квантили. Но задачи стохастического программирования, где в качестве критерия выбрана функция квантили, оказываются намного сложнее, чем задачи с критерием в форме математического
1 Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований (проект № 12-07-00191-а).
3* 67
ожидания. В частности, функция квантили не обладает линейными свойствами. Особенности этого критерия подробно изучены в монографии [4]. Одним из основных инструментов решения задач квантильной оптимизации оказывается доверительный метод [4], сводящий исходную стохастическую задачу к некоторой минимаксной, решение которой является гарантирующим для исходной задачи.
Двухэтапные задачи квантильной оптимизации впервые сформулированы в [5], где рассмотрена линейная функция потерь и показана эквивалентность априорной и апостериорной постановок задач квантильной оптимизации. Кроме того, в [5] за счет перехода к двойственным переменным при гауссовском распределении вспомогательная минимаксная задача сведена к задаче линейного программирования. В [6] рассмотрена подобная постановка двухэтапной задачи стохастического линейного программирования, но для дискретного распределения. За счет перехода к двойственным переменным стохастическая задача сведена к задаче смешанного целочисленного линейного программирования большой размерности. В [7] рассмотрена более общая, чем в [6], постановка двухэтапной задачи квантильной оптимизации, в которой случайные переменные тоже принимают дискретные значения. В [7] задача сведена к задаче смешанного целочисленного линейного программирования. В [8] рассмотрена многоэтапная задача квантильной оптимизации с дискретными случайными факторами и функцией потерь, линейной по стратегиям. Эта задача, как ив [7], тоже сведена к задаче смешанного целочисленного программирования. Особенностью задач линейного программирования, получаемых в [7, 8], является их большая размерность. В [9] предложен алгоритм решения задачи квантильной оптимизации для случая линейной целевой функции при линейных ограничениях для гауссовских случайных помех. Этот алгоритм состоит в последовательном решении задач линейного программирования, полученных из минимаксных задач для доверительного множества в виде шара.
В данной статье рассматривается двухэтапная задача квантильной оптимизации, в которой функция потерь билинейна, а случайный вектор имеет нормальное распределение. Также в работе исследуются свойства верхней оценки функции квантили и предлагается процедура сведения двухэтапной задачи стохастического программирования к задаче выпуклого программирования. Сведение осуществляется с использованием доверительного метода [4] и известных результатов теории двойственности из [10]. Получаемая задача выпуклого программирования параметризована скалярным параметром, который подлежит выбору с помощью метода дихотомии. В результате решения данной задачи получается гарантирующее решение исходной задачи. В статье содержится описание результатов численных экспериментов, подтверждающих эффективность предложенного алгоритма решения.
2. Постановка задачи
Рассмотрим двухэтапную задачу следующей структуры. Пусть случайный вектор X с реализациями х € Нга имеет нормальное распределение N(0,1). Введем функцию потерь, зависящую от стратегии первого этапа и € и С М™
и от реализаций х случайного вектора X и учитывающую оптимальную стратегию второго этапа у:
(2.1) Ф(и, х) = е^и + хт А^ + И с^ у,
у€У (и,х)
где
(2.2) У (и, х) = {у € У : хтА2^1, + с^и + у ^ а^ж + -¿ = 1,8},
Г = {у еГ1 ^0, ] =
с0 и с1 — заданные детерминированные вектор-столбцы размерности т и т1 соответственно, матрицы А1 и имеют размерность п х т, С2г, Ь и азг — вектор-столбцы размерности т, т1 и п соответственно, а йг — константа.
Замечание 1. Отметим, что часть матриц А21 и векторов а-ц, г = 1,5, определяющих множество У (и, х) допустимых стратегий второго этапа у, могут быть нулевыми. Тогда часть ограничений с теми же номерами г, соответствующими этим матрицам и векторам в множестве У (и, х), будут детерминированными.
Пусть векторы с\ и = 1,5, таковы, что множество
(2.3) V = {у € И" : Вти < сь иг ^ 0, г = !"§} компактно, где
, ьТ
в й' 1 ' ьТ
а ограничения на допустимые стратегии первого этапа и являются линейными, т.е.
и = {и € Нт : А«и < Ь„},
где вектор Ьи имеет размерность к1, матрица Аи имеет размерность к1 х т, причем они являются такими, что и — компакт. Рассмотрим функцию вероятности
(2.4) Р¥,(г/,) = 7? {X : + Х^г,, + Ф(и, X) < ,
где Р — вероятностная мера, порожденная распределением N(0,1),
Ы сЪ, У{и,Х)ф0,
(2.5) Ф(г/,Х) = <( !/еУ(«,л:)
то, У (и, X) = 0, и функцию квантили
(2.6) <ра(и) = шт{р : рДи) ^ а}, а € (0, Р*),
где
Р* = вир Р{Х : У(и,Х) = 0}.
пей
Сформулируем задачу первого этапа
(2.7)
У а = И фаЫ), Па = аЩШШ У« (и).
Замечание 2. Задача (2.7) записана для двух случаев: оптимальное значение функции квантили не достигается и это значение достигается.
Замечание 3. Подобная постановка рассматривалась в [5]. Но в [5] ограничения, описывающие У(и,х), были линейными и по и, и по х. В рассматриваемой постановке (2.7) ограничения являются линейными отдельно по и и по х (билинейными).
Далее в статье приводится ряд утверждений, направленных на получения алгоритма решения исходной задачи. Поясним проведенные рассуждения. Для решения задачи (2.7) применяется доверительный метод [4]. Данный метод позволяет заменить исходную стохастическую задачу (2.7) некоторой минимаксной, решение которой может быть найдено аналитически. Оптимальное значение критерия при этом можно оценить сверху путем рассмотрения произвольного доверительного множества. Исследуя свойства верхней оценки функции квантили и учитывая рекомендации по выбору оптимального доверительного множества из [4], удается осуществить сведение исходной задачи (2.7) к задаче выпуклого программирования. Для полученной задачи выпуклого программирования проводятся дополнительные исследования, касающиеся существования оптимизируемой стратегии, зависящей от скалярного параметра, и монотонности и непрерывности критериальной функции по этому же параметру. В ходе данных исследований получается двусторонняя оценка функции квантили задачи выпуклого программирования. Данная оценка может быть улучшена. Для этого рассматривается вспомогательное утверждение о сравнении вероятностных мер произвольного и симметричного многогранных множеств. На основании полученных результатов формулируется теорема, позволяющая предложить алгоритм решения полученной задачи выпуклого программирования.
Согласно доверительному методу [4] задача (2.7) эквивалентна задаче
(3.1) 1ра = Ы и), (йа, ва) = &щ тт
где введена функция максимума
а 5 — доверительное множество, т.е. 5 € Та, V(5) ^ а. Эквивалентность здесь понимается в следующем смысле [7].
3. Верхняя оценка функции квантили
(3.2)
и) = Сд и + вир [хТА\и + Ф(и, ж)] , хея
Определение 1. Две задачи оптимизации будем считать эквивалентными, если:
1) либо обе эти задачи имеют допустимые решения (с конечными значениями целевых функций), либо обе не имеют таких решений;
2) если эти задачи имеют допустимые решения, то оптимальные значения их целевых функций (конечные или бесконечные) совпадают;
3) если оптимальные значения их целевых функций конечны, то эти значения в обеих задачах либо достигаются, либо не достигаются;
4) если оптимальные значения целевых функций достигаются, то по оптимальному решению одной задачи с помощью явно описанного алгоритма указывается оптимальное решение другой задачи;
5) если оптимальные значения целевых функций конечны, но не достигаются, то по оптимизирующей последовательности стратегий одной задачи по явно описанному алгоритму указывается оптимизирующая последовательность для другой задачи.
Замечание 4. В соответствии с определением 1 выполняется ipa = Tfia, ua =ua, причем под допустимым решением задачи (2.7) понимается пара (u, (u)), для которой ^ pa(u), u € U, а для задачи (3.1) — тройка (u, S, ip(S, и)), для которой Tpa ^ ij){S, и), S € и € U.
Зафиксируем некоторое множество S € Fa и рассмотрим подзадачу из (3.1):
(3.3) фв = inf ^(S, u), uS = arg min ^(S, u).
u£U u£U
Справедливо следующее утверждение.
Лемма 1. Если
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.