6. Многоэкстремальная стохастическая аппроксимация

При формулировке теорем сходимости в алгоритмах стохастической аппроксимации типа Роббинса - Монро или Кифера — Вольфовица, как правило, предполагается единственность корня уравнения регрессии (для процедур типа Роббинса — Монро) или единственность экстремума функции регрессии (для процедур типа Кифера — Вольфовица). Причем в последнем случае обычно предполагается, что даже локальный экстремум функции регрессии единствен, и, естественно, что он совпадает поэтому с глобальным экстремумом. Некоторые утверждения по поводу алгоритмов стохастической аппроксимации для многоэкстремальных функций регрессии получены Фабианом [1]. Красулина [3], используя результат Фабиана и уточняя его, получила теорему о сходимости процедуры Роббинса — Монро к одному из корней функции регрессии (теорема 1.1 настоящего обзора). Некоторые результаты, о сходимости процедур стохастической аппроксимации к множеству корней функции регрессии получены Браверманом и Розоноэром [1].

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

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

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

Из первого неравенства следует, что достигает своей нижней грани в некоторой конечной точке х. Для упрощения формулировки результата будем предполагать, что нижняя грань достигается в единственной точке, хотя с очевидным изменением формулировки результат остается верным и для любого конечного числа таких точек:

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

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

— точка -мерного пространства целое число из интервала ( целое число). Изменение состояния процесса происходит согласно следующим правилам. Для компоненты при

Функция строго монотонно возрастающая функция, удовлетворяющая условиям

Если то где случайная величина, принимающая значения ( с произвольным законом распределения.

Введем обозначения: максимальное целое число, удовлетворяющее условиям

т. е. это момент времени, когда случайная величина в последний раз перед моментом приняла значение 1.

где — постоянные, а числа удовлетворяют условиям

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

где а и — не зависящие от положительные постоянные.

Условие б) означает, грубо говоря, что не все реализации случайного вектора лежат в подпространствах пространства размерности

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

где X — некоторая компактная область пространства содержащая точку случайный вектор, плотность распределения которого всюду на X положительна и не зависит от При этих условиях имеет место такое утверждение:

Теорема 6.1 (Вайсборд и Юдин). Для случайного процесса который зависит от параметра имеет место соотношение

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