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

При построении процесса оптимизации стараются сократить объем вычислений и время поиска. Этого достигают обычно путем сокращения количества вычислений значений целевой функции f(x). Одним из наиболее эффективных методов, в которых при ограниченном количестве вычислений f(x) достигается наилучшая точность, является метод золотого сечения.

Если известно, что функция f(x) унимодальная на отрезке [a,b], то положение точки минимума можно уточнить, вычислив f(x) в двух внутренних точках отрезка. При этом возможны две ситуации:

1.

f(x₁)<f(x₂)

Минимум реализуется на отрезке [a, x₂].

2.

f(x₁)>f(x₂)

Минимум реализуется на отрезке [x₁, b].

В методе золотого сечения каждая из точек x ₁ и x₂ делит исходный интервал на две части так, что отношение целого к большей части равно отношении большей части к меньшей, т.е. равно так называемому "золотому отношению". Это соответствует следующему простому геометрическому представлению:

Здесь

или

(6)

Обозначив

получаем

откуда

Итак, длины отрезков [a,x₁] и [x₂,b] одинаковы и составляют 0,382 от длины (a,b). Значениям f(x₁) и f(x₂) определяется новей интервал (a,x₂) или (x₁,b), в котором локализован минимум. Найденный интервал снова делится двумя точками в том же отношении, причем одна из новых точек деления совпадает с уже использованной на предыдущем шаге.

Взаимное расположение точек первых трех вычислений можно показать следующим образом:

1) f(x₁)<f(x₂)

Первый шаг
Второй шаг

2) f(x₁)≥f(x₂)

Первый шаг
Второй шаг

Рис. 5

Таким образом, длина интервала неопределенности на каждом шаге сжимается с коэффициентом 0,618. На первом шаге необходимы два вычисления функции, на каждом последующем - одно.

Длина интервала неопределенности после S вычислений значений f(x) составляет:

(7)

Алгоритм метода золотого сечения для минимизации функции f(x) складывается из следующих этапов:

1. Вычисляется значение функции f(x₁), где x₁=a+0,382(b-a).

2. Вычисляется значение функции f(x₂), где x₁=b+0,382(b-a).

3. Определяется новый интервал (a,x2) или (x1,b), в котором локализован минимум.

4. Внутри полученного интервала находится новая точка (x₁ в случае 1) или (x₂ в случае 2), отстоящая от его конца на расстоянии, составляющем 0,382 от его длины. В этой точке рассчитывается значение f(x). Затем вычисления повторяются, начиная с пункта 3, до тех пор, пока величина интервала неопределенности станет меньше или равна ε, где ε - заданное сколь угодно малое положительное число.