Поиск золотого сечения

Схема поиска золотого сечения. Исходная тройка значений x — это { x ₁ , x ₂ , x ₃ }. Если f ( x ₄ ) = f _4a , тройка { x ₁ , x ₂ , x ₄ } выбирается для следующей итерации. Если f ( x ₄ ) = f _4b тройка { x ₂ , x ₄ , x _{3 }.} , выбирается

Поиск золотого сечения — это метод поиска экстремума (минимума или максимума) функции внутри заданного интервала. Для строго унимодальной функции с экстремумом внутри интервала она найдет этот экстремум, а для интервала, содержащего несколько экстремумов (возможно, включая границы интервала), она сходится к одному из них. Если единственный экстремум на интервале находится на границе интервала, он сходится к этой граничной точке. Метод работает путем последовательного сужения диапазона значений на указанном интервале, что делает его относительно медленным, но очень надежным. Этот метод получил свое название от того факта, что алгоритм сохраняет значения функции для четырех точек, ширина трех интервалов которых находится в соотношении φ :1: φ , где φ — золотое сечение . Эти соотношения сохраняются для каждой итерации и являются максимально эффективными. За исключением граничных точек, при поиске минимума центральная точка всегда меньше или равна внешним точкам, что гарантирует наличие минимума между внешними точками. Обратное верно при поиске максимума. Алгоритм – это предел Поиск Фибоначчи (также описанный ниже) для многих оценок функций. Поиск Фибоначчи и поиск золотого сечения были открыты Кифером (1953) (см. также Авриэль и Уайльд (1966)).

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

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

Диаграмма выше иллюстрирует один шаг метода поиска минимума. Функциональные значения $f(x)$ находятся на вертикальной оси, а горизонтальная ось — это параметр x . Стоимость $f(x)$ уже оценен по трем пунктам: $x_{1}$, $x_{2}$, и $x_{3}$. С $f_{2}$ меньше, чем любой $f_{1}$ или $f_{3}$, ясно, что минимум лежит внутри интервала от $x_{1}$ к $x_{3}$.

Следующим шагом в процессе минимизации является «зондирование» функции путем оценки ее нового значения x , а именно: $x_{4}$. Наиболее эффективно выбрать $x_{4}$ где-то внутри наибольшего интервала, т.е. между $x_{2}$ и $x_{3}$. Из диаграммы видно, что если функция дает $f_{4a}>f(x_{2})$, то минимум лежит между $x_{1}$ и $x_{4}$, и новая тройка точек будет $x_{1}$, $x_{2}$, и $x_{4}$. Однако если функция возвращает значение $f_{4b}<f(x_{2})$, то минимум лежит между $x_{2}$ и $x_{3}$, и новая тройка точек будет $x_{2}$, $x_{4}$, и $x_{3}$. Таким образом, в любом случае мы можем построить новый, более узкий интервал поиска, который гарантированно будет содержать минимум функции.

Выбор точки измерения

Из диаграммы выше видно, что новый интервал поиска будет либо между $x_{1}$ и $x_{4}$ длиной a + c или между $x_{2}$ и $x_{3}$ длиной b . Поиск золотого сечения требует, чтобы эти интервалы были равны. Если это не так, серия «невезений» может привести к тому, что более широкий интервал будет использоваться много раз, что замедлит скорость сходимости. Чтобы гарантировать, что b = a + c , алгоритм должен выбрать $x_{4}=x_{1}+(x_{3}-x_{2})$.

Однако остается вопрос, где $x_{2}$ следует располагать по отношению к $x_{1}$ и $x_{3}$. Поиск золотого сечения выбирает расстояние между этими точками таким образом, чтобы эти точки имели ту же пропорцию расстояния, что и последующая тройка. $x_{1},x_{2},x_{4}$ или $x_{2},x_{4},x_{3}$. Поддерживая одинаковую пропорцию интервалов по всему алгоритму, мы избегаем ситуации, в которой $x_{2}$ очень близко к $x_{1}$ или $x_{3}$ и гарантировать, что ширина интервала уменьшается на одну и ту же постоянную пропорцию на каждом шаге.

Математически, чтобы гарантировать, что интервал после оценки $f(x_{4})$ пропорционально интервалу до этой оценки, если $f(x_{4})$ является $f_{4a}$ и наша новая тройка очков $x_{1}$, $x_{2}$, и $x_{4}$, тогда мы хотим

${\frac {c}{a}}={\frac {a}{b}}.$

Однако, если $f(x_{4})$ является $f_{4b}$ и наша новая тройка очков $x_{2}$, $x_{4}$, и $x_{3}$, тогда мы хотим

${\frac {c}{b-c}}={\frac {a}{b}}.$

Исключение c из этих двух одновременных уравнений дает

$\left({\frac {b}{a}}\right)^{2}-{\frac {b}{a}}=1,$

или

${\frac {b}{a}}=\varphi ,$

где φ — золотое сечение :

$\varphi ={\frac {1+{\sqrt {5}}}{2}}=1.618033988\ldots$

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

Условие прекращения действия

В зависимости от приложения может быть применено любое количество условий прекращения действия. Интервал Δ X = X ₄ − X ₁ является мерой абсолютной ошибки оценки минимума X и может использоваться для завершения алгоритма. Значение Δ X уменьшается в раз r = φ − 1 для каждой итерации, поэтому количество итераций для достижения абсолютной ошибки Δ X составляет примерно ln(Δ X /Δ X ₀ ) / ln( r ), где Δ X ₀ - начальное значение Δ X .

Поскольку гладкие функции вблизи минимума плоские (их первая производная близка к нулю), следует обратить внимание на то, чтобы не ожидать слишком большой точности определения минимума. Условие завершения, представленное в книге «Численные рецепты на C», основано на проверке пробелов между $x_{1}$, $x_{2}$, $x_{3}$ и $x_{4}$, заканчивающийся, когда он находится в пределах относительной точности

$|x_{3}-x_{1}|<\tau {\big (}|x_{2}|+|x_{4}|{\big )},$

где $\tau$ является параметром допуска алгоритма, и $|x|$ это абсолютное значение $x$. Проверка основана на размере скобки относительно ее центрального значения, поскольку эта относительная ошибка в $x$ приблизительно пропорциональна квадрату абсолютной ошибки в $f(x)$ в типичных случаях. По той же причине в тексте «Численные рецепты» рекомендуется, чтобы $\tau ={\sqrt {\varepsilon }}$, где $\varepsilon$ требуемая абсолютная точность $f(x)$.

Алгоритм

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

Итерационный алгоритм

Схема поиска минимума золотого сечения. Начальный интервал, окруженный X ₁ и X _4, делится на три интервала, и f[X] оценивается в каждом из четырех X _i . Затем выбираются два интервала, содержащие минимум f ( X _i ), вычисляются третий интервал и функциональное значение, и процесс повторяется до тех пор, пока не будут выполнены условия завершения. Ширина трех интервалов всегда находится в соотношении c:cr:c , где r = φ - 1 = 0,619... и c = 1 - r = 0,381..., φ - золотое сечение . Этот выбор отношений интервалов является единственным, который позволяет поддерживать отношения во время итерации.

1. Укажите функцию, которую необходимо минимизировать, $f(x)$, интервал поиска как { X ₁ , X ₄ } и их функциональные значения F ₁ и F ₄ .
2. Вычислите внутреннюю точку и ее функциональное значение F ₂ . Длины двух интервалов находятся в соотношении c: r или r: c , где r = φ - 1; и c = 1 − r , где φ — золотое сечение.
3. Используя тройку, определите, выполняются ли критерии сходимости. Если да, оцените X как минимум из этой тройки и вернитесь.
4. Из тройки вычислите другую внутреннюю точку и ее функциональное значение. Три интервала будут находиться в соотношении $c:cr:c$.
5. Тремя точками для следующей итерации будут та, где F является минимумом, и две ближайшие к ней точки по X.
6. Перейдите к шагу 3.

"""
Python program for golden section search.  This implementation
does not reuse function evaluations and assumes the minimum is c
or d (not on the edges at a or b)
"""

import math

invphi = (math.sqrt(5) - 1) / 2  # 1 / phi


def gss(f, a, b, tolerance=1e-5):
    """
    Golden-section search
    to find the minimum of f on [a,b]

    * f: a strictly unimodal function on [a,b]

    Example:
    >>> def f(x): return (x - 2) ** 2
    >>> x = gss(f, 1, 5)
    >>> print(f"{x:.5f}")
    2.00000

    """
    while abs(b - a) > tolerance:
        c = b - (b - a) * invphi
        d = a + (b - a) * invphi
        if f(c) < f(d):
            b = d
        else:  # f(c) > f(d) to find the maximum
            a = c

    return (b + a) / 2

// a and c define range to search
// func(x) returns value of function at x to be minimized
function goldenSection(a, c, func) {
  function split(x1, x2) { return x1 + 0.6180339887498949*(x2-x1); }
  var b = split(a, c);
  var bv = func(b);
  while (a != c) {
    var x = split(a, b);
    var xv = func(x);
    if (xv < bv) {
      bv = xv;
      c = b;
      b = x;
    }
    else {
      a = c;
      c = x;
    }
  }
  return b;
}
function test(x) { return -Math.sin(x); }
console.log(goldenSection(0, 3, test)); // prints PI/2

"""
Python program for golden section search.  This implementation
does not reuse function evaluations and assumes the minimum is c
or d (not on the edges at a or b)
"""

import math

invphi = (math.sqrt(5) - 1) / 2  # 1 / phi
invphi2 = (3 - math.sqrt(5)) / 2  # 1 / phi^2


def gss(f, a, b, tolerance=1e-5):
    """
    Golden-section search.

    Given a function f with a single local minimum in
    the interval [a,b], gss returns a subset interval
    [c,d] that contains the minimum with d-c <= tolerance.

    Example:
    >>> def f(x): return (x - 2) ** 2
    >>> print(*gss(f, a=1, b=5, tolerance=1e-5))
    1.9999959837979107 2.0000050911830893
    """
    a, b = min(a, b), max(a, b)
    h = b - a
    if h <= tolerance:
        return (a, b)

    # Required steps to achieve tolerance
    n = int(math.ceil(math.log(tolerance / h) / math.log(invphi)))

    c, d = a + invphi2 * h, a + invphi * h
    yc, yd = f(c), f(d)

    for _ in range(n - 1):
        h *= invphi
        if yc < yd:
            b, d = d, c
            yd = yc
            c = a + invphi2 * h
            yc = f(c)
        else:  # yc > yd to find the maximum
            a, c = c, d
            yc = yd
            d = a + invphi * h
            yd = f(d)

    return (a, d) if yc < yd else (c, b)

Рекурсивный алгоритм

public class GoldenSectionSearch {
    public static final double invphi = (Math.sqrt(5.0) - 1) / 2.0;
    public static final double invphi2 = (3 - Math.sqrt(5.0)) / 2.0;

    public interface Function {
        double of(double x);
    }

    // Returns subinterval of [a,b] containing minimum of f

    public static double[] gss(Function f, double a, double b, double tol) {
        return gss(f, a, b, tol, b - a, true, 0, 0, true, 0, 0);
    }
    private static double[] gss(Function f, double a, double b, double tol,
                                double h, boolean noC, double c, double fc,
                                boolean noD, double d, double fd) {
        if (Math.abs(h) <= tol) {
            return new double[] { a, b };
        }
        if (noC) {
            c = a + invphi2 * h;
            fc = f.of(c);
        }
        if (noD) {
            d = a + invphi * h;
            fd = f.of(d);
        }
        if (fc < fd) {  // fc > fd to find the maximum
            return gss(f, a, d, tol, h * invphi, true, 0, 0, false, c, fc);
        } else {
            return gss(f, c, b, tol, h * invphi, false, d, fd, true, 0, 0);
        }
    }

    public static void main(String[] args) {
        Function f = (x)->Math.pow(x-2, 2);
        double a = 1;
        double b = 5;
        double tol = 1e-5;
        double [] ans = gss(f, a, b, tol);
        System.out.println("[" + ans[0] + "," + ans[1] + "]");
        // [1.9999959837979107,2.0000050911830893]
    }
}

import math


invphi = (math.sqrt(5) - 1) / 2  # 1 / phi
invphi2 = (3 - math.sqrt(5)) / 2  # 1 / phi^2


def gssrec(f, a, b, tol=1e-5, h=None, c=None, d=None, fc=None, fd=None):
    """Golden-section search, recursive.

    Given a function f with a single local minimum in
    the interval [a, b], gss returns a subset interval
    [c, d] that contains the minimum with d-c <= tol.

    Example:
    >>> f = lambda x: (x - 2) ** 2
    >>> a = 1
    >>> b = 5
    >>> tol = 1e-5
    >>> (c, d) = gssrec(f, a, b, tol)
    >>> print (c, d)
    1.9999959837979107 2.0000050911830893
    """

    (a, b) = (min(a, b), max(a, b))
    if h is None:
        h = b - a
    if h <= tol:
        return (a, b)
    if c is None:
        c = a + invphi2 * h
    if d is None:
        d = a + invphi * h
    if fc is None:
        fc = f(c)
    if fd is None:
        fd = f(d)
    if fc < fd:  # fc > fd to find the maximum
        return gssrec(f, a, d, tol, h * invphi, c=None, fc=None, d=c, fd=fc)
    else:
        return gssrec(f, c, b, tol, h * invphi, c=d, fc=fd, d=None, fd=None)

Связанные алгоритмы

Поиск Фибоначчи

Основная статья: Техника поиска Фибоначчи

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

Поиск Фибоначчи был впервые предложен Кифером (1953) как минимаксный поиск максимума (минимума) унимодальной функции на интервале.

Метод бисекции

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

См. также

• Троичный поиск
• метод Брента
• Бинарный поиск

Ссылки

• Кифер, Дж. (1953), «Последовательный минимаксный поиск максимума», Труды Американского математического общества , 4 (3): 502–506, doi : 10.2307/2032161 , JSTOR   2032161 , MR   0055639
• Авриэль, Мордехай; Уайльд, Дуглас Дж. (1966), «Доказательство оптимальности для симметричного метода поиска Фибоначчи», Fibonacci Quarterly , 4 : 265–269, MR   0208812

• Пресс, WH; Теукольский, С.А.; Феттерлинг, WT; Фланнери, BP (2007), «Раздел 10.2. Поиск золотого сечения в одном измерении» , Численные рецепты: искусство научных вычислений (3-е изд.), Нью-Йорк: Cambridge University Press, ISBN  978-0-521-88068-8 , заархивировано из оригинала 11 августа 2011 г. , получено 12 августа 2011 г.