El método de Powell

El método de Powell , estrictamente el método de dirección conjugada de Powell , es un algoritmo propuesto por Michael J. D. Powell para hallar un mínimo local de una función. La función no necesita ser diferenciable y no se toman derivadas.

La función debe ser una función de valor real de un número fijo de entradas de valor real. El llamador pasa el punto inicial. El llamador también pasa un conjunto de vectores de búsqueda iniciales. Normalmente se pasan N vectores de búsqueda (por ejemplo ) que son simplemente las normales alineadas a cada eje. ^[1] ${\textstyle \{s_{1},\dots,s_{N}\}}$

El método minimiza la función mediante una búsqueda bidireccional a lo largo de cada vector de búsqueda, a su vez. La búsqueda de línea bidireccional a lo largo de cada vector de búsqueda se puede realizar mediante la búsqueda de sección áurea o el método de Brent . Sea el mínimo encontrado durante cada búsqueda de línea bidireccional , donde es el punto de partida inicial y es el escalar determinado durante la búsqueda bidireccional a lo largo de . La nueva posición ( ) se puede expresar entonces como una combinación lineal de los vectores de búsqueda, es decir . El nuevo vector de desplazamiento ( ) se convierte en un nuevo vector de búsqueda y se añade al final de la lista de vectores de búsqueda. Mientras tanto, el vector de búsqueda que más contribuyó a la nueva dirección, es decir, el que tuvo más éxito ( ), se elimina de la lista de vectores de búsqueda. El nuevo conjunto de N vectores de búsqueda es . El algoritmo itera un número arbitrario de veces hasta que no se produce ninguna mejora significativa. ^[1] ${\textstyle \{x_{0}+\alpha _{1}s_{1},{x}_{0}+\sum _{i=1}^{2}\alpha _{i}{s}_{i},\puntos ,{x}_{0}+\sum _{i=1}^{N}\alpha _{i}{s}_{i}\}}$ ${\textstyle {x}_{0}}$ ${\textstyle \alpha _{i}}$ ${\textstyle {s}_{i}}$ ${\textstyle x_{1}}$ ${\textstyle x_{1}=x_{0}+\sum _{i=1}^{N}\alpha _{i}s_{i}}$ ${\textstyle \suma _{i=1}^{N}\alpha _{i}s_{i}}$ ${\textstyle i_{d}=\arg \max _{i=1}^{N}|\alpha _{i}|\|s_{i}\|}$ ${\textstyle \{s_{1},\puntos ,s_{i_{d}-1},s_{i_{d}+1},\puntos ,s_{N},\sum _{i=1}^{N}\alpha _{i}s_{i}\}}$

El método es útil para calcular el mínimo local de una función continua pero compleja, especialmente una que no tenga una definición matemática subyacente, porque no es necesario tomar derivadas. El algoritmo básico es simple; la complejidad está en las búsquedas lineales a lo largo de los vectores de búsqueda, que se pueden lograr mediante el método de Brent .

Referencias

^ ab Mathews, John H. "Módulo para el método de búsqueda de Powell para un mínimo". Universidad Estatal de California, Fullerton . Consultado el 16 de junio de 2017 .

Powell, MJD (1964). "Un método eficiente para hallar el mínimo de una función de varias variables sin calcular derivadas". Computer Journal . 7 (2): 155–162. doi :10.1093/comjnl/7.2.155. hdl : 10338.dmlcz/103029 .
Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Sección 10.7. Métodos de conjuntos de direcciones (de Powell) en multidimensiones". Recetas numéricas: el arte de la computación científica (3.ª ed.). Nueva York: Cambridge University Press. ISBN 978-0-521-88068-8.
Brent, Richard P. (1973). "Sección 7.3: Algoritmo de Powell". Algoritmos para la minimización sin derivadas . Englewood Cliffs, NJ: Prentice-Hall. ISBN 0-486-41998-3.