8.3. МЕТОД ПРОЕКТИРОВАНИЯ СТОХАСТИЧескИХ КВАЗиГРАДиеНТоВ
Рассмотрим класс оперативных задач стохастического программирования, в которых необходимо минимизровать целевую функцию 
, измеряемую в условиях действия погрешностей.
Точное значение самой функции 
, а также ее производных 
, определить невозможно. Впрочем имеется возможность многократно наблюдать состояния природы 
(внешней среды) и оценивать реализации целевой функции 
. В этом случае целесообразно использование прямых методов стохастического программирования, к числу которых относится метод проектирования стохастических квазиградинтов (СКГ), или стохастический квазиградиентный метод, разработанный Ю. М. Ермольевым [17].
Стохастический квазиградиентный метод предназначен для решения задач как стохастического программирования, так и нелинейного программирования с негладкими, но выпуклыми функциями и ограничениями в условиях неточной информации об этих функциях и их производных.
Итак, пусть требуется минимизировать
(8.3.1)
при ограничении
где 
- выпуклое замкнутое множество; - выпуклая негладкая функция, точное значение которой, а также его производных вычислить невозможно. В этом случае вместо точных значений градиентов или обобщенных градиентов функции используют случайные векторы, являющиеся статистическими оценками этих величин. В методе СКГ за направление спуска и выбирают такие случайные векторы.
Итак, пусть имеется некоторое вероятностное пространство с множеством элементарных событий . Рассмотрим последовательность случайных точек 
определяемых по формуле
(8.3.2)
где 
- оператор проектирования на множество 
; x0 - произвольная начальная точка пространства; 
- величина шага; 
- нормируюий множитель; 
- случайный вектор, условное математическое ожидание которого равно
, (8.3.3)
где скаляр 
; 
- случайный вектор, не зависящий от последовательности 
; величины 
, 
измеримы по Борелю.
Как известно (см. гл. 6.8), обобщенный градиент функции 
в точке 
- вектор 
- удовлетворяет при любом векторе 
неравенству
. (8.3.4)
Вектор 
, удовлетворяющий (8.3.3), с точностью до параметров 
, 
совпадает в среднем с вектором обобщенного градиента. Если положить 
то вполне естественно назвать стохастическим обобщенным градиентом (или квазиградиентом), а процедуру (8.3.2) - методом проектирования стохастических квазиградиентов.
При анализе процедуры (8.3.3) возникает вопрос о сходимости последовательности 
. Существуют различные варианты сходимости случайных последовательностей: по вероятности, в среднем квадратическом и с вероятностью 1 (то есть почти наверное).
Наибольший практический интерес представляет сходимость с вероятностью 1. Приведем условия, при которых эта сходимость гарантируется.
Предположим, что 
а не зависит от . Обозначим через 
множество оптимальных решений задачи (8.3.1). Справедлива следующая теорема [17;18].
Теорема 8.3. Пусть выполняются условия
(8.3.5)
(8.3.6)
, (8.3.7)
, с вероятностью 1. (8.3.8)
Пусть множество ограничено и 
. Тогда последовательность 
, определенная согласно (8.3.2), (8.3.3), сходится к с вероятностью 1, причем 
.
Доказательство. Пусть 
, согласно определению операции проектирования (п. 6.8) имеем
(8.3.9)
Возьмем операцию условного математического ожидания от обеих частей неравенства (8.3.9) при условиях x1, x2, . , xs
(8.3.10)
Поскольку - выпуклая вниз функция, то
,
ведь
. (8.3.11)
Поэтому, применив неравенство Коши-Буняковского 
и используя (8.3.5), получим из (8.3.10)
, (8.3.12)
где 
- некоторая константа.
Обозначим
. (8.3.13)
Тогда из (8.3.13) следует
,
и в силу того что 
зависит только от xs,
.
Такая последовательность случайных величин 
называется супермартингалом [17]. Поскольку супермартингал неотрицателен 
,
то он сходится с вероятностью 1 [17]. Отсюда с учетом (8.3.7) заключаем, что последовательность 
сходится с вероятностью 1, следовательно, последовательность ограничена и множество ее предельных точек 
непусто. Пусть 
- две произвольные предельные точки последовательности 
. Тогда для любого 
имеем
. Если теперь показать, что одна из предельных точек с вероятностью 1 принадлежит множеству , то из последнего равенства будет следовать, что она будет и единственной предельной точкой последовательности. Из (8.3.9) имеем
.
Отсюда
(8.3.14)
Поскольку левая часть (8.3.14) неотрицательна, то справедливо неравенство
.
Переходя к пределу при 
и учитывая (8.3.7), получим с вероятностью 1:
и в силу (8.3.6)
. (8.3.15)
Поскольку 
, то отсюда следует, что найдется такая последовательность 
, что с вероятностью 1
при 
,
но 
- обобщенный градиент, поэтому
.
Следовательно, для любой предельной точки 
последовательности , получим
, то есть с вероятностью 1 
.
Теорема доказана.
Покажем теперь, как с помощью метода СКГ можно конструировать различные варианты прямых методов стохастического программирования. К ним, в частности, относится метод стохастической аппроксимации.
Метод стохастической аппроксимации
Этот метод предложили Н. Роббинс и С. Монро и развили Э. Кифер и Дж. Вольфовитц для решения экстремальных стохастических задач без ограничений.
Пусть требуется найти минимум функции регрессии
, (8.3.16)
где
.
Основная идея этого метода состоит в том, что при минимизации 
в качестве направления спуска выбирается антиградиент функции 
вместо неизвестного антиградиента - 
функции 
, которую точно измерить (определить) невозможно.
В методе стохастической аппроксимации рассматриваются итеративные процедуры поиска, определяемые соотношениями
(8.3.17)
Если при каждом градиент 
аналитически вычислить трудно, то рассматривается разностный вариант метода, в котором градиент определяется численно:
, (8.3.18)
где 
- орт 
-й оси; 
- результаты независимых наблюдений за состоянием природы ; - длина шага; 
- смещение.
Сходимость метода стохастической аппроксимации обычно исследуют в предположении, которое имеет непрерывные и ограниченные вторые производные. Можно показать, что при этих предположениях [17]
, (8.3.19)
где 
- некоторый вектор такой, что 
.
Итак, метод стохастической аппроксимации является частным случаем метода СКГ, где
. (8.3.20)
Приведем некоторые обобщения процедуры (8.3.17). Предположим, что размерность пространства 
велика, и на численное определение направления спуска согласно (8.3.20) расходуется очень много времени, а кроме того имеются ограничения 
. Тогда можно использовать случайные направления 
с независимыми и равномерно распределенными компонентами 
на интервале [-1, 1] и рассмотреть следующий процесс поиска:
, (8.3.21)
где 
- серия независимых наблюдений вектора в 
-й итерации 
; - смещение по оси. Величины 
и считаются всюду измеримыми по Борелю. В даном случае, если дважды дифференцируема, имеет ограниченные вторые производные при , то
, (8.3.22)
где 
- некоторый случайный вектор, причем 
.
Поскольку вторые производные функции ограничены, то 
, а величины , , следует выбирать так, чтобы
а) 
, б) 
,
в) 
, г) 
.
Если 
, то условия сходимости имеют вид
а) , 
, б) , в) 
. (8.3.23)
Типичным примером последовательности, удовлетворяющей условию (8.3.23), является гармонический ряд
.
Статистические методы поиска нелинейного программирования
С помощью метода СКГ можно решать задачи не только стохастического, а и нелинейного программирования, в которых по каким-то обстоятельствам вычислить значения 
трудно (или невозможно). В случае, если неизвестен аналитический вид функции , то вычислить непрерывные производные 
невозможно и тогда используют разностный аналог градиента
, (8.3.24)
где - орт -й оси; - смещение вдоль -й оси. Если 
- достаточно велико 
, то вычисление численного значения градиента требует больших затрат. В этом случае отказываются от использования направления градиента и используют любое допустимое направление такое, что угол между и 
меньше 90?. В частности, оказывается целесообразным использовать методы случайного поиска, которые представляют собой частный случай метода СКГ [40].
Рассмотрим случайный вектор 
с независимыми и равномерно распределенными на интервале [-1, 1] компонентами и положим
, (8.3.25)
где 
- серия независимых наблюдений вектора в -й итерации ; 
. Случайные величины , считаются всюду измеримыми по Борелю. Нетрудно показать, что
, (8.3.26)
где - некоторый случайный вектор, причем 
. Итак для минимизации можно применить метод СКГ вида 
в котором вектор вычисляется в соответствии с (8.3.25). Поскольку вторые производные функции считаются ограниченными, то 
и величины , , следует выбирать так, чтобы выполнялись условия
, ,
, 
.
В этом случае последовательность 
будет сходиться к точке минимума 
.
