Podręcznik

Poruszymy teraz trzy najważniejsze problemy implementacyjne gradientowych algorytmów optymalizacji: 

Pierwszy jest związany z wykonaniem podstawowego polecenia z początku każdego algorytmu punktu 4.2: „oblicz $∇f (x)$”. Od tego jak dokładnie wyliczymy gradient bardzo istotnie zależy jakość otrzymanej propozycji rozwiązania zadania minimalizacji.

Dwa pozostałe zasygnalizowano na początku punktu 3.2.1: jak ustalić kryterium stopu i jak będąc odważnym zachować rozwagę.

Jeżeli znamy wzór określający funkcję f możemy wyznaczyć wzór określający gradient, chociaż dla bardziej złożonych funkcji może być to kłopotliwe. Wyznaczony wzór trzeba wstawić w odpowiednie miejsce algorytmu. Gdy dysponujemy odpowiednim oprogramowaniem, komputer może nas zwolnić z niewdzięcznej pracy i wyznaczyć stosowny wzór na gradient drogą różniczkowania symbolicznego. Przy rozwiązywaniu zadań praktycznych często mamy do czynienia z sytuacją, w której funkcja f jest obliczana przez dany z zewnątrz program. Jeżeli ten program do wyznaczenia wartości funkcji dla danego argumentu wykorzystuje cztery działania arytmetyczne i funkcje elementarne , to na podstawie jego kodu drogą automatycznego różniczkowania można otrzymać program obliczający wartość gradientu funkcji. Przystępne wprowadzenie do zagadnień związanych z  automatycznym  różniczkowaniem  Czytelnik znajdzie w rozdziale 7.2 monografii J. Nocedal S.J. Wright: Numerical Optimization, 2nd ed. Springer 1999. 

Co robić w sytuacji gdy nie mamy programu automatycznego różniczkowania przetwarzającego kod języka, którym posłużono się do napisania programu wyliczającego wartości funkcji celu? Zostaje nam estymacja gradientu. Estymacja gradientu funkcji celu f w punkcie bieżącym $x^ {(k)}$ polega na obliczeniu wartości tej funkcji w pewnej liczbie punktów próbnych $y^{(j)},j∈\overline{1,J}$ leżących w otoczeniu punktu bieżącego. Poszczególne elementy estymaty gradientu funkcji f wyznaczane są na podstawie różnic jej wartości w tych punktach. Stosowane metody estymacji różnią się liczbą i sposobem ustalenia punktów próbnych. Jedna z najprostszych metod, to metoda różnic centralnych, w której przyjmuje się następujące przybliżenie

$\dfrac{∂}{(∂x_i )}f(x^ {(k)})≈\dfrac{f(x^ {(k)}+Δx_i e^i)-f(x^ {(k)}-Δx_i e^i)}{2Δx_i }, \,i=1,...,n$

gdzie wektory $e^1,…,e^n$ są naturalną bazą przestrzeni $\mathbb{R}^n$, a $Δx_i$– przyrostami kolejnych współrzędnych. Jak widać w tej metodzie estymatę gradientu obliczamy na podstawie wartości funkcji w dwu punktach próbnych. Zauważmy, że stosowny wybór wielkości przyrostów $Δx_i$może być trudny dla funkcji wolno zmieniających się, ponieważ małym przyrostom mogą odpowiadać zmiany funkcji celu porównywalne lub mniejsze od dokładności reprezentacji liczb w komputerze, co może doprowadzić do przedwczesnego uznania, że dana współrzędna gradientu jest zerowa. W konsekwencji obliczona norma gradientu zostanie uznana za dostatecznie małą i, zgodnie z zastosowanym kryterium stopu, algorytm przedwcześnie zatrzyma się. W związku z tym twórcy komercyjnych pakietów rozwiązywania zadań optymalizacji wyposażają swoje produktu w specjalne algorytmy wyznaczania wielkości przyrostów.

W przedstawionych wersjach algorytmów jako kryterium stopu wybrano „zerowanie” się normy gradientu, co w praktyce oznacza wybór dokładności $\varepsilon$równej co najmniej 10–4 i zatrzymanie działania algorytmu gdy

$||∇f(x^ {(k)})||$

Oznacza to, że najczęściej stosowane algorytmy gradientowe rozwiązują zadanie optymalizacji bez ograniczeń stosując metodę redukcji do układu równań 

$∇f(x)=0, \qquad (3.1)$

opisaną ogólnie w punkcie 3.1.1., z dodatkowymi warunkami ograniczającymi, aby nie doszło do znalezienia punktów siodłowych albo wielowymiarowych powierzchni przegięcia takich jak na Rys. 3.26. Ze złożoności tego problemu nieliniowego z którymi spotkaliśmy się w punkcie 3.1.1. i powrócimy do nich przy bardziej skompli-kowanych warunkach w punkcie 5.2. Modułu piątego wynika, że jak napisali J.E Dennis i R.B. Schnabel na początku swej klasycznej monografii Numerical Methods for Unconstrained Optimization and nonlinear Equations z 1983 r.

Pozostałe proponowane w rożnym czasie kryteria: 

• małości relatywnego przyrostu kroku:  $\dfrac{||x^ {(k+1)}-x^ {(k)} ||}{||x^ {(k)} ||}$  albo
• braku dostatecznego postępu w ciągu N kroków
  w przestrzeni argumentów: $||x^ {(k+N)}-x^ {(k)} ||$, albo

  w przestrzeni wartości: $|f(x^ {(k+N)})-f(x^ {(k)})|$

stosowane są rzadko, ponieważ praktyka pokazała, że często zawodzą powodując zatrzymanie algorytmu daleko od rozwiązania. Omawiając wybór kryterium stopu trzeba także przypomnieć wymaganie, na które zwracaliśmy już uwagę, tj. wymaganie mówiące, że praktyczna implementacja każdego algorytmu powinna zawierać zabezpieczenie przed wynikającą z nałożenia się różnych niedokładności, możliwością jego „zapętlenia się”, w postaci warunku przerwania obliczeń po wykonaniu maksymalnej liczby iteracji.

W przedstawionych metodach gradientowych odpowiedzi na pytanie „jak będąc odważnym zachować rozwagę?” udzielono odpowiedzi poprzez wykorzystanie narzędzia odnowy pamięci, która buduje rozwagę lecz z biegiem czasu może hamować śmiałe działania.

W obu metodach zastosowano „sztywny program odnowy”, co n kroków w metodzie gradientu sprzężonego, i co $2n + 1$ kroków w przedstawionej metodzie quasi-newtonowskiej przy czym n to liczność zmiennych zadania. Obie liczby wyniknęły z doświadczenia i przy rozwiązywaniu konkretnego zadania optymalizacji mogą być zmienione. Dlaczego pierwsza liczba jest mniejsza? Patrząc na rys. 4.16 widzimy, że algorytm BFGS jest lepszy od algorytmu gradientu sprzężonego. Dlatego dla niewielkich (do mniej więcej 10 zmiennych) zadań optymalizacji zaleca się jego stosowanie. Dla zadań dużych – kilkadziesiąt i więcej zmiennych stosowanie algorytmu quasi-newtonowskiego może być kłopotliwe, ponieważ trzeba pamiętać macierz transformacji D. Wobec tego do rozwiązywania dużych zadań częściej stosuje się metodę gradientu sprzężonego. Widać więc, że n dla zadania dużego może być dużo większe niż $2n + 1$ dla zadania małego i nie ma niebezpieczeństwa, że działanie algorytmu gradientu sprzężonego stanie się podobne do działania nieefektywnego algorytmu największego spadku.