Suche im Goldenen Schnitt - Golden-section search

Diagramm einer Suche im Goldenen Schnitt. Das anfängliche Triplett von x- Werten ist {x1,x2,x3}. Falls f(x ₄ ) = f _4a , wird das Triplett {x ₁ ,x ₂ ,x ₄ } für die nächste Iteration gewählt. Falls f(x ₄ ) = f _4b , wird das Triplett {x ₂ ,x ₄ ,x ₃ } gewählt.

Die Suche im Goldenen Schnitt ist eine Technik zum Finden eines Extremums (Minimum oder Maximum) einer Funktion innerhalb eines bestimmten Intervalls. Bei einer streng unimodalen Funktion mit einem Extremum innerhalb des Intervalls wird dieses Extremum gefunden, während es bei einem Intervall mit mehreren Extrema (möglicherweise einschließlich der Intervallgrenzen) gegen eines davon konvergiert. Wenn das einzige Extremum des Intervalls an einer Grenze des Intervalls liegt, konvergiert es zu diesem Grenzpunkt. Das Verfahren arbeitet durch sukzessives Einschränken des Wertebereichs in dem angegebenen Intervall, was es relativ langsam, aber sehr robust macht. Die Technik leitet ihren Namen von der Tatsache ab, dass der Algorithmus die Funktionswerte für vier Punkte beibehält, deren drei Intervallbreiten im Verhältnis 2-φ:2φ-3:2-φ stehen, wobei φ der goldene Schnitt ist . Diese Verhältnisse werden für jede Iteration beibehalten und sind maximal effizient. Mit Ausnahme von Grenzpunkten ist bei der Suche nach einem Minimum der zentrale Punkt immer kleiner oder gleich den äußeren Punkten, wodurch sichergestellt wird, dass zwischen den äußeren Punkten ein Minimum enthalten ist. Bei der Suche nach einem Maximum gilt das Umgekehrte. Der Algorithmus ist die Grenze der Fibonacci-Suche (auch weiter unten beschrieben) für viele Funktionsauswertungen. Die Fibonacci-Suche und die Suche nach dem Goldenen Schnitt wurden von Kiefer (1953) entdeckt (siehe auch Avriel und Wilde (1966)).

Die Grundidee

Die Diskussion hier erfolgt im Hinblick auf die Suche nach einem Minimum (die Suche nach einem Maximum ist ähnlich) einer unimodalen Funktion . Im Gegensatz zum Finden einer Null, wo zwei Funktionsauswertungen mit entgegengesetztem Vorzeichen ausreichen, um eine Wurzel einzuklammern, sind bei der Suche nach einem Minimum drei Werte erforderlich. Die Suche im Goldenen Schnitt ist eine effiziente Möglichkeit, das Intervall zum Auffinden des Minimums schrittweise zu reduzieren. Der Schlüssel ist zu beachten, dass unabhängig davon, wie viele Punkte bewertet wurden, das Minimum innerhalb des Intervalls liegt, das durch die beiden Punkte neben dem Punkt mit dem bisher niedrigsten bewerteten Wert definiert wird.

Das obige Diagramm veranschaulicht einen einzelnen Schritt in der Technik zum Finden eines Minimums. Die Funktionswerte von sind auf der vertikalen Achse und die horizontale Achse ist der x- Parameter. Der Wert von wurde bereits an den drei Punkten ausgewertet: , , und . Da kleiner als entweder oder ist, liegt ein Minimum innerhalb des Intervalls von bis . $f(x)$ $f(x)$ $x_{1}$ $x_{2}$ $x_{3}$ $f_{2}$ $f_{1}$ $f_{3}$ $x_{1}$ $x_{3}$

Der nächste Schritt im Minimierungsprozess besteht darin, die Funktion zu "prüfen", indem sie bei einem neuen Wert von x ausgewertet wird , nämlich . Es ist am effizientesten, irgendwo innerhalb des größten Intervalls zu wählen , dh zwischen und . Aus dem Diagramm ist klar, dass, wenn die Funktion ergibt , ein Minimum zwischen und liegt , und das neue Triplett von Punkten ist , , und . Ergibt die Funktion jedoch den Wert , dann liegt ein Minimum zwischen und , und das neue Triplett von Punkten ist , , und . Somit können wir in jedem Fall ein neues schmaleres Suchintervall konstruieren, das garantiert das Minimum der Funktion enthält. $x_{4}$ $x_{4}$ $x_{2}$ $x_{3}$ $f_{4a}$ $x_{1}$ $x_{4}$ $x_{1}$ $x_{2}$ $x_{4}$ $f_{4b}$ $x_{2}$ $x_{3}$ $x_{2}$ $x_{4}$ $x_{3}$

Auswahl der Sondenpunkte

Aus dem obigen Diagramm ist ersichtlich, dass das neue Suchintervall entweder zwischen und mit einer Länge von a + c oder zwischen und mit einer Länge von b liegt . Die Suche nach dem Goldenen Schnitt erfordert, dass diese Intervalle gleich sind. Wenn dies nicht der Fall ist, könnte eine Reihe von "Pech" dazu führen, dass das breitere Intervall viele Male verwendet wird, wodurch die Konvergenzrate verlangsamt wird. Um sicherzustellen, dass b = a + c , sollte der Algorithmus wählen . $x_{1}$ $x_{4}$ $x_{2}$ $x_{3}$ $x_{4}=x_{1}+(x_{3}-x_{2})$

Es bleibt jedoch die Frage, wo in Bezug auf und einzuordnen ist . Die Suche im Goldenen Schnitt wählt den Abstand zwischen diesen Punkten so, dass diese Punkte den gleichen Abstandsanteil haben wie das nachfolgende Tripel oder . Durch Beibehalten des gleichen Abstandsanteils im gesamten Algorithmus vermeiden wir eine Situation, die sehr nahe an oder liegt, und garantieren, dass die Intervallbreite in jedem Schritt um den gleichen konstanten Anteil schrumpft. $x_{2}$ $x_{1}$ $x_{3}$ $x_{1},x_{2},x_{4}$ $x_{2},x_{4},x_{3}$ $x_{2}$ $x_{1}$ $x_{3}$

Um mathematisch sicherzustellen, dass der Abstand nach der Auswertung proportional zum Abstand vor dieser Auswertung ist, wenn ist und unser neues Punkttripel ist , , und , dann wollen wir $f(x_{4})$ $f(x_{4})$ $f_{4a}$ $x_{1}$ $x_{2}$ $x_{4}$

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

Wenn es jedoch ist und unser neues Punktetriplett ist , , und , dann wollen wir $f(x_{4})$ $f_{4b}$ $x_{2}$ $x_{4}$ $x_{3}$

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

Eliminieren von c aus diesen beiden simultanen Gleichungen ergibt

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

oder

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

wobei φ der Goldene Schnitt ist :

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

Das Erscheinen des Goldenen Schnitts im proportionalen Abstand der Bewertungspunkte gibt diesem Suchalgorithmus seinen Namen.

Kündigungsbedingung

Je nach Anwendung können beliebig viele Kündigungsbedingungen angewendet werden. Das Intervall ΔX = X ₄ − X ₁ ist ein Maß für den absoluten Fehler bei der Schätzung des Minimums X und kann verwendet werden, um den Algorithmus zu beenden. Der Wert von ΔX wird für jede Iteration um den Faktor r = φ − 1 reduziert , sodass die Anzahl der Iterationen zum Erreichen eines absoluten Fehlers von ΔX ungefähr ln(ΔX/ΔX _o ) / ln(r) beträgt, wobei ΔX _o der Anfangswert von ΔX .

Da glatte Funktionen in der Nähe eines Minimums flach sind (ihre erste Ableitung ist nahe Null), muss darauf geachtet werden, keine zu große Genauigkeit bei der Lokalisierung des Minimums zu erwarten. Die Abbruchbedingung im Buch Numerical Recipes in C basiert auf dem Testen der Lücken zwischen , , und , und endet innerhalb der relativen Genauigkeitsgrenzen $x_{1}$ $x_{2}$ $x_{3}$ $x_{4}$

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

Dabei ist ein Toleranzparameter des Algorithmus und der Absolutwert von . Die Prüfung basiert auf der Klammergröße relativ zu ihrem Mittelwert, da dieser relative Fehler in typischen Fällen ungefähr proportional zum quadrierten absoluten Fehler ist. Aus dem gleichen Grund empfiehlt der Text Numerical Recipes, dass , wo die erforderliche absolute Genauigkeit von ist . $\tau$ $|x|$ $x$ $x$ $f(x)$ $\tau ={\sqrt {\varepsilon}}$ ${\displaystyle\varepsilon}$ $f(x)$

Algorithmus

Iterativer Algorithmus

Diagramm der Suche im Goldenen Schnitt nach einem Minimum. Das von X ₁ und X ₄ eingeschlossene Anfangsintervall wird in drei Intervalle unterteilt, und f[X] wird bei jedem der vier X _i ausgewertet . Die zwei Intervalle, die das Minimum von f(X _i ) enthalten, werden dann ausgewählt, und ein drittes Intervall und ein Funktionswert werden berechnet, und der Vorgang wird wiederholt, bis die Beendigungsbedingungen erfüllt sind. Die drei Intervallbreiten stehen immer im Verhältnis c:cr:c mit r = φ − 1=0,619... und c = 1 − r = 0,381... , wobei φ der Goldene Schnitt ist . Diese Wahl der Intervallverhältnisse ist die einzige, die es ermöglicht, die Verhältnisse während einer Iteration beizubehalten.

Geben Sie die zu minimierende Funktion f(x), das zu durchsuchende Intervall als {X ₁ ,X ₄ } und ihre Funktionswerte F ₁ und F _{4 an} .
Berechnen Sie einen inneren Punkt und seinen Funktionswert F ₂ . Die beiden Intervalllängen stehen im Verhältnis c : r bzw. r : c mit r = φ − 1; und c = 1 − r , wobei φ der Goldene Schnitt ist.
Bestimmen Sie mit dem Triplett, ob die Konvergenzkriterien erfüllt sind. Wenn dies der Fall ist, schätzen Sie das Minimum von X aus diesem Triplett und kehren Sie zurück.
Berechnen Sie aus dem Triplett den anderen inneren Punkt und seinen funktionalen Wert. Die drei Intervalle stehen im Verhältnis c:cr:c .
Die drei Punkte für die nächste Iteration sind derjenige, bei dem F ein Minimum ist, und die beiden Punkte, die ihm in X am nächsten sind.
Gehen Sie zu Schritt 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

gr = (math.sqrt(5) + 1) / 2

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

    Example:
    >>> f = lambda x: (x-2)**2
    >>> x = gss(f, 1, 5)
    >>> print("%.15f" % x)
    2.000009644875678

    """
    c = b - (b - a) / gr
    d = a + (b - a) / gr
    while abs(b - a) > tol:
        if f(c) < f(d):
            b = d
        else:
            a = c

        # We recompute both c and d here to avoid loss of precision which may lead to incorrect results or infinite loop
        c = b - (b - a) / gr
        d = a + (b - a) / gr

    return (b + a) / 2

"""Python program for golden section search.  This implementation
   reuses function evaluations, saving 1/2 of the evaluations per
   iteration, and returns a bounding interval."""
import math


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

def gss(f, a, b, tol=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 <= tol.

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

    (a, b) = (min(a, b), max(a, b))
    h = b - a
    if h <= tol:
        return (a, b)

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

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

    for k in range(n-1):
        if yc < yd:
            b = d
            d = c
            yd = yc
            h = invphi * h
            c = a + invphi2 * h
            yc = f(c)
        else:
            a = c
            c = d
            yc = yd
            h = invphi * h
            d = a + invphi * h
            yd = f(d)

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

Rekursiver Algorithmus

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) {
            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:
        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)

Fibonacci-Suche

Ein sehr ähnlicher Algorithmus kann auch verwendet werden, um das Extremum (Minimum oder Maximum) einer Folge von Werten zu finden, die ein einzelnes lokales Minimum oder lokales Maximum hat. Um die Sondenpositionen der Suche im Goldenen Schnitt anzunähern, während nur ganzzahlige Sequenzindizes untersucht werden, behält die Variante des Algorithmus für diesen Fall typischerweise eine Klammerung der Lösung bei, bei der die Länge des eingeklammerten Intervalls eine Fibonacci-Zahl ist . Aus diesem Grund wird die Sequenzvariante der Suche im Goldenen Schnitt oft als Fibonacci-Suche bezeichnet .

Die Fibonacci-Suche wurde zuerst von Kiefer (1953) als Minimax- Suche für das Maximum (Minimum) einer unimodalen Funktion in einem Intervall entwickelt.

Siehe auch

Verweise

Kiefer, J. (1953), "Sequential minimax search for a maximum", Proceedings of the American Mathematical Society , 4 (3): 502–506, doi : 10.2307/2032161 , JSTOR 2032161 , MR 0055639
Avriel, Mordechai; Wilde, Douglass J. (1966), „Optimalitätsbeweis für die symmetrische Fibonacci-Suchtechnik“, Fibonacci Quarterly , 4 : 265–269, MR 0208812

Drücken Sie, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), "Section 10.2. Golden Section Search in One Dimension" , Numerical Recipes: The Art of Scientific Computing (3. Aufl.), New York: Cambridge University Press, ISBN 978-0-521-88068-8

Languages

In other projects