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).