Wykład 7

6.1 Szukanie minimum funkcji jednej zmiennej metodami niegradientowymi

6.1.3. Metoda Armijo

Aby znaleźć długość kroku w metodzie największego spadku dla minimum funkcji f(x) należy szukać minimum po α funkcji g (α) = 
        f((Subscript[x, 0]) - α ▽ f((Subscript[x, 0]))), gdzie (Subscript[x, 0]) jest punktem, w którym szukamy wektora największego spadku.

Przykład 6.1.3.1

Szukamy długości  kroku w metodzie największego spadku dla minimum funkcji f((Subscript[x, 1]), (Subscript[x, 2])) = 2  ((Subscript[x, 1])^2) + ((Subscript[x, 2])^2) w punkcie (Subscript[x, 0]) = (1, 3)

Funkcja g(α)=2 (((1 - 4 α))^2) + (((3 - 6 α))^2)

■

Styczna do funkcji g  w punkcie 0 ma równanie y = g(0) + α g' (0), zaś sieczna w tym samym punkcie, niewiele różniąca się od stycznej  ma równanie y = y(α) = 
          g(0) + ϵ α g' (0), gdzie ϵ>0 (zazwyczaj przyjmuje się ϵ = 0.2). Wartość g' (0) można wyliczyć ze wzoru \(TraditionalForm\`g' \((0)\) = \(-‖▽\ \(f(x\_0)\)‖\^2\)\)
Jeżeli w ustalonym punkcie α wartość funkcji g jest mniejsza niż wartość na siecznej to minimum warto szukać na prawo od α (a więc należy zwiększać α); gdy wartość funkcji g jest większa niż wartość na siecznej to minimum warto szukać na lewo od α (a więc należy zmniejszać α)

Przykład 6.1.3.1 (c.d.)

g(0) = 11,  g' (0) = -52 a więc, przyjmując ϵ = 0.2, równanie siecznej ma postać:  y = 11 - 10.4  α .
W punkcie α=0.3 wartość funkcji wynosi 1.52 , a wartość na siecznej w tym punkcie jest równa 7.88;  punkcie α=0.8 wartość funkcji wynosi 12.92 , a wartość na siecznej w tym punkcie jest równa 2.68. Jak widać z wykresu, minimum tej funkcji jest w okolicach punktu 0.4, a więc na prawo od 0.3 i na lewo od 0.8

■

Metoda Armijo jest iteracyjna i składa się z kroków:
1. (Subscript[α, 1]) = 1, i = 1
2. gdy g((Subscript[α, i])) > y((Subscript[α, i])) zmniejszamy α (zazwyczaj (Subscript[α, i + 1]) = 0.5 (Subscript[α, i])) tak długo aż po raz pierwszy g((Subscript[α, i])) ≤ y((Subscript[α, i])).
3. gdy g((Subscript[α, i])) < y((Subscript[α, i])) zwiększamy α (zazwyczaj (Subscript[α, i + 1]) = 2 (Subscript[α, i])) tak długo aż po raz pierwszy g((Subscript[α, i])) ≥ y((Subscript[α, i])).

Ostatnia uzyskana wartość α jest oszacowaniem punktu minimum funkcji g.

Przykład 6.1.3.1 (c.d.)

(Subscript[α, 1]) = 1, g ((Subscript[α, 1])) = 27, y ((Subscript[α, 1]))=0.6 - zmniejszamy α,
(Subscript[α, 2]) = 0.5, g ((Subscript[α, 2])) = 2, y ((Subscript[α, 1]))=5.8-  α=\(\(0.5\)\(\ \)\(jest\)\(\ \)\(przybliżonym\)\(\ \)\(rozwiązaniem\)\(\ \)\)

Dokładna wartość minimum funkcji g jest osiągnięta w α=0.38. W ogólnym przypadku znalezienie dokładnej wartości jest trudne więc użycie metody Armijo jest często efektywnym sposobem ustalenia optymalnej długości wektora najszybszego spadku. ■

7. Metoda gradientu sprzężonego

Stosując metodę najszybszego spadku, tempo zbliżania się do minimum obniża się, gdy jesteśmy już blisko celu (efekt wirowy). Dlatego zaleca się w pobliżu punktu minimum zmodyfikować kierunek spadku, zachowując do pewnego stopnia kierunek uzyskany w poprzednich krokach. Takie metody nazywamy metodami gradientu sprzężonego.
Stosując te metody w k-tym kroku (k ≥ 2) kierunek spadku w punkcie (x^k) jest równy

(d^k) = -▽f ((x^k)) + (β^k) 
          (d^(k - 1)),  
    (d^1) = -▽f ((x^1))

Skalar (β^k) wyznacza stopień zachowania poprzedniego kierunku - daleko od minimum te wartości są małe, natomiast w pobliżu minimum są one znacząco większe od 0.
Przytoczymy tu dwa wzory:
Wzór Fletchera-Reevesa

\(\(\(			\)\(β\^k = ‖▽f \((x\^k)\)‖\^2\/‖▽f \((x\^\(k - 1\))\)‖\^2\)\)\)

Wzór Polaka-Ribiere'a

\(\(\(			\)\(β\^k = ⟨▽f \((x\^\(k - 1\))\) - ▽f \((x\^k)\), ▽f \((x\^k)\)⟩\/‖▽f \((x\^\(k - 1\))\)‖\^2\)\)\)

Wzór Polaka-Ribiere'a uważany jest za skuteczniejszy. 
W pobliżu minimum gradient jest wektorem o małej długości, mianownik w obu wzorach będzie mały, a więc wartość współczynnika (β^k) może być duża.

Przykład 7.1 (metody gradientu sprzężonego)

Wykonamy 3 kroki metodą Fletchera-Reevesa dla minimum funkcji f(x, y) = (x^4) + 4  (y^2), startując z punktu (1,1). Długość kierunku spadku wyznaczać będziemy metodą Armijo.

\(▽f = \((4  x\^3, 8  y)\), 
\ 
    x\^1 = \((1, 1)\), \ ▽f \((x\^1)\) = \((4, 
        8)\), \ \ ‖▽f \((x\^1)\)‖\^2 = 80\ , 
    d\^1 = \((\(-4\), \(-8\))\)\)
\(g \((α)\) = \((1 - 4  α)\)\^4 + 
        4 \((1 - 8  α)\)\^2, \ g \((0)\) = \(f \((x\^1)\) = 5\), \ 
    g' \((0)\) = \(\(-‖▽f \((x\^1)\)‖\^2\) = \(-80\)\), \ 
    y \((α)\) = 5 - 16  α\)
α = 1,  g (1) = 277,  
    y (1) = -11 
α = 0.5,  g (0.5) = 37,  
    y (0.5) = -3
α = 0.25,  g (0.25) = 4,  
    y (0.25) = 1
α = 0.12,  g (0.12) = 0.080,  
    y (0.12) = 3.08
\(x\^2 = \(\((1, 1)\) + 0.12 \((\(-4\), \(-8\))\) = \((0.52, 
          0.04)\)\), \ ▽f \((x\^2)\) = \((0.56, 
        0.32)\), \ \ ‖▽f \((x\^2)\)‖\^2 = 
      0.42\ , 
d\^2 = \(\((\(-0.56\), \(-0.32\))\) + \(0.42\/80\) \((\(-4\), \(-8\))\) = \((\(-0.58\), \(-0.36\))\)\)\)
\(g \((α)\) = \((0.52 - 0.58  α)\)\^4 + 
        4 \((0.04 - 0.36  α)\)\^2, \ 
    g \((0)\) = \(f \((x\^2)\) = 0.080\), \ 
    g' \((0)\) = \(\(-‖▽f \((x\^2)\)‖\^2\) = \(-0.42\)\), \ 
    y \((α)\) = 0.08 - 0.084  α\)
α = 1,  g (1) = 0.410,  y (1) = -0.004
α = 0.5,  g (0.5) = 0.081,  y (0.5) = 0.038
α = 0.25,  g (0.25) = 0.030,  y (0.25) = 0.059
(x^3) = (0.52, 0.04) + 
          0.25 (-0.58, -0.36) = (0.38, -0.004)

■