Поиск золотого сечения - Golden-section search

Схема поиска золотого сечения. Начальная тройка Икс значения: {x1, x2, x3}. Если f (x₄) = f_4а, тройка {x₁,Икс₂,Икс₄} выбирается для следующей итерации. Если f (x₄) = f_4b, тройка {x₂,Икс₄,Икс₃} выбран.

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

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

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

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

Следующим шагом в процессе минимизации является "зондирование" функции путем оценки ее нового значения Икс, а именно ${ displaystyle x_ {4}}$ . Оптимальнее всего выбрать ${ displaystyle x_ {4}}$ где-то внутри самого большого интервала, т.е. между ${ displaystyle x_ {2}}$ и ${ displaystyle x_ {3}}$ . Из диаграммы видно, что если функция дает ${ displaystyle f_ {4a}}$ , то минимум лежит между ${ displaystyle x_ {1}}$ и ${ displaystyle x_ {4}}$ , а новая тройка очков будет ${ displaystyle x_ {1}}$ , ${ displaystyle x_ {2}}$ , и ${ displaystyle x_ {4}}$ . Однако, если функция возвращает значение ${ displaystyle f_ {4b}}$ , то минимум лежит между ${ displaystyle x_ {2}}$ и ${ displaystyle x_ {3}}$ , а новая тройка очков будет ${ displaystyle x_ {2}}$ , ${ displaystyle x_ {4}}$ , и ${ displaystyle x_ {3}}$ . Таким образом, в любом случае мы можем построить новый более узкий интервал поиска, который гарантированно будет содержать минимум функции.

Выбор точки зонда

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

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

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

{ displaystyle { frac {c} {a}} = { frac {a} {b}}.}

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

{ displaystyle { frac {c} {b-c}} = { frac {a} {b}}.}

Устранение c из этих двух одновременных уравнений дает

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

или же

{ displaystyle { frac {b} {a}} = varphi,}

где φ - Золотое сечение:

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

Появление золотого сечения в пропорциональном интервале точек оценки - вот как этот поиск алгоритм получает свое название.

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

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

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

{ displaystyle | x_ {3} -x_ {1} | < tau (| x_ {2} | + | x_ {4} |),}

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

Алгоритм

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

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

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

"" "Программа на Python для поиска золотого сечения. Эта реализация   не использует повторно оценки функций и предполагает минимум c   или d (не на краях a или b) "" "импорт математикагр = (математика.sqrt(5) + 1) / 2def gss(ж, а, б, тол=1e-5):    "" "Поиск по золотому сечению    найти минимум f на [a, b]    f: строго унимодальная функция на [a, b]    Пример:    >>> f = лямбда x: (x-2) ** 2    >>> х = gss (f, 1, 5)    >>> print ("%. 15f"% x)    2.000009644875678    """    c = б - (б - а) / гр    d = а + (б - а) / гр    пока пресс(б - а) > тол:        если ж(c) < ж(d):            б = d        еще:            а = c        # Мы пересчитываем здесь c и d, чтобы избежать потери точности, которая может привести к неверным результатам или бесконечному циклу        c = б - (б - а) / гр        d = а + (б - а) / гр    возвращаться (б + а) / 2

"" "Программа на Python для поиска золотого сечения. Эта реализация   повторно использует оценки функций, экономя 1/2 оценок на   итерация и возвращает ограничивающий интервал. "" "импорт математикаinvphi = (математика.sqrt(5) - 1) / 2  # 1 / фиinvphi2 = (3 - математика.sqrt(5)) / 2  # 1 / фи ^ 2def gss(ж, а, б, тол=1e-5):    "" "Поиск по золотому сечению.    Для функции f с единственным локальным минимумом в    интервал [a, b], gss возвращает интервал подмножества    [c, d], который содержит минимум с d-c <= tol.    Пример:    >>> f = лямбда x: (x-2) ** 2    >>> а = 1    >>> b = 5    >>> тол = 1э-5    >>> (c, d) = gss (f, a, b, tol)    >>> print (c, d)    1.9999959837979107 2.0000050911830893    """    (а, б) = (мин(а, б), Максимум(а, б))    час = б - а    если час <= тол:        возвращаться (а, б)    # Необходимые шаги для достижения толерантности    п = int(математика.потолок(математика.бревно(тол / час) / математика.бревно(invphi)))    c = а + invphi2 * час    d = а + invphi * час    yc = ж(c)    ярд = ж(d)    за k в классифицировать(п-1):        если yc < ярд:            б = d            d = c            ярд = yc            час = invphi * час            c = а + invphi2 * час            yc = ж(c)        еще:            а = c            c = d            yc = ярд            час = invphi * час            d = а + invphi * час            ярд = ж(d)    если yc < ярд:        возвращаться (а, d)    еще:        возвращаться (c, б)

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

общественный учебный класс GoldenSectionSearch {    общественный статический окончательный двойной invphi = (Математика.sqrt(5.0) - 1) / 2.0;    общественный статический окончательный двойной invphi2 = (3 - Математика.sqrt(5.0)) / 2.0;    общественный интерфейс Функция {        двойной из(двойной Икс);    }    // Возвращает подынтервал [a, b], содержащий минимум f    общественный статический двойной[] gss(Функция ж, двойной а, двойной б, двойной тол) {        возвращаться gss(ж, а, б, тол, б - а, истинный, 0, 0, истинный, 0, 0);    }    частный статический двойной[] gss(Функция ж, двойной а, двойной б, двойной тол,                                двойной час, логический noC, двойной c, двойной fc,                                логический кивок, двойной d, двойной fd) {        если (Математика.пресс(час) <= тол) {            возвращаться новый двойной[] { а, б };        }        если (noC) {            c = а + invphi2 * час;            fc = ж.из(c);        }        если (кивок) {            d = а + invphi * час;            fd = ж.из(d);        }        если (fc < fd) {            возвращаться gss(ж, а, d, тол, час * invphi, истинный, 0, 0, ложный, c, fc);        } еще {            возвращаться gss(ж, c, б, тол, час * invphi, ложный, d, fd, истинный, 0, 0);        }    }    общественный статический пустота главный(Нить[] аргументы) {        Функция ж = (Икс)->Математика.пау(Икс-2, 2);        двойной а = 1;        двойной б = 5;        двойной тол = 1e-5;        двойной [] ответ = gss(ж, а, б, тол);        Система.из.println("[" + ответ[0] + "," + ответ[1] + "]");        // [1.9999959837979107,2.0000050911830893]    }}

импорт математикаinvphi = (математика.sqrt(5) - 1) / 2  # 1 / фиinvphi2 = (3 - математика.sqrt(5)) / 2  # 1 / фи ^ 2def gssrec(ж, а, б, тол=1e-5, час=Никто, c=Никто, d=Никто, fc=Никто, fd=Никто):    "" "Поиск золотого сечения, рекурсивный.    Для функции f с одним локальным минимумом в    интервал [a, b], gss возвращает интервал подмножества    [c, d], который содержит минимум с d-c <= tol.    Пример:    >>> f = лямбда x: (x-2) ** 2    >>> а = 1    >>> b = 5    >>> тол = 1э-5    >>> (c, d) = gssrec (f, a, b, tol)    >>> print (c, d)    1.9999959837979107 2.0000050911830893    """    (а, б) = (мин(а, б), Максимум(а, б))    если час является Никто: час = б - а    если час <= тол: возвращаться (а, б)    если c является Никто: c = а + invphi2 * час    если d является Никто: d = а + invphi * час    если fc является Никто: fc = ж(c)    если fd является Никто: fd = ж(d)    если fc < fd:        возвращаться gssrec(ж, а, d, тол, час * invphi, c=Никто, fc=Никто, d=c, fd=fc)    еще:        возвращаться gssrec(ж, c, б, тол, час * invphi, c=d, fc=fd, d=Никто, fd=Никто)

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

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

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