Metoda kierunków sprzężonych (Powell'a)

Metoda kierunków sprzężonych jest bezgradientową, iteracyjną metodą optymalizacji bez ograniczeń. Dla form kwadratowych jest ona zbieżna w N krokach. Idea metody jest podobna do metody Hooke'a-Jeavsa'a, gdyż także bada ona zachowania funkcji wykonując kroki w kierunkach pewnej bazy. Zasadnicza różnica polega jednak na tym, że w metodzie Powell'a baza ta zmienia się w trakcie wykonywania algorytmu. Modyfikacja bazy polega na stworzeniu i dodaniu do niej nowego sprzężonego kierunku i równoczesnym usunięciu z niej takiego kierunku, wzdłuż którego nastąpiło największe przesunięcie.

Oznaczenia:

e_k – k-ty kierunek N-wymiarowej bazy, początkowo:(wersor kartezjańskiego układu współrzędnych)

d – wyznacznik macierzy, służący do kontrolowania czy wektory bazy są liniowo niezależne (powinien być różny od 0), początkowo d = det(I_N) = 1.

x – aktualne przybliżenie rozwiązania (początkowa wartość może być wylosowana)

ε – wymagana dokładność

- norma wektora x

Algorytm:

1. x_p := x

2. Dla każdego z kierunków k=1, 2, ..., N wybierz optymalny krok m_k dokonując minimalizacji jednowymiarowej wzdłuż kierunku e_k

3. x := x + m₁e₁ + m₂e₂ + ... + m_Ne_N

4. Wyznacz kierunek sprzężony i podstaw x := x + m_N+1e_N+1 , gdzie m_N+1 jest optymalnym krokiem uzyskanym w wyniku minimalizacji funkcji g(m_N+1)=f(x+m_N+1e_N+1)

5. jeżeli(zachodzi warunek stopu) to koniec obliczeń

6. x_p := x

7. wyznacz numer kierunku k (1≤k≤N), w którym nastąpiło największe przesunięcie (kierunek dla którego m_k było największe)

8. jeżeli(wyznacznik dla nowej bazy - stopień liniowej niezależności - jest bezpiecznie duży), to zmień bazę:

e_k := e_N+1 i

9. przejdź do pkt. 2