Powell's dog leg method

Construction of the dog leg step

Given a least squares problem in the form

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

with ${\displaystyle f_{i}:\mathbb {R} ^{n}\to \mathbb {R} }$, Powell's dog leg method finds the optimal point ${\displaystyle {\boldsymbol {x}}^{*}=\operatorname {argmin} _{\boldsymbol {x}}F({\boldsymbol {x}})}$ by constructing a sequence ${\displaystyle {\boldsymbol {x}}_{k}={\boldsymbol {x}}_{k-1}+\delta _{k}}$ that converges to ${\displaystyle {\boldsymbol {x}}^{*}}$. At a given iteration, the Gauss–Newton step is given by

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

where ${\displaystyle {\boldsymbol {J}}=\left({\frac {\partial {f_{i}}}{\partial {x_{j}}}}\right)}$ is the Jacobian matrix, while the steepest descent direction is given by

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

The objective function is linearised along the steepest descent direction

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

To compute the value of the parameter ${\displaystyle t}$ at the Cauchy point, the derivative of the last expression with respect to ${\displaystyle t}$ is imposed to be equal to zero, giving

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

Given a trust region of radius ${\displaystyle \Delta }$, Powell's dog leg method selects the update step ${\displaystyle {\boldsymbol {\delta _{k}}}}$ as equal to:

• ${\displaystyle {\boldsymbol {\delta _{gn}}}}$, if the Gauss–Newton step is within the trust region (${\displaystyle \left\|{\boldsymbol {\delta _{gn}}}\right\|\leq \Delta }$);
• ${\displaystyle {\frac {\Delta }{\left\|{\boldsymbol {\delta _{sd}}}\right\|}}{\boldsymbol {\delta _{sd}}}}$ if both the Gauss–Newton and the steepest descent steps are outside the trust region (${\displaystyle t\left\|{\boldsymbol {\delta _{sd}}}\right\|}$);
• ${\displaystyle t{\boldsymbol {\delta _{sd}}}+s\left({\boldsymbol {\delta _{gn}}}-t{\boldsymbol {\delta _{sd}}}\right)}$ with ${\displaystyle s}$ such that ${\displaystyle \left\|{\boldsymbol {\delta }}\right\|=\Delta }$, if the Gauss–Newton step is outside the trust region but the steepest descent step is inside (dog leg step).[1]

• Lourakis, M.L.A.; Argyros, A.A. (2005). "Is Levenberg-Marquardt the most efficient optimization algorithm for implementing bundle adjustment?". Tenth IEEE International Conference on Computer Vision (ICCV'05) Volume 1. 2: 1526–1531 Vol. 2. doi:10.1109/ICCV.2005.128.
• Yuan, Ya-xiang (2000). "A review of trust region algorithms for optimization". Iciam. 99.
• Powell, M.J.D. (1970). "A new algorithm for unconstrained optimization". In Rosen, J.B.; Mangasarian, O.L.; Ritter, K. (eds.). Nonlinear Programming. New York: Academic Press. pp. 31–66.
• Powell, M.J.D. (1970). "A hybrid method for nonlinear equations". In Robinowitz, P. (ed.). Numerical Methods for Nonlinear Algebraic Equations. London: Gordon and Breach Science. pp. 87–144.

• "Equation Solving Algorithms". MathWorks.