§ 3.13. Условия сходимости
Сходимость алгоритмов адаптации, или,
что то же самое, устойчивость неавтономных стохастических систем с обратной
связью,— наиболее существенный вопрос, возникающий при реализации алгоритмов
адаптации.
К настоящему времени можно установить
некоторые необходимые признаки и достаточные условия сходимости. Об этом и
будет идти речь в настоящем параграфе.
Рассмотрим алгоритм адаптации в
разностной форме (3.10):
(3.32)
Для того чтобы вектор 
стремился
к 
почти
наверное, необходимо, по крайней мере, чтобы при 
правая часть стремилась к
нулю, т. е.
(3.33)
практически
при любых реализациях
.
В общем случае градиент реализации 
, как мы уже
упоминали (см. условие (3.7)), отличен от нуля, и поэтому необходимо, чтобы 
с ростом 
стремилось к нулю.
Достаточные условия сходимости
алгоритмов адаптации можно сформулировать так. Алгоритмы адаптации (3.9) —
(3.11) сходятся почти наверное при соблюдении следующих условий:
(3.34)
Эти
условия имеют весьма простой физический и геометрический смысл.
Условие а) требует, чтобы скорость
уменьшения была
такова, чтобы дисперсия оценки 
уменьшалась до нуля, но чтобы за время
изменения можно
было использовать достаточно большое число данных, при котором еще справедлив
закон больших чисел.
Условие б) определяет характер поведения
поверхности 
вблизи
корня, и, следовательно, знаки приращений 
. Наконец, условие в) гласит, что
математическое ожидание квадратической формы, т. е. 
, с увеличением с должно расти
не быстрее квадратичной параболы.
Для поисковых алгоритмов адаптации,
естественно, налагаются определенные ограничения на 
, а сама форма условий
изменяется в связи с отсутствием реализации градиента. Поисковые алгоритмы
адаптации (3.15) сходятся почти наверное и в среднеквадратичном смысле при
выполнении следующих условий:
(3.35)
Эти условия имеют примерно тот же смысл,
что и рассмотренные нами выше, поэтому мы не станем их обсуждать.
Стохастические алгоритмы обладают
высокой помехоустойчивостью. Случайные аддитивные помехи с нулевым средним
значением устраняются и не влияют на результат, т. е. на оптимальный вектор 
.
Если эти помехи отсутствуют, т. е. если
их дисперсия равна нулю и при любом 
выполняется условие
, (3.36)
то
условие (3.33) будет выполняться не только при , стремящемся к нулю, но и при 
или при 
, стремящемся к
постоянной величине. В этом случае для установления максимального значения 
можно воспользоваться
тем же подходом, который был использован для регулярных алгоритмов оптимизации.
При 
будет
обеспечена сходимость почти наверное, которая очень близка к обычной.
Алгоритмы, получающиеся в этом случае из
(3.9) и (3.11) при 
,
естественно, обладают низкой помехоустойчивостью, и при наличии помех с дисперсией
сходимость
в принятом выше смысле отсутствует, хотя
, (3.37)
причем
при
.
Практически мы часто можем принять это менее жесткое условие, которое
соответствует в некотором смысле неасимптотической устойчивости по Ляпунову.
Аналогичные условия сходимости известны и для непрерывных алгоритмов. Эти
условия более жесткие. Мы их здесь приводить не будем, тем более, что в связи с
большим энтузиазмом, который наблюдается в развитии вероятностной теории
устойчивости, в этой области можно ожидать более широких и более простых
условий устойчивости. Пока же в основе доказательств сходимости вероятностных
итеративных методов лежат фундаментальные теоремы А. Дворецкого и теория
мартингалов.
