Метод собачьей ноги Пауэлла

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

Название метода происходит от сходства между конструкцией шага с изогнутой ногой и формой лунки с изогнутой ногой в гольфе .

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

Изготовление ступеньки для собачьей ноги

Дана задача наименьших квадратов в виде

$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}$

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

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

где ${\boldsymbol {J}}=\left({\frac {\partial {f_{i}}}{\partial {x_{j}}}}\right)$ — матрица Якобиана , а направление наибольшего спуска определяется выражением

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

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

${\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}}$

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

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

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

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

Источники

• Луракис, MLA; Аргирос, А.А. (2005). «Является ли Левенберг-Марквардт наиболее эффективным алгоритмом оптимизации для реализации корректировки пакета?». Десятая международная конференция IEEE по компьютерному зрению (ICCV'05), том 1 . стр. 1526–1531. дои : 10.1109/ICCV.2005.128 . ISBN  0-7695-2334-Х . S2CID   16542484 .
• Юань, Я-сян (2000). «Обзор алгоритмов оптимизации области доверия». Ициам . Том. 99.
• Пауэлл, MJD (1970). «Новый алгоритм неограниченной оптимизации». В Розене, Дж.Б.; Мангасарян, OL; Риттер, К. (ред.). Нелинейное программирование . Нью-Йорк: Академическая пресса. стр. 31–66.
• Пауэлл, MJD (1970). «Гибридный метод для нелинейных уравнений». Робиновиц, П. (ред.). Численные методы решения нелинейных алгебраических уравнений . Лондон: Гордон и наука о нарушениях. стр. 87–144.

Внешние ссылки

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