Powell's dog leg method

Powell's dog leg method, also called Powell's hybrid method, is an iterative optimisation algorithm for the solution of non-linear least squares problems, introduced in 1970 by Michael J. D. Powell.^[1] Similarly to the Levenberg–Marquardt algorithm, it combines the Gauss–Newton algorithm with gradient descent, but it uses an explicit 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).^[2]

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.^[2]

Formulation

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

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]

References

Sources

• 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. pp. 1526–1531. doi:10.1109/ICCV.2005.128. ISBN 0-7695-2334-X. S2CID 16542484.
• Yuan, Ya-xiang (2000). "A review of trust region algorithms for optimization". Iciam. Vol. 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.

External links

• "Equation Solving Algorithms". MathWorks.

• v
• t
• e

Optimization: Algorithms, methods, and heuristics

Unconstrained nonlinear

Functions Golden-section search Interpolation methods Line search Nelder–Mead method Successive parabolic interpolation Gradients Convergence Trust region Wolfe conditions Quasi–Newton Berndt–Hall–Hall–Hausman Broyden–Fletcher–Goldfarb–Shanno and L-BFGS Davidon–Fletcher–Powell Symmetric rank-one (SR1) Other methods Conjugate gradient Gauss–Newton Gradient Mirror Levenberg–Marquardt Powell's dog leg method Truncated Newton Hessians Newton's method

Constrained nonlinear
General Barrier methods Penalty methods Differentiable Augmented Lagrangian methods Sequential quadratic programming Successive linear programming

Convex optimization
Convex minimization Cutting-plane method Reduced gradient (Frank–Wolfe) Subgradient method Linear and quadratic Interior point Affine scaling Ellipsoid algorithm of Khachiyan Projective algorithm of Karmarkar Basis-exchange Simplex algorithm of Dantzig Revised simplex algorithm Criss-cross algorithm Principal pivoting algorithm of Lemke

Combinatorial
Paradigms Approximation algorithm Dynamic programming Greedy algorithm Integer programming Branch and bound/cut Graph algorithms Minimum spanning tree Borůvka Prim Kruskal Shortest path Bellman–Ford SPFA Dijkstra Floyd–Warshall Network flows Dinic Edmonds–Karp Ford–Fulkerson Push–relabel maximum flow

Metaheuristics
Evolutionary algorithm Hill climbing Local search Parallel metaheuristics Simulated annealing Spiral optimization algorithm Tabu search

• Software