Численные методы для стохастических задач

Описанные в п. 11.3 методы предназначены для решения так называемых детерминированных задач.
Определение Задачу называют детерминированной, если погрешностью вычисления (или экспериментального определения) функции f(x) можно пренебречь. В противном случае задачу называют стохастической.
Метод золотого сечения рассчитан на детерминированные задачи. В стохастических задачах из-за ошибок эксперимента можно неправильно определить соотношения между значениями функции в точках; тогда дальнейшие итерации пойдут по ложному пути. Поэтому, если различия функции в выбранных точках стали того же порядка, что и экспериментальная погрешность, то итерации надо прекращать. Поскольку вблизи минимума чаще всего δf∼(δx)², небольшая погрешность функции приводит к появлению довольно большой области неопределенности δx∼(δf∼)^1/2.
Для стохасчтиеских задач разрабаытвают специальные методы их решения. Однако эти методы очень медленные, и применять их к детерминированным задачам невыгодно.
Опишем один алгоритм, который специально рассчитан на стохастические задачи. Он основан на предоположении о том, что ошибки в определении значения функции f(x) имеют статистическую природу, т.е. они целиком случайны, и систематической погрешности нет. Тогда можно определить минимум со сколь угодно высокой точностью (фактически игнорируя область неопределенности δx∼(δf∼)^1/2), если воспользоваться следующим итерационным процессом:
x_n+1 = x_n − (a_n/b_n)·[f(x_n+b_n)− f(x_n−b_n)]
где a_n, b_n − последовательности положительных чисел, удовлетворяющие следующим условиям:
При n→∞ a_n, b_n → 0, Σa_n=∞, Σ(a_n/b_n)²<∞
При выполнении этих условий x→x* с вероятностью 1 при n→∞. Это означает, что x→x* почти всегда, но не обязательно. Этим условиям удовлетворяют, в частности, следующие последовательности чисел:
a_n =1/n; b_n = n^−1/3
Описанный выше алгоритм является обобщением известного алгоритма минимизации Роббинса-Монро. Он сходится очень медленно, ибо изменение аргумента за шаг равно |x_n+1 − x_n| ≈ 2a_n|f′(x_n)|, а величины a_n убывают очень медленно. Поэтому применять этот алгоритм к детерминированным задачам невыгодно.

Геометрическое представление процесса минимизации

Классификация видов рельефа

Основные трудности многомерного случая удобно рассмотреть на примере функции двух переменных f(x,y). Функция z=f(x,y) задает в трехмерном пространстве x,y,z некоторую поверхность. Задача минимизации функции z=f(x,y) означает поиск наинизшей точки этой поверхности.
Рассмотрим рельеф этой поверхности,используя известные из топографии линии уровня. Для этого проведем равноотстоящие плоскости f=const и найдем линии их пересечения с поверхностью f(x,y); проекции этих линий на плоскость Oxy называются линиями уровня. Полученная в итоге картина напоминает топографическое изображение рельефа горизонталями. По виду линий уровня принято выделять три типа рельефа:

Типы рельефа

1. котловинный

2. овражный

3. неупорядоченный

Котловинный рельеф

При котловинном рельефе линии уровня напоминают эллипсы:

Рис. 11.6. Котловинный рельеф

В малой окрестности невырожденного минимума рельеф функции котловинный. Необходимые условия минимума функции двух переменных ∂f/∂x=0, ∂f/∂y=0 приводят к тому, что в разложении функции f(x,y) в окрестности минимума (x*,y*) отличными от нуля являются следующие члены:
f(x,y)=f(x*,y*)+0,5f_xx(Δx)²+ f_xyΔxΔy+0,5f_yy(Δy)²+...
где введены следующие обозначения:
f_xx = ∂²f/∂x²
f_xy = ∂²f/∂x∂y
f_yy = ∂²f/∂y²
причем квадратичная форма в правой части этого выражения - положительно определенная в окрестности минимума. Это означает, что при любых x,y (за исключением одновременно обращающихся в нуль) она положительна. Линии уровня положительно определенной квадратичной офрмы представляют собой эллипсы. В окрестности максимума эта квадратичная форма отрицательно определенная, а в седловинах − знакопеременна. Случай, когда все вторые производные обращаются в тчоке минимума в нуль, по существу ничего нового не дает, поскольку линии уровня вместо эллипсов будут похожими на них кривыми четвертого порядка.
Вблизи такого минимума функция мало меняется при заметных изменениях переменных. Поэтому, даже если мы не очень точно определим те значения переменных, которые должны минимизировать функцию, само значение функции при этом будет мало отличаться от минимального.

Овражный рельеф

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

Рис. 11.7. Овражный тип рельефа

Чаще встречается ситуация, в которой линии уровня всюду гладкие, однако на них имеются участки с большой кривизной; геометрические места точек с наибольшей кривизной называют разрешимыми оврагами или гребнями. В качестве примера можно привести рельеф функции f(x,y)=10(y−sinx)² + 0,1x², приведенный на следующем рисунке:

Рис. 11.8. Рельеф функции f(x,y)=10(y−sinx)² + 0,1x²,

Рельеф, изображенный на этом рисунке, имеет ярко выраженный извилистый разрешимый овраг, "дно" которого - синусоида, а низшая точка - начало координат.
В физических задачах овражный рельеф указывает на то, что вычислитель не учел какую-то закономерность, имеющую вид связи между переменными. Обнаружение и явный учет этой закономерности облегчают решение задачи. Так, если в приведенном выше примере ввести новые переменные ξ=x, η=y−sinx, то рельеф становится котловинным.

Неупорядоченный рельеф

Неупорядоченный тип рельефа характеризуется наличием многих максимумов, минимумов и седловин. Примером может служить функция f(x,y)=(1+sin²x)(1+sin²y): она имеет минимумы в точках с координатами x_k=πk; x_l=πl; и максимумы в точках x_k=π(k+1.2); x_l=π(l+1.2); (здесь k,l − целые числа).

Рис. 11.9. Рельеф функции f(x,y)=(1+sin²x)(1+sin²y)

На первый взгляд кажется, что для нахождения точки минимума функции f(x,y) можно просто решить систему нелинейных уравнений ∂f/∂x=0, ∂f/∂y=0 любым известным численным мтеодом (например, методом простых итераций) и затем отбросить те решения, которые являются седловинами или максимумами. Однако на практике эти методы обычно сходятся в настолько малой окрестности минимума, что выбрать подходящее нулевое приближение удается далеко не всегда.
Все эффективные методы поиска минимума функции многих переменных сводятся к выбору направления движения по склонам ко "дну"; разные методы отличаются способами выбора траектории спуска. На сегодняшний день пока не предложено метода, одинаково эффективного для всех типов рельефа; метод, приспособленный к одному типу рельефа, может оказаться плохим на рельефе другого типа.
Общим для всех является необходимость выбора точки начального приближения (x₀,y₀) − то есть такой точки, из которой начинается спуск. После этого ищется следующая точка (x₁,y₁), значение функции в которой f(x₁,y₁) должно быть меньше значения функции в исходной точке f(x₀,y₀). Выбор начального приближения обычно представляет собой достаточно серьезную проблему, потому что