Zejście gradientowe i zejście gradientowe sprzężone

W przypadku projektu muszę zaimplementować te dwie metody i porównać ich działanie na różnych funkcjach.

Wygląda na to, że metoda gradientu sprzężonego służy do rozwiązywania układów równań liniowych for

$$A\mathbf{x} = \mathbf{b}$$

Gdzie jest macierzą n-na-n, która jest symetryczna, dodatnia i rzeczywista.$A$

Z drugiej strony, kiedy czytam o spadku gradientu , widzę przykład funkcji Rosenbrocka , którą jest

$$f(x_1,x_2) = (1-x_1)^2+100(x_2-x_1^2)^2$$

Moim zdaniem nie mogę tego rozwiązać metodą gradientu sprzężonego. Czy coś mi umknęło?

Obniżanie gradientu i metoda gradientu sprzężonego to algorytmy minimalizujące funkcje nieliniowe, to znaczy funkcje takie jak funkcja Rosenbrocka

$f(x_1,x_2) = (1-x_1)^2 + 100(x_2 - x_1^2)^2$

lub wielowymiarowa funkcja kwadratowa (w tym przypadku z symetrycznym wyrażeniem kwadratowym)

$f(x) = \frac{1}{2} x^T A^T A x - b^T A x.$

Oba algorytmy są również iteracyjne i oparte na kierunkach wyszukiwania. W pozostałej części tego postu i będą wektorami o długości ; i są skalarami, a indeksy górne oznaczają indeks iteracji. Zejście gradientu i metodę gradientu sprzężonego można użyć do znalezienia wartości która rozwiązujed n f ( x ) α x $x$$d$$n$$f(x)$$\alpha$$x^*$

$\min f(x)$

Obie metody zaczynają się od wstępnego odgadnięcia , a następnie obliczają następną iterację przy użyciu funkcji formularza$x^0$

$x^{i+1} = x^i + \alpha^i d^i.$

Innymi słowy, następną wartość można znaleźć, rozpoczynając od bieżącej lokalizacji , i przesuwając się w kierunku wyszukiwania na pewną odległość . W obu metodach odległość do przesunięcia można znaleźć poprzez wyszukiwanie linii (minimalizuj ponad ). Można również zastosować inne kryteria. Różnice między tymi dwiema metodami polegają na wyborze . W przypadku metody gradientowej . W przypadku metody gradientu sprzężonego do ortogonalizacji wektorów gradientu stosowana jest procedura Grahm-Schmidta. W szczególności , ale wtedy jest równex i d i α i f ( x i + α i d i ) α i d $x$$x^i$$d^i$$\alpha^i$$f(x^i + \alpha^i d^i)$$\alpha_i$$d^i$d 0 = - ∇ f ( x 0 ) d 1 - ∇ f ( x 1 ) d 0 ( d 1 ) T d 0 = $d^i = -\nabla f(x^i)$$d^0 = -\nabla f(x^0)$$d^1$$-\nabla f(x^1)$ minus rzut tego wektora na tak, że . Każdy kolejny wektor gradientowy jest ortogonalizowany względem wszystkich poprzednich, co prowadzi do bardzo dobrych właściwości powyższej funkcji kwadratowej.$d^0$$(d^1)^Td^0 = 0$

Powyższa funkcja kwadratowa (i powiązane sformułowania) ma również miejsce, gdy pochodzi dyskusja na temat rozwiązywania przy użyciu metody gradientu sprzężonego, ponieważ minimum tej osiąga się w punkcie gdzie .f ( x ) x A x = $Ax = b$$f(x)$$x$$Ax = b$

W tym kontekście obie metody można traktować jako problemy z minimalizacją funkcji: Gdy jest symetryczny, to jest zminimalizowane, gdy .AϕAx=

$$\phi(\boldsymbol{x}) = \frac{1}{2}\boldsymbol{x}^T\boldsymbol{A}\boldsymbol{x} - \boldsymbol{x}^T\boldsymbol{b}$$ $\boldsymbol{A}$$\phi$$\boldsymbol{A}\boldsymbol{x} = \boldsymbol{b}$

Zejście gradientu to metoda, która iteracyjnie szuka minimalizatora, patrząc w kierunku gradientu. Gradient sprzężony jest podobny, ale kierunki wyszukiwania również muszą być względem siebie ortogonalne w tym sensie, że .$\boldsymbol{p}_i^T\boldsymbol{A}\boldsymbol{p_j} = 0 \; \; \forall i,j$