Одномерная оптимизация. Постановка задачи. Метод "золотого" сечения, Фибоначчи.
Постановка задачи.
Пусть функция f(x) - унимодальная, по крайней мере, на отрезке [a,b] и известны ее значения на концах этого отрезка. Т.е. минимум локализован и необходимо определить его как можно точнее, с наименьшим возможным интервалом неопределенности, но при этом возможно выполнить только n вычислений функции? Как следует выбрать n точек xk, k=1,..,N вычисления функции на отрезке [a,b], чтобы как можно точнее определить минимум
Метод Фибоначчи.
Предположим, что имеется интервал неопределенности (a,b), известны значения f(a), f(b) и f(x1). Где поместить точку x2, x1<x2 , а затем после измерения f(x2) и сужения интервала неопределенности точку x3, затем x4 и т.д. для того, чтобы получить наименьший возможный интервал неопределенности после N измерений?
Поскольку исход заранее неизвестен, то необходимо минимизировать наибольшую из длин возможных новых интервалов неопределенности, поэтому также как и в методе дихотомии размещаем x1 и x2 внутри интервала неопределенности симметрично. Так как после сужения интервала мы будем использовать одну из срединных точек, то следующая точка должна располагаться опять же симметрично относительно оставшейся. При этом выполняется равенство (рис.8.3):
L0 = L1 =L2 + L3 . (1)
Рис.8.3. Сужение интервала неопределенности методом «Фибоначчи» и методом «золотого сечения» .
Дальнейшие аналогичные рассуждения приводят нас к рекуррентной формуле:
Lk =Lk+1 + L k+2 , k=1,N-2. (2)
На последнем шаге интервал неопределенности будет иметь длину LN, следовательно:
LN-2 =LN-1 + LN . (3)
Кроме этого, чтобы на последнем шаге сужение интервала неопределенности было бы максимальным, необходимо, чтобы последняя серединная точка делила его пополам, т.е.
LN-1 =2*LN . (4)
Разделим это равенство и все предыдущие на LN:
LN-1/LN = 2 ,
LN-2/LN =LN-1/LN + 1 ,
Lk/LN =Lk+1/LN + L k+2/LN , k=1,N-2. (5)
Обозначим через Fk= LN-k+1/LN , k=1,N и перепишем (5):
F2 = 2F1, F1=1,
F3= F2 + F1 ,
FN+1-k = FN-k + FN-k-1 , k=N-3,1. (6)
Если мы теперь определим
F0 = F1 = 1, Fk= Fk-1 + Fk-2 для k=2,3,...,N, (7)
то получим последовательность, совпадающую с последовательностью чисел (6), называемую числами Фибоначчи.
Если начальный интервал (a,b) имеет длину L1= b-a, то
L1= Fn*Ln
или
Ln= L1/Fn . (8)
Следовательно, произведя n вычислений функции, мы уменьшим начальный интервал в Fn раз по сравнению с его начальной длиной.
Если поиск начат, продолжить его несложно, используя приведенное выше правило добавления новой точки (симметрично). Следовательно, необходимо найти положение первой внутренней точки x1 , которая располагается на расстоянии L2 от одного из концов начального интервала, причем не важно от какого конца, поскольку вторая точка помещается согласно правилу симметрии на расстоянии L2 от второго конца интервала:
L2= Fn-1*Ln = L1*Fn-1/Fn . (9)
или
х1= b - (b-a)*Fn-1/Fn . (9’)
После того как найдено положение первой внутренней точки, числа Фибоначчи больше не нужны. Новые точки генерируются на каждой итерации, исходя из соотношений симметрии.
Поиск методом «золотого сечения».
Не всегда можно заранее определить, сколько раз придется вычислять функцию. В методе Фибоначчи это нужно знать для определения L2, т.е. положения начальной внутренней точки (см. выше).
Метод «золотого сечения» почти столь же эффективен, как и метод Фибоначчи, при этом он не требует знания n - количества вычисления функции.
Исходя из соображений, рассмотренных ранее (см. (2)) записываем:
Lk =Lk+1 + L k+2 , k=1,N-2. (10)
Чтобы степень уменьшения интервала неопределенности была постоянной необходимо, чтобы выполнялось соотношение
Lk+1/Lk= = const, k=1,N-1. (11)
В этом случае имеем систему уравнений, из которой следует, что
1= +2 . (12)
Таким образом имеем квадратное уравнение, из которого определяем значение постоянной:
= (-1+5)/2 = 0.6180 . (13)
На этом числе и основан рассматриваемый метод. Таким образом, имеем:
х1= b - (b-a) . (14)
Интересно, что при больших n эффективность данного метода практически совпадает с эффективностью метода Фибоначчи, т.к.
lim Fk/Fk+1 = . (15)