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:

ek – 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(IN) = 1.

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

ε – wymagana dokładność

- norma wektora x

Algorytm:
    1. xp := x

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

    3. x := x + m1e1 + m2e2 + ... + mNeN

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

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

    6. xp := x

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

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

ek := eN+1 i

    1. przejdź do pkt. 2