Powells metod

Powells metod , strikt Powells konjugerade riktningsmetod , är en algoritm som föreslagits av Michael JD Powell för att hitta ett lokalt minimum av en funktion. Funktionen behöver inte vara differentierbar och inga derivator tas.

Funktionen måste vara en verkligt värderad funktion av ett fast antal realvärderade indata. Den som ringer passerar i startpunkten. Den som ringer passerar också in en uppsättning initiala sökvektorer. Vanligtvis skickas N sökvektorer (säg ${\textstyle \{s_{1},\dots ,s_{N}\}} ) i vilka helt enkelt är normalerna inriktade på varje axel.$

Metoden minimerar funktionen genom en dubbelriktad sökning längs varje sökvektor i sin tur. Den dubbelriktade linjesökningen längs varje sökvektor kan göras med Golden-section-sökning eller Brents metod . Låt minima som hittas under varje dubbelriktad linjesökning vara ${\textstyle \ {x_{0}+\alpha _{1}s_{1},{x}_{0}+\summa _{i=1}^{2}\alpha _{i}{s}_{i} ,\dots ,{x}_{0}+\sum _{i=1}^{N}\alpha _{i}{s}_{i}\}} , där x {\textstyle {$ x $_ {0}}$ är den initiala startpunkten och ${\textstyle \alpha _{i}}$ är skalären som bestäms under dubbelriktad sökning längs ${\textstyle {s}_{i}}$ . Den nya positionen ( ${\textstyle x_{1}}$ ) kan sedan uttryckas som en linjär kombination av sökvektorerna, dvs ${\textstyle x_{1}= x_{0}+\summa _{i=1}^{N}\alpha _{i}s_{i}}$ . Den nya förskjutningsvektorn ( ${\textstyle \sum _{i=1}^{N}\alpha _{i}s_{i}}) blir$ en ny sökvektor och läggs till till slutet av sökvektorlistan. Under tiden sökvektorn som bidrog mest till den nya riktningen, dvs den som var mest framgångsrik ( ${\textstyle i_{d}=\arg \ max _{i=1}^{N}|\alpha _{i}|\|s_{i}\|} ), tas$ bort från sökvektorlistan. Den nya uppsättningen av N sökvektorer är ${\textstyle \{s_{1} ,\dots ,s_{i_{d}-1},s_{i_{d}+1},\dots ,s_{N},\sum _{i=1}^{N}\alpha _{i} s_{i}\}}$ . Algoritmen itererar ett godtyckligt antal gånger tills ingen signifikant förbättring görs.

Metoden är användbar för att beräkna det lokala minimumet för en kontinuerlig men komplex funktion, speciellt en utan en underliggande matematisk definition, eftersom det inte är nödvändigt att ta derivator. Den grundläggande algoritmen är enkel; komplexiteten ligger i de linjära sökningarna längs sökvektorerna, vilket kan uppnås via Brents metod .

• Powell, MJD (1964). "En effektiv metod för att hitta minimum av en funktion av flera variabler utan att beräkna derivator". Datorjournal . 7 (2): 155–162. doi : 10.1093/comjnl/7.2.155 . hdl : 10338.dmlcz/103029 .
•   Tryck, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Avsnitt 10.7. Riktningsuppsättning (Powells) metoder i multidimensioner" . Numeriska recept: The Art of Scientific Computing (3:e upplagan). New York: Cambridge University Press. ISBN 978-0-521-88068-8 .
•   Brent, Richard P. (1973). "Avsnitt 7.3: Powells algoritm" . Algoritmer för minimering utan derivator . Englewood Cliffs, NJ: Prentice-Hall. ISBN 0-486-41998-3 .