Метод Пауэлса - Википедия - Powells method

Эта статья нужны дополнительные цитаты для проверка. Пожалуйста помоги улучшить эту статью к добавление цитат в надежные источники. Материал, не полученный от источника, может быть оспорен и удален Найдите источники: «Метод Пауэлла»  – Новости  · газеты  · книги  · ученый  · JSTOR (Август 2009 г.) (Узнайте, как и когда удалить этот шаблон сообщения)

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

Функция должна быть действительной функцией фиксированного числа действительных входных данных. Вызывающий переходит в начальную точку. Вызывающий также передает набор начальных векторов поиска. Обычно 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 _ {я}}$ - скаляр, определяемый при двунаправленном поиске по ${ textstyle {s} _ {я}}$. Новая должность (${ textstyle x_ {1}}$) затем можно выразить как линейную комбинацию векторов поиска, т.е. ${ textstyle x_ {1} = x_ {0} + sum _ {i = 1} ^ {N} alpha _ {i} s_ {i}}$. Новый вектор смещения (${ textstyle сумма _ {я = 1} ^ {N} альфа _ {я} s_ {я}}$) становится новым вектором поиска и добавляется в конец списка векторов поиска. Между тем, вектор поиска, который внес наибольший вклад в новое направление, то есть наиболее успешный (${ 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]

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

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

• Пауэлл, М. Дж. Д. (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.