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

Module steihaug_cg

source code

Steihaug conjugate-gradient trust region optimization.

This file is part of the minfx optimisation library at https://sourceforge.net/projects/minfx.

Classes [hide private]
  Steihaug
Functions [hide private]
 
steihaug(func=None, dfunc=None, d2func=None, args=(), x0=None, func_tol=1e-25, grad_tol=None, maxiter=1000000.0, epsilon=1e-08, delta_max=100000.0, delta0=1.0, eta=0.2, full_output=0, print_flag=0, print_prefix='')
Steihaug conjugate-gradient trust region algorithm.
source code
Variables [hide private]
  __package__ = 'minfx'

Imports: dot, float64, sqrt, zeros, Min, Trust_region, Newton


Function Details [hide private]

steihaug(func=None, dfunc=None, d2func=None, args=(), x0=None, func_tol=1e-25, grad_tol=None, maxiter=1000000.0, epsilon=1e-08, delta_max=100000.0, delta0=1.0, eta=0.2, full_output=0, print_flag=0, print_prefix='')

source code 

Steihaug conjugate-gradient trust region algorithm.

Page 75 from 'Numerical Optimization' by Jorge Nocedal and Stephen J. Wright, 1999, 2nd ed. The CG-Steihaug algorithm is:

  • epsilon > 0
  • p0 = 0, r0 = g, d0 = -r0
  • if ||r0|| < epsilon:
    • return p = p0
  • while 1:
    • if djT.B.dj <= 0:
      • Find tau such that p = pj + tau.dj minimises m(p) in (4.9) and satisfies ||p|| = delta
      • return p
    • aj = rjT.rj / djT.B.dj
    • pj+1 = pj + aj.dj
    • if ||pj+1|| >= delta:
      • Find tau such that p = pj + tau.dj satisfies ||p|| = delta
      • return p
    • rj+1 = rj + aj.B.dj
    • if ||rj+1|| < epsilon.||r0||:
      • return p = pj+1
    • bj+1 = rj+1T.rj+1 / rjT.rj
    • dj+1 = rj+1 + bj+1.dj