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
- „Metody wyszukiwania linii”. Optymalizacja numeryczna . Seria Springer w badaniach operacyjnych i inżynierii finansowej. 2006. s. 30-32. doi : 10.1007/978-0-387-40065-5_3 . Numer ISBN 978-0-387-30303-1.
- „Metody Quasi-Newtona”. Optymalizacja numeryczna . Seria Springer w badaniach operacyjnych i inżynierii finansowej. 2006. s. 135-163. doi : 10.1007/978-0-387-40065-5_6 . Numer ISBN 978-0-387-30303-1.