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

Имеется сравнительно немного работ, в которых изучаются методы стохастической аппроксимации применительно к задачам отыскания условного экстремума. Упомянем о работе Фабиана [7], который исследовал применение метода стохастической аппроксимации в сочетании с методом штрафных функций аппроксимации точки минимума функции на множестве Обозначим через координату вектора у. Будем писать , если для каждой координаты вектора у. Пусть функция определена на -мерном евклидовом пространстве Обозначим через вектор первых частных производных от по х, а через матрицу Гессе матрицу вторых частных производных по

Примем следующие предположения:

1. Функции определены на Функция скалярная, функция есть -мерная векторная функция. Матрицы существуют для и ограничены на

2. Функции выпуклы, ограничена снизу константой (может быть и отрицательной), множество ограничено.

3. Существует вектор такой, что для т. е. открытое ядро множества непусто.

4. Градиент ограничен на множестве для каждого

Последнее предположение принято лишь для упрощения обозначений. Пусть последовательности таковы, что (монотонно), (монотонно) и (монотонно). Обозначим Положим где Введем функции

Идея Фабиана состоит в том, что на шаге к применяется обычная стохастическая аппроксимация и доказывается, что

Теорема 3.1 (Фабиан). Пусть выполнены предположения последовательности положительных чисел,

Пусть случайные векторы из

где С — константа, или 1 в зависимости от того, наблюдается ли с ошибкой или без нее. Пусть следующие последовательности ограничены для некоторого

(здесь и следующие ряды сходятся:

Тогда с вероятностью единица кроме того, с вероятностью единица.

В работах Ермольева Ермольева и Некрыловой Ермольева и Шора а также в докторской диссертации Ермольева развивался подход к решению задач на условный экстремум с помощью процедур типа стохастической аппроксимации, основанный на понятии стохастического квазиградиента.

В этих работах оптимизируемая функция, как правило, предполагается выпуклой, но не обязательно всюду дифференцируемой. Кроме того, предполагается, что значения функции в каждой точке наблюдаются без ошибок, но значения градиентов и квазиградиентов (обобщенных градиентов) определяются, вообще говоря, с ошибками. Для решения задачи на условный экстремум предлагается сочетать метод стохастической аппроксимации с методом проектирования градиента или с методом штрафных функций. Рассматривается задача минимизации функции при условии, что где X — выпуклое и замкнутое множество -мерного пространства непрёрывная, выпуклая вниз, но не обязательно непрерывно дифференцируемая в области X функция, такая, что

Используем для оператора проектирования точки на множество X обозначение это такая точка из множества X, для которой выполняется условие где расстояние; для замкнутых выпуклых X оператор определен однозначно).

Для решения задачи предлагается построение последовательности определяемой рекуррентным соотношением

Здесь произвольная случайная точка, для которой скалярные величины, а §? — случайный вектор, удовлетворяющий условию

где случайная величина, — случайный вектор, а вектор обобщенный градиент функции в точке любой вектор, удовлетворяющий неравенству

Случайный вектор , удовлетворяющий условию (3.1), называется стохастическим квазиградиентом функции в точке х. Если то этот вектор называется стохастическим обобщенным градиентом, а если функция непрерывно дифференцируема, то — стохастическим градиентом. Обозначим через X множество решений задачи

Теорема 3.2 (Ермольев). Пусть случайная величина, такая, что для любого числа и некоторого числа

при множитель для некоторых чисел удовлетворяет условию

где если если величины такие, что

и с вероятностью единица

Тогда с вероятностью единица последовательность сходится к некоторому элементу

Теорема 3.2 остается справедливой, если наряду с условием (3.2) выполняется такое условие: при вместо (3.3) выполняется условие

где у — некоторое число; вместо (3.4) выполняется условие

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

где Предположим, что и для любого числа существует число такое, что при .

Теорема 3.3 (Ермольев). Пусть градиент удовлетворяет равномерному условию Липшица с константой т. е. для любых точек х, у

пусть случайная величина, такая, что для любого и некоторого

при а множитель удовлетворяет условию

Тогда последовательность точек определенная согласно (3.5) и (3.6), такова, что с вероятностью единица последовательность сходится и при

Теорема 3.3 утверждает сходимость процедуры лишь к локальному экстремуму. Для невыпуклой трудно рассчитывать на большее.

В методе стохастических квазиградиентов предполагается, что допустимая область X позволяет осуществить операцию проектирования. Далеко не всегда удается получить конструктивный метод проекций градиента. В таких случаях метод стохастических квазиградиентов предлагается сочетать с методом штрафных функций. При некоторых условиях можно, доказать сходимость получаемого при этом случайного процесса к решению задачи минимизации.