View source for Powell's dog leg method

'''Powell's dog leg method''', also called Powell's hybrid method, is an [[Iterative method|iterative]] [[Mathematical optimization|optimisation]] algorithm for the solution of [[Non-linear least squares|non-linear least squares]] problems, introduced in 1970 by Michael J. D. Powell.<ref name="powell1970">Powell (1970)</ref> Similarly to the [[Levenberg–Marquardt algorithm]], it combines the [[Gauss–Newton algorithm]] with [[Gradient descent|gradient descent]], but it uses an explicit [[Trust region|trust region]]. At each iteration, if the step from the Gauss–Newton algorithm is within the trust region, it is used to update the current solution. If not, the algorithm searches for the minimum of the objective function along the steepest descent direction, known as Cauchy point. If the Cauchy point is outside of the trust region, it is truncated to the boundary of the latter and it is taken as the new solution. If the Cauchy point is inside the trust region, the new solution is taken at the intersection between the trust region boundary and the line joining the Cauchy point and the Gauss-Newton step (dog leg step).<ref name="yuan">Yuan (2000)</ref>
The name of the method derives from the resemblance between the construction of the dog leg step and the shape of a dogleg hole in golf.<ref name="yuan"/>

== Formulation ==
[[File:Powell dog leg.svg|thumb|Construction of the dog leg step]]

Given a [[Least squares|least squares]] problem in the form

: <math>
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
</math>

with <math>f_i: \mathbb{R}^n \to \mathbb{R}</math>, Powell's dog leg method finds the optimal point <math>\boldsymbol{x}^* = \operatorname{argmin}_{\boldsymbol{x}} F(\boldsymbol{x})</math> by constructing a [[Sequence|sequence]] <math>\boldsymbol{x}_k = \boldsymbol{x}_{k-1} + \delta_k</math> that converges to <math>\boldsymbol{x}^*</math>. At a given iteration, the [[Gauss–Newton algorithm|Gauss–Newton]] step is given by

: <math>
\boldsymbol{\delta_{gn}} = - \left( \boldsymbol{J}^\top \boldsymbol{J} \right)^{-1} \boldsymbol{J}^\top \boldsymbol{f}(\boldsymbol{x})
</math>

where <math>\boldsymbol{J} = \left( \frac{\partial{f_i}}{\partial{x_j}} \right)</math> is the [[Jacobian matrix and determinant|Jacobian matrix]], while the steepest descent direction is given by

: <math>
\boldsymbol{\delta_{sd}} = - \boldsymbol{J}^\top \boldsymbol{f}(\boldsymbol{x}) .
</math>

The objective function is linearised along the steepest descent direction

: <math>
\begin{align}
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{align}
</math>

To compute the value of the parameter <math>t</math> at the Cauchy point, the [[Derivative|derivative]] of the last expression with respect to <math>t</math> is imposed to be equal to zero, giving

: <math>
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}.
</math>


Given a trust region of radius <math>\Delta</math>, Powell's dog leg method selects the update step <math>\boldsymbol{\delta_k}</math> as equal to:
* <math>\boldsymbol{\delta_{gn}}</math>, if the Gauss–Newton step is within the trust region (<math>\left\| \boldsymbol{\delta_{gn}} \right\| \le \Delta</math>);
* <math>\frac{\Delta}{\left\| \boldsymbol{\delta_{sd}} \right\|} \boldsymbol{\delta_{sd}}</math> if both the Gauss–Newton and the steepest descent steps are outside the trust region (<math>t \left\| \boldsymbol{\delta_{sd}} \right\| </math>);
* <math>t \boldsymbol{\delta_{sd}} + s \left( \boldsymbol{\delta_{gn}} - t \boldsymbol{\delta_{sd}} \right)</math> with <math>s</math> such that <math>\left\| \boldsymbol{\delta} \right\| = \Delta</math>, if the Gauss–Newton step is outside the trust region but the steepest descent step is inside (dog leg step).<ref name="powell1970"/>

== References ==
<references />

== Sources ==
*{{Cite book|last1=Lourakis|first1=M.L.A.|last2=Argyros|first2=A.A.|title=Tenth IEEE International Conference on Computer Vision (ICCV'05) Volume 1|chapter=Is Levenberg-Marquardt the most efficient optimization algorithm for implementing bundle adjustment?|year=2005 |pages=1526-1531 |doi=10.1109/ICCV.2005.128|isbn=0-7695-2334-X|s2cid=16542484}}
*{{cite conference|title=A review of trust region algorithms for optimization|book-title=Iciam|year=2000|volume=99|last1=Yuan|first1=Ya-xiang}}
*{{cite book|first=M.J.D.|last=Powell|chapter=A new algorithm for unconstrained optimization|editor1-first=J.B.|editor1-last=Rosen|editor2-first=O.L.|editor2-last=Mangasarian|editor3-first=K.|editor3-last=Ritter|title=Nonlinear Programming|publisher=Academic Press|place=New York|year=1970|pages=31–66}}
*{{cite book|first=M.J.D.|last=Powell|chapter=A hybrid method for nonlinear equations|editor-first=P.|editor-last=Robinowitz|title=Numerical Methods for Nonlinear Algebraic Equations|publisher=Gordon and Breach Science|place=London|year=1970|pages=87–144}}

== External links ==
* {{cite web|url=https://mathworks.com/help/optim/ug/equation-solving-algorithms.html|title=Equation Solving Algorithms|publisher=MathWorks}}

{{Optimization algorithms|unconstrained}}

{{DEFAULTSORT:Powell's dog leg method}}

[[Category:Least squares]]
[[Category:Optimization algorithms and methods]]

{{Sourceattribution|Powell's dog leg method}}