Wyszukiwarka Line - Line search

W optymalizacji The wyszukiwania linia strategia jest jednym z dwóch podstawowych iteracyjnych podejść do znalezienia lokalnego minimum danego funkcji celu . Drugim podejściem jest regionem zaufanie . ${\ Displaystyle \ mathbf {x} ^ {*}}$ ${\ Displaystyle f: \ mathbb {R} ^ {A} \ z \ mathbb {R}}$

Podejście wyszukiwania linia pierwszy znajdzie kierunek opadania wzdłuż którego funkcja celu zostaną zmniejszone, a następnie oblicza wielkość kroku, który określa, jak daleko powinien poruszać się wzdłuż tego kierunku. Kierunek opadania w dół może być obliczany za pomocą różnych metod, takich jak metoda gradientu prostego , metoda Newtona i quasi-Newton metody . Wielkość kroku można określić dokładnie lub niedokładnie. ${\ Displaystyle f}$${\ Displaystyle \ mathbf {x}}$

Przykładowe zastosowanie

Oto przykład metodą gradientu, który wykorzystuje linię wyszukiwania w kroku 4.

1. Ustaw licznik iteracji i dokonać wstępnego odgadnięcia dla minimum${\ Displaystyle \ displaystyle k = 0}$${\ Displaystyle \ mathbf {x} _ {0}}$
2. Powtarzać:
3.     Obliczyć kierunek opadania ${\ Displaystyle \ mathbf {s} _ {k}}$
4.     Wybierz się „luźno” zminimalizować ponad${\ Displaystyle \ displaystyle \ _ a {k}}$${\ Displaystyle H (\ a) = f (\ mathbf {x} _ {k} + \ a \ mathbf {s} _ {k})}$${\ Displaystyle \ a \ w \ mathbb {R} _ {+}}$
5.     Aktualizacja i${\ Displaystyle \ mathbf {x} _ {k + 1} = \ mathbf {x} _ {k} + \ _ a {k} \ mathbf {s} _ {k}}$${\ Displaystyle \ displaystyle k = k + 1}$
6.     Aż <tolerancji${\ Displaystyle \ | \ nabla f (\ mathbf {x} _ {k}) \ |}$

Na etapie wyszukiwania linia (4) algorytm może albo dokładnie zminimalizować h , rozwiązując lub luźno , prosząc o dostatecznym spadkiem godz . Przykładem pierwszego z nich jest sposób koniugat gradientu . Ten ostatni jest nazywany niedokładne szukaj linii i może być wykonywana w wielu sposobów, takich jak poszukiwanie linii wycofywania lub stosując warunki Wolfe . ${\ Displaystyle h '(\ a _ {k}) = 0}$

Podobnie jak inne metody optymalizacji wyszukiwania linia może być łączony z symulowanego wyżarzania , aby umożliwić jej przeskoczyć pewne lokalne minima .

algorytmy

Bezpośrednie metody wyszukiwania

W tej metodzie, minimalna musi być najpierw nawias, więc algorytm musi zidentyfikować punkty x ₁ i x ₂ takie, że poszukiwane minimum leży pomiędzy nimi. Przerwa jest następnie dzielona przez przetwarzania w dwóch punktach wewnętrznych x ₃ i x ₄ i odrzucenie tego z dwóch punktów zewnętrznej nie przylega do tego z X ₃ i x ₄ , która ma najmniejszą wartość funkcji. W kolejnych etapach, tylko jeden dodatkowy punkt wewnętrzny musi być obliczona. Spośród różnych metod podzielenie przedziału, metoda złotego podziału jest szczególnie proste i skuteczne, jako przedział proporcje są zachowane, niezależnie od tego, jak przebiega wyszukiwania: ${\ Displaystyle f (x)}$

${\ Displaystyle {\ Frac {1} {\ cp}} (x_ {2} -x_ {1}) = x_ {4} -x_ {1} = x_ {2} -x_ {3} = \ cp (x_ {2} -x_ {4}) = \ cp (x_ {3} -x_ {1}) = \ cp ^ {2} (x_ {4} -x_ {3})}$ gdzie ${\ Displaystyle \ cp = {\ Frac {1} {2}} (1 + {\ sqrt {5}}) \ ok 1,618}$

Zobacz też

• szukaj linii backtracking
• metoda siecznych
• Metoda Newtona w optymalizacji
• szukaj wzór (optymalizacja)
• Sposób Neldera-Mead
• Metoda złotego podziału

Referencje