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

Материал из MachineLearning.

Версия от 21:16, 18 июля 2026; Kamilia Gibadullina (Обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Содержание

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

Метод золотого сечения — это численный метод поиска минимума функции одной переменной на заданном отрезке. Он относится к методам безградиентной оптимизации, поскольку для его работы не требуется вычислять производную функции.

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

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

Основная идея

Пусть минимум функции f(x) ищется на отрезке [a,b]. Внутри него выбираются две точки x_1 и x_2, причём x_1 расположена левее x_2.

Если значение f(x_1) меньше значения f(x_2), то минимум следует искать в левой части отрезка. Правая часть, расположенная правее точки x_2, отбрасывается. Если f(x_1) больше f(x_2), то отбрасывается левая часть.

Для выбора точек используется число

\tau=\frac{\sqrt{5}-1}{2}\approx 0{,}618.

Положения внутренних точек определяются следующим образом:

x_1=b-\tau(b-a).

x_2=a+\tau(b-a).

Здесь a и b — границы текущего отрезка, а \tau — коэффициент золотого сечения.

Число \tau связано с пропорцией золотого сечения. Благодаря такому расположению точек после уменьшения отрезка одна из них может использоваться на следующей итерации. Значение функции в этой точке не требуется вычислять повторно.

Алгоритм

Метод золотого сечения можно описать следующими шагами:

  1. Задаётся начальный отрезок [a,b], на котором находится минимум функции.
  2. Внутри отрезка выбираются точки x_1 и x_2.
  3. Вычисляются значения f(x_1) и f(x_2).
  4. Если f(x_1) меньше f(x_2), отбрасывается правая часть отрезка.
  5. Если f(x_1) больше f(x_2), отбрасывается левая часть отрезка.
  6. Действия повторяются, пока длина оставшегося отрезка не станет достаточно маленькой.

После завершения работы в качестве приближённой точки минимума обычно берут середину полученного отрезка:

x^*=\frac{a+b}{2}.

Здесь x^* — приближённое положение минимума. Чем меньше итоговый отрезок, тем точнее полученный результат.

Пример

Рассмотрим функцию

f(x)=(x-2)^2

на отрезке [0,5]. Эта функция имеет минимум в точке x=2, но предположим, что заранее это неизвестно.

На первой итерации выбираются точки примерно x_1=1{,}91 и x_2=3{,}09. Значение функции в первой точке меньше, чем во второй:

f(1{,}91)\approx 0{,}01,

f(3{,}09)\approx 1{,}19.

Следовательно, правую часть отрезка можно отбросить. Новый отрезок поиска будет примерно равен [0;3{,}09].

На следующей итерации рассматриваются точки примерно 1{,}18 и 1{,}91. Значение функции в точке 1{,}91 меньше, поэтому отбрасывается часть отрезка левее точки 1{,}18. Новый отрезок имеет вид [1{,}18;3{,}09].

После ещё одного шага область поиска уменьшается примерно до отрезка [1{,}18;2{,}36]. Таким образом, границы постепенно приближаются к точке x=2.

Условия применения

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

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

Если функция имеет несколько локальных минимумов, разрывы или сильные колебания, метод может найти не тот минимум, который ожидался. Поэтому важно правильно выбрать начальный отрезок и убедиться, что на нём функция ведёт себя унимодально.

Преимущества и ограничения

Основные преимущества метода:

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

Основные ограничения:

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

Сравнение с другими методами

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

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

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

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

См. также

Литература

  • Brent R. P. Algorithms for Minimization without Derivatives. — Englewood Cliffs: Prentice-Hall, 1973.
  • Nocedal J., Wright S. J. Numerical Optimization. — 2nd ed. — New York: Springer, 2006.
  • Press W. H., Teukolsky S. A., Vetterling W. T., Flannery B. P. Numerical Recipes: The Art of Scientific Computing. — 3rd ed. — Cambridge: Cambridge University Press, 2007.
  • Bazaraa M. S., Sherali H. D., Shetty C. M. Nonlinear Programming: Theory and Algorithms. — 3rd ed. — Hoboken: Wiley, 2006.
Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%B7%D0%BE%D0%BB%D0%BE%D1%82%D0%BE%D0%B3%D0%BE_%D1%81%D0%B5%D1%87%D0%B5%D0%BD%D0%B8%D1%8F»