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

Первоначально метод стохастической аппроксимации использовался в задачах поиска экстремума функции искаженной ошибками, лишь для случая, когда оптимизируемая функция представляет собой функцию регрессии некоторой случайной величины, зависящей от параметра х. Однако для различных прикладных задач бывает существенно уметь оптимизировать также и функции от функции регрессии. Подобные задачи, как это отмечается в монографии Цыпкина [6], особенно часто возникают в теории обучающихся систем. В той же монографии для решения этой задачи предлагаются схемы типа алгоритмов стохастической аппроксимации. Рассмотренные там вычислительные схемы основаны на эвристических соображениях. Сходимость этих алгоритмов не доказана. Ниже излагаются основы алгоритма оптимизации для которого можно при некоторых условиях строго обосновать сходимость процедуры стохастической аппроксимации.

Пусть есть -мерная векторная случайная величина с ограниченной дисперсией, зависящая от

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

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

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

Случайные величины таковы, что для любого конкретного выполнены условия сходимости многомерной процедуры Роббинса — Монро при решении уравнения

3. Известен метод решения задачи

т. е. можно найти значение для которого

Предлагаемый для решения задачи (5.1) алгоритм распадается на два этапа.

Согласно предположению 1 известно множество значений принимаемых функцией при На первом этапе определяем значение решение задачи (5.2). Это можно сделать согласно предположению 3. На втором этапе используем процедуру Роббинса — Монро для решения уравнения Согласно предположению 2 процедура сходится к корню этого уравнения. Корень и будет, очевидно, решением задачи (5.1).

Предположения 1—3 носят общий характер и выглядят трудно проверяемыми. Особенно это относится к предположениям 1 и 3. Однако в некоторых случаях они заведомо выполнены, так что алгоритм применим.

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

Рассмотрим частный случай, когда функция является квадратичной функцией, а Предположим, что квадратичная часть функции является отрицательно определенной квадратичной формой. Как легко видеть, в этом случае функция представима в виде

где А — положительно определенная квадратная -симметричная матрица, 0 — точка максимума функции в пространстве — значение максимума Предположим, что функция осуществляет взаимно однозначное непрерывно ференцируемое отображение пространства на себя, причем якобиан нигде не обращается в нуль

Пусть в любой точке х мы можем вычислять значения где случайная матрица с нулевым математическим ожиданием,

ограниченной дисперсией и независимая от . Тогда для определения оптимального значения являющегося решением задачи (5.1), можно вместо описанной выше двухэтапной процедуры воспользоваться рекуррентным соотношением

Справедлива следующая теорема.

Теорема 5.1. Пусть

Тогда с вероятностью единица стремится к где т. е. решение задачи (5.1) для рассматриваемого частного случая.

Доказательство. Примем следующие обозначения:

(аргумент у в левой части введен для указания на случайный характер функции

Покажем, что введенные функции удовлетворяют всем условиям теоремы 2.4 настоящего Обзора, где Тогда утверждение теоремы 5.1 будет следствием теоремы 2.4.

Действительно, в силу положительной определенности матрицы А, взаимной однозначности и непрерывности отображения имеем при для любого

Далее,

и в силу того, что и независимости имеем

Отсюда в силу невырожденности якобиана матрицы А и взаимной однозначности отображения имеем для любого

Кроме того,

Учитывая ограниченность дисперсий их независимость и формулу (5.5), получим Легко видеть, что

Таким образом, условие 1) теоремы 2.4 для функции выполнено с Выше показано, что выполняются также ограничения для функций Остальные условия теоремы 2.4 следуют из условий теоремы 5.1 и соотношения (5.4). Итак, все условия теоремы 2.4 выполнены. Доказательство теоремы 5.1 завершено.