Поиск с помощью золотого сечения

Эта статья находится в разработке!

Поиск с помощью золотого сечения (Golden section search) - это улучшение наивной реализации троичного поиска, служащий для поиска минимума/максимума функции. При простом троичном поиске на каждой итерации функция вычисляется в двух точках. Метод же золотого сечения требует вычисления лишь в одной точке (за исключением первой итерации). За счет этого достигается выйгрыш в производительности.

Алгоритм

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

Точки [math]x_1[/math] и [math]x_2[/math] разбивают отрезок на три части. Потребуем, чтобы одновременно выполнялось:

[math] \frac{a + b}{c} = \frac{b + c}{a} = \phi [/math]

[math] \frac{a}{b} = \phi [/math]

[math] \frac{c}{b} = \phi [/math]

Где [math] \phi [/math] - это некоторое отношение, в котором делим отрезок (точки [math]x_1[/math] и [math]x_2[/math] разбивают отрезок симметрично).

Тогда:

[math] a + b = \phi c, a = \phi b, c = \phi b[/math], откуда получаем [math] \phi + 1 = \phi^2 \Rightarrow \phi = \frac{1 + \sqrt{5}}{2}[/math]   (тот корень уравнения, который меньше нуля, по понятным причнам отбросили)

Это число совпадает с золотым сечением. Отсюда название метода.

Формально для поиска минимума (для максимума - делается аналогично) функции [math] f [/math]:

Шаг 1:

Определяем границы поиска [math]lbound[/math] и [math]rbound[/math], затем устанавливаем текущее разбиение:

[math]x_1 = lbound + \frac{rbound - lbound}{\phi + 1}[/math]

[math]x_2 = rbound - \frac{rbound - lbound}{\phi + 1}[/math]

и вычислем функцию на них: [math]f_1 = f(x_1), f_2 = f(x_2)[/math]

Шаг 2:

если [math]f(x_1) \lt f(x_2)[/math]

Шаг 3:

Псевдокод

Ссылки

Википедия - Метод золотого сечения

Wikipedia - Golden section search (english)