Zamieszanie na temat reguły Armijo

Mam zamieszanie w związku z regułą Armijo używaną do wyszukiwania linii. Czytałem wyszukiwanie linii śledzenia wstecz, ale nie zrozumiałem, o co chodzi w tej regule Armijo. Czy ktoś może wyjaśnić, czym jest zasada Armijo? Wikipedia wydaje się nie wyjaśniać dobrze. Dzięki

optimization

— użytkownik34790
źródło

Co jeśli w równaniu zmienna x nie jest wektorem, ale macierzą? Jak należy zaktualizować regułę Armijo?

— Frank Puk

nic się nie zmienia. powinieneś po prostu przekształcić swoją X_k w wektor (kolumnowy) .

X_{k}

$X_k$

x_{k}

$x_k$

— GoHokies

Tam utknąłem. Kiedy staje się macierzą, wartość po lewej stronie ( ) jest nadal skalarem. Ale wartość po prawej stronie nie jest - zamiast tego jest to macierz ( jest skalarem, a jest macierzą.)

x_{k}

$x_k$

f (x_{k} + α p_{k})

$f(x_k+\alpha p_k)$

f (x_{k})

$f(x_k)$

β α \nabla f (x_{k})^{T} p_{k}

$\beta\alpha∇f(x_k)^Tp_k$

— Frank Puk

będziesz musiał pracować z wektorem, a nie z macierzą. więc przekształcasz swoją macierz zmiennych kontrolnych ( to przez ) w wektor z elementami. Kierunek wyszukiwania i gradient będą również wektorami z elementami . w ten sposób zarówno RHS, jak i LHS stanu Armijo są skalarami i można je porównać.

N \times N

$N \times N$

X_{k}

$X_k$

x_{k}

$x_k$

N^{2}

$N^2$

N^{2}

$N^2$

— GoHokies

Po uzyskaniu kierunku opadania dla funkcji celu należy wybrać „dobrą” długość kroku. Nie chcesz robić kroku, który jest zbyt duży, aby funkcja w nowym punkcie była większa niż bieżąca. Jednocześnie nie chcesz, aby twój krok był zbyt mały, aby zbieganie trwało wieczność. $p$ $f(x)$

Stan Armijo zasadniczo sugeruje, że „dobra” długość kroku jest taka, że masz „wystarczające zmniejszenie” w nowym punkcie. Warunek jest matematycznie określony jako gdzie jest kierunkiem opadania przy i . $f$

f (x_{k} + α p_{k}) \leq f (x_{k}) + β α \nabla f (x_{k})^{T} p_{k}

$f(x_k+\alpha p_k)\leq f(x_k)+\beta\alpha\nabla f(x_k)^Tp_k$

p_{k}

$p_k$

x_{k}

$x_k$

β \in (0, 1)

$\beta\in(0,1)$

Intuicja tego polega na tym, że wartość funkcji w nowym punkcie powinna znajdować się pod zmniejszoną „linią styczną” w punkcie w kierunku . Zobacz książkę Nocedal & Wright „Optymalizacja numeryczna”. W rozdziale 3 znajduje się doskonały graficzny opis stanu wystarczającego zmniejszenia armijo. $f(x_k+\alpha p_k)$ $x_k$ $p_k$

— Paweł
źródło

Zamiast myśleć o nim jako o linii stycznej, można go również traktować jako rozszerzenie Taylora pierwszego rzędu. W tym przypadku jedynie zapewnia, że istnieje taki krok .

β

$\beta$

α

$\alpha$

— cjordan1

Powodem, dla którego to ma znaczenie, tj. Dlaczego potrzebny jest „dobry” krok, jest to, że wiele schematów optymalizacji będzie zbiegać się wolniej, jak mówi Paul, lub może wcale się nie zbiegać. Tak więc przeszukiwania linii - które występują w kilku odmianach, Armijo jest po prostu najbardziej popularny - można użyć do nadania algorytmom bardziej niezawodnych właściwości konwergencji.

— cjordan1

Paul: twoje wyjaśnienie jest niepełne. Sama ta nierówność nie gwarantuje „wystarczającego” spadku. W rzeczywistości możesz mieć wartość alfa = 0 i nadal spełnia nierówności, które napisałeś. Ważną cechą reguły Armijo jest ograniczenie wielkości kroku od zera, co wynika z innej nierówności: f (gamma * x_new) -f (x_old)> beta * (gamma * x_new-x_old) ^ T * grad (f (x_old))

Po przeczytaniu tej dyskusji wciąż jestem zdezorientowany zasadą Armijo. Rozważmy , oraz (najbardziej stromy kierunek zniżania). Wybór która minimalizuje to . Jeśli jednak , to . Zatem reguła Armijo nie jest spełniona przy faktycznym minimum dla tego wyboru . W szczególności, jeśli masz wyszukiwanie liniowe, które iteracyjnie szuka lokalnego minimum, może skończyć się w nieskończoną pętlę. Czy coś brakuje?

f (x) = x^{2}

$f(x) = x^2$

x_{k} = - 1

$x_k = -1$

p_{k} = - 2

$p_k = -2$

α

$\alpha$

f (x_{k} + α p_{k})

$f(x_k + \alpha p_k)$

α = 1 / 2

$\alpha = 1/2$

β > 1 / 2

$\beta > 1/2$

f (x_{k} + 1 / 2 p_{k}) = 0 > 1 - 2 β = f (x_{k}) + β α f^{'} (x_{k}) p_{k}

$f(x_k + 1/2 p_k) = 0 > 1 - 2 \beta = f(x_k) + \beta \alpha f'(x_k) p_k$

β

$\beta$

— Joris Bierkens

Aby dodać do mojego powyższego komentarza, możesz powiedzieć, że jest zdecydowanie za duże (Nocedal, Wright wspomina o powszechnym wyborze ), ale z drugiej strony, na dowolny wybór możesz zbudować przykład jak wyżej.

β > 1 / 2

$\beta > 1/2$

β = 10^{- 4}

$\beta = 10^{-4}$

β

$\beta$

— Joris Bierkens,

Pięć lat później to pytanie jest nadal aktualne.

Tutaj (strony 16 i 17) można znaleźć świetne wyjaśnienie, w tym algorytm.

— Bojan Hrnkas
źródło