Метод Пауэлса - Powells method

Метод Пауэлла, строго Метод сопряженных направлений Пауэлла, является алгоритм предложено Майкл Дж. Д. Пауэлл для поиска местный минимум функции. Функция не обязательно должна быть дифференцируемой, и производные не берутся.

Функция должна быть действительной функцией фиксированного числа действительных входных данных. Вызывающий переходит в начальную точку. Вызывающий также передает набор начальных векторов поиска. Обычно N поисковые векторы (скажем${\textstyle \{s_{1},\dots ,s_{N}\}}$), в которых просто нормали выровнены по каждой оси.^[1]

Метод минимизирует функцию за счет двунаправленного поиска по каждому вектору поиска. Двунаправленный линейный поиск вдоль каждого вектора поиска может быть выполнен с помощью Поиск золотого сечения или же Метод Брента. Пусть минимумы, найденные во время каждого двунаправленного поиска линии, будут ${\textstyle \{x_{0}+\alpha _{1}s_{1},{x}_{0}+\sum _{i=1}^{2}\alpha _{i}{s}_{i},\dots ,{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 \sum _{i=1}^{N}\alpha _{i}s_{i}}$) становится новым вектором поиска и добавляется в конец списка векторов поиска. Между тем, вектор поиска, который внес наибольший вклад в новое направление, то есть наиболее успешный (${\textstyle i_{d}=\arg \max _{i=1}^{N}|\alpha _{i}|\|s_{i}\|}$), удаляется из списка векторов поиска. Новый набор N поисковые векторы ${\textstyle \{s_{1},\dots ,s_{i_{d}-1},s_{i_{d}+1},\dots ,s_{N},\sum _{i=1}^{N}\alpha _{i}s_{i}\}}$Алгоритм повторяется произвольное количество раз, пока не будет достигнуто существенное улучшение.^[1]

Этот метод полезен для вычисления локального минимума непрерывной, но сложной функции, особенно функции без основного математического определения, потому что нет необходимости брать производные. Основной алгоритм прост; сложность заключается в линейном поиске по векторам поиска, что может быть достигнуто с помощью Метод Брента.

Рекомендации

1. Мэтьюз, Джон Х. «Модуль для метода поиска Пауэлла на минимум». Калифорнийский государственный университет, Фуллертон. Получено 16 июн 2017.

• Пауэлл, М. Дж. Д. (1964). «Эффективный метод нахождения минимума функции нескольких переменных без вычисления производных». Компьютерный журнал. 7 (2): 155–162. Дои:10.1093 / comjnl / 7.2.155. HDL:10338.dmlcz / 103029.
• Нажмите, WH; Теукольский С.А.; Феттерлинг, штат Вашингтон; Фланнери, ВР (2007). «Раздел 10.7. Методы набора направлений (Пауэлла) в многомерности». Числовые рецепты: искусство научных вычислений (3-е изд.). Нью-Йорк: Издательство Кембриджского университета. ISBN  978-0-521-88068-8.
• Брент, Ричард П. (1973). «Раздел 7.3: Алгоритм Пауэлла». Алгоритмы минимизации без производных. Энглвуд Клиффс, Нью-Джерси: Прентис-Холл. ISBN  0-486-41998-3.