Wykład 5

5. Metody numeryczne szukania minimum

W praktyce, szukanie minimum funkcji, z ograniczeniami czy bez ograniczeń, sprowadza się do rozwiązywania układów równań. Często równań tych nie można rozwiązać dokładnie - można jedynie zastosować metodynumeryczne. I to jest jedna z możliwych dróg w takiej sytuacji.

Można jednak postąpić inaczej. Postawić zagadnienie szukania minimum od początku w języku metod numerycznych. Taką drogę przedstawimy w kilku kolejnych wykładach.

5.1 Metody numeryczne szukania minimum bez ograniczeń

W metodach numerycznych szukamy rozwiązania, definiując ciąg przybliżeń, zbieżny do dokładnej wartości.
	W naszym zagadnieniu szukania minimum bez ograniczeń chcemy zdefiniować ciąg wektorów (x^k) zbiezny do minimum funkcji f(x), spełniający następujące warunki:

1. (x^(k + 1)) = (x^k) + (Subscript[α, k]) (d^k) (wzór rekurencyjny), (Subscript[α, k])>0

2. f((x^(k + 1))) < f((x^k)) (k + 1-sze przybliżenie jest lepsze od k-tego przybliżenia),

3. ‖∇f(
              (x^t))‖ < ε (reguła stopu w kroku t).

Warunek 1. nie narzuca żadnych ograniczeń. Pozwala jednak opisać wektor, będący różnicą (x^(k + 1)) - (x^k). (Subscript[α, k]) jest skalarem i będzie wyrażać długość skoku od punktu (x^k) do punktu (x^(k + 1)). Wektor (d^k) będzie, w świetle warunku 2. określał kierunek spadku funkcji f (punkt 5.1.1).

Warunek 3. wynika z tego, że w punkcie minimum gradient funkcji celu jest równy 0. Reguła stopu oznacza, że jesteśmy w pobliżu punktu stacjonarnego, co jest warunkiem koniecznym na istnienie w tym punkcie minimum funkcji.

5.1.1. Wyznaczenie kierunku spadku i najszybszego spadku.

Definicja. Kierunkiem spadku funkcji f w niestacjonarnym punkcie (x^0) nazywamy wektor d taki, że istnieje dostatecznie mały skalar α > 0 taki, że f((x^0) + α d) < f((x^0))

Stwierdzenie 5.1. ( wektor  spadku). Wektor  spadku dla f ∈ (C^2) spełnia warunek  ∇f ((((x^0)))^T) (d^k) < 0

Dowód.

Wektora  spadku będziemy szukać, jeśli  ‖∇f(
              (x^0))‖ > 0. W przeciwnym przypadku (x^0) jest punktem stacjonarnym
Dla dostatecznie małych α>0

f ((x^0) + αd) = 
      f ((x^0)) + α ∇f ((((x^0)))^T) d + 
        O ((α^2))
\(f \((x\^0 + αd)\) < 
      f \((x\^0)\)\ ⟺\ α ∇f \(\((x\^0)\)\^T\) d + O \((α\^2)\) < 
      0⟺\ \(∇f\) \(\((x\^0)\)\^T\) d < 
      0\)

Co kończy dowód ■

Stwierdzenie 5.2. ( wektor najszybszego spadku). Największy spadek funkcji f  przy ustalonym α  spośród wszystkich wektorów spadku d o tej samej długości ma wektor równoległy do  -∇f ((x^0))(wektor najszybszego spadku).

Dowód .

Rozłóżmy wektor d na dwie prostopadłe do siebie składowe: równoległą do ∇f ((x^0)) i wektor q, do niego prostopadły. Wtedy

d = -λ ∇f ((x^0)) + q ,  (λ > 
        0)
\(‖d‖\^2 = \(λ\^2\) ‖∇f \((x\^0)\)‖\^2 + ‖q‖\^2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \((5.1)\)\)

\(f \((x\^0 + αd)\) - 
        f \((x\^0)\)\  = \ \(α ∇f \(\((x\^0)\)\^T\) d + 
          O \((α\^2)\) = 
\(α \((∇f \(\((x\^0)\)\^T\) \((\(-λ\) ∇f \((x\^0)\) + q)\))\) + 
            O \((α\^2)\) = \(-αλ\) ‖∇f \((x\^0)\)‖\^2 + 
            O \(\((α\^2)\)\(.\)\)\)\)\)

Spadek wartości funkcji f jest niezależny od wektora q i jest największy, gdy λ ma największą wartość. Z (5.1) wynika, że λ ma największą wartość, gdy \(TraditionalForm\`‖q‖\)= 0, a więc gdy d = -λ ∇f ((x^0))■

Przykład 5.1

Czy wektory  (1,1), (-1,-1)  są wektorami spadku dla funkcji f(x, y) = (x^2) + (y^2) w punkcie (1,2)? Znaleźć wektor najszybszego spadku w tym punkcie.

Rozwiązanie

\(∇f \((x)\) = \((2  x, 2  y)\)\^T, 
∇f \((x\^0)\) = \((2, 4)\)\^T\)

Wektor (Subscript[d, 1])=(((1, 1))^T) nie jest wektorem spadku gdyż

∇f ((((x^0)))^T) (Subscript[d, 1]) = (((2, 4))^T) (1, 1) = 
        6 > 0

Wektor (Subscript[d, 2])=(((-1, -1))^T)  jest wektorem spadku gdyż

∇f ((((x^0)))^T) 
        (Subscript[d, 2]) = (((2, 4))^T) (-1, -1) = -6 < 
          0

Wektorem najszybszego spadku jest

-∇f ((x^0)) = (((-2, -4))^T)

Narysujmy wektory (Subscript[d, 1]) = (((1, 1))^T), 
      (Subscript[d, 2]) = (((-1, -1))^T), (Subscript[d, 3]) = (((-2, -4))^T) zaczepione w punkcie (1,2) na tle poziomic funkcji f.

Wartość funkcji f jest najmniejsza w  punkcie (0,1), będącym końcem wektora (Subscript[d, 2]), a nie w punkcie (-1,-2), będącym końcem wektora (Subscript[d, 3]), który jest kierunkiem najszybszego spadku. Jednak umiejętnie dobrana długość tego wektora pozwoli na dotarcie do punktu minimum, mieszczšcego się w punkcie (0,0). ■

Jak widać z poprzedniego przykładu, aby zbliżyć się do punktu minimum trzeba nie tylko znaleźć kierunek najszybszego spadku, ale również umiejętnie dobrać długość wektora najszybszego spadku.

5.1.2. Wyznaczenie długości wektora spadku.

Przykład 5.2 (kontynuacja przykładu 5.1)

Dla funkcji z przykładu 5.1 znaleźć współczynnik α przy kierunku spadku (-1,-1)  w punkcie (1,2).

Wektor (x^0) + α d = (1, 
              2) + α (-1, -1) = (1 - α, 
            2 - α). Zdefiniujmy funkcję

\(Φ \((α)\) = \(f \((1 - α, 
            2 - α)\) = \((1 - α)\)\^2 + \((2 - α)\)\^2\)\)

Długość wektora największego spadku wyznaczymy, minimalizujšc funkcję Φ(α).

Φ' (α) = -2 (1 - α) - 
          2 (2 - α) = 4  α - 6

Minimum jest więc w punkcie α = (3/2). Nowy punkt, w którym powinniśmy obliczyć wartość funkcji i podjąć decyzję o dalszych obliczeniach ma wspólrzędne:

(x^1) = (1 - α, 2 - α) = (((-1)/2), 
          (1/2))

Wartość funkcji w punkcie (1, 2) wyniosła 5, w nowym punkcie (((-1)/2), (1/2)) wynosi (1/2). Zauważmy, że wektor spadku jest styczny do poziomicy (1/2) i koniec tego wektora, odpowiadający największemu spadkowi jest umieszczony w punkcie styczności.

■

Tak jest zawsze. Zachodzi bowiem

Stwierdzenie 5.2. ( największa długość wektora spadku). Niech \(TraditionalForm\`\(α\^*\)\) będzie największą długością wektora spadku d w punkcie (x^0) dla minimalizowanej funkcji f. Wtedy wektor o początku w (x^0) a o końcu w \(TraditionalForm\`x\^0 + \(α\^*\) d\) jest styczny do  poziomicy, odpowiadającej \(TraditionalForm\`f(x\^0 + \(α\^*\) d)\).

Dowód .

Zdefiniujmy funkcję

Φ (α)=f((Subscript[x, 0]) + αd)

Pochodna tej funkcji wynosi:

\(Φ' \((α)\) = \(∑\+\(i = 1\)\%n\(∂f\/∂x\_i\) \((x\_0 + αd)\) ∂\((x\_0 + αd)\)\_i\/∂α = ∇f \((x\_0 + αd)\) 
          d\^T\)\)

Z warunku koniecznego istnienia minimum (pochodna musi być równa 0) wynika, że iloczyn skalarny po prawej stronie jest równy 0, co jest równoznaczne z zachodzeniem tezy stwierdzenia. ■

Ostatnie stwierdzenie daje nam graficzną metodę szukania minimum:
	- w danym punkcie szukamy kierunku spadku funkcji i wybieramy w tym kierunku punkt styczności z jedną z poziomic,
	- w tak uzyskanym nowym punkcie znów szukamy kierunku spadku i wybieramy w tym kierunku punkt styczności z jedną z poziomic, itd. aż do uzyskania zadowalajšcej bliskości minimum.

Przykład 5.3 (wyznaczenie długości wektora spadku)

Wyznacz długość wektora spadku w punkcie (x^0) = (0, 0) w kierunku d = (1, 2) dla funkcji f(x, y) = ((((x^2) + y - 11))^2) + x + (y^2) - 7.

Wektor d jest wektorem spadku, gdyż

∇f (x)=(({{1 - 44  x + 4  (x^3) + 4  xy}, {-22 + 2  (x^2) + 4  y}})),
∇f ((x^0))=(({{1}, {-22}}))

\(∇f \(\((x\^0)\)\^T\) 
        d = \(\(-\)\(43\)\(\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \)\)\)

Wektor uzyskany z ruchu w kierunku wektora d  będzie miał współrzędne (x^1) = (α, 2  α). Największy przyrost funkcji celu uzyskamy, gdy będzie spełniony warunek

d(Φ/d)α = ∇(f^T) ((x^1)) 
          d = -43 - 28  α + 12  (α^2) + 4  (α^3) = 
          0

Rozwiązując to równanie 3-go stopnia uzyskamy jedyną dodatnią wartość α = 2.24639. Druga pochodna funkcji Φ po α 
wynosi

-28 + 24 α + 12 (α^2)

i w punkcie α = 2.24639 ma wartość 86.4687 , więc mamy w tym punkcie minimum. Wartość funkcji f wynosi:

f ((x^0)) = f (0, 0) = 
        114, 
f ((x^1)) = f (2.24639, 4.49278) = 
        17.5658

■

Znalezienie długości wektora spadku jest trudnym problemem numerycznym, gdyż sprowadza się do szukania rozwiązania równania, czasami bardzo skomplikowanego. Można jednak problem ten próbować rozwiązać bezpośrednio, szukając minimum funkcji jednej zmiennej Φ(α).

Przykład 5.4 (Metoda najszybszego spadku)

\(Wykonaj\ dwa\ kroki\ metody\ najszybszego\ spadku\ \ dla\ obliczenia\ minimum\ funkcji\) 
f (x, y)=((((x^2) + y - 11))^2)+x+(y^2)-7 startując z punktu (x^0)=(0,0.  
Obliczenia wykonaj z dokładnością do dwóch cyfr \(\(znaczących\)\(.\)\)

∇f (x)=(({{1 - 44  x + 4  (x^3) + 4  xy}, {-22 + 2  (x^2) + 4  y}})),
f ((x^0)) = 114
d=-∇f ((x^0))=(({{-1}, {22}}))

Szukamy najdłuższego kroku w kierunku najszybszego spadku

Wektor uzyskany z ruchu  w kierunku wektora d  będzie miał współrzędne (x^1) = (-α, 22  α). Największy przyrost funkcji celu uzyskamy, gdy będzie spełniony warunek

d(Φ/d)α = ∇(f^T) ((x^1)) 
          d = -485 + 1892  α + 132  (α^2) + 
            4  (α^3) = 0

Rozwiązanie dodatnie tego równania wynosi α = 0.25. Wtedy

(x^1)=(({{-0.25}, {5.5}})),
f ((x^1)) = 
        52.57
d=-∇f ((x^1))=(({{-6.44}, {-0.12}}))

Wektor uzyskany z ruchu w kierunku wektora d  będzie miał współrzędne (x^2) = (-0.25 - 6.44  α, 
          5.5 - 0.12 α). Największy przyrost funkcji celu uzyskamy, gdy będzie spełniony warunek

d(Φ/d)α = ∇(f^T) ((x^1)) 
          d = -41.472500000000004` - 882.802` α + 
            771.4089600000001` (α^2) + 
            6880.2379878400025` (α^3) = 0

Rozwiązanie dodatnie tego równania wynosi α = 0.33. Wtedy

(x^2)=(({{-2.38}, {5.46}})),
f ((x^2)) = 
        20.45
d=-∇f ((x^1))=(({{-6.44}, {-0.12}}))

Następny kierunek spadku będzie równy

d=-∇f ((x^2))=(({{0.18}, {-11.17}}))

Interesujące jest, że startując z punktu (0,0) w kierunku (1,2) można w jednym kroku osiągnąć wartość funkcji równą 17.57. Czyli ruch w kierunku nie będącym kierunkiem najszybszego spadku nie gwarantuje szybkiego osiagnięcia minimum. Przekonamy się (w metodzie gradientu sprzężonego) że czasami jest to metoda szybsza.■