Package minfx :: Module dogleg
[hide private]
[frames] | no frames]

Module dogleg

source code

Dogleg trust region optimization.

This file is part of the minfx optimisation library at https://gna.org/projects/minfx.

Classes [hide private]
  Dogleg
Functions [hide private]
 
dogleg(func=None, dfunc=None, d2func=None, args=(), x0=None, min_options=(), func_tol=1e-25, grad_tol=None, maxiter=1000000.0, delta_max=10000000000.0, delta0=100000.0, eta=0.0001, mach_acc=1e-16, full_output=0, print_flag=0, print_prefix='')
Dogleg trust region algorithm.
source code
Variables [hide private]
  __package__ = 'minfx'

Imports: dot, float64, identity, outer, sort, sqrt, inv, match, Hessian_mods, Min, Trust_region, Bfgs, Newton


Function Details [hide private]

dogleg(func=None, dfunc=None, d2func=None, args=(), x0=None, min_options=(), func_tol=1e-25, grad_tol=None, maxiter=1000000.0, delta_max=10000000000.0, delta0=100000.0, eta=0.0001, mach_acc=1e-16, full_output=0, print_flag=0, print_prefix='')

source code 

Dogleg trust region algorithm.

Page 71 from 'Numerical Optimization' by Jorge Nocedal and Stephen J. Wright, 1999, 2nd ed. The dogleg method is defined by the trajectory p(tau):

             / tau . pU            0 <= tau <= 1,
   p(tau) = <
             \ pU + (tau - 1)(pB - pU),    1 <= tau <= 2.

where:

  • tau is in [0, 2]
  • pU is the unconstrained minimiser along the steepest descent direction.
  • pB is the full step.

pU is defined by the formula:

           gT.g
   pU = - ------ g
          gT.B.g

and pB by the formula:

   pB = - B^(-1).g

If the full step is within the trust region it is taken. Otherwise the point at which the dogleg trajectory intersects the trust region is taken. This point can be found by solving the scalar quadratic equation:

   ||pU + (tau - 1)(pB - pU)||^2 = delta^2