Лекция: Методы одномерной минимизации

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

8.7.1. Метод деления шага пополам

Начальная точка и начальный шаг задаются на основе предварительных знаний о функции. Движение с неизменным шагом в одном направлении продолжается пока значение функции уменьшается. При увеличении значения направление меняется на противоположное и шаг уменьшается в два раза. Поиск заканчивается, когда при очередном шаге значение ухудшилось, а длина шага меньше заданной точности (рис. 8.8). Очевидно, что после прохождения минимума происходят колебания вокруг него с уменьшающейся амплитудой.

Алгоритм.

1. Задать начальную точку x0, начальный шаг h0и точность e; k=0.

2. Вычислить f(xk).

3. xk+1 =xk+hk.

4. Вычислить f(xk+1).

5. Еслиf(xk+1)<f(xk), то hk+1= hk и идти на 9.

6. Если hk<e, перейти на 10.

7. Если k=0, то hk+1= -hk и идти на 9.

8. hk+1= -hk/2;

9. k=k+1и перейти на 3.

10. Конец.▲

Проверка в п.7 необходима для того, чтобы не уменьшать шаг до достижения окрестности минимума. После окончания алгоритма в качестве оптимального x* может быть взято любое значение между xk и xk+1. При сильной изменчивости функции в окрестности минимума условие п.6 можно заменить на (hk<e) & (f(xk+1) – f(xk)<ef), гдеef – точность по функции.

8.7.2. Квадратичная аппроксимация

Для нахождения приближенного минимума исходная функция аппроксимируется функцией второго порядка

, (8.35)

где х0– точка отсчета реального диапазона значений x, в частности х0=0. Для определения коэффициентов, входящих в функцию (8.35), выбираются 3 точки и в них вычисляется значение функции f. Получается простая система 3-х уравнений с 3-мя неизвестными a,b и c:

Стационарная точка функции (8.35) вычисляется из равенства ее производной нулю:

. (8.36)

Она используется в условии останова и как новая точка для аппроксимации.

Алгоритм.

1. Задать первую точку x1, шаг Dх и точность по координате e и функции ef.

2. Определить 2-ю точку: x2=x1+Dх.

3. Вычислить f(x1) и f(x2).

4. Если f(x2)<f(x1), принять x3=x2+Dх, иначе x3=x1-Dх.

5. Вычислить f(x3).

6. Вычислить fm=min{f(x1),f(x2),f(x3)} и определить точку xm, соответствующую fm.

7. По трем точкам и значениям функции в них найти коэффициенты в (8.35).

8. Вычислить xa по формуле (8.36).

9. Если (|fm-f(xa)|<ef) & (|xm-xa |<e), окончить поиск.

10. Если fm<f(xa), взять xm и две ближайшие к ней точки, иначе взять xa и две ближайшие к ней точки. Выбранные точки пронумеровать в порядке возрастания значений, вычислить f в новой точке и перейти на 6.

8.7.3. Метод деления интервала пополам

Этот метод, как и два следующих, относится к методам сокращения интервала неопределенности. Предполагается, что точка минимума находится на заданном интервале [a,b].

Рассматриваемый метод также называют трехточечным. Точки выбираются так, что делят интервал на 4 равные части (рис. 8.9):

xm=(a+b)/2, x1=(a+ xm)/2, x2=(xm+b)/2.

Функция вычисляется в этих точках и после сравнения ее значений интервал сокращается в 2 раза. С новым интервалом действия повторяются.

Алгоритм.

1. Задать точность по координате e.

2. Вычислить xm и f(xm).

3. Вычислить x1 и x2.

4. Вычислить f(x) в этих точках.

5. Если f(x1) < f(xm), то принять b = xm, xm= x1. Иначе, если f(x2) < f(xm), положить a= xm, xm= x2 , иначе – a= x1, b = x2.

6. Если b — a<e, закончить поиск, иначе перейти на 3.

Нетрудно подсчитать, что после n вычислений функции интервал неопределенности уменьшится в раз. Доказано, что этот метод эффективнее других прямых методов, использующих равноудаленные точки.

8.7.4. Метод золотого сечения

Золотое сечение – это определенное отношение части к целому. Отрезок АВ делится точкой С в отношении золотого сечения (рис. 8.10), если

. (8.37)

Положим АВ = 1, АС = х, СВ = 1 – х, тогда из (8.37) получаем уравнение

х2 + х – 1 = 0,

из которого следует

, .

Эти отношения используются для выбора двух точек внутри интервала неопределенности. Они располагаются, как показано на рис. 8.11. Каждая из точек делит интервал [a, b] в отношении золотого сечения.

В этих точках вычисляется функция. Если f(x1) > f(x2), то отбрасывается часть интервала [a, x1], если f(x1) < f(x2), то отсекается часть [x2, b], а при равенстве значений функции – любая из них. Оставшаяся часть интервала равна от величины исходного. Очевидно, что после такого сокращения интервала одна из внутренних точек остается с изменением индекса, а вторая берется на основе золотого сечения или, что одно и то же, симметрично оставшейся (рис. 8.12). Сокращение интервала продолжается до достижения заданной точности.

Алгоритм.

1. Задать точность по координате e.

2. Вычислить

3. Вычислить f( x1), f( x2).

4. Если f(x1)>f(x2), положить a=x1, x1=x2, илиx2=a+b-x1, иначе – b=x2, x2=x1, или x1=a+b-x2.

5. Если (b-a)<e, закончить поиск.

6. Вычислить функцию в новой точке и перейти на 4.▲

Итерации алгоритма графически иллюстрируются на рис. 8.12.

Покажем, что сохраняемая точка (x1 или x2) делит сокращенный интервал также в отношении золотого сечения. Пусть на k-й итерации внутренние точки делят интервал [ak, bk] в отношении золотого сечения. Обозначив =bk — ak, имеем

.

Тогда для нового, сокращенного, интервала находим

,

В результате получаем:

.

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

Согласно алгоритму функция вычисляется 2 раза на начальном интервале и по одному разу на всех последующих. Поэтому после n вычислений функции интервал неопределенности составит от величины первоначального. При заданной точности можно найти необходимое количество вычислений функции n из условия

8.7.5. Метод Фибоначчи

Схема метода почти полностью совпадает с методом золотого сечения. Отличие в том, что вместо золотого сечения используется отношение чисел Фибоначчи: на k-й итерации доли малого и большого отрезков интервала равны и соответственно.

Числа ФибоначчиFn вычисляются по известным соотношениям: F0=F1=1, Fn= Fn-1+Fn-2, n³2.

Точки x1 и x2вычисляются по формулам:

, (8.38)

. (8.39)

Как видно, они идентичны приведенным в предыдущем разделе. Однако если при использовании золотого сечения внутренние точки не могут сливаться, то здесь это не так. Действительно, при k=n-1 из (8.38) и (8.39) имеем

, .

Но так как F0/F2=F1/F2=1/2, тои, следовательно, точки сливаются в середине интервала. Поэтому до начала итераций необходимо определить значение n, гарантирующее достижение минимума с заданной точностью e. После 1-й итерации длина интервала составит от величины исходного, после 2-й – ( )( ),…, после (n-1)-й –

.

Значит, длина последнего интервала будет равна (b1 — a1)/Fn, где [a1, b1] – исходный интервал. Для обеспечения заданной точности требуется, чтобы

или. (8.40)

Таким образом, соотношение (8.40) позволяет определить номер числа Фибоначчи по исходным данным. На начальном интервале точки вычисляются по формулам (8.38) и (8.39) при k=1. На последующих итерациях числа Фибоначчи не требуются, так как одна точка переносится из предшествующей итерации, а вторая берется симметрично ей, то есть лучше использовать вторые формулы из п.4 алгоритма золотого сечения.

После слияния внутренних точек остается неопределенность с положением минимума. Для ее устранения вторая точка берется слева или справа от центра на расстоянии e1@(0,01¸0,05)e. Для случая сдвига второй точки влево (рис. 8.13) при f(x1)< f(x1-e1) минимум лежит в интервале (2), в противном случае – в интервале (1).

Метод Фибоначчи является самым эффективными из всех прямых методов. Очень близок к нему метод золотого сечения: при n>9 они практически совпадают по эффективности и чем больше n, тем ближе эти методы. А в пределе отношение, используемое в методе Фибоначчи на 1-й итерации, становится равным золотому сечению:

.