2. Процедура Кифера-Вольфовица для оценки экстремума неизвестной функции регрессии

Следуя формулировке Роббинса и Монро, необходимо оценить единственный экстремум (максимум или минимум, о котором известно, что он является единственным) функции или, что то же самое, оценить единственный корень уравнения

Кифер и Вольфовиц [8] предложили следующую процедуру:

где знак плюс берется при оценке максимума и знак минус при оценке минимума. Заметим, что величину

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

Теорема 3. Пусть функция регрессии удовлетворяет следующим условиям:

строго возрастающая функция при и строго убывающая при

Существуют такие что

Существуют такие что

Для всякого существует такое что

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

то

где определяется формулой Отметим, что условия и представляют собой условия регулярности Липшица. Блюм доказал, что теорема 3 остается справедливой, даже когда не удовлетворяется условие Для этого случая Блюм доказал также, что

Процедура Кифера-Вольфовица была распространена на многомерный случай Блюмом [3] и Саксом [10] и на непрерывный случай Сакрисоном [11].