9.10. Метод случайного спуска

Один из весьма распространенных релаксационных методов случайного поиска минимума дает следующий способ построения последовательности {x_k}.

На n-мерной единичной сфере с центром в начале координат выбирается случайная точка s_k, подчиняющаяся на этой сфере равномерному распределению, и затем по вычисленному на k-м шаге процесса элементу х_k определяется х_k+1 по формуле (9.7).

Схема 1.

(9.8)

Схема 2.

(9.7)

(9.14)

Обратимся к исследованию сходимости последовательности {x_k}, построенной по одной из этих схем.

Определение. Случайный вектор s∈E_n называется равномерно распределенным на квадрируемой поверхности S, если для всякого измеримого подмножества S' (S'⊆S)

Здесь символ "mes" означает площадь.

Пусть

Поскольку при ортогональном преобразовании Q единичная сфера переходит в себя (QS ≡ S) и, кроме того, mes S'= mes QS' для любого S' ⊆ S, то для любой ортогональной матрицы Q случайный вектор Qs равномерно распределен на S, если равномерно распределен на 5 случайный вектор s.

Пусть l^T = (l₁, ..., l_n) - произвольный единичный вектор (||l||²=1). В таком случае, если s-случайный вектор, равномерно распределенный на S, то скалярное произведение <l, s> имеет тот же закон распределения, что и любая компонента вектора s (например, s₁). Действительно, рассмотрим ортогональную матрицу Q, первая строка которой совпадает с l^T. Выше констатировано, что Qs имеет то же распределение, что и s, то есть первая компонента вектора Qs, равная , имеет то же распределение, что и s₁ Но распределение s₁ от l не зависит, следовательно, если l-случайный единичный вектор, то условное распределение <l, s> (при заданном l) совпадает с безусловным распределением s₁ Это означает, что <l, s> не зависит (в вероятностном смысле) от I: P {<l, s>≤ξ|l} = Р {s₁ ≤ ξ}, ξ∈E₁.

Таким образом, плотность вероятности случайной величины <l, s> совпадает с плотностью вероятности случайной величины s₁ Обозначим эту плотность p_s1(ξ), где, очевидно, -1≤ξ≤+ 1. Таким образом,

Но

где S' - кольцо на сфере S, расположенное между плоскостями с уравнениями s₁=ξ и s₁ = ξ + dξ (рис. 9.2). Площадь сферы радиуса r в m-мерном пространстве равна С_mr^m-1, где С_m-постоянная. Таким образом, mes S = C_n и площадь сферы радиуса √(1-²) в пространстве размерности n-1 равна C_n-1(1-ξ²)^(n-2)/2 Но именно такая сфера и служит "основанием" кольца S' на единичной сфере S. Отсюда следует, что

Рис. 9.2

Итак,

или, что то же самое, p_s1 (ξ)dξ = C(1 - ξ²)^(n-3)/2dξ, где С не зависит от ξ и определяется условием

Найдем теперь плотность p_s²1 (ξ) вероятности случайной величины s²₁ (0<ξ<1). Поскольку

и распределение s₁ симметрично относительно нуля (p_s²1(ξ)=p_s1(-ξ)), то

Иными словами,

поэтому окончательно получаем

и, как мы убедились,

^* (О гамма-функциях Г и бета-функциях В см. на стр. 201, )

Так как моменты m-го порядка случайной величины s²_i суть

то, в частности,

Теперь не представляет труда вычислить дисперсию случайной величины s²_i:

Пусть l₀, l₁, ..., l_k, ... - последовательность случайных единичных векторов, a s₀, s₁, ..., s_k, ...- последовательность взаимно независимых случайных векторов, равномерно распределенных на единичной сфере S (последовательности {l_k} и {s_k} предполагаются независимыми). Обозначим α_k = <l_k, s_k>. В результате предыдущих рассмотрений доказана следующая теорема.

Теорема 9.10.Случайные величины α₀, α₁, ..., α_k,... взаимно независимы, квадрат каждой из них имеет распределение с плотностью p_s²1(ξ) и

Выше мы пользовались некоторыми свойствами гамма-функций:

и бета-функций:

известными из курса математического анализа. В частности, что

Теорема 9.11.Если

3) последовательность {x_k} строится либо по схеме 1, либо по схеме 2, то для любого действительного m справедлива при m→∞ оценка

где

в случае схемы 1 и

в случае схемы 2, а

- нормальная функция распределения.

Доказательство. Как и прежде,

Из доказанных утверждений (если положить

следует, что случайные величины α²₀, α²₁, ... взаимно независимы, одинаково распределены в-интервале (0, 1), причем

и

Согласно центральной предельной теореме

В нашем случае это соотношение принимает вид

Отсюда в результате элементарных преобразований получаем

Из теорем 9.4 и 9.6 следует, что

где

в случае схемы 1 и

в случае схемы 2. Воспользовавшись свойствами (9.28) и (9.29), получаем окончательно

Замечание 1. В последней оценке константа С в n раз превосходит соответствующую константу в оценке скорости сходимости метода градиентного спуска и в n раз меньше соответствующей константы в оценке скорости сходимости метода случайного покоординатного спуска.

Замечание 2. Если функция φ(x) сильно выпукла, то, пользуясь той же методикой, не представляет труда показать, что с вероятностью, стремящейся к единице при m→∞, будет x_m→x^* с экспоненциальной скоростью.