Podręcznik

W przypadku optymalizacji w przestrzeni ciągłej, jedną z najstarszych i najbardziej klasycznych grup metod są algorytmy gradientowe. Ich zasada działania opiera się na założeniu, że funkcja celu jest gładka – czyli ciągła i różniczkowalna.

Intuicja: jak zejść po schodach w ciemności

Wyobraź sobie, że stoisz na środku zbocza i chcesz zejść na sam dół. Nie widzisz całej doliny – widzisz tylko to, co masz bezpośrednio wokół siebie. Możesz dotknąć ziemi wokół i ocenić, gdzie jest najstromiej w dół – i właśnie w tę stronę zrobisz krok. To właśnie jest gradient: wektor wskazujący kierunek najszybszego spadku wartości funkcji.

Gradient i krok

Jeśli funkcja celu to $f(x)$, a $x \in \mathbb{R}^n$, to gradient to:

$\nabla f(x) = \left[ \frac{\partial f}{\partial x_1}, \ldots, \frac{\partial f}{\partial x_n} \right]$

Podstawowa iteracyjna formuła wygląda następująco:

$x_{k+1} = x_k - \alpha \nabla f(x_k)$

• $x_k$ to punkt aktualny,
• $\alpha$ to współczynnik uczenia (długość kroku),
• $\nabla f(x_k)$ to gradient w punkcie $x_k$.

Metoda największego spadku

To najprostszy algorytm gradientowy. Za każdym razem idziemy w kierunku przeciwnym do gradientu – czyli w stronę, gdzie funkcja maleje najszybciej. W praktyce ważne jest dobranie odpowiedniej wartości $\alpha$, bo:

• zbyt duży krok może przeskoczyć minimum,
• zbyt mały krok prowadzi do powolnej zbieżności.

Metoda Newtona i quasi-Newtona

Metoda Newtona wykorzystuje nie tylko gradient, ale też drugą pochodną – tzw. hesjan (macierz drugich pochodnych cząstkowych):

$H(x) = \left[ \frac{\partial^2 f}{\partial x_i \partial x_j} \right]$

Formuła iteracyjna:

$x_{k+1} = x_k - H^{-1}(x_k) \nabla f(x_k)$

Dlaczego druga pochodna daje nam przewagę? Bo zawiera informację o krzywiźnie funkcji celu. Gradient mówi tylko, w którą stronę funkcja maleje – ale nie mówi, jak szybko. Hesjan dostarcza wiedzy o tym, jak zakrzywiona jest funkcja w danym punkcie. Dzięki temu można:

• lepiej dobrać długość kroku (adaptacyjnie, zamiast na sztywno),
• szybciej zbliżyć się do minimum – zwłaszcza w pobliżu punktu optymalnego,
• unikać efektu "zygzakowania" w przypadku funkcji o bardzo różnych krzywiznach w różnych kierunkach.

Warunki stopu

W algorytmach gradientowych zatrzymujemy się, gdy:

• $\| \nabla f(x_k) \| < \epsilon$ – gradient jest prawie zerowy,
• $\| x_{k+1} - x_k \| < \delta$ – zmiana rozwiązania jest minimalna,
• osiągnięto maksymalną liczbę iteracji.

Ograniczenia i trudności

• Minimum lokalne – mogą "utknąć" w lokalnym minimum, nie docierając do globalnego,
• Brak gładkości – jeśli funkcja celu nie jest różniczkowalna, nie możemy użyć pochodnych,
• Siodła i płaskowyże – gradient może nie prowadzić w dobrą stronę.

Przykłady zastosowań

• Optymalizacja kształtów elementów mechanicznych,
• Minimalizacja strat w sieciach neuronowych (np. SGD w ML),
• Wyznaczanie parametrów modeli analitycznych,
• Problemy portfela inwestycyjnego, gdzie funkcja ryzyka i zwrotu ma formę analityczną.

W kolejnym rozdziale zobaczymy, jak w algorytmach klasycznych i gradientowych można wprowadzać ograniczenia – zarówno twarde (jawne) jak i miękkie (np. kary za przekroczenie dopuszczalnego zakresu).