Metoda gradientu prostego

Metoda gradientu prostego (ang. Gradient descent) – algorytm iteracyjny mający na celu znalezienie minimum lokalnego funkcji wielu zmiennych rzeczywistych o wartościach w zbiorze liczb rzeczywistych; zasadniczym elementem algorytmu jest obliczanie gradientu funkcji w punkcie startowym oraz w kolejnych punktach i przemieszczanie się w kierunku przeciwnym do wektora gradientu funkcji. To, które minimum lokalne zostanie znalezione, zależy od przyjętego punktu startowego algorytmu. Obliczanie gradientu wymaga, by funkcja była różniczkowalna. Problem znajdowania minimum funkcji występuje jako podstawowe zagadnienie problemów optymalizacji. Wtedy funkcją, dla której szuka się minimum, jest tzw. funkcji straty / funkcja kosztu.

Metoda gradientu prostego jest jedną z prostszych metod optymalizacyjnych. Rozszerzenie tej metody — tzw. metoda stochastycznego spadku gradientu — znajduje zastosowanie m. in. w uczeniu większości sieci neuronowych, w ramach tzw. metody propagacji wstecznej (backpropagation).

Sformułowanie metody spadku gradientowego jest zazwyczaj przypisywane Augustinowi-Louisowi Cauchy’emu, który jako pierwszy zasugerował ją w 1847 roku^[1]. Jacques Hadamard niezależnie zaproponował podobną metodę w 1907 roku^[2][3]. Problem zbieżności metody dla nieliniowych problemów optymalizacyjnych został po raz pierwszy zbadany przez Haskella Curry’ego w 1944 roku^[4], a metoda była coraz intensywniej badana i stosowana w kolejnych dekadach^[5].

Termin „gradient prosty” w polskiej literaturze matematycznej oznacza bazowy, klasyczny gradient i odróżnia go od bardziej złożonych metod (np. Newtona czy quasi-Newtona). Nie jest dosłownym tłumaczeniem angielskiego „Gradient descent”.

Słowo „prosty” nie odnosi się do łatwości doboru współczynnika kroku ${\displaystyle \alpha }$ w kolejnych iteracjach; w najprostszej wersji metoda używa stałej wartości ${\displaystyle \alpha }$. W wariantach bardziej zaawansowanych ${\displaystyle \alpha }$ dobiera się w każdej iteracji, aby zwiększyć szybkość i skuteczność znalezienia minimum. W szczególności w metodzie gradientu prostego z maksymalnym spadkiem w każdym kroku (ang. maximal line search) znajduje się taką wartość ${\displaystyle \alpha }$, aby przemieszczając się wzdłuż gradientu wybrać punkt, w którym funkcja maksymalnie obniża się.

Reasumując, w metodzie gradientu prostego mamy

• krok w każdej iteracji jest skierowany przeciwnie do gradientu funkcji, wystawionego w aktualnym punkcie ${\displaystyle x_{k}}$, tj. wzdłuż wektora ${\displaystyle -\nabla f(\mathbf {x_{k}} )}$
• nowy punkt oblicza się ze wzoru ${\displaystyle \mathbf {x_{k+1}} =\mathbf {x_{k}} -\alpha _{k}\nabla f(\mathbf {x_{k}} )}$, gdzie ${\displaystyle \alpha _{k}}$ - współczynnik, który można dobrać w każdym kroku indywidualnie
• metoda stałego współczynnika: w najprostszym przypadku ustala się jako stałą wartość dla całej iteracji ${\displaystyle \alpha _{k}=\alpha }$
• metoda maksymalnego spadku (ang. maximal line search) - to najbardziej optymalna metoda, gdzie ${\displaystyle \alpha }$ dobiera się tak, by w nowym punkcie ${\displaystyle \mathbf {x_{k+1}} }$ wartość funkcji była możliwie najmniejsza: ${\displaystyle \alpha _{k}=\arg \min _{\eta >0}f(\mathbf {x_{k}} -\alpha \nabla f(\mathbf {x_{k}} ))}$; każdy ruch jest maksymalnie efektywny, co przyspiesza zbieżność (szczególnie istotne dla funkcji kwadratowych lub o wydłużonych dolinach).
• w innych wariantach stosuje się często przybliżone line search, jeśli maksymalne minimalizowanie byłoby kosztowne.

1. Jeżeli ${\displaystyle f}$ jest ściśle wypukła w badanej dziedzinie ${\displaystyle D\subset \mathbb {R} ^{n}}$, to istnieje jedno globalne minimum i algorytm gradientu znajdzie to jedno minimum.
2. Jeżeli funkcja nie jest ściśle wypukła, to ma wiele minimów. Wtedy w metodzie gradientu zostanie znalezione jedno minimum lokalne, w zależności od doboru punktu startowego ${\displaystyle \mathbf {x_{0}} }$. Aby znaleźć minimum globalne, trzeba poszukać wszystkich minimów, wybierając różne punkty startowe (np. zbadać, do jakich minimów prowadzą punkty startowe ulokowane w węzłach gęstej siatki, pokrywającej całą dziedzinę funkcji - por. animacja; lub posłużyć się metodą Metropolisa-Hastingsa, która pozwala efektywnie poszukiwać minimum globalnego w przestrzeniach wielowymiarowych). Minimum globalne - to najmniejsze ze znalezionych minimów lokalnych.

Metodę gradientu prostego stosuje się do znajdowania ekstremów funkcji ${\displaystyle f}$ wielu zmiennych rzeczywistych, mającej zbiór wartości rzeczywistych, tj.

${\displaystyle f\colon D\mapsto \mathbb {R} ,}$

gdzie ${\displaystyle D\subset \mathbb {R} ^{n},}$ przy czym funkcja ${\displaystyle f}$ winna być klasy ${\displaystyle \mathrm {C} ^{1}}$ (funkcja ciągła i różniczkowalna).

Na początku wybierany jest dowolny punkt startowy ${\displaystyle \mathbf {x_{0}} \in D.}$ W punkcie tym obliczany jest kierunek poszukiwań ${\displaystyle \mathbf {d_{0}} \in D}$, taki że ${\displaystyle \mathbf {d_{0}} =-\nabla f(\mathbf {x_{0}} )}$, tj. jest to antygradient funkcji w punkcie ${\displaystyle \mathbf {x_{0}} }$ czyli wektor wskazujący kierunek najszybszego spadku funkcji. Następnie obliczany jest nowy punkt ${\displaystyle \mathbf {x_{1}} \in D}$ według wzoru

${\displaystyle \mathbf {x_{1}} =\mathbf {x_{0}} +\alpha _{0}\mathbf {d_{0}} ,}$

gdzie ${\displaystyle \alpha _{0}}$ - dowolnie wybrana liczba rzeczywista, ale taka, by odległość od poprzedniego punktu nie była zbyt duża. Następnie oblicza się kolejne punkty

${\displaystyle \mathbf {x_{k+1}} =\mathbf {x_{k}} +\alpha _{k}\mathbf {d_{k}} ,\quad k=1,2,3,\dots }$

gdzie

${\displaystyle \alpha _{k}}$ - dowolnie wybrane liczby rzeczywiste

${\displaystyle \mathbf {d_{k}} =-\nabla f(\mathbf {x_{k}} )}$

aż kolejny punkt ${\displaystyle \mathbf {x_{k}} }$ spełni warunek stopu algorytmu (patrz dalej).

Współczynniki ${\displaystyle \alpha _{k}}$ decydują o wielkości kolejnych kroków - im większe, tym większe kroki. Algorytm powinien być tak skonstruowany, aby znajdowane wartości funkcji malały w kolejnych krokach, tj.

${\displaystyle f(\mathbf {x_{0}} )>\dots >f(\mathbf {x_{k}} )>f(\mathbf {x_{k+1}} )>\dots }$

(a) Jeżeli warunek ten nie jest w danym kroku spełniony, to należy powtórzyć krok z mniejszą wartością ${\displaystyle \alpha _{k}.}$

(b) W wielu przypadkach przyjmuje się jednakowe wartości ${\displaystyle \alpha _{k}}$, tj.

${\displaystyle \alpha _{k}=\alpha ={\textrm {const}},\quad k=1,2,3,\dots }$

(c) Jeśli ${\displaystyle f}$ jest funkcją kwadratową wielu zmiennych o dodatnio określonym hesjanie ${\displaystyle H}$ to można przyjąć:

${\displaystyle 0<\alpha <{\frac {1}{\lambda }},}$

gdzie ${\displaystyle \lambda }$ jest największą wartością własną macierzy ${\displaystyle H.}$

W celu określenia, czy punkt w danym kroku dostatecznie dobrze przybliża minimum funkcji celu w metodzie gradientu prostego można użyć następujących kryteriów stopu (dla zadanej precyzji ${\displaystyle \epsilon }$ oraz normy ${\displaystyle \|{\cdot }\|}$ w przestrzeni ${\displaystyle D\subset \mathbb {R} ^{n}}$):

${\displaystyle \|\nabla f(\mathbf {x_{k}} )\|\leqslant \epsilon \quad {}}$ - test stacjonarności gradientu

${\displaystyle \|\mathbf {x_{k+1}} -\mathbf {x_{k}} \|\leqslant \epsilon }$ - test stacjonarności przemieszczania się punktu

Metoda gradientu prostego jest metodą o zbieżności liniowej. Oznacza to, iż przy spełnieniu założeń metody, odległości pomiędzy kolejnymi przybliżeniami a minimum funkcji ${\displaystyle \mathbf {x} ^{*}}$ maleją liniowo:

${\displaystyle \|\mathbf {x} ^{*}-\mathbf {x_{k+1}} \|\leqslant c\|\mathbf {x} ^{*}-\mathbf {x_{k}} \|.}$

Algorytm gradientu prostego składa się z 4 etapów postępowania:

1. Wybierz punkt startowy ${\displaystyle \mathbf {x_{0}} .}$ Przyjmij ${\displaystyle k=0}$. Ustal wartość ${\displaystyle \alpha _{0}}$.
2. Oblicz ${\displaystyle \mathbf {x_{k+1}} =\mathbf {x_{k}} -\alpha _{k}\cdot \nabla f(\mathbf {x_{k}} )}$
3. Jeżeli ${\displaystyle f(\mathbf {x_{k+1}} )\geqslant f(\mathbf {x_{k}} )}$ to zmniejsz wartość ${\displaystyle \alpha _{k}}$ i powtórz punkt 2.
4. Sprawdź kryterium stopu:
   1. jeśli nie jest spełnione, to przyjmij ${\displaystyle k:=k+1}$, ustal wartość ${\displaystyle \alpha _{k}}$, przejdź do punktu 2.
   2. jeśli jest spełnione to funkcja ma minimum w punkcie ${\displaystyle \mathbf {x_{k+1}} }$; STOP.

W kontekście metod gradientowych, funkcja kwadratowa to funkcja wielu zmiennych o wartościach rzeczywistych, o postaci ogólnej:

${\displaystyle f(\mathbf {x} )={\frac {1}{2}}\mathbf {x} ^{T}A\mathbf {x} -\mathbf {b} ^{T}\mathbf {x} +c}$

gdzie:

• 

  ${\displaystyle \mathbf {x} \in \mathbb {R} ^{n}}$ – wektor zmiennych zapisany w postaci kolumny,
• ${\displaystyle \mathbf {x} ^{T}\in \mathbb {R} ^{n}}$ – wektor zmiennych transponowany (zapisany w postaci wiersza),
• ${\displaystyle A\in \mathbb {R} ^{n\times n}}$ – macierz symetryczna i dodatnio określona,
• ${\displaystyle \mathbf {b} \in \mathbb {R} ^{n}}$ – wektor,
• ${\displaystyle c\in \mathbb {R} }$ – stała liczba.

Funkcja kwadratowa jest klasycznym przypadkiem testowym dla metod gradientowych, ponieważ gradient zależy liniowo od ${\displaystyle x}$:

${\displaystyle \nabla f(\mathbf {x} )=A\mathbf {x} -\mathbf {b} }$

Dzięki temu łatwo obliczyć optymalny krok. W przypadku funkcji kwadratowej z dodatnio określoną macierzą ${\displaystyle A}$, metoda ta z dokładnym doborem kroku (exact line search) zbiega do minimum w skończonej liczbie kroków lub bardzo szybko.

Charakterystyka

• Minimum funkcji kwadratowej jest jednoznaczne i wynosi ${\displaystyle \mathbf {x} ^{*}=A^{-1}\mathbf {b} }$, gdzie ${\displaystyle A^{-1}}$ - macierz odwrotna do macierzy ${\displaystyle A}$ (wynika to z rozwiązania równania na zerowanie się gradientu: ${\displaystyle \nabla f(\mathbf {x} )=0}$)

• Wydłużone doliny (tzn. różne wartości własne macierzy ${\displaystyle A}$) pokazują, jak szybkość zbieżności zależy od doboru kroku
• Funkcje kwadratowe są często używane do ilustrowania różnicy między metodą stałego kroku a line search.

Rozważmy funkcję dwu zmiennych, o wartościach w dziedzinie rzeczywistej

${\displaystyle f(x,y)_{(example)}=\sin \left({\frac {1}{2}}x^{2}-{\frac {1}{4}}y^{2}+3\right)\cdot \cos(2x+1-e^{y})}$

Funkcja ta jest ciągła, różniczkowalna, wypukła w otoczeniu wybranego punktu startowego. Stosując metodę gradientu wyznaczamy trajektorię punktu, która zmierza do lokalnego minimum (por. rysunki obok).

Metody optymalizacji

1. szukanie minimum funkcji 1 zmiennej

• metoda złotego podziału

2. szukanie minimum funkcji n zmiennych

• metoda najszybszego spadku
• metoda Newtona (optymalizacja)
• metoda Levenberga-Marquardta

Inne

• optymalizacja

W języku polskim

• Fortuna Z., Macukow B., Wąsowski J.: Metody numeryczne, Wydawnictwa Naukowo-Techniczne, 2006.
• Stachurski A., Wierzbicki A.: Podstawy optymalizacji, Oficyna Wydawnicza Politechniki Warszawskiej, 1999.

W języku angielskim

• Cauchy and the gradient method. W: C. Lemaréchal: Optimization Stories. T. 6. EMS Press, s. 251–254, seria: Documenta Mathematica Series. DOI: 10.4171/dms/6/27. ISBN 978-3-936609-58-5.
• Jacques Hadamard. Mémoire sur le problème d'analyse relatif à l'équilibre des plaques élastiques encastrées. „Mémoires présentés par divers savants éstrangers à l'Académie des Sciences de l'Institut de France”, 1908. 
• R. Courant. Variational methods for the solution of problems of equilibrium and vibrations. „Bulletin of the American Mathematical Society”, s. 1–23, 1943. DOI: 10.1090/S0002-9904-1943-07818-4. 
• Haskell B. Curry. The Method of Steepest Descent for Non-linear Minimization Problems. „Quart. Appl. Math.”, s. 258–261, 1944. DOI: 10.1090/qam/10667. 
• Akilov, G. P.; Kantorovich, L. V. (1982). Functional Analysis (2nd ed.). Pergamon Press, ISBN 0-08-023036-9

• https://web.archive.org/web/20170815181749/http://www.isep.pw.edu.pl/~ambor/Pomoce/gradientowe.htm