Warunki Wolfe'a - Wolfe conditions

W zagadnieniu minimalizacji nieograniczonej warunki Wolfe'a są zbiorem nierówności do wykonania niedokładnego wyszukiwania liniowego , szczególnie w metodach quasi-Newtona , opublikowanych po raz pierwszy przez Philipa Wolfe'a w 1969 roku.

W tych metodach chodzi o to, aby znaleźć

dla niektórych sprawne . Każdy krok często obejmuje przybliżone rozwiązanie podproblemu

gdzie jest aktualnym najlepszym przypuszczeniem, jest kierunkiem wyszukiwania i jest długością kroku.

Niedokładne wyszukiwanie wierszy zapewnia wydajny sposób obliczania dopuszczalnej długości kroku, który „w wystarczającym stopniu” redukuje funkcję celu , a nie dokładnie minimalizuje funkcję celu . Algorytm wyszukiwania wierszy może użyć warunków Wolfe'a jako wymagania dla każdego zgadywanego przed znalezieniem nowego kierunku wyszukiwania .

Zasada Armijo i krzywizna

Mówi się, że długość kroku spełnia warunki Wolfe'a , ograniczone do kierunku , jeśli następujące nierówności są spełnione:

z . (Badając warunek (ii), przypomnij sobie, że aby upewnić się, że jest to kierunek opadania, mamy , jak w przypadku gradientu , gdzie , lub Newtona-Raphsona , gdzie z dodatnim określonym.)

jest zwykle wybierany jako dość mały, podczas gdy jest znacznie większy; Nocedal i Wright podają przykładowe wartości i dla metod Newtona lub quasi-Newtona oraz dla nieliniowej metody gradientu sprzężonego . Nierówność i) jest znana jako reguła Armijo oraz ii) jako warunek krzywizny ; i) zapewnia, że ​​długość stopnia zmniejsza się „wystarczająco”, oraz ii) zapewnia, że ​​nachylenie zostało odpowiednio zmniejszone. Warunki i) i ii) mogą być interpretowane jako zapewniające odpowiednio górną i dolną granicę dopuszczalnych wartości długości kroku.

Silny warunek Wolfe'a na krzywiźnie

Oznaczają funkcję jednowymiarową ograniczoną do kierunku jako . Warunki Wolfe'a mogą skutkować wartością długości kroku, która nie jest bliska minimalizacji . Jeśli zmodyfikujemy warunek krzywizny na następujący,

a następnie i) i iii) tworzą razem tak zwanych warunkach silnie Wolfe i siły leżeć blisko punktu krytycznego w .

Racjonalne uzasadnienie

Głównym powodem nałożenia warunków Wolfe'a w algorytmie optymalizacji jest zapewnienie zbieżności gradientu do zera. W szczególności, jeśli cosinus kąta między a gradientem,

jest ograniczony od zera i spełnione są warunki i) i ii), wtedy .

Dodatkową motywacją w przypadku metody quasi-Newtona jest to, że jeśli , gdy macierz jest aktualizowana wzorem BFGS lub DFP , to jeśli jest dodatnio określona ii) implikuje również dodatnio określona.

Uwagi

Chociaż warunki Wolfe'a są bardziej skomplikowane niż warunek Armijo, od teraz algorytm oparty na warunku Armijo (tj. Gradient z wycofywaniem) ma lepszą gwarancję teoretyczną, zobacz sekcje "Górna granica szybkości uczenia się" i "Gwarancja teoretyczna" w wyszukiwaniu linii z cofaniem .

Zobacz też

Bibliografia

Dalsza lektura