8.3. МЕТОД ПРОЕКТИРОВАНИЯ СТОХАСТИЧескИХ КВАЗиГРАДиеНТоВ

Рассмотрим класс оперативных задач стохастического программирования, в которых необходимо минимизровать целевую функцию , измеряемую в условиях действия погрешностей.

Точное значение самой функции , а также ее производных , определить невозможно. Впрочем имеется возможность многократно наблюдать состояния природы  (внешней среды) и оценивать реализации целевой функции . В этом случае целесообразно использование прямых методов стохастического программирования, к числу которых относится метод проектирования стохастических квазиградинтов (СКГ), или стохастический квазиградиентный метод, разработанный Ю. М. Ермольевым [17].

Стохастический квазиградиентный метод предназначен для решения задач как стохастического программирования, так и нелинейного программирования с негладкими, но выпуклыми функциями и ограничениями в условиях неточной информации об этих функциях и их производных.

Итак, пусть требуется минимизировать

                          (8.3.1)

при ограничении

где  – выпуклое замкнутое множество;  – выпуклая негладкая функция, точное значение которой, а также его производных вычислить невозможно. В этом случае вместо точных значений градиентов или обобщенных градиентов функции  используют случайные векторы, являющиеся статистическими оценками этих величин. В методе СКГ за направление спуска и выбирают такие случайные векторы.

Итак, пусть имеется некоторое вероятностное пространство с множеством элементарных событий . Рассмотрим последовательность случайных точек  определяемых по формуле

                          (8.3.2)

где  – оператор проектирования на множество ; x₀ – произвольная начальная точка пространства;  – величина шага;  – нормируюий множитель;  – случайный вектор, условное математическое ожидание которого равно

 ,                    (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) при условиях x₁, x₂, … , x_s

     (8.3.10)

Поскольку  – выпуклая вниз функция, то

 ,

ведь

 .                             (8.3.11)

Поэтому, применив неравенство Коши-Буняковского  и используя (8.3.5), получим из (8.3.10)

 ,   (8.3.12)

где  – некоторая константа.

Обозначим

 .                        (8.3.13)

Тогда из (8.3.13) следует

 ,

и в силу того что  зависит только от x_s,

 .

Такая последовательность случайных величин  называется супермартингалом [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). Поскольку вторые производные функции  считаются ограниченными, то  и величины , ,  следует выбирать так, чтобы выполнялись условия

 , ,

 , .

В этом случае последовательность  будет сходиться к точке минимума .