Метод лапки Пауэлла - Powells dog leg method

Метод собачьей ноги Пауэлла является итеративный оптимизация алгоритм решения нелинейный метод наименьших квадратов проблемы, введенные в 1970 г. Майкл Дж. Д. Пауэлл.^[1] Аналогично Алгоритм Левенберга-Марквардта, он сочетает в себе Алгоритм Гаусса – Ньютона с градиентный спуск, но он использует явный регион доверия. На каждой итерации, если шаг алгоритма Гаусса – Ньютона находится в пределах доверенной области, он используется для обновления текущего решения. Если нет, алгоритм ищет минимум целевая функция по самому крутому направлению спуска, известному как точка Коши. Если точка Коши находится за пределами доверенной области, она обрезается до границ последней и принимается в качестве нового решения. Если точка Коши находится внутри доверительной области, новое решение берется на пересечении границы доверительной области и линии, соединяющей точку Коши и шаг Гаусса-Ньютона (шаг собачьей ноги).^[2]

Название метода происходит от сходства конструкции ступеньки собачьей ноги и формы ступеньки. отверстие изогнутой формы в гольф.^[2]

Формулировка

Построение ступеньки собачьей ноги

Учитывая наименьших квадратов проблема в форме

${\displaystyle F({\boldsymbol {x}})={\frac {1}{2}}\left\|{\boldsymbol {f}}({\boldsymbol {x}})\right\|^{2}={\frac {1}{2}}\sum _{i=1}^{m}\left(f_{i}({\boldsymbol {x}})\right)^{2}}$

с ${\displaystyle f_{i}:\mathbb {R} ^{n}\to \mathbb {R} }$, Метод собачьей ноги Пауэлла находит оптимальную точку ${\displaystyle {\boldsymbol {x}}^{*}=\operatorname {argmin} _{\boldsymbol {x}}F({\boldsymbol {x}})}$ построив последовательность ${\displaystyle {\boldsymbol {x}}_{k}={\boldsymbol {x}}_{k-1}+\delta _{k}}$ что сходится к ${\displaystyle {\boldsymbol {x}}^{*}}$. На данной итерации Гаусс – Ньютон шаг дается

${\displaystyle {\boldsymbol {\delta _{gn}}}=-\left({\boldsymbol {J}}^{\top }{\boldsymbol {J}}\right)^{-1}{\boldsymbol {J}}^{\top }{\boldsymbol {f}}({\boldsymbol {x}})}$

куда ${\displaystyle {\boldsymbol {J}}=\left({\frac {\partial {f_{i}}}{\partial {x_{j}}}}\right)}$ это Матрица якобиана, в то время как крутой спуск направление дается

${\displaystyle {\boldsymbol {\delta _{sd}}}=-{\boldsymbol {J}}^{\top }{\boldsymbol {f}}({\boldsymbol {x}}).}$

Целевая функция линеаризуется по направлению наискорейшего спуска.

${\displaystyle {\begin{aligned}F({\boldsymbol {x}}+t{\boldsymbol {\delta _{sd}}})&\approx {\frac {1}{2}}\left\|{\boldsymbol {f}}({\boldsymbol {x}})+t{\boldsymbol {J}}({\boldsymbol {x}}){\boldsymbol {\delta _{sd}}}\right\|^{2}\\&=F({\boldsymbol {x}})+t{\boldsymbol {\delta _{sd}}}^{\top }{\boldsymbol {J}}^{\top }{\boldsymbol {f}}({\boldsymbol {x}})+{\frac {1}{2}}t^{2}\left\|{\boldsymbol {J}}{\boldsymbol {\delta _{sd}}}\right\|^{2}.\end{aligned}}}$

Чтобы вычислить значение параметра ${\displaystyle t}$ в точке Коши производная последнего выражения относительно ${\displaystyle t}$ полагается равным нулю, что дает

${\displaystyle t=-{\frac {\delta _{sd}^{\top }{\boldsymbol {J}}^{\top }{\boldsymbol {f}}({\boldsymbol {x}})}{\left\|{\boldsymbol {J}}{\boldsymbol {\delta _{sd}}}\right\|^{2}}}.}$

Учитывая доверительную область радиуса ${\displaystyle \Delta }$, Метод собачьей ноги Пауэлла выбирает этап обновления ${\displaystyle {\boldsymbol {\delta _{k}}}}$ как равно:

• ${\displaystyle {\boldsymbol {\delta _{gn}}}}$, если шаг Гаусса – Ньютона находится в пределах доверительной области (${\displaystyle \left\|{\boldsymbol {\delta _{gn}}}\right\|\leq \Delta }$);
• ${\displaystyle {\frac {\Delta }{\left\|{\boldsymbol {\delta _{sd}}}\right\|}}{\boldsymbol {\delta _{sd}}}}$ если ступеньки Гаусса – Ньютона и наиболее крутой спуск находятся за пределами доверительной области (${\displaystyle t\left\|{\boldsymbol {\delta _{sd}}}\right\|}$);
• ${\displaystyle t{\boldsymbol {\delta _{sd}}}+s\left({\boldsymbol {\delta _{gn}}}-t{\boldsymbol {\delta _{sd}}}\right)}$ с ${\displaystyle s}$ такой, что ${\displaystyle \left\|{\boldsymbol {\delta }}\right\|=\Delta }$, если шаг Гаусса – Ньютона находится вне доверительной области, но самый крутой шаг спуска находится внутри (шаг собачьей ноги).^[1]

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

1. Пауэлл (1970)
2. Юань (2000)

Источники

• Lourakis, M.L.A .; Аргирос, А.А. (2005). «Является ли Левенберг-Марквардт наиболее эффективным алгоритмом оптимизации для реализации настройки связки?». Десятая Международная конференция IEEE по компьютерному зрению (ICCV'05) Том 1. 2: 1526–1531 Vol. 2. Дои:10.1109 / ICCV.2005.128.
• Юань, Я-сян (2000). «Обзор алгоритмов доверительной области для оптимизации». Iciam. 99.
• Пауэлл, M.J.D. (1970). «Новый алгоритм безусловной оптимизации». In Rosen, J.B .; Мангасарян, О.Л .; Риттер, К. (ред.). Нелинейное программирование. Нью-Йорк: Academic Press. С. 31–66.
• Пауэлл, M.J.D. (1970). «Гибридный метод для нелинейных уравнений». В Робиновице, П. (ред.). Численные методы решения нелинейных алгебраических уравнений.. Лондон: Гордон и наука о нарушениях. С. 87–144.

внешняя ссылка

• «Алгоритмы решения уравнений». MathWorks.