8.4. ПРИМЕНЕНИЕ МЕТОДА СТОХАСТИЧескИХ КВАЗиГРАДиеНТоВ К ЗАДАЧАМ СТОХАСТИЧескОГО ПРОГРАММИРОВАНИЯ
Простейшая задача управления запасами
Пусть имеется некоторый склад вместимостью 
, в котором нужно создать запас некоторого однородного продукта. Пусть спрос 
на продукт случаен с функцией распределения 
. Обозначим планируемый объем запаса через 
единиц. Рассмотрим функцию затрат
(8.4.1)
где 
- удельные затраты по хранению единицы запасов; 
- удельный штраф вследствие дефицита. Требуется найти такой уровень запасов , при котором
. (8.4.2)
Поскольку функция 
- недифференцируема при 
, то в общем случае 
- тоже недифференцируема. Очевидно,
, (8.4.3)
то есть имеем частный случай минимаксной задачи.
Находим стохастический квазиградиент
(8.4.4)
и рекуррентный процесс определения оптимального объема запасов 
выглядит следующим образом:
или 
. (8.4.5)
Игровая стохастическая задача
Задачи этого типа возникают при выборе оптимальных решений в условиях неопределенности и риска, когда имеется первый игрок - ЛПР и второй игрок - противодействующая среда. Предположим, что все факторы можно разбить на три группы:
факторы, контролируемые первым игроком;
факторы, контролируемые вторым игроком;
- состояние природы (случайные факторы).
Пусть первый игрок принимает (выбирает) решение x из допустимого множества решений 
, второй игрок принимает решение y, 
, где 
- допустимое множество решений второго игрока, - элементарное событие некоторого вероятностного пространства 
.
Предположим, что второй игрок делает свой выбор после первого, ему известно решение первого игрока и состояние природы . Обозначим через 
сумму, которую первый игрок платит второму, если природа находится в состоянии .
Тогда ожидаемый проигрыш первого игрока равен
(8.4.6)
и надо найти такой 
, для которого
. (8.4.7)
Итак, приходим к минимаксной задаче, которая является задачей стохастического программирования.
Ее сложность состоит в том, что только в исключительных случаях можно найти 
в аналитическом виде, и, кроме того, не будет неперервно дифференцируемой даже при гладкой функции 
. Пусть множество выпукло и замкнуто, и при каждом x и существует такой 
, что
,
причем 
- непрерывная и выпуклая функция в области , а 
- ее обобщенный градиент по x при фиксированном y и . Применим для решения задачи (8.4.7) метод СКГ, в котором 
- стохастический квазиградиент, где 
- результаты независимых наблюдений за состоянием природы .
Чтобы убедиться в этом, покажем, что для любой точки выполняется неравенство
, (8.4.8)
другими словами, что 
. Очевидно,
.
В силу сделанных предположений относительно функции 
имеем
(8.4.9)
и поэтому
. (8.4.10)
Беря операцию условного математического ожидания от обеих частей (8.4.10) при фиксированных и 
, получим условие (8.4.8).
Стохастическая задача о наилучшем приближении
(стохастический аналог задачи Чебышева)
Задачу вида:
минимизировать 
, (8.4.11)
где 
, 
, называют стохастическим аналогом задачи Чебышева [18]. В этом случае вектор 
, определяемый как , будет иметь вид
(8.4.12)
Двухэтапная задача стохастического программирования
В разделе 8.2 была рассмотрена двухэтапная задача стохастического программирования:
минимизировать
(8.4.13)
при ограничениях
(8.4.14)
. (8.4.15)
Функция 
в общем случае не имеет непрерывных производных. В наиболее общем виде предварительный план 
и план-компенсация 
вместо (8.4.14) имеют при всех удовлетворять ограничениям
, 
. (8.4.16)
Далее, пусть затраты, связанные с реализацией плана и его коррекцией в состоянии , равны 
.
Обозначим через 
план-компенсацию, который минимизирует при условиях (8.4.16), (8.4.15) и фиксированных , 
. Тогда ожидаемые затраты на реализацию плана и его коррекцию составляют
, (8.4.17)
и необходимо найти такой , для которого
при условиях (8.4.15), (8.4.16). Предположим, что 
и при каждом выпуклы вниз при всех , и существует седловая точка 
функции Лагранжа:
(8.4.18)
при 
и 
.
Пусть 
, 
- обобщенные градиенты функций , по при фиксированном .
Тогда для решения задачи (8.4.13) методом СКГ при условиях (8.4.15), (8.4.16) на выпуклом и замкнутом множестве 
следует положить
(8.4.19)
, (8.4.20)
или
. (8.4.21)
Можно показать [17], что для функции и вектора 
, задаваемого в (8.4.19), 
, то есть 
- субградиент функции 
.
Рассмотрим двухэтапную задачу стохастического программирования с линейными ограничениями и функцией затрат
(8.4.22)
при ограничениях
(8.4.23)
. (8.4.24)
Вектор 
минимизирует
(8.4.25)
при ограничениях
(8.4.26)
то есть является решением задачи ЛП (8.4.25), (8.4.26).
Обозначим через 
- двойственные переменные, отвечающие 
. В этом случае вектор в методе СКГ вычисляется так: после 
-й итерации получаем 
, наблюдаем 
(например, моделируя некоторые сценарии на ЭВМ), находим 
и вычисляем 
, где 
- транспонированная матрица к 
.
Запишем задачу, двойственную к (8.4.25), (8.4.26):
|
(8.4.27)
при ограничении
.
Поскольку 
, то двухэтапной задаче (8.4.22)-(8.4.24) соответствует следующая эквивалентная задача
минимизировать 
, (8.4.28)
а так как 
, то .
Соответствующая процедура для поиска оптимального решения записывается так:
- для задачи без ограничений;
- для задачи с ограничениями.
Экстремальные задачи математической статистики
В математической статистике довольно распространенной оказывается задача оценки параметров распределения случайных величин и процессов, которая формулируется следующим образом.
Имеется случайная величина (или вектор) 
, распределение которой известно с точностью до параметров 
, и известны реализации 
случайной величины при 
. Требуется по этим наблюдениям определить 
.
Обычно стремятся отыскать такую оценку 
, которая была бы несмещенной и эффективной. Покажем, что многие задачи оценки сводятся к решению соответствующих задач стохастического программирования.
Оценка среднего значения. Пусть - случайный вектор с неизвестным средним 
, а - независимые наблюдения вектора , по которым необходимо оценить . Рассмотрим функцию 
. Минимум этой функции достигается при = . Кроме того, для 
имеем 
. Тогда в соответствии с общим алгоритмом СКГ (8.3.2), (8.3.3) получим следующую процедуру оценивания[17]:
(8.4.29)
Если 
, а 
, то процедура (8.4.29) примет вид
, (8.4.30)
то есть получим классическую формулу оценки среднего.
Оценка моментов. Пусть в постановке задачи предыдущего раздела (оценка среднего) требуется оценить моменты 
. Предположим, что эти моменты принадлежат некоторому множеству 
.
Аналогично предыдущей задаче искомые моменты являются точками минимума функций
, (8.4.31)
, 
соответственно.
Применяя стохастический квазиградиентный метод для первых двух случаев в процедуре (8.4.30), положим 
, соответственно. Тогда приходим к процедуре
. (8.4.32)
При этом для соответствующей функции 
имеем
Для задачи минимизации функции
в процедуре (8.3.2) или (8.3.3) в качестве вектора 
можно взять :
. (8.4.33)
Тогда соответствующая рекуррентная процедура поиска оценки центрального момента 
-го порядка примет вид :
. (8.4.34)
Можно легко показать, что при этом 
. Действительно, в силу независимости 
и 
от 
имеем
(8.4.35)
